企业官网建设流程全解析

408数据结构的图这章，存储结构是每年最稳定的得分点之一。很多同学把邻接矩阵和邻接表背得滚瓜烂熟，但一看到十字链表和邻接多重表就开始打磕绊。原因很直接：这两个结构考的不是“背名字”，而是能不能说清指针怎么串、复杂度怎么算、面对题目能不能当场画出来。

这篇文章就把十字链表和邻接多重表从头拆到尾：节点长什么样、边怎么插入、和邻接表比到底好在哪、考试爱从哪个角度出题、30分钟内怎么复习完。不绕弯，直接进入正题。

1. 十字链表与邻接多重表是怎么考的

先看命题角度。408和自命题院校的真题中，这两个结构的考法集中在三类：

邻接矩阵和邻接表是“手感题”，十字链表和邻接多重表是“精确题”。前者可以靠理解混过去，后者必须把指针方向、链的顺序、每个域的语义全部落实。

2. 先分清图存储结构的整体定位

很多同学把十字链表和邻接多重表放在一起背，结果越背越混。先理清楚：四个结构各有明确的主场。

一句话记忆：有向图求入度麻烦，所以发明十字链表；无向图边存储重复，所以发明邻接多重表。

这个“动机”理解之后，后面所有细节都顺了。

3. 十字链表的存储结构

十字链表解决的是有向图的核心痛点：邻接表能快速得到某顶点的出边，但想找入边必须遍历整张表；逆邻接表反过来。十字链表把两种表合成一张，用指针把每条弧同时挂到两个维度上。

3.1 顶点节点

每个顶点对应一个节点，包含三个域：

