【初阶数据与算法】线性表之顺序表的定义与实现
文章目录
- 一、线性表的概念
- 二、顺序表
- 1.概念与结构
- 2.顺序表的分类
- 静态顺序表
- 动态顺序表
- 三、顺序表的实现
- 1.顺序表的结构
- 2.顺序表的初始化和销毁
- 初始化函数
- 销毁函数
- 3.顺序表的扩容
- 4.顺序表的尾插和头插
- 尾插函数
- 头插函数
- 5.顺序表的尾删和头删
- 尾删函数
- 头删函数
- 6.顺序表的查找
- 7.指定位置插⼊/删除数据
- 指定位置之前插入
- 指定位置删除数据
一、线性表的概念
线性表（linearlist）是n个具有相同特性的数据元素的有限序列，线性表在物理结构上并不⼀定是连续的，在逻辑结构上是连续的
物理结构就是在存储数据时真实的内存存储位置，物理结构上连续就是说在存储数据时，使用的是一段连续的内存空间存储数据，例如数组，它开辟出来的内存空间就是连续不断的，我们在数组的章节也做了介绍，数组就属于物理结构连续的一种结构
而逻辑结构独立于物理结构，它关注的是数据元素之间的关系，逻辑结构连续就是，它虽然在物理结构上可能不是采用连续存储数据的方式，但是我们可以通过某种方式使得这些数据连续起来，使得在访问数据时可以将物理结构上分散的数据连续起来，这就是逻辑结构连续
我们今天介绍的线性表在逻辑上是线性结构，但是它在物理结构上并不⼀定是连续的，也就是在访问数据时，我们一定可以按照顺序进行访问，但是在存储数据时，我们既可以采用连续的内存空间存储数据，也可以采用不连续的内存空间存储数据，只要我们采用某种方式使得线性表的数据可以连续的访问即可
当线性表的物理结构是连续的时候，一般使用数组来存储数据，当线性表的物理结构不是连续的时候，一般以链式的结构存储，线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串等等，我们今天介绍的就是线性表之一的顺序表
二、顺序表
1.概念与结构
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储，如图：
那么肯定就会有人有疑问了，顺序表既然底层使用了数组，为什么不直接使用数组，而要取一个顺序表的名字，那么它们真实的区别是什么呢？其实很简单，数组只是数组而已，一种可以连续存储数据的结构
但是我们在上一篇文章讲过，数据结构不仅要能够存储数据，还要能够合理的管理数据，我们的顺序表虽然底层是数组，但是在数组的基础上提供了增删查改等多种方法让我们可以去合理的管理数据
所以严格地说，单独的数组不算一种数据结构，而拥有增删查改等等功能的数组，也就是顺序表，才是一种数据结构，那么顺序表到底长什么样子呢？它其实是一个结构体，不同的顺序表定义的结构体不同，所以我们先来学习顺序表的分类
2.顺序表的分类
顺序表又可以分为静态顺序表和动态顺序表，我们接下来就来学习一下这两种不同顺序表的概念，以及我们平常使用的到底是哪种顺序表
静态顺序表
静态顺序表的静态是指顺序表底层的数组的元素大小是静态的，也就是静态顺序表使⽤的是定⻓的数组存储元素，而顺序表实际上就是使用一个结构体来进行维护，一般静态顺序表的结构如下：
typedef int SLDateType;
#define N 7
struct SeqList
{
SLDateType arr[N];
int size;
};
在上面我们提到了，顺序表其实是由一个结构体进行维护的，不同种类的顺序表的结构体不同，在静态顺序表中，底层数组的元素大小是确定了的，一般使用#define来定义一个常量来充当它的大小
而由于我们并不知道顺序表中会存储什么数据类型，所以我们可以使用typedef关键字对类型进行重命名，以后我们想要修改顺序表的数据类型时，就可以只修改typedef这一条语句，否则的话每次修改数据类型将会十分麻烦
我们也可以看到，这里结构体的名字就是SeqList，它里面包含了两个单词，Seq代表英文单词sequential，意思是顺序的，List就是表的意思，合起来就是我们的顺序表
在静态顺序表中的结构有两个成员，应该就是底层存储数据的数组，它的大小是确定的，第二个成员是整型变量size，它的含义是目前顺序表中有效元素的个数
静态顺序表的缺点也很明显，就是它的大小是固定的，空间给大了可能造成浪费，如果空间给小了可能不够用，就会十分纠结
动态顺序表
在上面静态顺序表的静态是指它的大小是固定的，同理，动态顺序表里面的动态就是指顺序表的大小是不固定的，也就是顺序表底层的数组的大小是不固定的，可以动态的变化，比如开始时给出4个元素的大小，不够时顺序表可以实现自动增容
接下来我们来看看动态顺序表的结构的定义：
//动态顺序表
typedef int SLDateType;
struct SeqList
{
SLDateType* arr;
int size;
int capacity;
};
在动态顺序表中，数组通过动态内存开辟来申请空间，如果不够用就再次申请，所以第一个成员是指向这个数组开头的指针，第二个成员就是当前顺序表中的有效元素的个数，而第三个成员则是当前顺序表的总容量
如果总容量和有效元素个数相等，说明开辟的数组的空间满了，需要增容，所以这两个成员也是必不可少的
在动态顺序表中，我们的空间浪费可以显著减少，至少不会担心给出的空间大小不够，因为它可以自动增容，比起静态顺序表要灵活得多，所以我们一般情况下都会使用动态顺序表，平常说的顺序表如果没有明确说明是静态的，那么都是在说我们的动态顺序表
所以接下来我们顺序表的实现也是使用的动态顺序表
三、顺序表的实现
1.顺序表的结构
在上面我们也讲过，一般提起的顺序表默认都是动态顺序表，所以我们这里顺序表的结构就是动态顺序表的结构，这个顺序表是一个结构体，它有三个成员，分别是底层存放数据的数组，然后就是当前有效元素个数，以及整个顺序表当前的容量，如下：
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* arr;
int size;
int capacity;
}SL;
其中，数组是一个指针，因为我们的空间需要动态开辟，这个指针就指向了我们开辟的空间，可以把它当作正常使用，在动态内存管理部分我们也讲过使用malloc来模拟实现数组的使用，链接：【C语言】动态内存管理及相关笔试题
我们对数组的数据类型作了优化，以后需要用到哪种数据我们就可以只修改typedef后面的int，方便我们使用，其次就是我们给顺序表也取了一个别名，叫SL，这样可以避免我们每次要使用顺序表时还要带上struct关键字，这就是一个顺序表的完整结构，接着我们就来实现顺序表的各种功能
2.顺序表的初始化和销毁
初始化函数
我们创建一个顺序表之后需要对它进行初始化才能使用，初始化的方法也很简单，就是将我们顺序表的第一个成员置为NULL，然后把有效元素个数和总容量都置为0
由于我们初始化顺序表时要修改里面的成员，所以我们在传参时需要传地址，那么我们的顺序表初始化函数的参数类型就是SL*，如下：
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
销毁函数
接着就是顺序表的销毁了，由于我们的顺序表的空间是动态申请的，所以我们使用完顺序表之后需要对申请的空间进行释放，以免造成内存泄漏，释放完之后将我们的指针置为NULL，有效元素个数和总容量重新置为0，这就是我们顺序表的销毁
然后顺序表的销毁还是需要修改里面的数据，所以还是传地址，如下：
void SLDestroy(SL* ps)
{
assert(ps);
//如果数组不为空，就释放动态申请的空间
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
3.顺序表的扩容
我们实现的顺序表是动态顺序表，底层的数组的大小是动态变化的，所以我们需要写一个函数来检查数组是否已经满了，如果满了就需要进行扩容，经过研究，确定了每次空间扩大2倍较好，可以尽量的减少浪费
需要扩容的条件就是，如果我们顺序表中的有效元素个数size和总容量capacity相等，那么顺序表就满了，需要进行二倍扩容，将空间扩大二倍
但是我们还要注意一个点，顺序表初始情况下容量为0，我们需要特殊处理一下，如果检测到它的容量为0，那么就直接给它申请四个元素的空间，如果不为0，那么就对原本的空间进行二倍扩容
由于我们扩容可能修改顺序表的大小以及指针指向，所以这个扩容函数还是需要传地址，如下：
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDateType* tmp = (SLDateType*)realloc(ps->arr, ps->capacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc");
return;
}
ps->arr = tmp;
}
}
4.顺序表的尾插和头插
我们初始化好了顺序表之后，就要使用顺序表来存放数据了，我们首先介绍头插和尾插，头插就是在顺序表开头插入数据，而尾插则是在顺序表尾部插入数据，要注意的是，在插入之前我们都要判断一下容量够不够，不够的话要进行增容，接下来就让我们来学习尾插和头插
尾插函数
由于尾插比较简单，所以我们首先介绍尾插函数，尾插就是向顺序表的最后面插入数据，也就是向数组的最后一个位置插入数据，那么我们怎么找到数组中最后一个数据的位置呢？
还记得顺序表中的size成员吗，它就是存放的有效元素的个数，我们可以通过size来进行尾插，如图：
通过这个图片我们可以发现，有效元素个数size是4，刚好size这个下标就是我们数组最后一个有效元素的下一个元素的下标，所以我们尾插的时候只需要在size这个下标处插入数据，同时记得让我们的size++，表示我们有效数据个数+1了
最后还有个要注意的点，就是我们插入数据前要看看顺序表容量够不够，如果已经满了就进行不了插入操作，所以我们刚刚之前写的增容函数就起到作用了
由于我们可能对顺序表进行修改，所以还是要传地址，如下：
void SLPushBack(SL* ps,SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
头插函数
头插函数相对于尾插函数要稍微复杂一点，我们可以思考一下，如何将一个数据插入到一个数组的最开始，是不是要把数组中的所有元素整体向后移动一位，然后再把我们的数据放进下标为0的位置上
那么怎么将数组中的所有元素整体向后移动一位呢？这里提供一种方法，就是我们在内存函数部分学过的函数：memmove，如果遗忘了请参照：【C语言】内存函数的使用和模拟实现
其中memmove的第一个参数是我们要移动的目标位置的地址，很明显就是顺序表中第二个元素的地址，即ps->arr+1，第二个参数就是我们源位置的地址，是顺序表中第一个元素的地址，即ps->arr，它的第三个参数就是要拷贝的字节数，就是有效元素个数乘以一个元素的大小
头插还是要插入数据，所以要在开始判断一下顺序表的容量是否满了，最后由于我们还是需要修改顺序表，所以还是传地址，如下：
void SLPushFront(SL* ps,SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
memmove(ps->arr + 1, ps->arr, ps->size * sizeof(SLDateType));
ps->arr[0] = x;
ps->size++;
}
5.顺序表的尾删和头删
有了插入数据那么就有删除数据，这里我们还是先讲头删和尾删，头删就是删除顺序表第一个元素，尾删就是删除顺序表最后一个元素，我们要注意的是，删除之前我们需要看看顺序表是否有数据，没有数据自然不能删除数据
尾删函数
由于尾删还是更加简单，所以我们先讲尾删，那么我们怎么实现尾删呢？其实很简单，我们只需要让size- -，其它什么都不需要做
因为我们尾插的时候是直接把要插入的数据直接放进size下标的元素中，如果size本身有数据也不影响我们覆盖它，我们画几张图来分析一下，首先是我们的尾删，也就是将size直接-1
可以看到我们的尾删就是让size-1，现在我们来尾插一个6，看看有没有影响：
可以看到，尾插操作会将5这个位置的数据进行覆盖，并不会影响尾插，头插也是这样，会覆盖size位置的数据，这里就不再演示了，可以自行推导一下
最后一点要注意的是我们最好在尾删之前要进行一下断言，确保顺序表中的size，也就是有效数据个数>0，如下：
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
头删函数
头删函数也很简单，我们的目的就是删除下标为0处的数据，我们就可以把从下标为1到下标为size-1的元素全部向前移动一位，如图：
可以看到最后我们实现了头删，虽然size位置上还有一个数据5留在那里，但是由于那里的下标是size，所以并不会影响插入，理由跟上面的尾删一致
想要下标为1到下标为size-1的元素全部向前移动一位，我们可以一步解决，就是使用库函数memmove，它的第一个参数就是目标地址，也就是ps->arr，第二个参数是源地址，也就是ps->arr+1，最后就是移动多少个字节，就是(- -ps->size)乘以每个元素的大小
接下来我们就来看看头删的实现：
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size > 0);
memmove(ps->arr, ps->arr + 1, --ps->size * sizeof(SLDateType));
}
6.顺序表的查找
顺序表的查找就是根据给出的值，去看它存不存在我们的顺序表中，如果存在就返回那个元素的下标，如果不存在就返回一个错误的下标，这里我们就返回-1，这个方法的实现只需要遍历数组就可以了，非常简单，如下：
int SLFind(SL* ps,SLDateType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
7.指定位置插⼊/删除数据
指定位置的插入和删除比较难，我讲的还是使用memmove的方法，代码量比较少，但是可能比较难理解，如果有不懂的地方欢迎提出来
指定位置之前插入
由于是指定位置之前插入，首先我们要有这个指定位置，在这里一般就是指那个位置的下标，它作为函数的参数传过来，所以这个函数有三个参数，一个是顺序表的地址，一个是指定位置的下标，最后一个是我们要插入的数据，如下：
void SLInsert(SL* ps, int pos, SLDateType x)
现在我们就想办法来实现这个功能，首先我们来画个数组，然后把相关信息写出来，方便我们理解：
现在我们要在3之前插入一个6，也就是在下标为pos的数据之前插入6，我们就可以这样，让pos及以后的数据往后挪动移位，然后把6放入pos中，如下图：
这样就实现了在3之前插入数据了，首先我们来实现第一步，就是将pos及以后的数据往后挪动一位，我们还是使用memmove，第一个参数就是我们移动的目的地的地址，也就是ps->arr+pos+1，第二个参数是我们的源地址，就是ps->arr+pos
最难的就是最后一个参数，就是我们要移动多少字节，要移动几个元素，这里我们可以使用实例来帮我们解决
在上面的例子里面，要移动的元素有三个，就是5-2，不正是ps->size - pos吗，所以很多情况下我们都可以通过一个例子来推出整个式子，如果下次写这个函数时忘记了，就可以这样画图来推，最后整个移动阶段的代码如下：
memmove(ps->arr + pos + 1, ps->arr + pos, sizeof(SLDateType) * (ps->size - pos));
随后就是在pos位置插入新的元素，如下：
ps->arr[pos] = x;
ps->size++;
最后就是，我们在函数开始前，也要判断一下pos的值是否有效，也就是是否是0到size的数，进行一下断言，完整代码如下：
void SLInsert(SL* ps, int pos, SLDateType x)
{
assert(ps && pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
memmove(ps->arr + pos + 1, ps->arr + pos, sizeof(SLDateType) * (ps->size - pos));
ps->arr[pos] = x;
ps->size++;
}
一般这个SLInsert函数会和上面讲过的查找函数一起使用，用查找方法找某个数据，然后将返回值作为SLInsert函数的参数，就可以实现在某个数据前进行插入数据
指定位置删除数据
这个指定位置删除数据和上面的指定位置之前插入数据很像，思路是差不多的，如果理解了上面的代码学习这个函数就轻松多了
首先我们要在指定位置删除数据，还是需要一个该位置的下标pos，这个就作为参数传过来，如下：
void SLErase(SL* ps,int pos)
我们删除指定位置的数据的思路就是，直接将pos后面的数据往前挪动一位，直接覆盖掉pos位置的数据，然后让size-1，这样就实现了删除指定位置的数据，我们可以画图来理解一下：
我们首先来实现第一步，就是将pos之后的数据往前移动一位，还是使用memmove函数，第一个参数就是目标地址，这里的目标地址就是ps->arr+pos，然后第二个参数就是源地址，就是ps->arr+pos+1
然后第三个参数就是要移动多少个字节，主要还是要求移动多少个元素，我们还是使用之前的方法，通过代入一个例子来把它写出来，在上面的例子中，我们要移动2个元素，不正好就是ps->size-pos-1吗？所以我们最后就可以写出这关键的一步：
memmove(ps->arr + pos, ps->arr + pos + 1, sizeof(SLDateType) * (ps->size - pos - 1));
下一步就是让size-1了，最后就是，我们在函数开始前，也要判断一下pos的值是否有效，也就是是否是0到size的数，进行一下断言，完整代码如下：
void SLErase(SL* ps,int pos)
{
assert(ps && pos>=0 && pos<=ps->size);
assert(ps->size > 0);
memmove(ps->arr + pos, ps->arr + pos + 1, sizeof(SLDateType) * (ps->size - pos - 1));
ps->size--;
}
这个SLErase函数一般也是配合上面的查找方法使用，先查找到某个数据的下标，然后再把返回值作为SLErase函数的参数，实现删除某个指定的元素的效果
今天的顺序表就到此结束啦，有什么不懂欢迎提出来
bye~