第31篇 数据结构入门：顺序表

数据结构入门顺序表与链表的深度解析在编程的世界里如何高效地存储和管理数据是核心问题。线性表Linear List作为最基础、最常用的数据结构是我们必须掌握的第一课。线性表在逻辑上是一条连续的直线但在物理存储上却分为两大流派顺序表和链表。今天我们就来深入剖析顺序表。文章目录1. 静态顺序表 vs 动态顺序表第一部分顺序表代码实现1. 项目文件划分2. 类型重定义与结构体优化3. 初始化与扩容机制4. 增删改查接口实现第二部分LeetCode 经典例题实战1. 移除元素 (LeetCode 27)2. 删除有序数组中的重复项 (LeetCode 26)3. 合并两个有序数组 (LeetCode 88)3. 顺序表的痛点与展望什么是顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。简单来说它的底层就是数组。你可以把它想象成一家米其林餐厅数组就像是原材料比如炒西蓝花。顺序表则是对数组进行了封装增加了“摆盘”和“服务”即增删改查接口变成了一道精致的菜比如绿野仙踪。1. 静态顺序表 vs 动态顺序表静态顺序表使用定长数组存储。缺陷在于空间给少了不够用给多了造成浪费不够灵活。动态顺序表按需申请空间。这是我们在实际开发中更常用的形式。它包含三个核心要素a指向数据的指针。size当前有效数据的个数。capacity当前空间的总容量。// 动态顺序表结构体定义typedefstructSeqList{SLDataType*a;// 指向动态开辟的数组intsize;// 有效数据个数intcapacity;// 空间容量}SL;正如前文所述顺序表是对数组进行了封装增加了增删改查的接口。接下来我们就来一步步实现这些功能。第一部分顺序表代码实现1. 项目文件划分为了方便管理和维护我们将代码分为三个文件SL.h公共接口声明函数、定义结构体。SL.c具体实现#include SL.h编写函数体。test.c测试逻辑#include SL.h调用函数进行验证。2. 类型重定义与结构体优化为了避免后续修改数据类型时产生大量冗余工作我们使用typedef对数据类型和结构体进行重命名。// 将元素类型重命名方便后续统一修改typedefintSLDataType;// 动态顺序表结构体定义typedefstructSeqList{SLDataType*a;// 指向动态开辟的数组intsize;// 有效数据个数intcapacity;// 空间容量}SL;3. 初始化与扩容机制由于后续操作需要修改结构体内部的数据因此传参一律采用传址调用指针。同时为了防范野指针我们引入assert.h进行断言检查。初始化函数voidSLinit(SL*ps){assert(ps);ps-aNULL;ps-size0;ps-capacity0;}扩容函数每次进行插入操作前都需要检查空间是否充足。扩容策略为若初始容量为0则默认开辟4个空间否则扩大为原来的2倍。同时必须妥善处理realloc可能返回NULL的隐患防止原数据丢失。voidSLdilat(SL*p){assert(p);intnewcapacity(p-capacity0?4:p-capacity*2);// 使用临时指针接收 realloc 的返回值防止扩容失败导致原指针丢失SLDataType*tmp(SLDataType*)realloc(p-a,newcapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail : );return;}p-atmp;p-capacitynewcapacity;}4. 增删改查接口实现尾部增加元素voidSLtailadd(SL*p,SLDataType x){assert(p);if(p-sizep-capacity){SLdilat(p);}p-a[p-size]x;// 后置使得代码更加简洁美观}尾部删除元素删除操作只需将有效数据个数size减 1 即可无需真正清除内存中的数据。voidSLtaildel(SL*p){assert(p);if(p-size0)return;p-size--;}头部增加元素需要将原有数据整体向后挪动一位再在首位置赋值。voidSLheadadd(SL*p,SLDataType x){assert(p);if(p-sizep-capacity){SLdilat(p);}for(intip-size;i0;i--){p-a[i]p-a[i-1];}p-a[0]x;p-size;}头部删除元素将第二个元素开始的数据依次向前覆盖最后更新size。voidSLheaddel(SL*p){assert(p);if(p-size0)return;for(inti0;ip-size-1;i){p-a[i]p-a[i1];}p-size--;}查找指定数据遍历数组寻找目标数据找到返回其索引找不到返回 -1。intSLfind(SL*p,SLDataType x){assert(p);for(inti0;ip-size;i){if(p-a[i]x)returni;}return-1;}在指定位置前插入数据结合查找函数先定位索引再将目标位置及之后的数据整体后移。voidSLfixadd(SL*p,SLDataType x,intpos){assert(p);if(p-sizep-capacity){SLdilat(p);}for(intip-size;ipos;i--){p-a[i]p-a[i-1];}p-a[pos]x;p-size;}打印函数用于测试voidSLprint(SL*p){assert(p);for(inti0;ip-size;i){printf(%d\t,p-a[i]);}printf(\nsize: %d\tcapacity: %d\n,p-size,p-capacity);}测试代码示例#includeSL.hintmain(){SL s;SLinit(s);SLtailadd(s,8);SLprint(s);SLheadadd(s,6);SLprint(s);printf(请输入你指定的数字);SLDataType i;scanf(%d,i);intposSLfind(s,i);if(pos-1){printf(你提供的数值不在该顺序表里面\n);}else{printf(请输入你想要插入的数字);SLDataType j;scanf(%d,j);SLfixadd(s,j,pos);SLprint(s);}return0;}第二部分LeetCode 经典例题实战掌握了顺序表的基础操作后我们通过三道经典题目来巩固“双指针法”这一核心思想。1. 移除元素 (LeetCode 27)思路使用快慢双指针。sou指针负责遍历数组当遇到不等于val的值时将其赋值给des指针指向的位置然后des后移。最终des与起始位置的差值即为新数组的长度。intremoveElement(int*nums,intnumsSize,intval){int*sounums;int*desnums;for(inti0;inumsSize;i){if(*sou!val){*des*sou;des;}sou;}returndes-nums;}2. 删除有序数组中的重复项 (LeetCode 26)思路同样使用双指针。des初始在首位sou从第二位开始遍历。当sou指向的值与des不同时des先自增再接收sou的值。注意由于是先自增再赋值最终返回的长度需要des - nums 1或者在循环外处理。intremoveDuplicates(int*nums,intnumsSize){if(numsSize0)return0;int*desnums;int*sounums1;for(inti1;inumsSize;i){if(*sou!*des){des;*des*sou;}sou;}returndes-nums1;}3. 合并两个有序数组 (LeetCode 88)思路为了避免从头开始比较带来的数据搬移开销我们采用“逆向双指针”法。从两个数组的有效尾部开始比较将较大的元素放到nums1的最终尾部依次向前填充。voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){intendnums1Size-1;while(m0n0){if(nums1[m-1]nums2[n-1]){nums1[end--]nums1[m-1];m--;}else{nums1[end--]nums2[n-1];n--;}}// 如果 nums2 还有剩余直接拷贝到 nums1 前面while(n0){nums1[end--]nums2[n-1];n--;}}3. 顺序表的痛点与展望虽然顺序表支持随机访问下标访问时间复杂度O ( 1 ) O(1)O(1)但它也有明显的短板头部/中间插入删除效率低需要搬移大量数据时间复杂度为O ( N ) O(N)O(N)。扩容成本高当空间不足时需要申请新空间、拷贝数据、释放旧空间。空间浪费扩容通常呈2倍增长如果插入少量数据后不再操作剩余空间会被白白浪费。那么有没有办法解决这些痛点呢有的这就需要用到链表了。不过那就是我们下一篇博客要探讨的内容了敬请期待