1. 线性表到底是什么先破除线性表等于数组的误解讲到数据结构十个教程里有九个会把线性表放在第一章。这个安排一点不奇怪因为后面你要学的栈、队列、字符串、数组本质上都是线性表的特殊形态。但线性表这个概念本身恰恰是很多人第一个糊里糊涂过去的坎。我见过不少同学学完这一章之后留下的印象就是线性表等于数组顶多再加个链表。这个理解不能说全错但把问题想窄了。线性表Linear List的定义其实很朴素它是n个数据元素组成的有限序列。注意两个关键词有限意思是元素的个数是确定的、可数的序列意思是元素之间有先后次序第一个元素没有前驱最后一个元素没有后继中间每个元素有且只有一个直接前驱和一个直接后继。这个一对一的逻辑结构才是线性表的本质。至于底层用数组存还是用链表存那是存储结构层面的选择跟逻辑结构是两码事。搞不清楚逻辑结构和存储结构这两个层次后面学树、学图的时候一定会更痛苦。树是一对多图是多对多它们的底层照样可以用数组来表示比如二叉树的顺序存储但你不会因此说树就是数组。1.1 从生活里找线性表的影子理解一个抽象概念最有效的方式是找现实中的映射。线性表在我们的生活中到处都是排队买奶茶的队伍每个人都知道自己前面是谁、后面是谁队头队尾固定新来的人站到队尾有人离开就整体往前挪一步——这就是最标准的线性表。手机通讯录一个联系人的记录有先后顺序可以按位置第几条记录访问也可以按名字查找支持中间插入和删除——线性表的基本操作齐了。Excel里的一列数据从上到下的每一格就是线性表的一个元素。这些例子的共同点是元素之间有明确的次序关系操作无外乎取某个位置的元素、在某个位置插一个、把某个位置的元素删掉、数一数有多少个。算法设计里的表抽象数据类型ADT List就是把这几个操作高度归纳之后的结果。提示学数据结构的时候一定要养成先画图再做代码的习惯。哪怕是一张非常潦草的方框箭头图都比直接上代码更接近数据结构的本质。1.2 线性表的ADT定义为什么要理解很多学校用的是严蔚敏老师的《数据结构C语言版》教材第二章开头就是一长串ADT定义。坦率讲那一段是全书劝退率最高的一页因为看起来全是抽象的名词不知道背来干嘛。我的建议是ADT定义不需要死背但你必须理解它为什么要这样写。它本质上是一份接口合同规定了线性表对外提供哪些操作InitList初始化、ListEmpty判空、Length求长度、GetElem按位取值、LocateElem按值查找、ListInsert插入、ListDelete删除、PrintList遍历输出。这几个操作覆盖了99%的实际使用场景。理解ADT的另一个价值在于它是实现无关的。你用顺序表实现这些操作是一种写法用链表实现又是一种写法但调用方的代码可以完全一样。这就是抽象的意义——它把怎么存和怎么用解耦了。举个工程例子Java里List接口有ArrayList和LinkedList两个实现换成面向接口编程业务代码几乎不用改这就是数据结构层面的抽象能力在工程里的直接体现。1.3 顺序存储和链式存储同一逻辑结构的两种肉身线性表有两种最基础的存储结构顺序存储顺序表用一段地址连续的存储单元依次存放数据元素。你可以直接把它理解成数组元素在内存里一个挨着一个。链式存储链表用一组地址任意的存储单元存放数据元素节点之间通过指针串起来。每个节点除了数据还要额外存一个指针单链表存一个后继指针双向链表存两个。这两种方案的核心矛盾就是**连续和非连续的对立**。顺序表强在随机访问弱在插入删除要挪动大量元素链表正好反过来插入删除只需改指针但想访问第k个元素得从头一格一格走。这个矛盾会贯穿整篇文章后面我会详细展开。2. 顺序表最直观的存储方案坑却藏在不显眼的地方顺序表的核心思路很简单声明一块连续内存把元素按次序放进去再用一个变量记录当前有多少个元素。这一节我会把初始化、查找、插入、删除、扩容全部过一遍重点说清楚每一段代码背后的为什么。2.1 顺序表的实现骨架C语言版以严蔚敏教材的风格为例顺序表常用如下定义#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 存储元素的数组 int length; // 当前表长 } SeqList;注意MAX_SIZE是数组的容量capacitylength是实际元素个数。这两个概念一定要分开因为后面不管是动态扩容还是判断满表全依赖它们。很多新手把length和数组下标混起来写插入的时候边界判断满天飞其实只要想清楚一个点元素从下标0存到length-1length随时指向下一个空闲位置。初始化、判空、求长度void InitList(SeqList *L) { L-length 0; } int ListEmpty(SeqList L) { return L.length 0; } int ListLength(SeqList L) { return L.length; }这几个函数看着简单但价值在于约束一致。你规定好了length 0表示空表、data才是元素区那么所有后续操作都围绕这个约定来写代码就不会乱。2.2 按位查找为什么顺序表能O(1)随机访问int GetElem(SeqList L, int i, int *e) { if (i 1 || i L.length) return 0; // 位置非法 *e L.data[i - 1]; // 第i个元素存在下标i-1 return 1; }这里有个位序和下标的经典换算逻辑位序从1开始物理下标从0开始。所以第i个元素的存储地址 首地址 (i-1) × sizeof(元素类型)。这个公式意味着什么意味着不需要遍历直接用下标做一次偏移就能拿到任意位置的元素——这就是所谓的随机存取Random Access。这正是顺序表最值钱的特性也是后面链表做不到的对照基准。C语言里L.data[i-1]这句话编译器算地址的过程就是上面那个公式的体现。你访问L.data[99]和访问L.data[0]耗时一模一样跟位置无关。理解了这个后面学数组和矩阵压缩存储的时候也会轻松很多。2.3 插入和删除移动元素才是真正的代价插入操作逻辑上不复杂先判断位置合法性和表是否已满然后把从插入位置开始的元素整体后移一位最后放入新元素length加1。int ListInsert(SeqList *L, int i, int e) { if (L-length MAX_SIZE) return 0; // 表满 if (i 1 || i L-length 1) return 0; // 位置非法 for (int j L-length; j i; j--) { L-data[j] L-data[j - 1]; // 从后往前逐个后移 } L-data[i - 1] e; L-length; return 1; }删除操作与之对称int ListDelete(SeqList *L, int i, int *e) { if (i 1 || i L-length) return 0; *e L-data[i - 1]; for (int j i - 1; j L-length - 1; j) { L-data[j] L-data[j 1]; // 从前往后逐个前移 } L-length--; return 1; }这两段代码的核心动作都是元素的批量搬移。插入时从后往前搬删除时从前往后搬方向千万别搞反——插到第1个位置需要把第1个到最后一个全部后移所以必须先把最后一个挪到后面的空位再依次往前如果从前往后搬前一个元素把后一个覆盖了数据就丢了。时间复杂度的计算是这样的在长度为n的表里插入位置i1 ≤ i ≤ n1有n1种选择每种选择需要移动n-i1个元素平均移动次数为平均移动次数 (1/(n1)) × Σ(i1 到 n1) (n-i1) (1/(n1)) × (n (n-1) ... 1 0) n/2所以在表长n的线性表中插入一个元素平均需要移动大约n/2个元素时间复杂度是O(n)。注意这个结论是平均意义上的——往表尾插入只需要移动0个元素O(1)往表头插入要移动n个O(n)。要是你的应用恰好总是往表尾追加顺序表的真实表现会比O(n)好看得多这一点到选型部分我会专门展开。2.4 动态扩容ArrayList扩容策略为什么是1.5倍静态数组写起来简单但MAX_SIZE定死了装不下更多元素就只能失败。实际工程里更常用的是动态扩容的版本——比如C的vector、Java的ArrayList、Python的list本质上都是会自动长大的顺序表。扩容的策略有意思。Java的ArrayList默认容量10扩容时按1.5倍增长C的vector没有统一的扩容倍数但很多实现是2倍。为什么不每次只加一个位置因为扩容要做两件事申请一块更大的连续内存然后把旧数据全部拷贝过去。假设每次扩容增加1个元素那么插入n个元素的时间是123...n O(n²)而按倍数扩容log₂n次扩容总共拷贝的元素数量是124...2^k ≈ 2^(k1) O(n)量级均摊到每次插入是O(1)。注意**均摊复杂度amortized analysis**这个概念在算法分析里很重要。动态数组的push_back操作绝大部分时候直接写入O(1)偶尔触发扩容O(n)但把n次操作的总时间摊到每次依然是常数级别。王道考研教材里经常考这个点理解后比死记结论靠谱得多。为什么用1.5倍而不是2倍一个常见的解释是翻倍扩容后之前释放的旧内存恰好小于新分配的内存可能无法被下一次扩容复用而1.5倍配合某些内存分配策略能提高内存复用率。另一个原因是1.5倍更节省空间极端情况下2倍扩容可能浪费一半容量。这些属于实现细节不同语言有不同取舍但你应该理解的核心是线性扩容不可取指数扩容配合均摊分析才是工程正解。3. 单链表指针操作是门手艺别靠背代码顺序表再好也有它的天花板——连续内存的整块要求决定了它在需要频繁插入删除、或者元素个数动态变化很大的场景里不好用。链表就是为打破这个约束而生的。3.1 单链表的结构与初始化单链表的基本单位是节点Node每个节点包含两个部分数据域存数据和指针域存下一个节点的地址。在C语言里通常这样定义typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;注意struct LNode *next里面为什么写struct LNode而不是LNode——因为typedef还没有执行完在struct内部只能用完整的类型名struct LNode来声明指针。这是C语言里一个很经典的自我引用写法面试偶尔会问到。初始化带头节点的链表int InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); // 申请头节点 if (*L NULL) return 0; // 内存分配失败 (*L)-next NULL; return 1; }这一步的细节值得抠一下为什么InitList的参数是LinkList *L而不是LinkList L因为LinkList本质上是指针类型LNode *的别名在函数内部要给这个指针本身赋值指向新申请的头节点就必须传指针的地址也就是LNode **。这是C语言里想在函数里修改指针变量本身的标准姿势。很多新手在这上面栽跟头函数里malloc了出来发现链表还是NULL就是因为传进去的是指针的副本。3.2 头节点 vs 头指针一个细节考倒一堆人这是个经典考点严蔚敏教材和王道考研书里都反复强调。头指针是指向链表中第一个节点的指针它标识了整个链表是链表的门面。头节点则是为了操作方便在第一个元素节点之前额外附加的一个节点它的数据域一般不存东西或存链表长度等附加信息指针域指向第一个元素节点。头节点的价值在于统一空表和非空表的操作逻辑。假设没有头节点链表为空时头指针直接是NULL插入第一个元素时要让头指针指向新节点链表非空时插入是在某个节点后面接一个节点——两套逻辑代码里就得写if分支。而有了头节点空表时头节点的next指向NULL非空时也还是头节点的next指向某节点插入和删除一律从头节点开始处理无需特殊判断。这个用哨兵节点消除边界分支的思路在后续很多数据结构实现里都会复用比如链式队列的dummy头、红黑树里的nil哨兵节点其实都是同一招。实战建议现在面试手撕链表题用C/C时我一般都会先定义dummy node作为头节点这一招能显著减少边界条件的bug。LeetCode上很多链表题的题解里ListNode *dummy new ListNode(0); dummy-next head;几乎是标配就是头节点思想在刷题领域的体现。3.3 链表的插入与删除先画图再写码单链表的插入分为两种情况在节点p之后插入节点s已知p的指针以及在指定位置i插入。第一种情况最简单s-next p-next; // 先把s接到p原来指向的后继上 p-next s; // 再把p的指针改为指向s这两行代码的顺序是铁律必须先接后继再改前驱的指针。如果反过来先执行p-next s那么p原来的后继节点就找不到了链表从这里断掉后面的节点全丢了。口诀是先连后断。第二种情况即给定位置i插入需要先通过遍历找到第i-1个节点再执行上面的两步操作int ListInsert(LinkList L, int i, int e) { LNode *p L; int j 0; while (p ! NULL j i - 1) { // 找到第i-1个节点 p p-next; j; } if (p NULL) return 0; // 位置非法 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; s-next p-next; p-next s; return 1; }这里的时间开销大头在遍历查找上平均要找n/2个节点所以总复杂度是O(n)。但请注意平均两个字。如果插入点已知比如已经拿着指向某个节点的指针插入本身只需要O(1)这也是链表插入比顺序表快这句话的适用前提——它必须建立在你已经定位到了目标位置附近这个条件上。删除操作同样分两步找到目标节点的前驱p然后q p-next; p-next q-next; free(q);。有个变体技巧值得一提如果要删除的是已知节点p且不想额外遍历找前驱可以把p的后继节点的值拷贝到p然后删掉p的后继节点这样也做到了O(1)删除——前提是p不是尾节点。这个技巧在LeetCodeDelete Node in a Linked List里就是标准解法思路相当精妙。3.4 头插法、尾插法、前插法建链表的三种姿势建链表有两种基本方法。头插法是从头节点开始每次把新节点插到头节点之后这样建出来的链表元素顺序和输入顺序相反尾插法则维护一个尾指针r新节点总是接到链表末尾顺序与输入一致。// 头插法结果逆序 LinkList CreateListHead(int arr[], int n) { LinkList L (LNode *)malloc(sizeof(LNode)); L-next NULL; for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next L-next; L-next s; } return L; } // 尾插法结果正序需要尾指针 LinkList CreateListTail(int arr[], int n) { LinkList L (LNode *)malloc(sizeof(LNode)); LNode *r L; // 尾指针初始指向头节点 for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; r-next s; r s; // 尾指针后移 } r-next NULL; // 别忘了封口 return L; }头插法虽然建出的链表是逆序的但在某些场景反而是优势——比如从单链表快速构造反转后的链表。尾插法的关键是尾指针的维护以及最后一定要r-next NULL否则链表末尾会悬空遍历时造成野指针问题。前插法是真题里的高频考点它要求在第i个元素之前插入一个新元素。由于单链表只能向后走前插的常规做法是找到第i-1个节点p在p之后插入——也就是把前插转化为p的后插插入位置向前移一位。代码逻辑和后面的ListInsert完全一致核心是理解这个前插变后插、位置左移一位的转化思想。4. 双向链表和循环链表什么时候值得多花一份指针空间单链表有个天生的短板只能往后走。做删除操作时我们惊T发现需要知道前驱但单链表里前驱只能重新遍历——这就是单向的代价。解决思路也很直接每个节点再存一个前驱指针于是有了双向链表。4.1 双向链表的节点定义与插入删除typedef struct DNode { int data; struct DNode *prior; // 前驱指针 struct DNode *next; // 后继指针 } DNode, *DLinkList;双向链表在任意位置删除节点理论上可以做到O(1)——因为有了前驱指针不需要再遍历找前驱。插入操作需要改四个指针比单链表多了两个因此改指针的顺序一定要彻底搞清楚否则很容易出现指针悬空或者节点从链表中丢出去的bug。在节点p之后插入节点ss-next p-next; s-prior p; if (p-next ! NULL) { p-next-prior s; // 这里判断很重要如果p是尾节点p-next为NULL } p-next s;删除节点pp-prior-next p-next; if (p-next ! NULL) { p-next-prior p-prior; } free(p);注意插入和删除都涉及对p-next是否为NULL的判断。尾节点后面没有后继所以它的next是NULL如果你不判断就直接访问p-next-prior就是空指针解引用程序直接崩溃。这类问题在考研选择题里是高频干扰项实战中调试也是高发区。代价很清楚每个节点多了一个指针的内存占用64位系统下是8字节而且插入删除时指针操作的数量翻倍出bug的概率也翻倍。所以工程上要不要用双向链表关键是看你的操作里删除已知节点和从后往前遍历是不是真的高频。像Java的LinkedList内部就是双向链表因为它要支持从两个方向迭代而Linux内核链表实现里更是把指针域做进了结构体所有节点通过list_head串起来那就是另一个层级的话题了。4.2 循环链表与快慢指针判环循环链表circular linked list把最后一个节点的next指针指向头节点带上头节点的话这样就形成了一个环从任意节点出发都能走回原点。它最直观的应用场景是循环队列和约瑟夫环问题。判断单链表是否有环是面试高频题。经典的解法是快慢指针Floyd判圈算法fast指针每次走两步slow指针每次走一步如果链表有环两者必然相遇如果无环fast会先到NULL。为什么快慢指针一定能相遇因为每轮迭代fast相对slow推进一个节点两者的距离逐步缩小最终会追上。这个证明思路比代码本身更重要面试官大概率会追问。int HasCycle(LNode *head) { if (head NULL || head-next NULL) return 0; LNode *slow head-next; LNode *fast head-next-next; while (fast ! NULL fast-next ! NULL) { if (slow fast) return 1; slow slow-next; fast fast-next-next; } return 0; }4.3 约瑟夫环问题循环链表最经典的实战约瑟夫环问题描述起来很简洁n个人围成一圈从第1个人开始报数报到m的人出列然后从下一个人重新报数直到所有人出列求出列顺序。这个题的经典解法就是循环链表void Josephus(int n, int m) { DLinkList head NULL, p NULL, q NULL; // 建一个循环双向链表节点数n编号1~n构建代码略 p head; while (p-next ! p) { // 当只剩一个节点时停止 for (int i 1; i m; i) { p p-next; // 报数相当于指针移动m-1次 } printf(%d , p-data); // 当前p出列 q p-next; p-prior-next p-next; p-next-prior p-prior; free(p); p q; // 从下一个节点继续 } printf(%d\n, p-data); }这里用双向循环链表比较顺手删除任意节点只需要O(1)报数移动指针的复杂度是O(m)总共n次整体O(n·m)。如果数据规模大有更聪明的数学解法约瑟夫环的递推公式不过那属于数学层面优化的范畴数据结构课程里能用循环链表把它跑通就已经达标了。5. 选型不靠口诀顺序表和链表的真实差距比你想的大我见过很多人背一句频繁插入删除用链表频繁查询用顺序表就去应付考试和面试了。这句话理论上没错但它掩盖了一个非常重要的工程事实同样的O(n)复杂度常数因子可能差出一个数量级。而在当代计算机的内存架构下顺序表在很多场景甚至比链表更快——即便它需要搬移元素。5.1 复杂度之外的两个隐藏维度第一个隐藏维度是CPU缓存命中率。顺序表的元素是连续存放的遍历时CPU会把相邻的内存块预取到缓存里cache line通常是64字节一趟遍历下来缓存命中率极高。链表的节点分散在各个malloc分配出来的内存块里遍历一个节点就要访问一次内存地址几乎每次都是cache miss。在数据量大到超过CPU缓存的场景比如几百万个节点顺序表遍历比链表遍历快10倍以上并不夸张。国外有人专门做过benchmark结果基本都是数组完胜。第二个隐藏维度是内存分配的开销。链表每创建一个节点就要malloc一次malloc本身有系统调用和堆管理开销而且会产生内存碎片顺序表只在扩容时分配一次内存摊销下来小得多。如果你在高频插入节点的场景使用链表malloc的时间很可能会让你怀疑人生。5.2 理论复杂度的精确对照把关键操作的时间复杂度n为表长列成一张表会更清楚操作顺序表链表说明按位查找O(1)O(n)顺序表的随机访问是碾压级优势按值查找O(n)O(n)两者都需要遍历差距在常数因子在第i位插入O(n)平均移动n/2个元素O(n)但只需遍历到i-1插入本身O(1)插入点靠前时链表优势大靠后时差距缩小删除第i位O(n)平均移动(n-1)/2个元素O(n)同理需要找到前驱同上在已知节点后插入O(n)O(1)链表唯一真正的理论碾压场景删除已知节点O(n)O(1)双向链表或O(1)变体前提是持有目标节点的指针看完这张表你会发现插入删除链表快这句话只有在已知节点指针的前提下才完全成立。如果每次都是从表头开始找位置插入链表的O(n)可能比顺序表的O(n)还要慢因为顺序表至少缓存友好而链表每次都伴随cache miss和malloc。5.3 实际项目中的选型建议根据我自己的项目经验几个实用的选型判断标准以随机访问为主按下标取元素、排序、二分查找无脑顺序表数组/vector/ArrayList就是为你准备的。频繁在头部插入删除顺序表要搬移大量元素链表头插O(1)这个场景链表胜。频繁在中间或尾部插入删除需要结合是否已持有插入位置指针判断。如果业务场景每次插入都伴随一次查找定位那两者的理论复杂度差不多此时优先考虑顺序表理由是缓存友好和实现简单。元素个数不确定且波动大动态扩容的顺序表或者直接上链表都行。如果插入的峰值很高且每个节点数据较小链表碎片化问题不严重如果节点数据很大顺序表扩容的拷贝成本高可以选链表。一句话总结不要背口诀要背场景。选型的前提永远是你的实际操作的访问模式是什么而不是哪句话听起来更经典。6. 高频题型拆解从考研真题到面试手撕线性表这一章是考研408、期末考、以及各大公司面试手撕算法题的重灾区。很多人感觉课都听懂了题就是做不出来原因是缺少一个题目模式的归纳。我按自己的备考和教学经验整理几类高频题型每一类给出解题套路这样你刷题时就能见题识套路而不是每次都是现场推。6.1 链表反转迭代、递归、头插三兄弟链表反转是面试出现频率最高的链表题没有之一。迭代写法最经典用三个指针prev、curr、next滚动推进LNode *ReverseList(LNode *head) { LNode *prev NULL; LNode *curr head; while (curr ! NULL) { LNode *next curr-next; curr-next prev; prev curr; curr next; } return prev; }递归写法非常简洁但理解门槛也高先反转后面的链表再把当前节点接到反转后的链表尾部LNode *ReverseListRecursive(LNode *head) { if (head NULL || head-next NULL) return head; LNode *newHead ReverseListRecursive(head-next); head-next-next head; head-next NULL; return newHead; }第三种是头插法反转新建一个头节点遍历旧链表把每个节点头插到新链表里自然就是逆序。这个思路如果你在建链表时练过头插法几乎不用思考就能写出来——这也是我把头插法放在前面讲的原因知识点都是串起来的。反转的变体还有反转前k个节点每k个一组反转反转区间万变不离其宗核心都是指针的重新连接顺序。我练的时候会在纸上画个五节点的链表手动走一遍三个指针的变化画熟之后再难的变体也不慌。6.2 快慢指针双雄找中点、找倒数第k个节点快慢指针不只是用来判环。找链表中间节点可以用快指针走两步、慢指针走一步快指针到链尾时慢指针正好在中点找倒数第k个节点则可以用快指针先走k步然后快慢指针同步走快指针到NULL时慢指针指向的就是倒数第k个节点。LNode *FindKthFromEnd(LNode *head, int k) { LNode *fast head, *slow head; for (int i 0; i k; i) { if (fast NULL) return NULL; // k超过链表长度 fast fast-next; } while (fast ! NULL) { fast fast-next; slow slow-next; } return slow; }这类题考的是用两个指针制造距离差的思维模型而不是什么高深的算法。一旦你建立了这个模型合并两个有序链表、删除倒数第N个节点、判断回文链表这些题目都会迎刃而解。6.3 合并有序链表与链表排序合并两个有序链表是归并排序链表版的前置技能标准写法用递归LNode *MergeTwoLists(LNode *l1, LNode *l2) { if (l1 NULL) return l2; if (l2 NULL) return l1; if (l1-data l2-data) { l1-next MergeTwoLists(l1-next, l2); return l1; } else { l2-next MergeTwoLists(l1, l2-next); return l2; } }这里递归的终止条件其实很关键——只要有一个链表走完直接把另一个剩下的整段接上省去逐节点遍历。链表排序最常考的是链表插入排序和链表归并排序两者都不需要额外的大块内存归并排序的时间复杂度可以稳定在O(n log n)。如果面试遇到对链表排序我一般先写归并排序——快速排序对链表并不友好因为快排的partition依赖随机访问元素链表下标访问是O(n)性能优势发挥不出来。6.4 实验报告和期末里的实现证明组合题除了算法题很多读者可能是为了课程实验报告来的。典型的实验报告题目包括顺序表的基本操作实现要求写初始化、插入、删除、查找、打印并输出每一步的结果。这种报告的重点不是代码多华丽而是测试用例要覆盖边界——空表插入、满表插入、越界位置插入、删除首尾元素每一条都要有输出截图和说明。单链表的建立与操作要求实现头插法/尾插法建表以及插入删除并验证头节点的重要性。报告中如果能加一段带头节点与不带头节点的对比测试分数通常会高一截。两个有序表的合并也就是归并思想的顺序表应用要求实现Merge操作并分析时间复杂度。这道题是考归并思想的代码实现不难重点是把三指针i、j、k的推进逻辑讲清楚。写实验报告的技巧是不要只贴代码要把每一步的设计意图写出来。比如删除时为什么从前往后搬插入时为什么从后往前搬为什么用循环双向链表实现约瑟夫环。很多老师改实验报告最看重的就是这个为什么而不是那一堆谁都能从网上抄来的代码。7. 学完这一章我踩过的坑和你大概率也会踩的坑最后聊一些人话总结。这部分是我自己当年学线性表、以及后来帮别人改代码时反复遇到的高频错误每一条都对应真实的debug经历希望你能跳过这些坑。第一个坑我不止一次说过就是把逻辑位序和物理下标搞混。教材里的插入删除一律用第i个元素来描述i从1开始而代码里的数组下标从0开始。写循环的时候顺拐要么越界要么漏元素最后打印结果错位。解决方法是写代码前先定好约定注释里写清楚i是逻辑位序从1开始代码里所有访问都用i-1转换位序。第二个坑是malloc之后不检查返回值。虽然在竞赛和刷题环境里malloc失败的概率很低但在课程设计里内存申请多了照样可能失败。不检查就直接解引用轻则段错误重则产生一堆莫名其妙的bug。我建议所有链表相关函数里malloc之后都要加一句if (s NULL) return 0;这不算繁琐是基本素养。第三个坑是遍历时修改链表结构。比如在遍历链表的过程中同时删除当前节点如果你直接用p p-next来推进删除后p可能已经指向了被释放的内存下一轮循环就成了野指针访问。正确的套路是先取next指针再做删除操作最后把p移到next。类似的还有在头插法建链时用原链表的遍历指针做forward稍不留神就把链表搞断了。第四个坑是只在初始化时malloc忘了销毁。C语言写链表不释放内存程序跑完可能没问题但课程设计里如果你写了一个多次创建链表的循环内存泄漏会越来越明显。终结点记得写一个DestroyList把每个节点free掉最后把头节点也free了。这不是数据结构的考点但它是你代码质量的门面。第五个坑其实算不上坑是认知层面的所有教科书都不是让你背的是让你操作的。线性表这一章的代码光看懂没有任何用真正有效的最小练习是关掉书自己从零写一个顺序表、一个单链表动手插删改查直到循环边界、指针指向、分配释放这些动作变成肌肉记忆。数据结构的感觉就是在这个过程里长出来的谁也替代不了你自己的手。学数据结构-线性表这一章就跟学骑自行车一样——看一百个教程不如摔一次跤。理论部分看到这里你已经把顺序表、链表、双向链表、循环链表以及它们的复杂度都过了一遍剩下的就是打开编辑器亲手把顺序表的插入循环写对、把链表反转的指针画明白。等你哪一天能把链表反转不看资料直接写出来你会发现后面学栈、队列、树、图都会顺滑很多因为那时候你已经打通了存储结构-逻辑结构-操作算法这条主线。