笔者主页ristarry 数据结构专栏数据结构 本篇代码:顺序表专题✨ 纸上谈来终觉浅觉知此事要躬行计算机的学习好似登山你敲下的每一段代码掌握的每一个算法完成的每一次复习都将化作登山路上坚实的脚印。最初你不知道前方等待着你的是什么但是如果你坚持向上攀登你看到的东西将越来越清晰终将一览众山小。希望我能与各位一同在顶峰见证黎明破晓的时刻。文章目录1. 线性表2. 顺序表2.1 顺序表的物理结构:2.2 顺序表的分类2.2.3 静态顺序表2.2.3 动态顺序表3. 动态顺序表的实现3.1 初始化3.2 销毁3.1 检查容量3.2 插入方式3.2.1 尾插3.2.2 头插3.2.3 指定位置之前插入3.3 删除数据3.3.1 尾删3.3.2 头删3.3.3 指定位置删除3.4 查找数据1. 线性表线性表是一种十分基础的数据结构它是n个具有相同特性的元素的有限序列。线性表主要分为顺序表、链表、栈、队列、字符串…既然它叫做线性表那么顾名思义表上的数据都应该是线性排列的而这种线性的表现就是一一对应的前后顺序关系我们就拿数组来举例下标为0的元素后面一定对应了下标为1的元素这就是一种对应关系。线性表在逻辑结构上一定是连续的也就是一定会有明确的前后关系但是在物理结构上不一定是连续的关于这一点我们会在后面进行讲解。2. 顺序表概念顺序表的底层是数组但是在数组的基础之上加入了增删查改等接口。数组和顺序表的关系就像是路边苍蝇小馆中的酸辣土豆丝来到米其林后将工艺变得复杂摇身一变成了法式酸香丝绒土豆脆条附加的东西变多了但是本质并没有改变。2.1 顺序表的物理结构:这就是我所说的物理结构和逻辑结构都是连续的逻辑结构连续是因为在数组中有这种前后对应的关系下标为0的元素后面就一定对应着下标为1的元素。而物理结构连续指的是数组中每个元素的地址全都相邻在如图的整型数组中每个元素的地址正好对应了一个整型的大小。在之后我们会讲到的链表中每个元素的地址是混乱分布的因此无法构成物理结构上的连续但是每一个元素又通过指针指向了下一个元素形成了一一对应的关系因此能够形成逻辑结构。2.2 顺序表的分类顺序表分为静态顺序表和动态顺序表。我们依次来进行讲解。2.2.3 静态顺序表语法形式如下typedefintSLDataType;#defineN7typedefstructSeqList{SLDataType a[N];//定长数组intsize;//有效数据个数}SL;在静态顺序表中最为显著的特征就是这个定长数组了它的元素个数是通过定义常数来确定的这正是“静态“的体现。但是我们来设想一下这样一种情况你独自开发了一款软件你使用了静态顺序表去存放用户数据最开始用户人少你将N定义为1000,然后你的软件突然火了用户人数越来越多你每次都要手动去把你的N定义为更大的值你还不能一次性给N定义太大比如直接赋值十个亿你用户没有那么多空间又浪费了。因此我们会发现静态顺序表的局限性太大了太小不够太大浪费考虑到这些因素动态顺序表也就诞生了本篇我们主要讲解的就是动态顺序表。2.2.3 动态顺序表语法形式如下typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;//有效空间个数intcapacity;//总容量大小}SL;在说明动态顺序表为什么“动态”之前让我先介绍一下这个代码中的各个部分。先看到typedef int SLDataType;这句话的意思是将int类型重命名为SLDataType我们都知道顺序表不可能全部存放同一种类型的数据可能你今天想放整型数据明天就像放字符型数据了到时候要修改时只需要将int换成char就行了。SLDataType* arr数组顺序表的主体大家都了解。int size;有效空间个数就是你的顺序表中已经存放了多少个数据了。int capacity;总容量大小等价于顺序表中数组所能够容纳的最大元素个数capacity减去size就是顺序表中还能容纳的元素个数。SL给结构体类型重新取的名字。3. 动态顺序表的实现3.1 初始化不论是我们现在学习数据结构还是以后学习c中的类和对象初始化和销毁都是必不可少的一个流程。初始化的意义如下消除随机垃圾值使变量处于合法状态。防止未定义的行为。让对象建立完整可用的状态。//初始化voidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}3.2 销毁这一步非常关键!!!因为现阶段特别容易忘记。销毁的意义使对象的生命周期结束将它占用的内存资源归还给系统//销毁voidSLDestroy(SL*ps){if(ps-arr)free(ps-arr);ps-arrNULL;ps-sizeps-capacity0;}3.1 检查容量代码voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){//若容量为0,给一个初始值为4,否则乘2intNewCapacityps-capacity0?4:2*ps-capacity;SLDataType*tmp(SLDataType*)realloc(ps-arr,NewCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacityNewCapacity;}}这就是我之前提到的动态顺序表“动态“的来源还记得吗静态顺序表的数组元素个数是宏定义的常数而动态顺序的元素个数是使用动态内存开辟的函数创建的通过realloc能够在空间不够时自动开辟适量空间。不了解realloc的可以点击这里跳转到我的另一篇文章现在来讲解一下这个函数1.先判断空间是否满了size是否等于capacity注意容量为0时也成立,size capacity 02. 一上来先去检查顺序表中是否有空间如果没有空间就给上空间的初始值为4,如果有空间就乘2,扩大一倍。3.2 插入方式3.2.1 尾插顺序表里面一定要存放有数据那么在我们的动态顺序表中一共有三种数据的存入方式尾插、头插、指定位置插入。先说尾插顾名思义我们如果将顺序表当作一个数组那么它就会有首元素和尾元素将新来的元素插入到尾元素的后面这就叫做尾插。尾插实现方式如下//尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps-arr[ps-size]x;}本质就是直接对底层数组进行操作。3.2.2 头插与尾插类似但这次是将新来的元素插入到首元素的前面。//头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;ps-size;}通过一个简单的数组遍历让所有的数组元素后移一位将下标为0的位置空出来再将新元素放入下标为0的位置头插就完成了。3.2.3 指定位置之前插入相较于尾插和头插指定位置之前插入明显在功能上更加灵活。//指定位置之前插入voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);//检查容量够不够SLCheckCapacity(ps);for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}可以看到指定位置之前插入和头插及其类似或者我们可以这么去看头插就是指定位置为0的插入方式。我们只需要将指定位置pos后面的数据都后移一位然后将新的数据插入空出来的pos的位置就行了。3.3 删除数据在讲完了插入数据了以后肯定还要讲讲删除数据与插入方式对应删除方式也分为三种尾删、头删、指定位置删除。数据的删除方式与插入方式几乎一模一样只是操作顺序略有差异不过多讲解了绝对不是因为我懒哈。3.3.1 尾删//尾删voidSLPopBack(SL*ps){assert(ps);assert(ps-size);ps-size--;}3.3.2 头删//头删voidSLPopFront(SL*ps){assert(ps);assert(ps-size);for(inti1;ips-size;i){ps-arr[i-1]ps-arr[i];}ps-size--;}3.3.3 指定位置删除//指定位置删除voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}3.4 查找数据//查找 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-arr[i] x) { return i; } } return -1; }和大部分的数组查找方式相同先遍历整个数组当发现要查找的数据时直接返回。