【数据结构篇】顺序表 超详细

 

目录

 

一.顺序表的定义

1.顺序表的概念及结构

1.1线性表

2.顺序表的分类

2.1静态顺序表

2.2动态顺序表 

二.动态顺序表的实现

1.准备工作和注意事项

2.顺序表的基本接口：

   2.0 创建一个顺序表

   2.1 顺序表的初始化

2.2 顺序表的销毁

2.3 顺序表的打印

3.顺序表的尾插和尾删接口：

4.顺序表的扩容接口：

5.顺序表的头插和头删接口：

6.顺序表的指定位置插入和删除接口：

7.顺序表的查找接口：

 三.完整代码

SeqList.c: 

SeqList.h:

test.c :

---

 

一.顺序表的定义

1.顺序表的概念及结构

1.1线性表

2.顺序表的分类

顺序表的底层是数组，但和数组不一样的是，它对数组进行了分装，增加了增删查改等接口

2.1静态顺序表

概念：使用定长的数组存储元素（用存储整型举例）

缺陷： 空间给多了造成空间浪费，给少了空间不够

这里我解释一下为什么用 replace 代替 int ： 这样是方便以后修改顺序表存储别的数据类型，用N代替数组的元素个数同理，修改时更方便

2.2动态顺序表 

二.动态顺序表的实现

1.准备工作和注意事项

 创建3个文件：

 

  第一个文件：用于接口函数和所有需要用到的库函数头文件的声明，定义顺序表的结构

  第二个文件：用于对接口函数的定义

  第三个文件：用于接口的测试

  注意事项：建议每个函数接口写完对其进行调试，避免最后产生大量报错而束手无措

                    我在每个接口的代码上面都添加了很多注释，帮助各位未来的大佬增加理解哦

2.顺序表的基本接口：

   2.0 创建一个顺序表

 

   2.1 顺序表的初始化

 

对于我为什么要先用arr来接收开辟好的空间，我本来是想着开辟失败会影响先前开辟好的空间，但转念一想先前本来也没有开辟空间那，如果开辟失败的还用arr接收还是直接用结构体成员指针接收都一样那，但从更广泛的编程实践和代码质量的角度考虑，先用arr接收是一种更好的编程习惯，有助于提高代码的严谨性和可读性，减少潜在的错误和问题。 

2.2 顺序表的销毁

2.3 顺序表的打印

 提前将打印接口写好，方便后面的观察

3.顺序表的尾插和尾删接口：

尾插：

切记：在插入数据后都要让有效数据个数+1

尾删：

4.顺序表的扩容接口：

由于顺序表的插入接口都要进行扩容判断，所以我们可以把扩容单独分装成一个函数

这样在后续的代码中我们直接调用这个函数就可以了 

5.顺序表的头插和头删接口：

头插：

头删：

6.顺序表的指定位置插入和删除接口：

插入：

删除：

由于下面这些代码逻辑都差不多，我也就没做注释了，指定位置的插入删除无非就是要挪动数据，这个你自己画图后就可以看懂了

7.顺序表的查找接口：

 三.完整代码

SeqList.c: 

 SeqList.h:

 

test.c :

这部分我只调用了部分函数（仅供参考）

四.顺序表的问题及思考  

1. 中间/头部的插⼊删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。

3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到

200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？

这就需要我们另一种数据结构了，卖个关子，后续内容就等下一篇文章了，顺序表哪块不理解的欢迎评论区提问，同时哪块有问题的也麻烦各位大佬及时指出我的问题，笔芯！！！