数据结构（2）——顺序表的模拟实现

一：顺序表的熟悉

通过数据结构（1）对于算法复杂度的明白，现在我们正式进入数据结构的焦点内容，今天，先来使用C语言实现一下数据结构中最简单的顺序表。
首先介绍一下顺序表的概念，先从线性表提及。
线性表：n个具有相同结构的数据元素的有限序列。在逻辑结构上一定是线性的，在物理结构上不一定是线性的。
顺序表：如果线性表的物理地址连续，那么其就算是顺序表。一般环境下接纳数组存储。
顺序表的底层逻辑就是数组。但相较于数组，它增添了一些功能。
也就是对数组举行一系列的功能包装，就形成了顺序表。
顺序表————>（数组+增长数据+修改数据+删除数据+查找数据……）

二：静态顺序表

如果数据地个数你是可以确定或者精确估计的，那么对于这样的一系列数据的存储就可以使用静态顺序表来完成。
好比：你要存储90个整型的数据，那么你就可以一次性创建一个容量为100个（大于90个）整型数据的数组（防止估计偏差）来举行存储。还要有一个变量size来统计数组中有效数据的个数。
我们可以使用结构体来举行实现

静态顺序表的缺点：
1.空间给小了 后期空间不够用了：会造成新注册用户数据的遗失。
2.空间给大了：浪费空间（费钱），卡顿，……
总之使用静态顺序表这一数据结构存储数据不够机动，使用频率相对较少。
怎么解决静态顺序表不够机动等一系列题目呢？
接下来引入动态顺序表————

三：动态顺序表

由于静态顺序表开发内存后就不能举行调解了，使用起来不够方便，因此我们创建动态顺序表来存储数据，可以使用动态内存开发函数对内存举行调解。
接下来我要向导大家用C语言的方式来模拟实现一下动态顺序表的一系列功能。
我将接纳多文件的形式（SeqList.h头文件 来举行结构的定义和函数的声名等）（SeqList.c 源文件来举行函数体的内容实现）（test.c 源文件来举行功能的测试）
1.动态顺序表的创建

相较于静态顺序表，动态顺序表由于其存储空间可变，需要额外一个变量capacity来标记存储空间的大小。

这里注意一下：使用typedef重定义的原因：
1.对int重定义：由于顺序表能够存储的数据类型不仅仅是整型，这里只是以整型为例来模拟实现顺序表的功能，之后但凡要使用顺序表存储其他类型的数据只需要将第七行的ing改为其他类型即可。
2.对struct SeqList重定义：为了后续誊写方便。
2.初始化

顺序表使用之前要先对其中成员举行初始化，否则其成员会是随机值，有潜伏的风险。

初始化的时间一定要传地址，传值的话起不到初始化的效果（详细原因参考我之前的博客）

3.判断内存空间是否够用

这里涉及一个题目，使用realloc函数扩容的话，如果每次只增长一个空间，会存在频繁扩容，频繁使用realloc函数程序执行效率会低下如果每次增长的空间比较大，会存在空间的浪费。
综合思量，接纳这样的扩容方式：每次扩容在原容量的底子上成二倍扩充（基于概率论）
5——10——20——40——80——160——320……
程序的第15行解释：如果size和capacity是相称的，说明数组有效数据个数和总数据个数相同，即空间已满，需要扩容。
程序的第17行解释：如果capacity是0，即一点空间都还没有开发，那就先开发4个整型空间使用（其实几个都无所谓，看本身习惯）。
4.尾插

尾插：在顺序表的尾部插入一个数据。

无论是尾插还是背面的头插，中央插入……只要涉及插入数据的操纵就要先判断内存空间是否够用，不够用的话要先扩充空间。
这里要注意：插入数据之后size值要加一。

5.头插

想要在顺序表的头部插入数据，就要把顺序表团体向后移动，流出一个整型数据的空间。
把顺序表团体向后移动方法：从后向前依次后移（否则会发生覆盖）。
6.尾删

无论是尾删还是前删……只要计划删除数据就好提前思量顺序表中是否有数据可删。
顺序表尾部删除数据其实操纵很简单，只需要让size减一，要删除的谁人数据就不再是有效数据了，其占据的空间就可以被尾插等操纵使用。
7.头删

头删操纵就是将顺序表从第二个数据开始不停到末尾，团体前移一位，将顺序表头部要删除的数据盖住。
这个操纵要使用循环从前向后依次覆盖。
头删操纵结束后size要减一。
8.查找

在顺序表中查找一个数据，如果找到，返回数据的下表，要是找不到返回-1；
9.指定位置之前插入数据

插入数据要先查抄空间是否够用，然后将插入位置以及之后的数据从后向前依次后移一位。
这里要注意，插入数据的位置必须要在pos>=0&&pos<=size这个范围内。
pos=size就是尾插，pos=0就是头插。
10.删除指定位置的数据

删除数据时一定要查抄是否有数据可以删。然后将删除的数据的位置之后的数据从前向后依次向前覆盖。
这里也要注意，删除的数据的位置必须要在pos>=0&&pos<=size这个范围内。
11.顺序表元素的打印

12.烧毁

顺序表使用完毕之后要举行烧毁（动态内存释放……）

以上就是动态顺序表的一些底子功能的模拟实现，当然顺序表的功能远不止这些，好比另有指定位置插入多个数据……，大家有兴趣的话可以本身下去尝试。

完：




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。