前言

顺序表是线性表的一种，是实际中运用非常广泛的一种数据结构，也应该是每一个初学者所接触到的第一种数据结构。所谓万事开头难，学好顺序表实现就是为数据结构的学习开了一个好头。

顺序表一般分为两种，一种为静态顺序表，实质上是一个静态的数组。还有一种是动态顺序表，动态顺序表的内存可以根据使用者需求来自主调整大小。本篇文章我将主要向大家介绍动态顺序表的以下功能：初始化、打印、尾插、尾删、头插、头删、查找、任意位置的插入、任意位置的删除。

每一个功能我都会向大家展示相应的效果，并且分析它就是如何来实现的，下面开始介绍。

---

1.概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

• 1.静态顺序表：使用定长数组存储。
• 2.动态顺序表：使用动态开辟的数组存储（摆脱数组大小的限制）。

1.1顺序表的静态存储：

typedef int SLDataType;
#define N 10struct SeqList
{SLDataType a[N];//定长的数组int size;// 有效数据的个数
};

静态顺序表就是一个静态数组，将其定义在一个结构体内部，同时还能定义该数组的有效位数。

1.2顺序表的动态存储：

typedef int SLDataType;typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组int size;      // 有效数据的个数int capacity;  // 容量
}SL;

动态顺序表不再是在栈上直接开辟一块定长的数组，而是在堆上开辟一块连续存储的动态空间，定义一个指针指向该连续空间。如果空间不足，可以使用realloc函数来进行扩容。所以在结构体中同时还定义了有效位数和动态空间容量。

2.动态顺序表接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，N定小了，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间的大小，所以下面我们实现动态顺序表。

首先我们创建一个工程，建三个文件：

• SeqList.h头文件存放动态顺序表的声明，以及所有功能接口函数的声明。
• SeqList.c文件存放我们所要实现的功能接口函数。
• test.c为主函数部分，用来测试每个功能是否实现成功。

2.1声明部分

我们先来完成SeqList.h头文件，声明动态顺序表并完成所有即将实现函数的声明，代码如下：

// 动态顺序表设计 （大小可变）
typedef int SLDataType;typedef struct SeqList
{SLDataType* a; //指向动态开辟的数组int size;      // 有效数据的个数int capacity;  // 容量
}SL;// 基本增删查改接口
//顺序表初始化
void SeqListInit(SL* ps);//顺序表打印
void SeqListPrint(SL* ps);//检查空间，如果满了进行扩容
void SeqListCheckCapacity(SL* ps);//顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾删
void SeqListPopBack(SL* ps);//顺序表头插
void SeqListPushFront(SL* ps, SLDataType x);//顺序表头删
void SeqListPopFront(SL* ps);// 任意位置的插入
void SeqListInsert(SL* ps, int pos, SLDataType x);//在任意位置删除
void SeqListErase(SL* ps, int pos);// 顺序表查找
int SeqListFind(SL* psl, SLDataType x);

2.2顺序表的初始化

在实现顺序表的功能之前应该先将顺序表初始化一下，让顺序表变量按照我们的预想开始。

void SeqListInit(SL* ps)
{ps->a = (SLDataType*)malloc(sizeof(SLDataType)* 4);if (ps->a == NULL){printf("申请内存失败\n");exit(-1);}ps->size = 0;ps->capacity = 4;
}

初始化的时候我们需要拿到顺序表结构体变量的地址，顺序表第一个成员指针变量指向的是顺序表动态开辟的空间，用malloc函数来开辟。

一开始我们先开辟四个元素的大小（具体的字节大小根据当前元素的字节大小决定），如果开辟失败就直接结束掉程序，如果内存开辟失败了后面的步骤也就没有必要再进行下去了。再设置的有效数size为0，容量capacity为4.

2.3顺序表的尾插

初始化完之后我们来考虑尾插的实现，尾插就是在顺序表的结尾插入一个元素。

先想一下，如果我们直接往顺序表尾部插入数据会不会有问题呢？当然是有的，我们知道顺序表是动态开辟出来的，一开始开辟的空间并不是很大，假如当前有效数已经达到顺序表的容量值了，而我们还要往顺序表中插入元素，这样是不是就会发生越界的现象。

