【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

Qomolangma

发布于 2024-07-30 09:24:16

1370

发布于 2024-07-30 09:24:16

文章被收录于专栏：深度学习

一、线性表

1. 线性表的定义

一个线性表是由零个或多个具有相同类型的结点组成的有序集合。

这里用（a1，a2，…，an）来表示一个线性表，n为自然数：

① 当n=0时，线性表中无结点（或曰包含零个结点），这样的线性表被称为空表；

② 当n=1时，线性表中仅有一个结点，该结点既是表头（head），又是表尾（tail）；

③ 当n≥1时，称a1为线性表的表头，称an为线性表的表尾；

④ 当n≥2时，称ai为ai+1的前驱结点，称ai+1为ai的后继结点，其中1≤ i < n；表头结点无前驱结点，表尾结点无后继结点。

线性表中的元素之间存在一对一的关系，也就是说每个元素都有一个直接前驱和一个直接后继，除了第一个元素没有前驱，最后一个元素没有后继。线性表可以用来表示各种具有线性关系的数据，例如数组、链表等。

2. 线性表的要素

元素类型：线性表中的元素具有相同的数据类型，可以是整数、字符、结构体等。
元素个数：线性表中的元素个数可以是任意的，可以是有限的或无限的。
元素顺序：线性表中的元素按照一定的次序排列，每个元素都有一个唯一的位置。
关系定义：线性表中的元素之间存在顺序关系，每个元素都与它的前驱和后继相连。
表头和表尾：线性表有一个表头和一个表尾，表头是线性表中第一个元素，表尾是线性表中最后一个元素。

二、线性表的基本操作

①创建一个线性表

②确定线性表的长度

③确定线性表是否为空

④存取表中指定位置结点的字段值

⑤查找指定字段值在表中的位置

⑥删除表中指定位置的结点

⑦在表中指定位置插入一个新结点

三、线性表的顺序存储结构

1. 定义

按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。

按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。若顺序表中的元素按其值有序，则称其为有序顺序表。

在高级程序设计语言中，“数组”这种数据类型同样具有随机存储的特性，因此用高级程序设计语言实现线性表的顺序存储结构时，通常选择数组。因此，数组的长度就是顺序表的最大长度（MaxSize），顺序表的实际长度为length，其值必须小于等于MaxSize。

// 定义顺序表结构体
typedef struct {
    int data[MAX_SIZE];  // 用数组存储元素
    int length;          // 顺序表的长度
} SeqList;

结构体基础知识：

【重拾C语言】八、表单数据组织——结构体（类型、类型别名、直接/间接访问；典例：复数、成绩单）-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/133793105?spm=1001.2014.3001.5502

2. 顺序表的操作

// 初始化顺序表
void initSeqList(SeqList *list) {
    list->length = 0;
}

a. 插入操作

插入操作用于向顺序表中插入一个新的元素：需要将插入位置之后的所有元素依次后移一位，为新元素腾出空间，并将新元素放入目标位置。

int insert(SeqList *list, int position, int element) {
    if (position < 0 || position > list->length || list->length == MAX_SIZE) {
        return 0;  // 插入位置非法或顺序表已满，插入失败
    }

    // 将插入位置之后的元素依次后移一位
    for (int i = list->length - 1; i >= position; i--) {
        list->data[i + 1] = list->data[i];
    }

    // 在插入位置放入新元素
    list->data[position] = element;
    list->length++;

    return 1;  // 插入成功
}

b. 删除操作

删除操作用于从顺序表中删除指定位置的元素：需要将删除位置之后的所有元素依次前移一位，覆盖被删除的元素，同时将顺序表的长度减一。

int delete(SeqList *list, int position) {
    if (position < 0 || position >= list->length) {
        return 0;  // 删除位置非法，删除失败
    }

    // 将删除位置之后的元素依次前移一位
    for (int i = position + 1; i < list->length; i++) {
        list->data[i - 1] = list->data[i];
    }

    list->length--;

    return 1;  // 删除成功
}

c. 查找操作

查找操作可以根据元素的值进行查找，也可以根据位置进行查找。

对于按值查找，需要遍历顺序表的所有元素，逐个比较元素的值；
对于按位置查找，直接通过索引访问数组中的元素即可。

int search(SeqList *list, int element) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == element) {
            return i;  // 找到元素，返回索引
        }
    }

    return -1;  // 未找到元素
}

d. 修改操作

修改操作用于修改顺序表中指定位置的元素的值：可以通过索引直接访问到目标位置的元素，并进行修改。

在顺序存储结构中，插入和删除操作可能需要移动大量元素，导致时间复杂度较高。而查找和修改操作可以在常数时间内完成，时间复杂度为O(1)。

int modify(SeqList *list, int position, int newElement) {
    if (position < 0 || position >= list->length) {
        return 0;  // 修改位置非法，修改失败
    }

    list->data[position] = newElement;

    return 1;  // 修改成功
}

e. 代码实例

#include <stdio.h>

#define MAX_SIZE 100

// 定义顺序表结构体
typedef struct {
    int data[MAX_SIZE];  // 用数组存储元素
    int length;          // 顺序表的长度
} SeqList;

// 初始化顺序表
void initSeqList(SeqList *list) {
    list->length = 0;
}

// 插入操作
int insert(SeqList *list, int position, int element) {
    if (position < 0 || position > list->length || list->length == MAX_SIZE) {
        return 0;  // 插入位置非法或顺序表已满，插入失败
    }
    
    // 将插入位置之后的元素依次后移一位
    for (int i = list->length - 1; i >= position; i--) {
        list->data[i + 1] = list->data[i];
    }
    
    // 在插入位置放入新元素
    list->data[position] = element;
    list->length++;
    
    return 1;  // 插入成功
}

// 删除操作
int delete(SeqList *list, int position) {
    if (position < 0 || position >= list->length) {
        return 0;  // 删除位置非法，删除失败
    }
    
    // 将删除位置之后的元素依次前移一位
    for (int i = position + 1; i < list->length; i++) {
        list->data[i - 1] = list->data[i];
    }
    
    list->length--;
    
    return 1;  // 删除成功
}

// 查找操作（按值查找）
int search(SeqList *list, int element) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == element) {
            return i;  // 找到元素，返回索引
        }
    }
    
    return -1;  // 未找到元素
}

// 修改操作
int modify(SeqList *list, int position, int newElement) {
    if (position < 0 || position >= list->length) {
        return 0;  // 修改位置非法，修改失败
    }
    
    list->data[position] = newElement;
    
    return 1;  // 修改成功
}

int main() {
    SeqList list;
    initSeqList(&list);
    
    // 在顺序表中插入元素
    insert(&list, 0, 10);
    insert(&list, 1, 20);
    insert(&list, 2, 30);
    
    // 删除顺序表中的元素
    delete(&list, 1);
    
    // 查找顺序表中的元素
    int index = search(&list, 30);
    if (index != -1) {
        printf("元素30的索引为：%d\n", index);
    } else {
        printf("未找到元素30\n");
    }
    
    // 修改顺序表中的元素
    modify(&list, 0, 40);
    
    return 0;
}