线性表

前言

欢迎来到本博客的线性表部分！😄🎉在这篇博文中，我将带您深入探索数据结构中的线性表，这是计算机科学中最基础也是最重要的数据结构之一。

线性表是一种线性数据结构，它由一组连续的元素组成，这些元素按照一定的顺序排列。在我们日常的编程工作中，线性表几乎无处不在，比如数组和链表就是线性表的两种常见实现形式。

本博客将重点关注线性表的插入和删除操作，以及其他一些基本功能，如按位置获取元素、获取长度和查找指定元素的位置。这些操作在实际编程中频繁使用，因此我们将为它们详细讲解，并提供简单易懂的示例代码，让您快速掌握这些核心功能。

线性表的插入和删除操作是其最为关键的特性之一，我们将详细讨论如何在线性表中高效地插入和删除元素，让您了解它们的内部实现原理和时间复杂度。无论您是初学者还是有一定编程经验的开发者，这里都会有对您有益的知识。📚💡

当然，我们也将不时地穿插一些有趣的表情包来轻松化干涩的知识点，让学习过程更加愉快轻松。😄🌈

希望您在本篇博客中能够找到对线性表有更深入了解的机会，并将这些知识应用到您未来的编程实践中。让我们一起开始探索线性表的奥秘吧！🚀😃💻

准备工作

定义数据类型和结构体

typedef int E;typedef struct List {E *array;       //顺序表int MaxSize;    //顺序表最大长度int length;     //顺序表实际长度
} SqList;

初始化操作

线性表初始化，需要对其开辟空间，这里采用动态分配的方式分配空间。即空间大小不够后，可在后面扩容。

• 首先开启 10 个对应存储的数据的大小空间。
• 判断开启空间是否成功，如果开辟失败，直接结束
• 初始化空间存放数据个数的最大容量为 10。
• 初始化空间内数据的当前长度，默认 为 0。

_Bool initList(SqList *list) {list->array = malloc(sizeof(E) * 10);if (list->array == NULL) return 0;list->MaxSize = 10;list->length = 0;return 1;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！");} else {printf("顺序表初始化失败！");}
}

插入操作

插入操作的基本步骤：

• 利用for循环找到插入位置。
• 元素后移：在找到插入位置后，需要将插入位置及其后面的元素都向后移动一位，以腾出空间给新元素。
• 插入元素：将新元素插入到腾空的位置。
• 底层数组的实际长度加一。

/**** @param list 顺序表* @param element 插入的元素* @param index 插入元素的位序*/
void insertList(SqList *list, E element, int index) {for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");insertList(&list, 111, 1);printList(&list);insertList(&list, 666, 2);printList(&list);insertList(&list, 888, 2);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

运行结果：

乍一看，我们的代码看上去写的还不错，貌似非常合理。但是，我们接下来更换一组测试数据：

//main函数
int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");insertList(&list, 111, 4);printList(&list);insertList(&list, 666, 1);printList(&list);insertList(&list, 888, 2);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

在初始化完后，我们第一个插入的数据的位序为 4，即下标为3 的位置，从第四个位置开始插入数据。但是最后输出的结果为0，不应该是111 吗？为什么会是 0 呢？这是因为我们插入数据的时候，位置不正确。因此，我们需要完善代码，保证代码的健壮性。

_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;		//判断插入位置是否合理for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}

这次我们再次运行main函数，发现就不会出现上面的问题了，但是这样就结束了吗？真的结束了吗？

我们目前开辟了 10 个大小的数据空间，但是我们只插入了三个数据，如果我们插入 20 个数据会出现怎么样的情况呢？

for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);
}
printList(&list);

输出的结果貌似是正确实，但是这并不代表这是正确的做法。

解释： malloc 函数在内存中分配一块指定大小的连续空间，并返回其指针。当你请求分配 10 个空间时，malloc 可能会给你返回一个指向 10 个连续字节的指针。但是，当你尝试往这个 10 个字节的空间中插入 20 个数据时，这会导致内存越界。这意味着你正在访问和写入一些你没有分配的内存空间，这个行为是未定义的行为。

最常见的问题就是数据损坏：当你在未分配的内存空间中进行写入操作时，这可能导致其他数据被覆盖，数据结构损坏，或者程序崩溃。

为了避免这种问题，应该始终确保在使用动态内存分配时，只访问你已经分配的内容空间，并确保分配的大小足够容纳存放的数据。当需要插入更多的数据时，应该重新分配更大的内存空间（即扩容）。

_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;        //判断插入位置是否合理if (list->MaxSize == list->length) { //判断是否需要扩容int newMaxSize = list->length + (list->length >> 1);E *newArray = realloc(list->array, newMaxSize * sizeof(E));if (newArray == NULL) return 0;list->array = newArray;list->MaxSize = newMaxSize;}for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}

