1.顺序表

带入主题

• Q假设要实现一个贪吃蛇本体（不考虑渲染和食物产生），我该如何思考呢

• A贪吃蛇是可改变方向的线性数据不断增删产出的结果

那么我们便带入我们要学习的线性表

1线性表及其实现方式

你别蒙，我们讲顺序表怎么又冒出来个线性表，别管我们的大学计算机学的，线性表就是虚头八脑的定义，真正的实现就是顺序表和链表

1.1线性表

贪吃蛇都知道撒，有头有尾的，我们在电脑存储中如果按照顺序1 2 3 4 依次存储配上线性表就是顺序表，如果是按照链式（后续讲）排列配上线性表就是链表。

1.2顺序表和链表

简单来说顺序表就是小朋友排队，而链表就是在我的世界藏宝图加上宝箱中还有藏宝图，当找到一个数据后紧跟而来的就是下一个数据的地址。

• 话不多说开始实操

2顺序表（动态和静态）

2.1静态顺序表

structSequenceList{intarr[10];intsize;};

静态顺序表就是用固定大小的静态数组来储存数据。长这样，你细想一下，他场景真的很局限，只适合你知道数组大小，此时有人就要说了，老师老师我知道柔性数组，：（ ，那就是我们要讲的动态顺序表的范畴了。

2.2动态顺序表

• 简单过一下 动态顺序表就是用一个堆上动态申请的数组来存储数据，如果空间不够可做扩容处理。

typedefintSqDateType;typedefstructSequenceList{SqDateType*arr;intsize;intcapacity;}SqList;

• 上面先取一个昵称方便后续使用（打个比方你有天不想用int了你就想存char 你还能把所有int 改成car吗？）

• size表示目前数据存储了多少，是水

• 而capacity 就是瓶子 容量在那里 ，水快满的时候就要加大“容量”，有时候可以原地在杯子上面加个容器，但有时候被子上空间受限，只能另外找一个的杯子且上方空间不受限，把水灌到新杯子。

• 而这个指针数组就是说的杯子的地址。

• 而全程 你要记住，capacity与你申请的额外容器加上杯子本身永远同步，别觉得是废话

typedefintSqDataType;// 柔性数组版本（注意：没有 arr 指针）typedefstructSequenceList{intsize;// 当前元素个数intcapacity;// 当前容量SqDataType arr[];// 柔性数组，不占结构体大小}SqLis;

• 柔性数组也类似，简单看看

3代码实现（贪吃蛇方式）

3.1从哪开始呢

• 首先要有文件分装的思想，函数实现是一个文件，头文件肯定要有，在是主函数所在地，所以分为三个文件，最好要有意识让别人看到这个文件就知道是什么东西。

主函数

#include"SqList.h"intmain(){SqList s1;}

头文件

#pragmaonce#include<stdio.h>typedefintSqDataType;typedefstruct{SqDataType*arr;intsize;intcapacity;}SqList;

函数实现还没到

3.2 初始化

不管三七二十一先assert断言 防小人！！

• malloc申请arr的地址 默认就申请四个刚刚取的昵称的大小
• -把什么和什么同步来着，你知道的，杯子对吧
• size制空

voidSqListInit(SqList*p){assert(p);p->arr=(SqDataType*)malloc(sizeof(SqDataType)*4);if(p->arr==NULL){printf("申请失败");return;}p->capacity=4;p->size=0;}

3.3 销毁

同样 assert ！！

• 由于是malloc动态开辟的内存所以需要手动free释放
• 其他制空就行

voidSqListDestroy(SqList*p){assert(p);free(p->arr);p->arr=NULL;p->capacity=0;p->size=0;}

3.4 插入

首先干什么！！防小人！

他的声明是void SqListInsert(SqList* p, int i, SqDataType x);

别急，你看声明就知道，这个i啊万一小人会输一个特别大的值，我们没有怎么办，也就是没有折磨大的capacity，所以！！ assert(i <= p->capacity);

1. 顺着想哈，你要插入首先要空出位子，除了在尾部插入对吧，那就分类来看。

3.4.1 前面插入

用空位子，要从后往前，把最后一个往右后才能动最后一个减一的位子，否则会覆盖.

注意为什么size减一再赋值给j，因为size表示有几个数从一开始，而arr是从0开始的

3.4.2 尾插

尾部插入，不用移动位置，直接放在size上，因此我们知道了，其实两个可以合并。

voidSqListInsert(SqList*p,inti,SqDataType x){assert(p);assert(i>=0&&i<=p->size);intj=p->size-1;while(j>=i){p->arr[j+1]=p->arr[j];j--;}p->arr[i]=x;p->size++;}

聪明的你一定想到了，我们不是举了杯子的例子吗，扩容！！

• 我们么此扩容扩成原来的1.5~2倍，他在未来会扩充的越来越慢，并且能尽量节省空间。我们再扩展一下就得到了。

扩容次数越来越少，分摊到每次插入上的平均成本（均摊时间复杂度）接近 O(1)

voidSqListInsert(SqList*p,invoidSqListInsert(SqList*p,inti,SqDataType x){assert(p);assert(i>=0&&i<=p->size);if(p->size==p->capacity){intnewcapacity=p->capacity*2;//为什么作者要在这里多此一举，如果capacity没有初始化呢，为0，那么不久完蛋了SqDataType*tmp=(SqDataType*)realloc(p->arr,sizeof(SqDataType)*(size_t)newcapacity);if(tmp==NULL){printf("realloc失败 \n");return;}p->arr=tmp;tmp=NULL;p->capacity*=2;}intj=p->size-1;while(j>=i){p->arr[j+1]=p->arr[j];j--;}p->arr[i]=x;p->size++;}

3.5 删除

原型是这个 SqDataType SqListDelete(SqList* ps, int i)

老规矩了，assert一定要断言

• 然后就是删除主体了，删除后，你要让后续数据依次往前一位，插入和删除的时间复杂度为 O(n)，需要移动大量数据，这是顺序表的主要短板，看看代码记得复刻哈。

SqDataTypeSqListDelete(SqList*p,inti){assert(p);assert(i>=0&&i<p->size);//保存数据留作返回值SqDataType dele=p->arr[i];for(intj=i;j<p->size-1;j++){p->arr[j]=p->arr[j+1];}--p->size;returndele;}

• 注意为什么是 循环条件为 < size - 1 ，永远要有边界思想，假设size == 5有效值为 0 - 4 那么读取到5 就有问题。

3.6 查找

不要怕，顺序表太好查找了，暴力拆出来不就行了，一个是按位查找，一个是按值查找。

3.6.1 按位查找

SqDataTypeGetElem(SqList*ps,inti){assert(ps);assert(i>=0&&i<ps->size);returnps->arr[i];}

3.6.2 按值查找

intLocateElem(SqList*ps,SqDataType x){assert(ps);for(inti=0;i<ps->size;++i){if(ps->arr[i]==x)returni;}return-1;}

尾

• 因此我们的增删改查大多已经实现清楚了，我们从最开始贪吃蛇的引入（当然后续会出），到线性表底下两个分支，我们都大概交代了，顺序表基本实现和作者本人有些困惑的点也当作知识点分享了，下一期，我们讲重头戏——链表，做好准备了吗？