【初阶数据与算法】线性表之顺序表的定义与实现
文章目录
一、线性表的概念
线性表（linearlist）是n个具有相同特性的数据元素的有限序列，线性表在物理结构上并不⼀定是连续的，在逻辑结构上是连续的
物理结构就是在存储数据时真实的内存存储位置，物理结构上连续就是说在存储数据时，使用的是一段连续的内存空间存储数据，例如数组，它开辟出来的内存空间就是连续不断的，我们在数组的章节也做了介绍，数组就属于物理结构连续的一种结构
而逻辑结构独立于物理结构，它关注的是数据元素之间的关系，逻辑结构连续就是，它虽然在物理结构上可能不是采用连续存储数据的方式，但是我们可以通过某种方式使得这些数据连续起来，使得在访问数据时可以将物理结构上分散的数据连续起来，这就是逻辑结构连续
我们今天介绍的线性表在逻辑上是线性结构，但是它在物理结构上并不⼀定是连续的，也就是在访问数据时，我们一定可以按照顺序进行访问，但是在存储数据时，我们既可以采用连续的内存空间存储数据，也可以采用不连续的内存空间存储数据，只要我们采用某种方式使得线性表的数据可以连续的访问即可
当线性表的物理结构是连续的时候，一般使用数组来存储数据，当线性表的物理结构不是连续的时候，一般以链式的结构存储，线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串等等，我们今天介绍的就是线性表之一的顺序表
二、顺序表
1.概念与结构
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储，如图：
那么肯定就会有人有疑问了，顺序表既然底层使用了数组，为什么不直接使用数组，而要取一个顺序表的名字，那么它们真实的区别是什么呢？其实很简单，数组只是数组而已，一种可以连续存储数据的结构
但是我们在上一篇文章讲过，数据结构不仅要能够存储数据，还要能够合理的管理数据，我们的顺序表虽然底层是数组，但是在数组的基础上提供了增删查改等多种方法让我们可以去合理的管理数据
所以严格地说，单独的数组不算一种数据结构，而拥有增删查改等等功能的数组，也就是顺序表，才是一种数据结构，那么顺序表到底长什么样子呢？它其实是一个结构体，不同的顺序表定义的结构体不同，所以我们先来学习顺序表的分类
2.顺序表的分类
顺序表又可以分为静态顺序表和动态顺序表，我们接下来就来学习一下这两种不同顺序表的概念，以及我们平常使用的到底是哪种顺序表
静态顺序表
静态顺序表的静态是指顺序表底层的数组的元素大小是静态的，也就是静态顺序表使⽤的是定⻓的数组存储元素，而顺序表实际上就是使用一个结构体来进行维护，一般静态顺序表的结构如下：
typedefint SLDateType;#defineN7structSeqList{ SLDateType arr[N];int size;};在上面我们提到了，顺序表其实是由一个结构体进行维护的，不同种类的顺序表的结构体不同，在静态顺序表中，底层数组的元素大小是确定了的，一般使用#define来定义一个常量来充当它的大小
而由于我们并不知道顺序表中会存储什么数据类型，所以我们可以使用typedef关键字对类型进行重命名，以后我们想要修改顺序表的数据类型时，就可以只修改typedef这一条语句，否则的话每次修改数据类型将会十分麻烦
我们也可以看到，这里结构体的名字就是SeqList，它里面包含了两个单词，Seq代表英文单词sequential，意思是顺序的，List就是表的意思，合起来就是我们的顺序表
在静态顺序表中的结构有两个成员，应该就是底层存储数据的数组，它的大小是确定的，第二个成员是整型变量size，它的含义是目前顺序表中有效元素的个数
静态顺序表的缺点也很明显，就是它的大小是固定的，空间给大了可能造成浪费，如果空间给小了可能不够用，就会十分纠结
动态顺序表
在上面静态顺序表的静态是指它的大小是固定的，同理，动态顺序表里面的动态就是指顺序表的大小是不固定的，也就是顺序表底层的数组的大小是不固定的，可以动态的变化，比如开始时给出4个元素的大小，不够时顺序表可以实现自动增容
接下来我们来看看动态顺序表的结构的定义：
//动态顺序表typedefint SLDateType;structSeqList{ SLDateType* arr;int size;int capacity;};在动态顺序表中，数组通过动态内存开辟来申请空间，如果不够用就再次申请，所以第一个成员是指向这个数组开头的指针，第二个成员就是当前顺序表中的有效元素的个数，而第三个成员则是当前顺序表的总容量
如果总容量和有效元素个数相等，说明开辟的数组的空间满了，需要增容，所以这两个成员也是必不可少的
在动态顺序表中，我们的空间浪费可以显著减少，至少不会担心给出的空间大小不够，因为它可以自动增容，比起静态顺序表要灵活得多，所以我们一般情况下都会使用动态顺序表，平常说的顺序表如果没有明确说明是静态的，那么都是在说我们的动态顺序表
所以接下来我们顺序表的实现也是使用的动态顺序表
三、顺序表的实现
1.顺序表的结构
在上面我们也讲过，一般提起的顺序表默认都是动态顺序表，所以我们这里顺序表的结构就是动态顺序表的结构，这个顺序表是一个结构体，它有三个成员，分别是底层存放数据的数组，然后就是当前有效元素个数，以及整个顺序表当前的容量，如下：
typedefint SLDateType;typedefstructSeqList{ SLDateType* arr;int size;int capacity;}SL;其中，数组是一个指针，因为我们的空间需要动态开辟，这个指针就指向了我们开辟的空间，可以把它当作正常使用，在动态内存管理部分我们也讲过使用malloc来模拟实现数组的使用，链接：【C语言】动态内存管理及相关笔试题
我们对数组的数据类型作了优化，以后需要用到哪种数据我们就可以只修改typedef后面的int，方便我们使用，其次就是我们给顺序表也取了一个别名，叫SL，这样可以避免我们每次要使用顺序表时还要带上struct关键字，这就是一个顺序表的完整结构，接着我们就来实现顺序表的各种功能
2.顺序表的初始化和销毁
初始化函数
我们创建一个顺序表之后需要对它进行初始化才能使用，初始化的方法也很简单，就是将我们顺序表的第一个成员置为NULL，然后把有效元素个数和总容量都置为0
由于我们初始化顺序表时要修改里面的成员，所以我们在传参时需要传地址，那么我们的顺序表初始化函数的参数类型就是SL*，如下：
voidSLInit(SL* ps){ assert(ps); ps->arr =NULL; ps->capacity = ps->size =
