目录
本节我们将介绍：
顺序表的有关概念
顺序表的特点
顺序表的代码实现：
编译环境：gcc；编辑器：vscode
（1）创建3个文件：SeqList.h SeqList.c mock.c
（2）创建节点
（3）具体实现：
1、初始化列表
void SeqListInit(SeqList* pq);
//接口1：初始化列表（函数）
2、销毁列表
void SeqListDestory(SeqList* pq);
//接口2： 用于销毁列表
3、打印列表
void SeqListPrint(SeqList* pq);
//接口3：用于打印列表
4、计算容量函数
void SeqCheckCapacity(SeqList* pq);
//接口4：用于计算列表的容量
5、尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//接口5：用于在顺序表的尾部增加数据
6、头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//接口6：用于在顺序表的前面增加数据
7、尾删
void SeqListPopBack(SeqList* pq);
//接口7：用于尾删
8、头删
void SeqListPopFront(SeqList* pq);
//接口8：用于头删
9、查找
int SeqListFind(SeqList* pq, SeqDataType x);
//接口9：查找某个元素
10、插入（任意位置）
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);
//接口10：在pos的后面插入一个数据
11、删除
void SeqListErase(SeqList* pq, int pos);
//接口11：删除pos位置的数据
12、修改
void SeqListModify(SeqList* pq, int pos, SeqDataType x);
//接口12：将在pos位置的数据修改为x
顺序表的有关概念
简而言之，就是用一段地址连续的存储单元依次存储数据的线性结构。
如图：
简而言之一句话，类比数组就行，和数组的存储方式几乎一模一样。
顺序表的特点：
1、空间连续；
2、缺点：在中间或前面部分的插入删除时间复杂度为O(n)，增容的代价比较大；
3、优点：支持随机访问；更适合频繁访问第n个元素的场景。
顺序表的代码实现：
好，废话不多说，我们来开始模拟实现顺序表（C语言版）
我们将会以项目工程和接口的形式来完成顺序表的实现。
编译环境：gcc；编辑器：vscode
很多童鞋说VS太大，用的不多，那好，我今天就用vscode来为大家展示（当然vscode的优势不在这里）
前提是大家要会vscode的多文件编译。
（1）创建3个文件：SeqList.h SeqList.c mock.c
我们接下来的操作，会在这三个文件当中去切换。
当然，我会为大家标注出切换到何处了。
好，我们正式开始。
（2）创建节点
实际上就是创建一个结构体。
首先，在SeqList.h中：
//SeqList.h #pragma once//防止头文件被重复引用 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int SeqDataType;//将int 重命名一下，这样我们以后如果存储的不是int类型， 就可以直接在这里改一下就可以了 typedef struct SeqList //创建一个结构体，作为顺序表的一个节点 { SeqDataType* a; //一个指针(或者叫数组)，用来存放数据 size_t capacity; //顺序表的总容量 size_t size; //顺序表的总大小 }SeqList; //同样的道理，我们重命名一下，这样以后的书写中，就不用带上struct了
视图效果：
那么接下来，我们将依次实现下面这些接口：
这些接口分别是：
增、删、查、改、打印、初始化、销毁等等
概览一下：
具体分析如下：
//SeqList.h #pragma once typedef int SeqDataType; typedef struct SeaqList { int* a; int capacity; int size; }SeaqList; void SeqListInit(SeqList* pq); //接口1：用于初始化列表 void SeqListDestory(SeqList* pq); //接口2：用于销毁列表 void SeqListPrint(SeqList* pq); //接口3：用于打印列表 void SeqCheckCapacity(SeqList* pq);//接口4：用于计算列表的容量，判断是否需要增容 void SeqListPushBack(SeqList* pq, SeqDataType x); //接口5：用于在顺序表的尾部增加数据 void SeqListPushFront(SeqList* pq, SeqDataType x); //接口6：用于在顺序表的前面增加数据 void SeqListPopBack(SeqList* pq); //接口7：用于尾删 void SeqListPopFront(SeqList* pq); //接口8：用于头删 int SeqListFind(SeqList* pq, SeqDataType x); //接口9：查找某个元素 void SeqListInsert(SeqList* pq, int pos, SeqDataType x); //接口10：在pos的后面插入一个数据 void SeqListErase(SeqList* pq, int pos); //接口11：删除在pos位置的一个数据 void SeqListModify(SeqList* pq, int pos, SeqDataType x); //接口12：将在pos位置的数据修改为x
别着急，接下来，我们将一个一个实现。
（3）具体实现：
1、初始化列表
void SeqListInit(SeqList* pq);
//接口1：初始化列表（函数）
初始化函数，简而言之，我们想要它能够将我的这个顺序表初始化（就什么数据也不给，最最开始的时候）
具体的作用见下：
//SeqList.c #include "SeqList.h" void SeqListInit(SeqList* pq) { assert(pq); //断言一下，防止pq本身是个空指针 pq->a = NULL; //将a置为空 pq->capacity = pq->size = 0; //将容量和大小都置为0 }
接下来，
2、销毁列表
void SeqListDestory(SeqList* pq);
//接口2： 用于销毁列表
因为我们的内存空间是动态开辟的，所以用完以后，我们需要手动销毁
我们想用它将整个顺序表销毁,它是这样的：
具体分析见下：
//SeqList.c void SeqListDestory(SeqList* pq) { assert(pq); //同样的道理，断延一下，防止pq为空 free(pq); //将pq free掉。 （后面在我们创建时会知道，pq实际上是动态开辟出来的） pq->a = NULL; //将a弄为空 pq->capacity = pq->size = 0; //容量和大小都变成0 }
3、打印列表
void SeqListPrint(SeqList* pq);
//接口3：用于打印列表
很简单，就是将列表中的数据打印出来。（假设都是整形）
这个还是比较容易理解的，就是一个for循环搞定的事情：
//SeqList.c void SeqListPrint(SeqList* pq) { assert(pq); for(int i =0;i < pq->size;i++) { printf("%d ",pq->a[i]); } printf("\n"); //为了使下一次打印的时候能够换行 }
来整体感受一下代码之美：
我们继续
4、计算容量函数
void SeqCheckCapacity(SeqList* pq);
//接口4：用于计算列表的容量
检测容量，如果不够要扩容（假如我们以二倍扩容)
解析如下：
//SeqList.c void SeqCheckCapacity(SeqList* pq) { assert(pq); //断延一下 if(pq->size == pq->capacity) //判断，如果二者相等，问你就要进行扩容 { int NewCapacity = pq->capacity == 0 ? 4 : pq->capacity*2; //如果原来的容量为0，那么就规定增至4，否则，扩容至原容量的二倍 SeqDataType* NewA = (SeqDataType*)realloc(pq->a, sizeof(SeqList)*NewCapacity); //动态开辟一块这么大的空间 if(NewA == NULL) { printf("realloc fail\n"); exit(-1); }//对是否开辟成功进行检测 pq->a = NewA; //将新的地址赋给a pq->capacity = NewCapacity; //新的容量赋给capacity } }
那么如果我们有了上面的接口，实现插入就是比较简单的了。
来看尾插：
5、尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//接口5：用于在顺序表的尾部增加数据
//SeqList.c void SeqListPushBack(SeqList* pq, SeqDataType x) { assert(pq); //断延 SeqCheckCapacity(pq); //检测容量是否够我插入的，不够则要自动扩容 pq->a[pq->size++] = x; //在a[pq->size]的位置插入x,插入完之后size++ }
继续：
6、头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//接口6：用于在顺序表的前面增加数据
//SeqList.c void SeqListPushFront(SeqList* pq, SeqDataType x) { assert(pq); //断延 SeqCheckCapacity(pq); //容量检测，容量不够要扩容 int end = pq->size; //标记size位置 while(end) //将顺序表中所有元素循环右移一位 { pq->a[end] = pq->a[end-1]; end--; } pq->a[0] = x; //把x的值给第一位 pq->size++; //值加一 }
那么接下来，我们可以来玩玩试试看了。
我们在mock.c中来去创建一个这样一个顺序表：
（就像这样）
那么我们让程序运行，得到如下的结果：
可以看到，我们成功了。它按照我们的方式，打印了我们所需要的数据。
好，我们继续：
7、尾删
void SeqListPopBack(SeqList* pq);
//接口7：用于尾删
//SeqList.c void SeqListPopBack(SeqList* pq) { assert(pq); //断延 assert(pq->size>0); //断延 pq->size--; //size减一 }
这个其实比较简单。
下一个：
8、头删
void SeqListPopFront(SeqList* pq);
//接口8：用于头删
//SeqList.c void SeqListPopFront(SeqList* pq) //头删 { assert(pq); //断延 assert(pq->size > 0); //断延 for(int i =0;i<pq->size -1;i++) //将所有后面的元素依次前移 { pq->a[i] = pq->a[i+1]; } pq->size--; //size减1 }
继续，
9、查找
下面的是查找一个元素：
int SeqListFind(SeqList* pq, SeqDataType x);
//接口9：查找某个元素
如果找到我们想要的元素，那么我们就返回这个元素所在的下标。否则，返回-1。
//SeqList.c int SeqListFind(SeqList* pq, SeqDataType x) { assert(pq); //断延 int end = 0; //标记一个位置 while(end<pq->size) { if(pq->a[end]==x)return end; //如果找到，则返回下标 else end++; } return -1; //如果没找到，则返回-1 }
10、插入（任意位置）
在pos元素后面插入一个元素x：
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);
//接口10：在pos的后面插入一个数据
void SeqListInsert(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pos < pq->size); //断延 SeqCheckCapacity(pq); //检测容量大小，是否需要扩容 int end = pq->size - 1; //找到这个列表中最后一个元素的下标 while(end>=pos) { pq->a[end+1] = pq->a[end]; //将在pos前面的元素依次左移 end--; } pq->a[pos] = x; //将在pos的位置赋值给x pq->size++; }
11、删除
删除下标为pos的元素：
void SeqListErase(SeqList* pq, int pos);
//接口11：删除pos位置的数据
void SeqListErase(SeqList* pq, int pos) { assert(pq); assert(pos < pq->size && pos > 0); //两次断延 int del = pos; //标记pos位置 while(del < pq->size - 1) { pq->a[del] =pq->a[del+1]; //将pos后面的元素依次左移 del++; } pq->size--; //size减1 }
12、修改
void SeqListModify(SeqList* pq, int pos, SeqDataType x);
//接口12：将在pos位置的数据修改为x
void SeqListModify(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pq->size>pos); //两次断延 pq->a[pos] = x; //直接将下标为pos的元素改为x }
好，现在我们就将所有的接口全部写完了。
我们再来玩玩看：
在mock.c中打入：
运行结果：
我们可以看到，我们成功了。