realloc函数：可以做到控制动态内存开辟的大小，重新申请的内存空间大小就是我们指定的新的大小，并且原有的数据也会放到新申请的空间中，非常方便。

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");printf("底层数组初始值：%d\n", list.MaxSize);for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printList(&list);printf("底层数组扩容到：%d\n", list.MaxSize);} else {printf("顺序表初始化失败！\n");}
}

到目前为止，可能出现的问题已经解决了，以此保障了代码的健壮性。接下来介绍线性表（顺序表）的删除操作。

删除操作

删除操作的基本流程：

• 判断删除的位置是否合理，不合理直接结束；（基本操作）
• 利用for循环将位序为index的元素删除，即将index后的值向前移动，后面的值覆盖前面的值。（核心思想）
• 底层数据的实际长度减一。

//删除某个位置的元素
_Bool deleteList(SqList *list, int index){if (index < 1 || index > list->length) return 0;for (int i = index; i < list->length - 1; ++i) {list->array[i] = list->array[i + 1];}list->length--;return 1;
}

main函数测试：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");printf("底层数组初始值：%d\n", list.MaxSize);for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("底层数组扩容到：%d\n", list.MaxSize);printf("删除后的元素为：");deleteList(&list, 20);printList(&list);} else {printf("顺序表初始化失败！\n");}
}

这里删除了位序为 20 的数据，即下标为 19 的数组元素。

其他简单操作

OK，这里的插入和删除操作我们就成功完成了，还有一些比较简单的功能，我们这里也来依次实现一下，首先是获取长度：

int getLengthList(SqList *list) {return list->length;
}

接着是按位置获取元素：

//位置获取元素和查找指定元素的位置
E * getList(SqList *list, int index){if (index < 1 || index > list->length - 1) return 0;return &list->array[index - 1];
}

查找指定元素的位置：

int findList(SqList *list, E element) {for (int i = 0; i < list->length - 1; ++i) {if (list->array[i] == element) return i + 1;}return -1;
}

main函数：

int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("%d", findList(&list, 5));} else {printf("顺序表初始化失败！\n");}
}

总结

注意⚠️⚠️⚠️：

1. 区分位序和下标的区别，大多数教材或者教程上面是将这两者区分开的，即位序 = 下标 + 1的关系，也有一些是位序 = 下标，这一点要格外的注意。
2. 在开辟新的空间的时候需要判断开辟空间是否成功，如果成功，继续执行后续代码，反之，结束函数。
3. 实际长度length比底层数组长度MaxSize重要的多。

重难点：

1. 扩容操作：了解扩容操作的realloc函数，其作用就是开辟一块新的空间然后将原有的数据存放到新申请的空间中，非常方便。当然，如果因为内存不足之类的原因导致内存空间申请失败，那么就返回NULL，所以不要忘记判断是否为空。
2. 在执行插入或者删除操作时，不要忘记底层数组的实际长度需要自增或自减。

源码部分

#include <stdio.h>
#include <stdlib.h>typedef int E;typedef struct List {E *array;       //顺序表int MaxSize;    //顺序表最大长度int length;     //顺序表实际长度
} SqList;_Bool initList(SqList *list) {list->array = malloc(sizeof(E) * 10);if (list->array == NULL) return 0;list->MaxSize = 10;list->length = 0;return 1;
}/**** @param list 顺序表* @param element 插入的元素* @param index 插入元素的位序*/
_Bool insertList(SqList *list, E element, int index) {if (index < 1 || index > list->length + 1) return 0;        //判断插入位置是否合理if (list->MaxSize == list->length) { //判断是否需要扩容int newMaxSize = list->length + (list->length >> 1);E *newArray = realloc(list->array, newMaxSize * sizeof(E));if (newArray == NULL) return 0;list->array = newArray;list->MaxSize = newMaxSize;}for (int i = list->length; i > index - 1; --i) {list->array[i] = list->array[i - 1];}list->array[index - 1] = element;list->length++;return 1;
}//删除某个位置的元素
_Bool deleteList(SqList *list, int index) {if (index < 1 || index > list->length) return 0;for (int i = index; i < list->length - 1; ++i) {list->array[i] = list->array[i + 1];}list->length--;return 1;
}//获取长度
int getLengthList(SqList *list) {return list->length;
}//位置获取元素和查找指定元素的位置
E *getList(SqList *list, int index) {if (index < 1 || index > list->length - 1) return 0;return &list->array[index - 1];
}int findList(SqList *list, E element) {for (int i = 0; i < list->length - 1; ++i) {if (list->array[i] == element) return i + 1;}return -1;
}void printList(SqList *list) {for (int i = 0; i < list->length; ++i) {printf("%d\t", list->array[i]);}printf("\n");
}int main() {SqList list;if (initList(&list)) {printf("顺序表初始化成功！\n");for (int i = 0; i < 20; ++i) {insertList(&list, i, i + 1);}printf("插入后的元素为：");printList(&list);printf("%d", findList(&list, 5));} else {printf("顺序表初始化失败！\n");}
}