顺序表从入门到精通

一、静态顺序表和动态顺序表

静态表

静态顺序表就是⽤固定⼤⼩的静态数组来存储数据。

// 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#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>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*时，强调它是「指向单个节点的指针」，比如遍历用的临时指针//初始化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(NewNode==NULL){printf("BuyListNode失败\n");exit(-1);}//申请成功后，对节点中的数据域或指针域进行初始化NewNode->data=data;NewNode->next=NULL;returnNewNode;}//初始化链表LNode*ListInit(){LNode*list=BuyListNode(-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设置NULL，size和capacity设置为0。 c.其次要注意的free本质并不是真的把空间销毁掉，free的本质是把这段空间的使⽤权还给操作系统，操作系统后续还可以把这段空间分配给别⼈。

//销毁链表voidListDestroy(LNode*L){LNode*cur=L->next;while(cur){LNode*next=cur->next;free(cur);cur=NULL;}free(L);//L = NULL;//这是临时变量写不写都可以}

新创建一个临时指针cur指向指向头节点的下一个节点（即第一个实际数据节点），从头节点之后开始释放。

• 保存当前节点的下一个节点地址到next，避免释放后丢失链表后续信息。

• 释放当前节点内存（free(cur)）。

• 将当前节点指针置为NULL（可选操作，防止野指针，但局部变量作用域结束后无效）。

• 释放头节点L的内存。注意此处未将L置为NULL，因参数为值传递，外部调用处的指针仍需手动置空。

//L = NULL;//这是临时变量写不写都可以

• 说明L = NULL是局部操作，不影响外部指针，因此可省略。

关键注意事项

1. 外部指针置空
   调用该函数后，外部需手动将链表头指针置为NULL，例如：

   ListDestroy(head);head=NULL;// 必须补充

2. 节点释放顺序
   必须先保存next再释放当前节点，否则无法访问后续节点。

3. 头节点处理
   区分头节点（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(i>=0);LNode*i_1Node=L;//相当于将i_1Node给定在头节点上intj=-1;while(j<i-1&&i_1Node){i_1Node=i_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*newNode=BuyListNode(x);newNode->next=i_1Node->next;i_1Node->next=newNode;}//头插voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNode=BuyListNode(x);newNode->next=L->next;L->next=newNode;}//头插voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNode=BuyListNode(x);newNode->next=L->next;L->next=newNode;}

总结

链表插入操作解析

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的特例（i=0时）。

代码结构共性

• 均通过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(i>=0);intj=-1;LNode*i_1Node=L;while(j<i-1&&i_1Node){i_1Node=i_1Node->next;j++;}assert(i_1Node&&i_1Node->next);LNode*iNode=i_1Node->next;LDataType x=iNode->data;i_1Node->next=iNode->next;free(iNode);iNode=NULL;returnx;}//头删LDataTypeListPopFront(LNode*L){assert(L);assert(L->next);LNode*first=L->next;LDataType x=first->data;L->next=first->next;free(first);first=NULL;returnx;}//尾删LDataTypeListPopBack(LNode*L){assert(L);assert(L->next);LNode*prve=L;LNode*cur=L->next;while(cur){cur=cur->next;prve=cur;}LDataType x=cur->data;free(cur);cur=NULL;prve->next=NULL;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*cur=L->next;while(cur){if(cur->data==x)returncur;cur=cur->next;//如果不相等cur就指向下一个地址}returnNULL;}//返回链表中下标为i的节点LNode*ListGetElem(LNode*L,inti){assert(L);assert(i>=0);LNode*iNode=L->next;intj=0;while(j<i&&iNode){iNode=iNode->next;j++;;}if(iNode==NULL){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。

注意事项

1. 两个函数均假设链表带头节点（L为头节点，实际数据从L->next开始）。
2. 时间复杂度均为O(n)，需遍历链表。
3. ListGetElem的下标从0开始，与数组索引规则一致。

2.6打印和获取个数

//打印链表voidListPrint(LNode*L){assert(L);//cur 表示当前LNode*cur=L->next;while(cur){printf("%d->",cur->data);cur=cur->next;}printf("NULL\n");}//获取个数intListSize(LNode*L){assert(L);LNode*cur=L->next;intn=0;while(cur){n++;cur=cur->next;}returnn;}

通过创建一个新的指针节点指向哨兵位节点让其从哨兵位开始，循环打印cur，当cur等于NULL时循环结束。

• 打印顺序表将结构体中的data数据进行打印，data中存放的是顺序表中的元素。
• 计算顺序表中的个数时，重新定义一个新的int类型的变量n，将其放在循环体之外，每当cur = cur->next;(将cur指向下一个元素的地址)时，n的数量不断进行增加，从而计算顺序表中的元素个数。

函数测试

//test.cpp#define_CRT_SECURE_NO_WARNINGS#include"List.h"LNode*CreateList(){//创建头节点LNode*L=BuyListNode(-1);//快速构建5个节点，方便测试LNode*node1=BuyListNode(1);LNode*node2=BuyListNode(2);LNode*node3=BuyListNode(3);LNode*node4=BuyListNode(4);LNode*node5=BuyListNode(5);//然后手动将节点来连接起来L->next=node1;node1->next=node2;node2->next=node3;node3->next=node4;node4->next=node5;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*LT=NULL;LT=CreateList();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*LTT=ListInit();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的模块化拆分思路，在实际项目中把通用数据结构封装成独立模块，提升团队效率。
• 面试与代码评审：熟练掌握顺序表的实现细节、复杂度分析和易错点，能在技术面试中从容作答，在代码评审中精准发现问题（如内存泄漏、野指针、断链）。