那么怎样解决这个问题呢，就是在尾插操作开始之前，先检查顺序表的容量是否已满，如果已满，就要对顺序表的空间进行扩容。

所以在进行尾插操作之前我们要先写一个检测顺序表容量是否已满的查容函数：

void SeqListCheckCapacity(SL* ps)
{// 如果满了需要增容if (ps->size == ps->capacity){ps->capacity *= 2;ps->a = (SLDataType*)realloc(ps->a, sizeof(SLDataType)*ps->capacity);if (ps->a == NULL){printf("扩容失败\n");exit(-1);}}
}

如果顺序表有效数和容量相等则说明顺序表已满，这个时候就要进行扩容了操作了。扩容的时候一般规定都是扩大一倍，先将容量capacity扩大一倍，然后用realloc函数重新开辟一块相应大小的空间。

扩容函数写好之后，我们就可以来实现尾插函数了：

void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

在进行尾插之前先调用查容函数看顺序表容量是否已满，如果已满进行扩容。查容函数调用完之后再来进行尾插，尾插函数接收两个参数，一个是顺序表结构体变量，一个是要插入的元素。只需把要插入的元素放到动态数组下标为size的位置即可，最后再给有效数size自加1.

2.4顺序表的打印

为了方便检测所写的每一个接口函数是否正确，这就需要将顺序表的内容打印出来看看了，所以这里我们还需要写一个打印函数，打印顺序表的每一个元素。

下面我们再来实现一个打印函数：

void SeqListPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}

打印函数的实现很简单，只需写一个简单的for循环即可，循环的次数也就是要打印的顺序表中有效数size，然后利用printf函数打印即可。

打印函数完成之后我们在测试文件的主函数中调用一个Test函数，在一个顺序表中尾插几个元素并且打印出来看看：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPrint(&s);SeqListPushBack(&s, 4);SeqListPrint(&s);SeqListPushBack(&s, 5);SeqListPrint(&s);SeqListPushBack(&s, 6);SeqListPrint(&s);
}int main()
{Test();return 0;
}

创建一个结构体变量s，我们先调用尾插函数直接一次性插入3个元素打印，然后每插入一个元素后打印一次，来看看尾插的效果，
运行结果：

可以看到一开始我们插入了3个数，后面的每一个数都是从顺序表的末端进行插入，这就是我们想要的尾插效果，到这里我们就成功写完尾插的接口了。

2.5顺序表的尾删

尾删就是每次从顺序表的末端删掉一个元素。

尾删的操作实现起来真的可以说是非常的简单：

void SeqListPopBack(SL* ps)
{assert(ps);ps->size--;
}

可以看到我们只需要将顺序表的有效位数减1就可以了。

看到这里有人可能会有这样一个疑惑，你把有效数减1了，但是该内存的数据还在里面啊，怎么能说是删除了呢？其实删除就是这样，大家日常理解的删除可能是把该内存里的内容清空，就像扫垃圾一样把它带走。但是实际上删除就是让当前内存的位置不在当前的管辖范围内，所以删掉之后我们就看不见它了，但是数据依旧还在内存中，这也是为什么我们删掉的数据可以被找回来。当然，当内存一直用啊用啊，如果你删掉的位置被其他地方调用，里面的内容被覆盖掉，原来内存里的东西就找不回来了。

尾删函数写完之后我们调用Test函数来验证一下：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPushBack(&s, 6);SeqListPushBack(&s, 7);SeqListPushBack(&s, 8);SeqListPrint(&s);SeqListPopBack(&s);SeqListPrint(&s);SeqListPopBack(&s);SeqListPrint(&s);SeqListPopBack(&s);SeqListPrint(&s);SeqListPopBack(&s);SeqListPrint(&s);
}int main()
{Test();return 0;
}

我们先调用头插函数插入8个元素，然后每调用一次尾删函数打印一次看看效果，
运行结果：

可以看到每调用一次尾删函数就会删掉顺序表末端的一个元素

2.6顺序表的头插

头插就是在顺序表的起始位置插入元素。

头插就没有尾插容易了，试想如果我们直接往起始位置插入元素，那原本起始位置的元素不就不见了吗？所以在插入之前应该先把顺序表的所有元素向后移动一位，在最开始的位置腾出一块空间来，然后再将要插入的元素放进去。

