一.什么是动态顺序表?
动态顺序表：使用动态开辟的数组存储，使用指针指向动态开辟的数组，可以进行扩容。可以队数组内容进行增删查改等操作。
这里顺便提一下什么是逻辑结构和物理结构
逻辑结构: 人为想象出来的,实际并不存在.
物理结构: 实际存在,可以被观察到
二.动态顺序表的优缺点
优点：空间连续，支持随机访问。
缺点：1.中间或前面部分的插入时间复杂度是O(N)，
2.增容的代价比较大
三.创建项目
| 工程文件 | 存放的内容 |
| SeqList.h | 函数声明，宏定义 |
| SeqList.c | 实现顺序表函数接口的定义 |
| test.c | 测试函数接口是否能实现功能 |
四.接口实现
1.定义顺序表
为了后续我们想更改数据类型时方便，我们一般对类型进行typedef操作。
typedef int SeqlistType; //创建结构体 typedef struct Seqlist { SeqlistType* arr; //指向动态开辟的数组 SeqlistType size; //有效个数 SeqlistType capacity;//容量 }SL;
2.结构体初始化
传值：因为形参是实参的一份临时拷贝，对形参的改变并不会改变实参。所以我们应该把结构体变量的地址传过去，用结构体指针接收！为了防止传过来的是空指针，我们可以用assert进行断言！
//
void SeqlistInit(SL* ps) { assert(ps); ps->arr = NULL; ps->size = 0; ps->capacity = 0; }
3.打印数据
我们只需要遍历顺序表就能完成打印
void SeqlistPrint(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); }
/
4.顺序表增容
我们插入数据时，应该要先检查顺序表的容量是否满了（ps->size == ps->capacity）
因为一开始我们时没有给容量的（capacity = 0），所以我们可以先给4个空间，后续不够空间了再两倍的扩容！
//检查容量 void SeqlistCheckCapacity(SL* ps) { assert(ps); //当size == capacity时要扩容了 int newcapacity = 0; if (ps->size == ps->capacity) { newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2); //如果一开始容量为0，就给4个空间 //不为0就扩为原来的2倍 //扩容还要重新开辟空间->realloc SeqlistType* tmp = (SeqlistType*)realloc(ps->arr, sizeof(SeqlistType) * newcapacity); //注意：要判断是否开辟成功 if (tmp == NULL) { printf("扩容失败\n"); //exit(-1); return; } else { ps->arr = tmp; ps->capacity = newcapacity; } } }
/
5.头插数据
头插数据：1.要先检查顺序表容量，不够则扩容
2.头插即为把数据放到第一个位置，那我们把数组原来的数据向后移动即可！要注意从最右边的开始移动(i = ps->size-1)，否则前面的数据会把后面的数据覆盖！
3.插入数据后，标记有效数字的size+1；
//头插 void SeqlistPushFront(SL* ps, SeqlistType x) { assert(ps); //注意先检查容量！！！！ SeqlistCheckCapacity(ps); int i = 0; for (i = ps->size-1; i >=0; i--) { ps->arr[i+1] = ps->arr[i]; } ps->arr[0] = x; ps->size++; }
/
6.尾插数据
尾插数据：1.尾插数据也要先检查容量
2.在数组的位置上插入数据即：ps->size位置
3.插入数据，szie++；
//尾插 void SeqlistPushBack(SL* ps, SeqlistType x) { assert(ps); //注意先检查容量！！！！ SeqlistCheckCapacity(ps); ps->arr[ps->size] = x; ps->size++; }
7.头删数据
头删数据：1.把后面的数据往前面覆盖，要注意从左边开始(i=0)，否则会造成数据丢失！
2.删除了数据，size--
void SeqlistPopFront(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i+1]; } ps->size--; }
8.尾删数据
只需让有效数字-1即可，数据虽然还在数组里，但是我们以及访问不到了！
void SeqlistPopBack(SL* ps) { assert(ps); ps->size--; }
9.查找数据、
1查找元素是否在顺序表内,如果元素在数组中的下标.
2.如果不在,返回-1 （-1为无效坐标）
3.返回类型为int 若返回类型写成我们之前typedef的类型要注意typedef的类型是什么！
int SeqlistFind(SL* ps, SeqlistType x) { assert(ps); //遍历查找 for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) return i; } return -1; //-1为无效坐标 }
10.某一位置插入数据
函数接口实现内容：给一个下标，在该下标前位置插入数据.
1.要保证位置在数组有效范围内（ps->size-1范围内）
2.把要插入位置的数据及后面的数据向后移动，注意要从最后的数据开始移动（i=ps->size-1），否则会造成前面的数据覆盖后面的数据。
3.最后把数据插入该位置，size++
//插入 void SeqlistInsert (SL* ps, SeqlistType pos, SeqlistType x) { assert(ps); //要保证在有效区域内插入 assert(pos < ps->size); //把pos位置及其后面的数据后移 // 要从最后面开始移动 //要保证容量 SeqlistCheckCapacity(ps); for (int i = ps->size-1; i >=pos;i--) { ps->arr[i+1] = ps->arr[i]; } ps->arr[pos] = x; ps->size++; }
11.删除某一位置
函数接口实现内容：给一个下标，删除该位置。
1.要保证要删除的位置的数组在数据范围内（（ps->size-1范围内））
2.把该位置后面的数据向前移动，把要删除位置的数据覆盖即可。
3.删除掉元素->size--
//删除 void SeqlistErase(SL* ps, SeqlistType pos) { assert(ps); assert(pos<ps->size); //把pos后面的东西前移动 for (int i = pos + 1; i < ps->size; i++) { ps->arr[i-1] = ps->arr[i]; } ps->size--; }
12.修改某一位置数据
函数接口实现内容：给一个下标，修改该下标对应的值
要保证该下标在数组的数据范围内(ps->size-1范围)
//更改数据 void SeqlistModify(SL* ps, SeqlistType pos, SeqlistType x) { //要保证在有效数据范围内更改 assert(pos < ps->size); ps->arr[pos] = x; }
13.顺序表的元素个数
size标识的就是顺序表的有效数字个数
/
14.销毁顺序表
释放掉动态开辟的数组即可，free和指针置空要同时使用！不然就可能造成野指针！
精华总结：
1. 有些童鞋理解不了size和数组下标的关系！下面请看图
size是有效数字的个数，即数组有多少个元素。数组的下标是从0开始的，所以ps->arr[ps->size]是数组最后一个元素后面的位置。数组最后一个元素下标为ps->arr[ps->size-1]
其他注意事项：
！搞清楚传值还是传址问题！
传值：形参是实参的一份临时拷贝，对形参的改变并不会改变实参
1.插入数据时要检查容量！
2.在某个下标，修改/删/插入数据，要保证该下标在数组下标的范围内(ps->size-1)
3.插入/删除数据后，size也要记得++ /-- ！
4.头插头删以及在某个下标位置前插入，要搞清楚从哪边元素开始移动！
当我们将全部接口实现时，我们就可以设计成一个游戏菜单了！
效果展示：
具体游戏代码以及本文章中的所有代码都在附录！
如果感觉本篇文章对你有所帮助，请给笔者一个小小的点赞，评论和关注吧！你们的支持就是我的动力！
