1.顺序表

数据结构-基础篇-顺序表带入主题1线性表及其实现方式1.1线性表1.2顺序表和链表2顺序表动态和静态2.1静态顺序表2.2动态顺序表3代码实现贪吃蛇方式3.1从哪开始呢3.2 初始化3.3 销毁3.4 插入3.4.1 前面插入3.4.2 尾插3.5 删除3.6 查找3.6.1 按位查找3.6.2 按值查找尾带入主题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从哪开始呢首先要有文件分装的思想函数实现是一个文件头文件肯定要有在是主函数所在地所以分为三个文件最好要有意识让别人看到这个文件就知道是什么东西。主函数#includeSqList.hintmain(){SqList s1;}头文件#pragmaonce#includestdio.htypedefintSqDataType;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-arrNULL){printf(申请失败);return;}p-capacity4;p-size0;}3.3 销毁同样 assert 由于是malloc动态开辟的内存所以需要手动free释放其他制空就行voidSqListDestroy(SqList*p){assert(p);free(p-arr);p-arrNULL;p-capacity0;p-size0;}3.4 插入首先干什么防小人他的声明是void SqListInsert(SqList* p, int i, SqDataType x);别急你看声明就知道这个i啊万一小人会输一个特别大的值我们没有怎么办也就是没有折磨大的capacity所以 assert(i p-capacity);顺着想哈你要插入首先要空出位子除了在尾部插入对吧那就分类来看。3.4.1 前面插入用空位子要从后往前把最后一个往右后才能动最后一个减一的位子否则会覆盖.注意为什么size减一再赋值给j因为size表示有几个数从一开始而arr是从0开始的3.4.2 尾插尾部插入不用移动位置直接放在size上因此我们知道了其实两个可以合并。voidSqListInsert(SqList*p,inti,SqDataType x){assert(p);assert(i0ip-size);intjp-size-1;while(ji){p-arr[j1]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(i0ip-size);if(p-sizep-capacity){intnewcapacityp-capacity*2;//为什么作者要在这里多此一举如果capacity没有初始化呢为0那么不久完蛋了SqDataType*tmp(SqDataType*)realloc(p-arr,sizeof(SqDataType)*(size_t)newcapacity);if(tmpNULL){printf(realloc失败 \n);return;}p-arrtmp;tmpNULL;p-capacity*2;}intjp-size-1;while(ji){p-arr[j1]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(i0ip-size);//保存数据留作返回值SqDataType delep-arr[i];for(intji;jp-size-1;j){p-arr[j]p-arr[j1];}--p-size;returndele;}注意为什么是 循环条件为 size - 1 永远要有边界思想假设size 5有效值为 0 - 4 那么读取到5 就有问题。3.6 查找不要怕顺序表太好查找了暴力拆出来不就行了一个是按位查找一个是按值查找。3.6.1 按位查找SqDataTypeGetElem(SqList*ps,inti){assert(ps);assert(i0ips-size);returnps-arr[i];}3.6.2 按值查找intLocateElem(SqList*ps,SqDataType x){assert(ps);for(inti0;ips-size;i){if(ps-arr[i]x)returni;}return-1;}尾因此我们的增删改查大多已经实现清楚了我们从最开始贪吃蛇的引入当然后续会出到线性表底下两个分支我们都大概交代了顺序表基本实现和作者本人有些困惑的点也当作知识点分享了下一期我们讲重头戏——链表做好准备了吗