void SeqListPushFront(SL* ps, SLDataType x){assert(ps);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

头插函数实现之前同样我们要检查顺序表的容量是否已满，调用查容函数。然后进行元素后移的操作，后移的时候是从后往前移的，我们拿到数组最后一块空间的下标size，移动的次数是size次，把前一个空间的内容拷贝到后一个空间中去，拷贝完之后，将要插入的元素放在顺序表的起始位置，然后再将有效数size自加1.

继续调用Test函数来验证一下：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPrint(&s);SeqListPushFront(&s, -1);SeqListPrint(&s);SeqListPushFront(&s, -2);SeqListPrint(&s);SeqListPushFront(&s, -3);SeqListPrint(&s);int main()
{Test();return 0;
}

先调用尾插函数插入三个元素，然后调用头插函数插入元素，每插入一个元素打印一次看一下效果，
运行结果：

可以看到每次从顺序表的起始位置插入一个元素。

2.7顺序表的头删

头删就是从顺序表的起始位置删掉一个元素。

我们在进行尾删的时候很简单，只需把顺序表中有效数的位数减1即可，当然这在头删这块是行不通的。

头删和头插起始十分类似，既然我们不想要第一个元素了，就把后面的元素拷贝过来将它覆盖掉，依次类推，将起始位置后面的元素依次往前挪一位，然后在把有效数减1即可。

void SeqListPopFront(SL* ps)
{assert(ps);int start = 0;while (start < ps->size-1){ps->a[start] = ps->a[start+1];++start;}ps->size--;
}

往前挪位的时候应该是从前往后挪的。我们先拿到起始下标0，然后把后一位元素往前一位元素的地方拷贝，拷贝的次数为size - 1次，因为删掉了一个元素。完成之后将有效数size的值自减1即可。

下面继续调用Test函数来验证一下：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPushBack(&s, 6);SeqListPushBack(&s, 7);SeqListPushBack(&s, 8);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);
}int main()
{Test();return 0;
}

我们先插入8个元素，然后每调用一次头删函数打印看一下效果，
运行结果：

可以看到每次都会删掉起始位置的一个元素，这就是头删的效果。

2.8顺序表任意位置的插入

顺序表在任意位置进行插入的时候，首先我们要拿到这个要插入的位置。

当我们要在某位置进行插入的时候，如果该位置本身是有元素的，那么我们就应该把这个位置给腾出来存放要插入的元素。具体的做法是将从该位置开始的元素依次向右挪一位，这样就可以成功的腾出一个位置来存放要插入的元素。

位置腾出来之后我们就可以将元素插入到顺序表的指定位置中了。

实现代码：

void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos <= ps->size && pos >= 0);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}

首先应该断言我们拿到的结构体指针不为空，还要确保所给的位置在顺序表有效位置的范围内。插入之前我们要调用查容函数检测当前顺序表的容量是否已满。

前面检查部分准备好之后，接下来就要进行前面提到的挪位，挪位的时候需要注意要从后往前挪。就是先挪动最后一个元素，再依次挪动他前面的元素。因为如果先挪前面的元素就会发生元素的覆盖，这不难理解。

这里有一点需要注意的是这里访问顺序表的时候是以数组的形式访问的，而我们知道数组的下标是从0开始的，所以最后一个元素的下标应该是有效数size-1，当挪到第pos位的元素截止，起始位置应该是第0位。

下面我们调用Test函数来验证一下这个插入函数：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListInsert(&s, 0, 1);SeqListInsert(&s, 0, 2);SeqListInsert(&s, 0, 3);SeqListPrint(&s);SeqListInsert(&s, 1, 0);SeqListPrint(&s);
}int main()
{Test();return 0;
}

先从0位置开始往里面插入3个元素1、2、3，然后在1位置插入元素0，打印顺序表，
运行结果：

可以看到成功将0插入到顺序表的1位置处了。

2.9顺序表任意位置的删除

由于顺序表示连续的，所以要删除某个位置的元素时不是说将此位置的空间弃之不用。首先我们要拿到需要删除的位置。

