一、静态顺序表和动态顺序表静态表静态顺序表就是⽤固定⼤⼩的静态数组来存储数据。// typedef是为了⽅便类型替换typedefintSqDataType;// 顺序表的最⼤存储的数据个数#defineSq_MAX_SIZE10//最⼤容量10// 静态顺序表结构定义typedefstructSequenceList{SqDataType arr[Sq_MAX_SIZE];// 存储数据的静态数组intsize;// 记录顺序表中已经存⼊的数据个数}SqList;// C语⾔中上述结构体类型为struct SequenceList太⻓了所以⼀般都会tyepdef定⼀个短的别名如SqList// 上述代码把结构体定义和typedef嵌套在⼀起也可以单独定义typedef struct SequenceList SqList;// 有些地⽅简化⼀下也可以直接定义匿名结构体再typedef⼀个名称如下typedefstruct{SqDataType arr[Sq_MAX_SIZE];// 存储数据的静态数组intsize;// 记录顺序表中已经存⼊的数据个数}SqList;动态表动态顺序表就是⽤⼀个堆上动态申请的数组来存储数据如果空间不够了可以做扩容处理。typedefintLDataType;typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放数据节点}LNode,*LinkList;//typedef struct ListNode LNode;//typedef struct ListNode* LinkList;//LinkList等价于LNode*//C语言中上述结构体中嵌套的typedef等价于这里的两个typedef//给struct ListNode起别名LNode//给struct ListNode*起别名LinkList//用LinkList时强调它是「整条链表的头指针」代表链表的入口//用LNode*时强调它是「指向单个节点的指针」比如遍历用的临时指针二、动态顺序表实现接⼝函数定义List.h#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintLDataType;typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放数据节点}LNode,*LinkList;//typedef struct ListNode LNode;//typedef struct ListNode* LinkList;//LinkList等价于LNode*//C语言中上述结构体中嵌套的typedef等价于这里的两个typedef//给struct ListNode起别名LNode//给struct ListNode*起别名LinkList//用LinkList时强调它是「整条链表的头指针」代表链表的入口//用LNode*时强调它是「指向单个节点的指针」比如遍历用的临时指针//初始化LNode*ListInit();//等价于LinkList ListInit();//创建一个新结点LNode*BuyListNode(intdata);//打印链表voidListPrint(LNode*L);//获取个数intListSize(LNode*L);//获取链表中第一个数据等价于x节点的地址若不存在就返回NULL指针LNode*ListLocateElem(LNode*L,LDataType x);//返回链表中下标为i的节点LNode*ListGetElem(LNode*L,inti);//在链表的第i个下标位置插入xvoidListInsert(LNode*L,inti,LDataType x);//删除链表中下表为i的节点并用x带出节点的值LDataTypeListDelete(LNode*L,inti);//检测链表是否为空空返回真否则返回假boolListEmpty(LNode*L);//头插voidListPushFront(LNode*L,LDataType x);//尾插voidListPushBack(LNode*L,LDataType x);//头删LDataTypeListPopFront(LNode*L);//尾删LDataTypeListPopBack(LNode*L);//销毁链表voidListDestroy(LNode*L);2.1 初始化顺序表的结构体变量创建好后系统会以随机值对其进⾏填充所以在使⽤前须先进⾏初始化步骤如下a.使⽤malloc申请⼀个默认⼤⼩动态数组空间⽐如默认⼤⼩为4这个空间⼀般不要太⼤因为太⼤了⽤不了就浪费了反正如果不够后续可以扩容。 b.申请成功后将有效元素个数初始化为0因为初始化阶段顺序表中还未存放任何有效元素 c. 将capacity设置为所申请空间的实际⼤⼩//开辟空间LNode*BuyListNode(intdata){//不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了//所以这里使用malloc从堆上动态申请节点LNode*NewNode(LNode*)malloc(sizeof(LNode));if(NewNodeNULL){printf(BuyListNode失败\n);exit(-1);}//申请成功后对节点中的数据域或指针域进行初始化NewNode-datadata;NewNode-nextNULL;returnNewNode;}//初始化链表LNode*ListInit(){LNode*listBuyListNode(-1);returnlist;}总结动态内存分配的必要性使用malloc动态申请节点内存是为了避免局部变量在函数退出后被自动销毁。在函数内部直接创建LNode结构体变量会导致该变量存储在栈上函数结束后其内存被回收返回的指针将指向无效内存。动态分配的内存从堆上获取生命周期由程序员控制需手动释放。错误处理与鲁棒性调用malloc后必须检查返回的指针是否为NULL因为内存分配可能失败。若分配失败打印错误信息并调用exit(-1)终止程序防止后续操作引发未定义行为如解引用空指针。这种设计增强了代码的健壮性。节点初始化动态分配节点后需显式初始化其成员。代码中将data赋值为传入参数next指针置为NULL确保新节点处于独立状态未链接其他节点。这种初始化方式为后续链表操作如插入、遍历提供一致的行为基础。链表初始化逻辑ListInit函数创建了一个带哨兵位结点的链表其data值为-1通常无实际意义仅作占位符。哑结点简化边界条件处理如头插/头删操作无需单独处理空链表情况。返回的list指针始终指向该哨兵位结点链表实际内容从list-next开始。结构一致性两个函数均返回LNode*类型指针保持接口统一。BuyListNode作为底层工具函数封装了节点创建细节ListInit在此基础上构建链表初始化逻辑体现模块化设计思想。2.2 销毁由于顺序表中的空间是⽤malloc从堆上动态申请的使⽤完后必须释放否则会内存泄漏。具体步骤如下a.检测顺序表s的空间是否被销毁。 b.如果未销毁使⽤free将其释放掉并将arr设置NULLsize和capacity设置为0。 c.其次要注意的free本质并不是真的把空间销毁掉free的本质是把这段空间的使⽤权还给操作系统操作系统后续还可以把这段空间分配给别⼈。//销毁链表voidListDestroy(LNode*L){LNode*curL-next;while(cur){LNode*nextcur-next;free(cur);curNULL;}free(L);//L NULL;//这是临时变量写不写都可以}新创建一个临时指针cur指向指向头节点的下一个节点即第一个实际数据节点从头节点之后开始释放。保存当前节点的下一个节点地址到next避免释放后丢失链表后续信息。释放当前节点内存free(cur)。将当前节点指针置为NULL可选操作防止野指针但局部变量作用域结束后无效。释放头节点L的内存。注意此处未将L置为NULL因参数为值传递外部调用处的指针仍需手动置空。//L NULL;//这是临时变量写不写都可以说明L NULL是局部操作不影响外部指针因此可省略。关键注意事项外部指针置空调用该函数后外部需手动将链表头指针置为NULL例如ListDestroy(head);headNULL;// 必须补充节点释放顺序必须先保存next再释放当前节点否则无法访问后续节点。头节点处理区分头节点L与其他节点L-next开始确保全部释放。2.3插⼊顺序表经过初始化之后才可以进⾏元素插⼊操作。插⼊函数原型为void SqListInsert(SqList* ps, int i, SqDataType x) ,即在顺序表的第i个位置之前插⼊新元素x如果i的位置⾮法则不进⾏插⼊插⼊具体步骤如下a.参数检测。主要检测位序i是否满⾜0 i s.size 满⾜则着插⼊否则⽆法插⼊ b. 检测是否需要扩容如果顺序表中存满了则需要先扩容之后才能插⼊。 c. 插⼊元素x。将i及其之后的所有元素整体往后移动⼀个位置然后将x填充到待插⼊位置。 d. 插⼊成功后给有效元素个数加1//在链表的第i个下标位置插入xvoidListInsert(LNode*L,inti,LDataType x){assert(L);assert(i0);LNode*i_1NodeL;//相当于将i_1Node给定在头节点上intj-1;while(ji-1i_1Node){i_1Nodei_1Node-next;j;}assert(i_1Node);//方法一//LNode* newNode BuyListNode(x);//LNode* iNode i_1Node-next;////i_1Node-next newNode;//将i_1Node的地址存放在新插入的元素中//newNode-next iNode;//新插入的元素的地址指向新插入元素之前的元素的地址//方法二LNode*newNodeBuyListNode(x);newNode-nexti_1Node-next;i_1Node-nextnewNode;}//头插voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNodeBuyListNode(x);newNode-nextL-next;L-nextnewNode;}//头插voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNodeBuyListNode(x);newNode-nextL-next;L-nextnewNode;}总结链表插入操作解析ListInsert函数该函数用于在链表的第i个位置插入元素x。参数L为链表头节点指针i为目标位置索引从0开始x为插入的数据。i_1Node初始指向头节点j初始化为-1因头节点不计入索引。循环移动i_1Node到第i-1个节点通过j计数和i_1Node i_1Node-next逐步后移直到j i-1或到达链表末尾。插入新节点创建新节点newNode将其next指向原第i个节点i_1Node-next再将i_1Node-next指向newNode。ListPushFront函数该函数实现头插法将元素x插入链表头部即第0个位置。创建新节点newNode其next指向原首节点L-next。头节点的next更新为newNode完成插入。关键点断言assert确保链表和索引有效。方法一与方法二逻辑等价均通过调整指针顺序避免断链。头插法是ListInsert的特例i0时。代码结构共性均通过BuyListNode(x)动态创建新节点。核心操作新节点的next指向后续节点前驱节点的next指向新节点。2.4删除删除函数的功能是删除顺序表中第i个位置上的元素删除的元素通过返回值带出注意i必须在0 ≤ i s.size否则⽆法删除。具体操作如下a.参数检测主要检测位序i是否满⾜0 i s.size满⾜则删除否则⽆法删除 b.将i位置之后所有元素整体往前搬移⼀个位置 c.删除成功将有效元素个数减1//删除链表中下表为i的节点并用x带出节点的值LDataTypeListDelete(LNode*L,inti){assert(L);assert(i0);intj-1;LNode*i_1NodeL;while(ji-1i_1Node){i_1Nodei_1Node-next;j;}assert(i_1Nodei_1Node-next);LNode*iNodei_1Node-next;LDataType xiNode-data;i_1Node-nextiNode-next;free(iNode);iNodeNULL;returnx;}//头删LDataTypeListPopFront(LNode*L){assert(L);assert(L-next);LNode*firstL-next;LDataType xfirst-data;L-nextfirst-next;free(first);firstNULL;returnx;}//尾删LDataTypeListPopBack(LNode*L){assert(L);assert(L-next);LNode*prveL;LNode*curL-next;while(cur){curcur-next;prvecur;}LDataType xcur-data;free(cur);curNULL;prve-nextNULL;returnx;}总结删除指定位置的节点ListDelete该函数删除链表中第i个节点并返回其值。LNode* i_1Node L;初始化指针i_1Node指向头节点用于定位待删除节点的前驱节点。while (j i - 1 i_1Node)通过循环找到第i-1个节点确保位置有效性。LNode* iNode i_1Node-next;获取待删除节点保存其数据到变量x。i_1Node-next iNode-next;修改前驱节点的指针跳过待删除节点。free(iNode);释放待删除节点的内存完成删除操作。头删操作ListPopFront该函数删除链表的第一个有效节点头节点后的节点并返回其值。LNode* first L-next;定位到第一个有效节点。L-next first-next;将头节点的指针指向第二个节点跳过原第一个节点。free(first);释放原第一个节点的内存。尾删操作ListPopBack该函数删除链表的最后一个节点并返回其值。LNode* prve L;LNode* cur L-next;初始化双指针prve用于跟踪cur的前驱节点。while (cur-next)循环结束后cur指向尾节点prve指向尾节点的前驱节点。prve-next NULL;将前驱节点的指针置空断开与尾节点的连接。free(cur);释放尾节点的内存。关键点说明所有操作均需确保链表非空assert(L-next)。删除后需及时释放内存并将指针置空避免内存泄漏。双指针法如尾删是链表操作的常见技巧。2.5查找顺序表有两种查找操作位序查找和按值查找。位序查找函数原型SqDataType GetElem(SqList* ps, int i) 第i个位置元素随机访问在i满⾜0 i s.size 时(不满⾜则报错)直接返回顺序表第i个元素即可。//获取链表中第一个数据等价于x节点的地址若不存在就返回NULL指针LNode*ListLocateElem(LNode*L,LDataType x){assert(L);LNode*curL-next;while(cur){if(cur-datax)returncur;curcur-next;//如果不相等cur就指向下一个地址}returnNULL;}//返回链表中下标为i的节点LNode*ListGetElem(LNode*L,inti){assert(L);assert(i0);LNode*iNodeL-next;intj0;while(jiiNode){iNodeiNode-next;j;;}if(iNodeNULL){printf(没有找到下标为i的地址\n);returnNULL;}returniNode;}总结函数功能分析ListLocateElem查找链表中第一个数据域等于x的节点返回其地址若不存在则返回NULL。ListGetElem返回链表中下标为i的节点地址从0开始计数若下标越界则返回NULL并打印提示信息。关键代码解析ListLocateElem参数校验assert(L)确保头节点指针非空。遍历链表cur L-next从头节点的下一个节点开始遍历。条件匹配if (cur-data x)检查当前节点数据是否等于目标值x匹配则立即返回节点地址。终止条件while (cur)确保遍历到链表末尾cur为NULL时终止。ListGetElem参数校验assert(i 0)确保下标非负。遍历控制j i iNode循环直到找到第i个节点或链表结束。越界处理若iNode NULL说明下标越界打印提示并返回NULL。注意事项两个函数均假设链表带头节点L为头节点实际数据从L-next开始。时间复杂度均为O(n)需遍历链表。ListGetElem的下标从0开始与数组索引规则一致。2.6打印和获取个数//打印链表voidListPrint(LNode*L){assert(L);//cur 表示当前LNode*curL-next;while(cur){printf(%d-,cur-data);curcur-next;}printf(NULL\n);}//获取个数intListSize(LNode*L){assert(L);LNode*curL-next;intn0;while(cur){n;curcur-next;}returnn;}通过创建一个新的指针节点指向哨兵位节点让其从哨兵位开始循环打印cur当cur等于NULL时循环结束。打印顺序表将结构体中的data数据进行打印data中存放的是顺序表中的元素。计算顺序表中的个数时重新定义一个新的int类型的变量n将其放在循环体之外每当cur cur-next;(将cur指向下一个元素的地址)时n的数量不断进行增加从而计算顺序表中的元素个数。函数测试//test.cpp#define_CRT_SECURE_NO_WARNINGS#includeList.hLNode*CreateList(){//创建头节点LNode*LBuyListNode(-1);//快速构建5个节点方便测试LNode*node1BuyListNode(1);LNode*node2BuyListNode(2);LNode*node3BuyListNode(3);LNode*node4BuyListNode(4);LNode*node5BuyListNode(5);//然后手动将节点来连接起来L-nextnode1;node1-nextnode2;node2-nextnode3;node3-nextnode4;node4-nextnode5;returnL;}//void test1()//{// LNode* LT NULL;//// LT CreateList();//// //测试打印方法和获取节点个数方法// printf(链表LT中总共有%d个节点\n, ListSize(LT));// ListPrint(LT);//// //测试按值获取// printf(链表中值%d节点为%p\n, 1, ListLocateElem(LT, 1));// printf(链表中值%d节点为%p\n, 3, ListLocateElem(LT, 2));// printf(链表中值%d节点为%p\n, 100, ListLocateElem(LT, 100));//// //测试按下标获取// printf(链表中下标%d的节点的值为%d\n, 0, ListGetElem(LT, 0)-data);// printf(链表中下标%d的节点的值为%d\n, 2, ListGetElem(LT, 2)-data);// printf(链表中下标%d的节点的值为%d\n, 4, ListGetElem(LT, 4)-data);// printf(链表中下标%d的节点的值为%d\n, 100, ListGetElem(LT, 100));//// //销毁链表// //ListDestroy(LT);// LT NULL;//}voidtest2(){LNode*LTNULL;LTCreateList();ListPrint(LT);ListInsert(LT,5,6);//尾插ListPrint(LT);ListInsert(LT,2,30);//中间插ListPrint(LT);ListInsert(LT,0,0);//头插ListPrint(LT);//非法位置//ListInsert(LT, 100, 100);printf(\n);//测试不使用CresteList创建链表LNode*LTTListInit();ListInsert(LTT,0,1);ListInsert(LTT,1,2);ListInsert(LTT,2,3);ListPrint(LTT);ListDelete(LT,0);//头删ListPrint(LT);ListDelete(LT,2);//中间删ListPrint(LT);ListDelete(LT,5);//尾删ListPrint(LT);//非法位置//ListDelete(LT, 100);//销毁链表ListDestroy(LT);}intmain(){//test1();test2();return0;}通过以下链接可以进行观看详细的源代码https://gitee.com/liuyinumber/sequential-list-2/commit/d399bfe7cb4c2345abd3c35de2741cfd03abbb45全文总结本文系统梳理了顺序表以动态链表形式实现的核心操作初始化用malloc动态申请节点带回错误处理和哨兵位节点设计。销毁逐节点释放内存注意外部指针手动置空避免野指针。插入与删除通过定位前驱节点、调整指针顺序来避免断链头插/头删/尾删均为特例。查找支持按值遍历查找和按下标遍历查找均为 O(n) 复杂度。打印与计数从头节点后遍历至 NULL 即可完成。测试验证通过CreateList快速构建链表覆盖常规和边界测试用例。如何熟练掌握顺序表实现手写核心操作反复脱离 IDE 手写初始化、插入、删除、查找、销毁的完整代码尤其关注指针操作的顺序和边界条件。理解哨兵位设计体会带哨兵位链表如何简化头插、头删、空链表等边界处理能对比不带哨兵位的实现。内存管理意识掌握malloc/free配对理解动态内存的生命周期养成销毁后外部指针置空、释放前保存next等好习惯。调试与测试针对空链表、单节点、正常多节点、非法索引等场景编写测试用assert辅助定位问题。对比顺序表与链表在纸上画出数组顺序表和链式顺序表在内存中的存储差异理解各自在随机访问和动态扩容上的优劣从而在合适场景做出正确选择。实习中如何运用顺序表数据处理与缓存在需要维护有序数据集合、消息队列、日志缓存等场景用顺序表数组版做快速随机访问用链表版做频繁增删。底层数据结构实现在栈、队列、哈希表链地址法、邻接表等常见数据结构中顺序表都是基础构建块掌握后可快速实现业务需求。性能优化思维实习任务中遇到性能问题时能根据顺序表的扩容开销和链表的内存碎片特征给出方案选型建议展现工程把控力。代码复用与接口设计参考文中BuyListNode与ListInit的模块化拆分思路在实际项目中把通用数据结构封装成独立模块提升团队效率。面试与代码评审熟练掌握顺序表的实现细节、复杂度分析和易错点能在技术面试中从容作答在代码评审中精准发现问题如内存泄漏、野指针、断链。