一个表头数组挂几条链：孩子表示法、邻接表、拉链法、基数排序是同一张图

Intro

树的孩子表示法、图的邻接表、散列表的拉链法、链式基数排序分在四个章节里讲，画出来却是同一张图：左边一列顺序存储的表头，每一格往右挂一条单链表。

这不只是长得像。四者的时间复杂度、"哪个方向好找、哪个方向难找"、"链里的先后次序由什么决定"，答案都一样。学会一个，另外三个的选择题和存储结构画图题可以直接推出来。

四张图摆在一起

四者只在两件事上不同：表头数组的下标代表什么，链上的结点存的是什么。

结构	表头下标代表	链上结点存	表头数	结点总数
孩子表示法	树中的一个结点	它的一个孩子的下标	$n$	$n-1$
邻接表（有向图）	一个顶点	一条出边的终点	$n$	$e$
邻接表（无向图）	一个顶点	一条关联边的另一端	$n$	$2e$
拉链法散列表	一个散列地址	一个关键字	值域大小 $m$	$n$
链式基数排序	当前位的一个取值	一个记录（这一趟分到这里）	基数 $r$	$n$

结构体定义也是同一个模子：一个"链结点"类型（数据 + next），一个"表头"类型（可能带自身数据 + 指向第一个链结点的指针），再开一个表头数组。

typedef struct ChildNode { int childIdx; struct ChildNode *next; } ChildNode;   // 孩子表示法
typedef struct { ElemType data; ChildNode *firstChild; } CTBox;

typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode;           // 邻接表
typedef struct VNode { char data; ArcNode *first; } VNode, AdjList[MaxVertexNum];

typedef struct Node { int key; struct Node *next; } Node;                       // 拉链法
typedef struct { Node *head; } HashTable[M];

孩子表示法和邻接表几乎逐字段对应：childIdx 就是 adjvex，firstChild 就是 first。把一棵树看成"每个结点向它的孩子连一条有向边"的图，它的邻接表就是孩子表示法。 画存储结构示意图时，四种结构的画法也完全一样：左边竖着画表头，每格向右画链，链尾写 ∧。

遍历一遍：表头数 + 结点数

把整个结构走一遍，要看每一个表头（哪怕它的链是空的），再沿每条链走到底，代价就是表头数 + 结点总数：

• 邻接表上的 BFS、DFS、拓扑排序：每个顶点处理一次，每条边结点扫一次，$O(n+e)$。
• 链式基数排序的一趟：分配扫 $n$ 个记录，收集要看全部 $r$ 个队列（空队列也得看一眼），$O(n+r)$；共 $d$ 趟，$O(d(n+r))$。
• 孩子表示法上做一次先根遍历：$n$ 个表头加 $n-1$ 个孩子结点，$O(n)$。

所以"为什么邻接表 BFS 是 $O(n+e)$"不需要单独记：$n$ 是表头那一列，$e$ 是挂在右边的那些结点。

顺着链找便宜，反着找要扫全表

链只有一个方向：从表头出发往右走。问题顺着这个方向问，只走一条链；反过来问，就得把每一条链都扫一遍。

结构	顺着问（走一条链）	反着问（扫全部链）
孩子表示法	结点 $i$ 有哪些孩子	结点 $i$ 的双亲是谁
有向图邻接表	顶点 $v$ 的出度、出边	顶点 $v$ 的入度、入边
拉链法	地址 $h$ 上有哪些关键字	（无此需求，查找总是从 $H(key)$ 出发）

2026 年第 6 题问的就是右下那一格：邻接表求某顶点的入度。头数组里没有入度信息，要把所有出边链挨个走一遍，看终点是不是这个顶点，$O(|V|+|E|)$。

反方向的需求多了，补救办法也一样：再建一份反方向的链。 有向图建逆邻接表，或者干脆用十字链表把出边链和入边链做进同一个结点里；树用"带双亲的孩子表示法"，表头里加一个 parent 字段。

链里的先后次序由插入方式决定

表头之间的次序是下标给的，固定不变；同一条链里谁在前，取决于插在链头还是链尾。 这一点在四种结构里的后果不一样：

• 邻接表：建表常用头插（$O(1)$），后插入的边排在前面。邻接点的次序决定了 DFS、BFS 序列，所以"按邻接表写遍历序列"的题，必须先看清链里的实际顺序。
• 拉链法：头插还是尾插，成功 ASL 不变——长为 $L$ 的链，各关键字的比较次数总是 $1,2,\cdots ,L$ 这一组数，变的只是"某一个关键字比几次"。
• 基数排序：必须尾插，每个桶是先进先出的队列。同一个桶里的记录要保持上一趟收集后的次序，排序才是对的。2013 年第 11 题、2021 年第 10 题的干扰项，都是把桶内次序弄错得到的。

矩阵是 n 个顺序表，邻接表是 n 个链表

写图的算法题时，这个对照可以再往前推一步：邻接矩阵的每一行就是一个顺序表，邻接表的每一条链就是一个单链表。 图上的操作，拆开看都是对若干个线性表的遍历：

• 有向图顶点 $i$ 的出度：邻接矩阵扫第 $i$ 行；邻接表走第 $i$ 条链。
• 顶点 $i$ 的入度：邻接矩阵扫第 $i$ 列；邻接表要走全部的链（就是上一节的"反着找"）。
• 2021 年第 41 题（数奇度顶点）、2023 年第 41 题（数出度大于入度的顶点）都用邻接矩阵存储，代码的主体就是一个二重循环按行、按列求和，难度和遍历顺序表是同一级的。

所以遇到"图采用 XX 存储"的算法题，先把它翻译成"$n$ 个顺序表"或"$n$ 个链表"，再用线性表那一套写循环。

考点速记

真题里被考过的形式：

• 存储结构与时间复杂度：2012 年第 5 题（邻接表 BFS 为 $O(n+e)$）、2016 年第 7 题（邻接表拓扑排序为 $O(n+e)$）、2011 年第 8 题（稀疏图用邻接表省空间）。
• 反方向查询：2026 年第 6 题（邻接表求入度要扫全部边链）。
• 链内次序：2013 年第 11 题、2021 年第 10 题（基数排序第 $k$ 趟后的序列，桶内次序沿用上一趟）。
• 邻接矩阵当 $n$ 个顺序表写算法：2021 年第 41 题、2023 年第 41 题。
• 孩子兄弟表示法（树、森林与二叉树的对应）：2014 年第 5 题、2021 年第 4 题、2026 年第 4 题，见树与森林的转换。

易错：邻接表只存出边。问入度、问"哪些顶点指向 $v$"时，复杂度是 $O(|V|+|E|)$，不是 $O(|V|)$，也不是 $v$ 的链长。

易错：基数排序的桶内次序必须是先进先出。按"后进的先出"收集，或者凭感觉把桶内元素重新排好，得到的都是干扰项。

真题练习

本篇涉及的真题（11题）

2012Q52分2016Q72分2011Q82分2026Q62分2013Q112分2021Q102分2021Q4115分2023Q4113分2014Q52分2021Q42分2026Q42分