typedef struct VexNode { VertexType data; // 顶点信息 ArcBox *firstin; // 指向第一条以该顶点为弧头的弧（入边） ArcBox *firstout; // 指向第一条以该顶点为弧尾的弧（出边） } VexNode;

关键理解：firstin管入边，firstout管出边。一个顶点有两条链，一条通向“指向我的弧”，一条通向“我指向的弧”。

3.2 弧节点

每条弧是一个节点，包含五个域：

typedef struct ArcBox { int tailvex; // 弧尾顶点下标 int headvex; // 弧头顶点下标 struct ArcBox *hlink; // 指向下一条与当前弧“弧头相同”的弧 struct ArcBox *tlink; // 指向下一条与当前弧“弧尾相同”的弧 InfoType *info; // 权值等其他信息 } ArcBox;

最容易混的就是hlink和tlink。记法：

• h → head → 弧头 →hlink串的是“到达同一个顶点”的弧。
• t → tail → 弧尾 →tlink串的是“从同一个顶点出发”的弧。

这两个指针让每条弧同时存在于两条链表中：在弧尾顶点的firstout链里有一个位置，在弧头顶点的firstin链里也有一个位置。这就是十字链表“一条弧出现一次，但逻辑上被两个维度共享”的含义。

4. 十字链表构建过程

背再多次定义，不如亲手插入几条弧。这里用一个有向图示例：

V0 → V1 V0 → V2 V2 → V1 V1 → V3

四个顶点，四条弧。按下标编号V0=0、V1=1、V2=2、V3=3。插入弧时统一用头插法。

第一步：插入弧A1 = <0, 1>。

• tailvex = 0，headvex = 1。
• 在顶点0的firstout链头插入A1：A1->tlink = V0.firstout，V0.firstout = A1。
• 在顶点1的firstin链头插入A1：A1->hlink = V1.firstin，V1.firstin = A1。

第二步：插入弧A2 = <0, 2>。

• tailvex = 0，headvex = 2。
• 顶点0：A2->tlink = A1，V0.firstout = A2。
• 顶点2：A2->hlink = NULL，V2.firstin = A2。

第三步：插入弧A3 = <2, 1>。

• tailvex = 2，headvex = 1。
• 顶点2：A3->tlink = NULL，V2.firstout = A3。
• 顶点1：A3->hlink = A1，V1.firstin = A3。

注意这里顶点1原来的firstin是A1，A3头插后，firstin变成A3，A3的hlink指向A1。

第四步：插入弧A4 = <1, 3>。

• tailvex = 1，headvex = 3。
• 顶点1：A4->tlink = NULL，V1.firstout = A4。
• 顶点3：A4->hlink = NULL，V3.firstin = A4。

最终结果如下：

弧节点内部指针汇总：

构建过程中最容易错的是这一步：挂firstin时也要头插，不是简单的追加。一旦漏掉旧链的衔接，后面的hlink顺序就全部错位。

5. 十字链表的三个复杂度结论

十字链表在考试里最大的价值是复杂度结论，不要只当普通链表记。

5.1 求入度和出度

求顶点v的出度，直接沿着v.firstout走一遍，数一下弧节点个数，复杂度O(d_out(v))。

求顶点v的入度，直接沿着v.firstin走一遍，复杂度O(d_in(v))。

对比邻接表：求有向图某顶点的入度，往往需要把全表扫一遍，最坏O(n+e)。十字链表把这个成本降到了“只看出边/入边链长”，这是它最大的卖点。

5.2 找邻接点

找顶点v的“出边邻接点”，沿着firstout链遍历，每个弧节点的headvex就是邻接点下标。找“入边邻接点”，沿着firstin链遍历，每个弧节点的tailvex就是邻接点下标。

复杂度同样是O(d)，不需要全图扫描。

5.3 空间复杂度

每个顶点一个顶点节点，每条弧一个弧节点，空间复杂度O(n+e)。

这里有一个常考的对比点：邻接矩阵是O(n²)，用十字链表存稀疏有向图，节省非常明显。

十字链表的判断句可以背成一句：既能找到以vi为尾的弧，也能找到以vi为头的弧。

6. 邻接多重表的存储结构

邻接多重表服务于无向图。无向图中如果用邻接表，每条边会在两个顶点的链表中各出现一次，比如边(u,v)，u的链表里存一个节点，v的链表里又存一个节点。删除一条边时要处理两个副本，非常麻烦。

邻接多重表的核心思路：每条边只保存一个节点，让两个顶点的指针都指向这个节点，节点内部用两个指针分别维护两条“依附链”。

6.1 顶点节点

typedef struct VexBox { VertexType data; // 顶点信息 EdgeBox *firstedge; // 指向第一条依附于该顶点的边 } VexBox;

顶点只有一个指针域，这一点和十字链表的双指针完全不同，是考场快速识别的依据。

6.2 边节点

typedef struct EdgeBox { int mark; // 访问标记 int ivex; // 边的第一个顶点下标 int jvex; // 边的第二个顶点下标 struct EdgeBox *ilink; // 指向依附于ivex的下一条边 struct EdgeBox *jlink; // 指向依附于jvex的下一条边 InfoType *info; // 权值等信息 } EdgeBox;

理解重点：

• ivex和jvex是这条边关联的两个顶点。
• ilink串的是“和当前边共享同一ivex的下一条边”。
• jlink串的是“和当前边共享同一jvex的下一条边”。

换句话说，一个边节点同时站在两条队伍里：一条队伍由“第一顶点相同”的边组成，一条队伍由“第二顶点相同”的边组成。顶点则通过firstedge进入其中一条队伍。

7. 邻接多重表构建过程

以三个顶点三条边的简单无向图为例：

0 —— 1 0 —— 2 1 —— 3

设边e1 = (0, 1)，边e2 = (0, 2)，边e3 = (1, 3)。插入时同样使用头插法。

第一步：插入边e1 = (0, 1)，设置ivex=0，jvex=1。

• 顶点0：e1->ilink = V0.firstedge，V0.firstedge = e1。
• 顶点1：e1->jlink = V1.firstedge，V1.firstedge = e1。

第二步：插入边e2 = (0, 2)，设置ivex=0，jvex=2。

• 顶点0：e2->ilink = e1，V0.firstedge = e2。
• 顶点2：e2->jlink = NULL，V2.firstedge = e2。

第三步：插入边e3 = (1, 3)，设置ivex=1，jvex=3。

• 顶点1：e3->ilink = e1，V1.firstedge = e3。
• 顶点3：e3->jlink = NULL，V3.firstedge = e3。

最终顶点链：

边节点指针汇总：

观察规律：每个顶点的firstedge链里，边的顺序和插入顺序相反。因为头插法，越后面插入的边越靠前。

再看一个关键细节：这条图里0、1两个顶点都有两条边。0的边链是e2→e1，1的边链是e3→e1，但底层只用了三个边节点。每条边只出现一次，却被两个顶点共享。这就是邻接多重表相对邻接表最大的优势。

8. 邻接多重表的核心结论

8.1 每条边只存一次

无向图的邻接表，每条边要存两份；邻接多重表，每条边只存一份。这是最常考的空间结论。空间复杂度O(n+e)。

8.2 求顶点的邻接边

求某个顶点的所有邻接边，直接遍历该顶点的firstedge链。每个边节点里，不等于当前顶点的那个下标就是邻接点。

对顶点0，遍历0的边链：e2(0, 2)给出邻接点2，e1(0, 1)给出邻接点1。整个过程只需要看当前顶点自己的链长，不需要全图扫描。

8.3 删除边方便

删除一条边时，只要找到这个边节点，把它从两个顶点的链中摘下即可。不用像邻接表那样同时处理两条链中的两份对称副本，也不容易出现删一半漏一半的情况。

8.4 适用场景

邻接多重表只适用于无向图。考题如果说“无向图存储，要求删除边操作方便”，优先选它。

9. 十字链表与邻接多重表的终极对比

把两张大表放一起，考场一眼定位：

选择题拿到一张存储结构图，第一件事不是背定义，而是数顶点节点的指针域：

• 两个指针域且名字带firstin/firstout，十字链表。
• 一个指针域firstedge，边节点里同时有ivex/jvex，邻接多重表。

10. 真题常见考法：简答题答题模板

如果考到简答题，不要写一堆散文。按“它是什么 -> 它用来解决什么 -> 复杂度多少”三段式回答，阅卷按点给分，这三点就是采分点。

十字链表简答题模板：

第一，十字链表是有向图的一种链式存储结构，在邻接表和逆邻接表的基础上，让每个弧节点同时处于两条链中。

第二，顶点同时维护firstin和firstout，因此既能快速找到以该顶点为弧尾的弧（出边），也能快速找到以该顶点为弧头的弧（入边），不需要扫描全表。

第三，建表时间O(n+e)，空间O(n+e)，适合存储稀疏有向图。

邻接多重表简答题模板：

第一，邻接多重表是无向图的一种链式存储结构，顶点只设firstedge指针，边节点同时包含两个顶点下标和两条链指针。

第二，每条无向边只保存一个边节点，由关联的两个顶点共享，避免了邻接表中边存储两份的问题，删除某条边时也只需要摘除一个节点。

第三，建表时间O(n+e)，空间O(n+e)，特别适合增删边频繁的无向图应用。

如果题目再深入一步，问“为什么邻接表求有向图入度慢”，补充一句：邻接表只记录了出边方向，求入度必须遍历所有顶点的边链表去统计指向该顶点的弧，最坏需要O(n+e)。

11. 30分钟冲刺速成方案

如果离考试没几天了，按下面这个节奏来：

前5分钟：背定位。

• 有向图入度难求，用十字链表。
• 无向图边存储重复且删除难，用邻接多重表。

中间10分钟：手画两个图。

• 随手画一个有向图，强制自己写出所有顶点的firstin和firstout链。
• 随手画一个无向图，强制自己写出所有顶点的firstedge链。
• 画完检查：每个弧/边节点是否同时挂在两条链里。

再10分钟：背复杂度。

• 十字链表求入度/出度O(d)，建表O(n+e)，空间O(n+e)。
• 邻接多重表找邻接点O(d)，建表O(n+e)，空间O(n+e)，每条边只存一次。

最后5分钟：默写两个简答题模板。

如果时间更紧，可以只画十字链表和邻接多重表各一个例子，其他内容靠上面的表复习。这两个结构一旦动手画过一遍，记忆效率远高于反复看概念。

12. 常见错误与自查表

考场和日常练习中最容易踩的坑，列成表格自查：

这里最隐蔽的是第一类和第三类错误。它们不是不会，而是考场读题太快，看到“十”或者“邻接”就开始默认成无向图或有向图。做题前先圈出题目第一句：有向图还是无向图，再动笔。

13. 考场遇到它，先做这三件事

复盘一下，十字链表和邻接多重表并没有想象中复杂。它们的难度只在于两条链交错，让第一次接触的人看不清楚“谁连着谁”。一旦亲手画过一张图，把弧节点和边节点的每个指针都落实到位，这两个结构就成了固定得分点。

考场做题顺序建议：

第一，判方向。有向图想十字链表，无向图想邻接多重表。

第二，认指针。顶点两个指针域是十字链表，顶点一个指针域且边节点带ivex/jvex是邻接多重表。

第三，写结论。构建复杂度O(n+e)，空间复杂度O(n+e)，求入度/出度或找邻接点只需要沿对应链走。

这套思路可以应对选择题、简答题和画图题。如果现在正复习到图这一章，建议立刻拿笔把第4节和第7节的例子重新画一遍，画完再去做历年真题里所有涉及十字链表和邻接多重表的题目，会有一种“怎么考都是这几板斧”的感觉。