考研笔记

单链表

单链表是全章算法题的底座。 教材【命题追踪】列了单链表的应用 2009、2012、2013、2015、2016、2019 六道大题，外加「单链表插入操作的过程」2016、2024 两道选择题。选择题的考法是给一串指针语句问执行结果，逐句画图就不会错。

机制

2.3.1 单链表的定义

每个结点除存放元素自身的信息（data）外，还存放一个指向其后继的指针（next）。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

单链表不需要大量连续的存储单元，但附加的指针域浪费存储空间。元素离散分布，是非随机存取的存储结构：查找特定结点必须从表头开始依次遍历。

头指针与头结点：

  • 头指针：标识一个单链表，始终指向链表的第一个结点，为 NULL 时表示空表。
  • 头结点：在第一个数据结点之前附加的结点，数据域可以不存信息，也可以记录表长。带头结点时，头指针指向头结点。

教材原话：「不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点。」引入头结点的两个优点：

  1. 第一个数据结点的位置存放在头结点的指针域中，在第一个位置上的操作和其他位置一致，无须特殊处理。
  2. 无论链表是否为空，头指针都是指向头结点的非空指针，空表和非空表的处理统一。

2.3.2 基本操作（默认带头结点）

操作要点时间
初始化带头：创建头结点，L->next=NULL；不带头：L=NULL
求表长从第一个结点起计数，不包括头结点；带不带头结点写法略有不同
按序号查找p=L; j=0;（头结点是第 0 个结点），走到第 个
按值查找从 L->next 起比较 data
插入到第 个位置找到第 个结点 *p，再后插查找 ，插入本身
删除第 个结点找到第 个结点 *p，q=p->next; p->next=q->next; free(q);同上
头插法建表新结点插在头结点之后；读入顺序与表中顺序相反，可用来逆置
尾插法建表设表尾指针 r，新结点接在 r 后；最后 r->next=NULL

插入的两句顺序不能颠倒：

s->next=p->next;   // ①
p->next=s;         // ②

若先执行 ②，*p 原后继的地址就丢了，再执行 ① 相当于 s->next=s。

不带头结点时，插入或删除位置 都要特殊处理：让头指针 L 指向新的首结点。带头结点则不用。

两个 的技巧：前插与删除给定结点

单链表只能从前往后找，所以「在 *p 之前插入」和「删除 *p 本身」本来都要先花 找前驱。教材给了两个绕开前驱的办法，核心都是交换数据域：

操作做法代码
在 *p 前插入 *s先把 *s 后插到 *p 后面，再交换两者的 datas->next=p->next; p->next=s; 然后交换 p->data 与 s->data
删除给定结点 *p把后继的值赋给 *p，再删除后继q=p->next; p->data=q->data; p->next=q->next; free(q);

删除的技巧要求 *p 有后继；*p 是尾结点时仍要从头找前驱。

手算模板

指针语句题：逐句画图，每句只改一个指针。

  1. 画出初始状态，标出每个指针变量（h、p、q）指向哪个结点。
  2. 一次执行一句：x->next=y 改的是 x 所指结点的 next 域，x=y 改的是指针变量本身。
  3. 执行完再从头指针走一遍，读出结果。

以 2024 为例，设 h 为头结点，链表为 ，p 指向 ：

语句效果链表
q=p->next;q 指向
p->next=q->next; 越过 直接指向 ， 被摘下
q->next=h->next; 指向首结点
h->next=q;头结点指向

结果：将 q 所指结点移动到 L 的头结点之后（选 D）。题目给的 p 「非首且非尾」保证 q 存在，且 q 不是首结点。

边界

说法判断说明
「头指针指向头结点，所以头指针就是头结点」❌头指针是指针，头结点是结点；不带头结点时头指针指向第一个数据结点
「增加头结点是为了使单链表至少有一个结点」❌是为了方便运算的实现：统一首位置的操作、统一空表与非空表
「带头结点的单链表判空用 head==NULL」❌用 head->next==NULL；head==NULL 是不带头结点的判空
「单链表的表长包括头结点」❌不包括
「链式存储时，结点内的存储单元地址可以不连续」❌不同结点之间可以不连续，结点内必须连续
「链式存储不能反映数据之间的逻辑关系」❌用指针表示逻辑关系，能更方便地表示各种逻辑结构
「单链表插入的两句可以交换顺序」❌只知道 *p 时不能：先改 p->next 会丢掉原后继。q、p 两端都有指针时顺序无关（2.3.7 第 6 题）
「设了尾指针就能 删除尾结点」❌删除尾结点要把前驱的 next 置空，仍需从头找，
「在有序单链表中插入并保持有序是 」❌找插入位置 ，插入 ，合计
「给定 个元素，建立有序单链表最低 」❌最低 ：先对数组排序，再用 尾插建表
「长度为 的链表接在长度为 的链表后面是 」❌要遍历前面那个长度为 的表找尾结点，
「头插法建立的链表与输入顺序相同」❌相反；尾插法才相同
「在线性表 中删除 要移动 50 个元素」⚠️顺序存储移动 50 个，链式存储移动 0 个，答案是「0 或 50」

错题复盘：2016 用内存表表示单链表

表头元素为 的单链表存在内存中：(1008H)→(1000H)→(1010H)→(1004H)→(100CH)→NULL。 把存放于 1014H 的 插到 和 之间，问 、、 的「链接地址」。 「链接地址」就是该结点 next 所存的地址： 改为指向 （1014H）； 不变，仍指向 （1004H）； 指向 （1010H）。答案是 1014H、1004H、1010H。 容易错把 也改掉。插入只改前驱和新结点两个 next，后继结点不动。

考点

  • 头指针 vs 头结点，头结点的两个好处。
  • 带头 / 不带头的判空条件。
  • 插入两句的顺序；前插、删除给定结点的交换数据技巧。
  • 头插法逆序、尾插法正序。
  • 指针语句题逐句画图：2016、2024。
  • 算法设计题：单链表是大题第二主力，模板见代码附录。

链接

反向链接