【C语言】顺序表（上卷）

什么是数据结构？

数据结构是由“数据”和“结构”两词组合而来的。

数据需要管理。数据结构就是计算机存储、组织数据的方式。比如一个班级就是一个结构，管理的就是班级里的学生。如果我们要找三年2班的同学李华，就可以直接去三年2班找而不用大海捞针。

其实我们已经学过一种数据结构：数组。有了数组后我们就可以通过下标，对指定的数据进行修改等操作。

顺序表

顺序表底层就是数组，是在数组的基础上进行了维护和封装。

那么，为什么我们已经有了数组，还要有顺序表呢？

比如我们想在数组最后的地方增加一个数据，知道位置后我们可以添加，但如果在大型程序中我们时常需要增删查改，会比较麻烦，而顺序表就提供了现成的方法可以使用。

数组和顺序表的区别就像苍蝇馆子和米其林餐厅的区别，食材都差不多，但由于摆盘等区别开来。在数组基础上，顺序表增加了增删查改的方法。

线性表

顺序表是线性表的一种。

那么什么是线性表？是具有相同特性的数据结构的集合。

举个例子，蔬菜不是某个具体的菜，而是莲藕、白菜、南瓜这些菜的集合。可以看到“蔬菜”具有一些共同的特征。水果有菠萝、草莓、树莓等，也是类似的道理。

草莓是水果里的一种，就像顺序表是线性表里的一种。

那么，线性表里的数据结构有哪些相同的特性呢？

线性表从两个方面有相同特性：物理结构和逻辑结构。

什么是物理结构？举个例子，数组arr[10]有10个空间，它的10个空间是连续的。每个空间都有自己的地址，称之为物理地址或物理内存。所以物理结构指的是数据在内存里面存储的时候的结构是否是物理的，也就是在内存上存储的时候长什么样子。

在线性表中，物理结构通常来说是不一定连续，而逻辑结构是连续的。

什么是逻辑结构？也就是想象出来的结构。比如去商店买东西排队时就是线性的，站成一条线，但实际上排队时并不总是站成笔直的一条线，而是可能站得零零散散的一条线。所以抽象来说是站成了一条线，这条线是我们想象出来的。

数组的物理结构是线性的。它的逻辑结构也是线性的。

数组在物理结构上是连续的，因为通过arr+1、arr+2...我们就可以连续地访问数据。

现在回过头来看顺序表，顺序表的特性：逻辑结构一定是连续的（因为线性表在逻辑结构上一定是连续的）；物理结构是连续的（顺序表底层是数组，在物理结构上的连续的）。

给数组申请空间，我们有两种方式：

int arr[10]={0}        定长的数组

int* arr        动态内存开辟，确定大小后再去动态申请

 所以顺序表的分类：

静态顺序表的定义：

struct SeqList

{

        int arr[100];//定长数组，编译阶段已确定大小

        int size;//顺序表当前有效的数据个数（存储了几个数据）

};

动态顺序表的定义：

struct SeqList

{

        int* arr;

        int size;//顺序表当前有效的数据个数

        int capacity;//当前空间大小

}；

哪种顺序表更好呢？我们能精确预测到需要多大空间来存储信息呢？ 如果后续我们一开始设置好的空间不够了，可能就会丢失用户信息等。也就是说数组大小给小了，空间不够用；数组大小给大了，会浪费空间。（代码能力很差，可能带来经济损失）

所以动态顺序表更好，可以动态增容，不够时我们就增容。

动态顺序表的实现与各种方法

我们创建3个文件，.h文件用来放顺序表结构、声明顺序表的方法，.c文件用来放实现顺序表的方法。最后再创建一个测试文件，也是.c结尾。

顺序表的初始化

注意：用typedef的意义在于我们想要改数据的类型时可以省去代码中的一个个修改。 （尤其是代码量大时）

顺序表的销毁

顺序表我们是动态开辟来的，所以要手动释放空间。

SeqList.h

SeqList.c

test.c

顺序表如何插入数据 

插入数据可以在顺序表的头部或尾部位置插入。

尾插

在插入数据前，我们需要先确保当前有空间可以插入数据。

插入数据前我们先进行空间是否足够的判断。

SeqList.c

注意，增容我们要申请多大的空间或者说一次增容多大呢？

增容通常来说是成倍数的增加，一般是2或者3倍。（往往是2倍）

realloc时，如果后续空间不足就会在其他地方重新申请空间，将原来数据拷贝过来并释放掉原来的空间。这个步骤是比较麻烦的，如果一次次realloc，每次申请空间都要重复这一过程，会造成性能低下，或者说程序的运行效率大大降低。

而增得太大又浪费空间，所以2倍2倍去扩容比较好。

了解了这一点后我们可以写成尾插函数代码：

SeqList.c

可以看到虽然插入数据的代码只有最后一行，前面的准备工作却必不可少。 

test.c

SeqList.h

头插

在这一步我们会发现，尾插和头插都需要判断空间是否足够，所以我们可以将其封装成一个函数：

然后我们再接着写头插代码：

 

顺序表如何删除数据 

尾删

SeqList.h

SeqList.c 

 

头删

SeqList.h 

 

SeqList.c  

 本文到此结束，祝阅读愉快^_^