【初阶数据结构】连续空间的秩序之舞: 顺序表

深入浅出顺序表 点击展开/收起 文章目录文章目录深入浅出顺序表*1.1 顺序表的定义**1.2 顺序表的初始化与销毁**1.3 顺序表核心讲解之增删改查**二.顺序表的特点**三.经典例题实践顺序表*1.删除顺序表中与val值相同的数并返回删除后的数组长度2.链接连个有序数组,并使合并后的两个数组有序3.旋转数组,输入一个K值然数组旋转希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力## 一.什么是顺序表?顺序表简单来说,顺序表就是数组,不过区别是他可以尽心增容,实现比数组更为精致的使用,可以实现自由增容,和柔性数组功能上有异曲同工之妙,当然他也有他的局限性,请听我为你娓娓道来.1.1 顺序表的定义typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;intcapacity;}SL;SLDataType,作用就是我们可以在这里把类型不写死,后续想改类型直接改typedef中间的就行不用一个一个改很方便.1.2 顺序表的初始化与销毁在这里我们首先对顺序表进行初始化和销毁讲解1.21 顺序表的初始化初始化我们要将指针置为空,要将空间大小和数组大小也一并改到0,为增删改查做好准备工作voidSLInit(SL*ps){ps-arrNULL;ps-capacityps-size0;}1.22 顺序表的销毁使用完顺序表我们需要释放所开辟的空间,防止内存泄漏,养成编程好习惯voidSLDestory(SL*ps){if(ps-arr){free(ps-arr);}ps-arrNULL;}1.3 顺序表核心讲解之增删改查1.31 顺序表的增加数据当然我们想要实现插入过程必然要先检查一下空间够不够,这就引出了检查空间操作空间大小检查与增容操作voidSLCheckCapacity(SL*ps){if(ps-capacityps-size){intnewcapacityps-capacity0?4:(ps-capacity)*2;//注意我们这里使用realloc是为了满足在空间不够的时候进行原有基础扩容SL*tmprealloc(ps-arr,sizeof(SLDataType)*newcapacity);if(tmpNULL){//扩容检查perror(realloc fail !);exit(1);}ps-arrtmp;ps-capacitynewcapacity;}}1.311 顺序表的头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);//要进行指针检查因为我们在下面操作中会用到ps解引用所以ps不可以为空指针SLCheckCapacity(ps);for(intips-size;i0;i--){//在头插时我们的思路是把每个元素整体往后移一位把头位置空出来给要插入的元素//当然我们要不数据整体往后挪要从后挪,从前面挪会覆盖数据ps-arr[i]ps-arr[i-1];}ps-arr[0]x;ps-size;}1.312顺序表的尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);//要进行指针检查因为我们在下面操作中会用到ps解引用所以ps不可以为空指针SLCheckCapacity(ps);ps-arr[ps-size]x;}1.313顺序表的任意pos位置插入在这里我们先实现了顺序表的头插尾插,这事就有人想了我么就可以在顺序表的任意位置插入吗,有的兄弟有的voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(posps-size);//你可以在任意位置插入你不能够超出顺序表大小//不可以在一个没有的位置插入数据所以要断言一下for(intips-size;ipos;i--){//这里来的逻辑与头插类似pos点以后的位置整体往后挪ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}1.32顺序表删除数据删除数据要注意首先顺序表要有数据所以开始之前要断言一下1.321 顺序表的头删voidSLPopFront(SL*ps){assert(ps);assert(ps-size0);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}1.322顺序表的尾删voidSLPopBack(SL*ps){assert(ps);assert(ps-size);ps-size--;}1.323顺序表的任意pos位置删除voidSLErase(SL*ps,intpos){assert(ps);assert(ps-size);assert(posps-size);//与插入一样删除的点要存在for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}1.34修改数据voidSLModify(SL*ps,SLDataType x,intpos){assert(ps);assert(posps-size);ps-a[pos]x;}1.34查找数据查找数据很简单思路是我们定义一个flag找到找到就加一没找到就是0然后用if–else进行判断voidSLFind(SL*ps,SLDataType x){assert(ps);intflag0;for(inti0;ips-size;i){if(ps-arr[i]x){printf(找到了下标为%d\n,i);flag;}}if(flag0){printf(该组数据中没有要查找的数据);}}二.顺序表的特点优点可根据自己插入的数据多少,自动增容,访问起来很方便,可直接根据下表访问,在存储内存上地址是连续的,当Cpu要访问数据时,可以将一整块数据拉去到缓存中备用,提升访问速度缺点realloc扩容影响存在一定的空间浪费,pos点插入删除时O(N)的时间复杂度效率低下三.经典例题实践顺序表1.删除顺序表中与val值相同的数并返回删除后的数组长度每次遇到val src就跳过dst就会覆盖掉val值从而实现删除val值intdel(int*p,intval,intarrsize){intsrc0;intdst0;while(srcarrsize){if(p[src]val){src;}else{p[dst]p[src];}}returndst;}intmain(){intarr[]{1,2,2,3,3,31,2,12};intval0;printf(请输入val);scanf(%d,val);intretdel(arr,val,8);printf(数组长度为%d\n,ret);for(inti0;iret;i){printf(arr[%d]%d ,i,arr[i]);}}2.链接连个有序数组,并使合并后的两个数组有序定义三个指针,因为是有序链表,所以我们从后往前插入合并,从前往后会被覆盖连个链表末尾比大小,大的往后放,当l2中有剩余,l10时,我们直接把l2插入数组1即可反之l20,l1还有剩余,则数组已合并好了voidmerge(int*p1,int*p2,intl1,intl2,intl3){while(l10||l20){if(p1[l1]p2[l2]){p1[l3--]p2[l2--];}else{p1[l3--]p1[l1--];}}if(l10){while(l3){p1[l3--]p2[l2--];}}}intmain(){intarr1[]{1,2,3,4,0,0};intarr2[]{1,2};merge(arr1,arr2,3,1,5);for(inti0;i6;i){printf(arr[%d]%d ,i,arr1[i]);}}3.旋转数组,输入一个K值然数组旋转思路先旋转前k个数,再旋转后n-1-k个数再整体旋转这里我们k做了处理取余运算,因为旋转周期为n,在这里旋转k个数kn时我们可以等价于旋转k%n次做一个简化voidreverse(int*p,intleft,intright){inttmp0;while(leftright){tmpp[left];p[left]p[right];p[right]tmp;}}intmain(){intk0;printf(输入一个k值使数组旋转k位);scanf(%d,k);kk%6;intarr[]{1,2,3,5,4,43};reverse(arr,0,5-k);reverse(arr,6-k,5);reverse(arr,0,5);for(inti0;i6;i){printf(arr[%d]%d ,i,arr[i]);}}希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力