接下来我们的做法应该是让该位置后面的元素覆盖上来，将要删除的元素给覆盖掉。然后后面的元素继续往前覆盖，最后顺序表的有效数会减少一个，我们只需将size-1即可。

实现代码：

void SeqListErase(SL* ps, int pos)
{assert(ps);assert(pos < ps->size && pos >= 0);int start = pos;while (start < ps->size - 1){ps->a[start] = ps->a[start + 1];++start;}ps->size--;
}

删除开始之前我们依旧要先确保要删除的位置在有效位置的范围内。

删除挪位操作和插入刚刚相反，应该从前往后挪，挪动的第一个元素应该是pos位置后面的元素，将其放在顺序表的第pos位，存放元素的第一个位置下标应该是pos，最后一个位置下标应该是size-2。

挪动完之后将顺序表有效数size的值减1，这样就可以成功将一个元素从顺序表之中删掉了。

下面继续调用Test函数来验证一下：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListInsert(&s, 0, 1);SeqListInsert(&s, 0, 2);SeqListInsert(&s, 0, 3);SeqListInsert(&s, 0, 4);SeqListInsert(&s, 0, 5);SeqListInsert(&s, 0, 6);SeqListPrint(&s);SeqListErase(&s, 1);SeqListPrint(&s);
}int main()
{Test();return 0;
}

我们先插入6个元素1、2、3、4、5、6，然后再将顺序表1位置的内容给删掉，
运行结果：

可以看到，顺序表原先1位置的元素5被删除掉了。

2.10顺序表的查找

顺序表的查找实现起来就比较简单了，我们只需将顺序表遍历一遍，看看顺序表中有没有元素和我们要查找的数据相等。如果有则说明找到了，返回该元素当前位置的下标即可，如果找不到就返回-1.

int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i = 0;while (i < ps->size){if (ps->a[i] == x){return i;}++i;}return -1;
}

下面调用Test函数来验证一下：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListInsert(&s, 0, 1);SeqListInsert(&s, 0, 2);SeqListInsert(&s, 0, 3);SeqListInsert(&s, 0, 4);SeqListInsert(&s, 0, 5);SeqListInsert(&s, 0, 6);SeqListPrint(&s);printf("%d\n", SeqListFind(&s, 3));
}int main()
{Test();return 0;
}

还是先插入6个元素，下面我们来找3在不在顺序表中，
运行结果：

可以看到找到了，3在顺序表中的下标是3，于是就返回3.

下面再来验证一个找不到的情况：

#include "SeqList.h"Test()
{SL s;SeqListInit(&s);SeqListInsert(&s, 0, 1);SeqListInsert(&s, 0, 2);SeqListInsert(&s, 0, 3);SeqListInsert(&s, 0, 4);SeqListInsert(&s, 0, 5);SeqListInsert(&s, 0, 6);SeqListPrint(&s);printf("%d\n", SeqListFind(&s, 3));
}int main()
{Test();return 0;
}

这次我们要查找的元素7并不在顺序表中，
运行结果：

可以看到查找函数的返回值是-1，说明要找的数不在顺序表中。

到这里顺序表的所有功能就介绍完了，下面我们来总结一下顺序表。

3.顺序表总结

3.1顺序表的特点:

• 1.内存空间可以动态增长。
• 2.数据在顺序表中的存储必须是连续的。

3.2顺序表的优点：

• 1.可以随机访问。
• 2.缓存命中率比较高（顺序表在物理空间是连续的，预加载比较有优势）。

3.3顺序表的缺点：

• 中间/头部的插入删除，时间复杂度为O（N）。
• 增容需要申请新的空间，拷贝数据，释放旧空间，会有不小的损耗。
• 增容一般是呈二倍的增长，势必会有一定的空间浪费。例如当前的容量为100，满了以后增容到两百，而我们只插入了5个数据，后面就没有数据的插入了，那么就浪费了95个空间。

既然我们知道了顺序表的缺点，那么思考有没有一种结构可以改进顺序表的缺点呢？

当然是有的，这就是链表结构，后面的文章中我会继续向大家介绍链表结构的相关功能，看看链表在实现起来相对于顺序表到底有哪些优势。

本篇文章到这里就结束了，希望能够为大家带来帮助。