1. 四向链表到底是个什么东西先把概念说清楚。四向链表英文一般叫 Quadruple Linked List 或者 Four-way Linked List本质上是一种每个节点持有四个指针的链式结构。最常见的定义是每个节点同时拥有上、下、左、右四个方向的指针分别指向相邻的四个节点。它和双向链表prev/next最大的区别在于双向链表只在一维上串联而四向链表在二维平面上建立了连接关系。你可以把它想象成一张稀疏矩阵或者网格地图。每个节点就是地图上的一个格子四个指针就是通往上下左右四个邻居的路。这种结构在需要表达二维邻接关系的场景里非常有用比如棋盘类游戏的状态表示、图像处理中的像素邻域关系、迷宫寻路算法中的节点建模以及某些稀疏矩阵的存储方案。那为什么不用二维数组呢因为二维数组是稠密的不管你有没有数据空间都得先分配好。而四向链表是稀疏的只有实际存在的节点才会占用内存节点之间的连接通过指针动态建立。当你的二维数据非常稀疏、或者节点数量动态变化的时候四向链表的优势就体现出来了。不过话说回来四向链表也有它自己的麻烦。指针多了维护成本就高。插入一个节点你可能需要同时修改四个方向的邻居指针删除一个节点同样要处理四个方向的断链和重连。稍有不慎就会出现悬空指针或者环形引用。这也是为什么很多人在实现四向链表的时候写着写着就乱了。提示四向链表的核心难点不在创建而在维护。创建只是搭骨架维护才是真正考验你对指针理解深度的地方。我见过不少初学者一上来就急着写遍历代码结果链表本身都没建对遍历出来的结果自然一塌糊涂。所以这篇文章我会从创建开始一步步把四向链表的完整实现讲透包括打印预览、遍历策略以及最关键的——从任意节点出发遍历整个链表且不重复。2. 节点结构设计与创建逻辑2.1 四个指针的命名与语义约定在动手写代码之前必须先约定好四个指针的命名和语义。这不是小事命名混乱是后期调试噩梦的根源。我推荐用 up、down、left、right 这四个名字语义直观不容易搞混。typedef struct QuadNode { int data; // 节点存储的数据 struct QuadNode* up; // 上邻居 struct QuadNode* down; // 下邻居 struct QuadNode* left; // 左邻居 struct QuadNode* right; // 右邻居 } QuadNode;如果你用的是 Java 或者 Python思路一样只是把指针换成引用而已。用泛型的话把 int 换成泛型参数 T 就行。public class QuadNodeT { T data; QuadNodeT up; QuadNodeT down; QuadNodeT left; QuadNodeT right; public QuadNode(T data) { this.data data; this.up null; this.down null; this.left null; this.right null; } }这里有一个设计决策需要解释为什么用四个独立的指针而不是用一个指针数组QuadNode* neighbors[4]两种方式都能工作但独立指针的可读性更好代码里写node-up比写node-neighbors[0]要清晰得多。当然如果你需要循环处理四个方向数组会更方便。我的建议是如果四个方向的逻辑差异较大用独立指针如果需要统一遍历四个方向用数组加枚举索引。2.2 从网格构建四向链表创建四向链表最直观的方式是从一个二维网格开始。假设我们有一个 m 行 n 列的网格每个格子对应一个节点然后按行列关系把指针连起来。QuadNode* createGrid(int rows, int cols) { // 先分配所有节点 QuadNode** grid (QuadNode**)malloc(rows * sizeof(QuadNode*)); for (int i 0; i rows; i) { grid[i] (QuadNode*)malloc(cols * sizeof(QuadNode)); for (int j 0; j cols; j) { grid[i][j].data i * cols j; grid[i][j].up NULL; grid[i][j].down NULL; grid[i][j].left NULL; grid[i][j].right NULL; } } // 建立四向连接 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (i 0) grid[i][j].up grid[i-1][j]; if (i rows - 1) grid[i][j].down grid[i1][j]; if (j 0) grid[i][j].left grid[i][j-1]; if (j cols - 1) grid[i][j].right grid[i][j1]; } } return grid[0][0]; // 返回左上角节点作为入口 }这段代码的逻辑很直接第一轮循环分配内存并初始化第二轮循环建立连接。注意边界处理——第一行没有上邻居最后一行没有下邻居第一列没有左邻居最后一列没有右邻居。这些边界节点的对应指针保持为 NULL。但这里有个坑上面这种写法是一次性分配一整块连续内存grid[i]和grid[i1]之间的地址是连续的。这在某些场景下没问题但如果你需要动态增删节点连续内存就不合适了。动态场景下每个节点应该独立 malloc。QuadNode* createNode(int data) { QuadNode* node (QuadNode*)malloc(sizeof(QuadNode)); node-data data; node-up node-down node-left node-right NULL; return node; }然后在需要的时候逐个创建并手动连接。这种方式更灵活但维护成本也更高因为你需要自己追踪所有已创建的节点否则容易内存泄漏。2.3 动态插入节点时的指针维护往已有的四向链表里插入一个新节点是最容易出错的操作。假设你要在节点 A 的右边插入新节点 B你需要做四件事B 的 left 指向 AB 的 right 指向 A 原来的 right记为 CA 的 right 指向 B如果 C 不为 NULLC 的 left 指向 Bvoid insertRight(QuadNode* a, QuadNode* b) { if (a NULL || b NULL) return; QuadNode* c a-right; b-left a; b-right c; a-right b; if (c ! NULL) { c-left b; } }看起来简单但实际项目中插入操作往往涉及上下方向的联动。比如你在一行中间插入了一个节点那这个节点上方的节点和下方的节点是否也需要对应调整这取决于你的业务逻辑。如果四向链表表示的是一个规则的网格那插入一个节点意味着整行或整列都要调整这时候就需要更复杂的批量操作。注意每次插入或删除操作后建议立即做一次完整性校验——检查每个节点的四个指针是否自洽。比如node-right-left应该等于nodenode-down-up应该等于node。这个校验能帮你尽早发现指针错误。3. 打印预览把链表可视化出来3.1 为什么打印预览比你想的重要很多人觉得打印链表就是调试用的临时手段不值得花时间。但我的经验恰恰相反一个设计良好的打印函数能帮你节省大量调试时间。四向链表的结构比单链表复杂得多光靠脑子想或者画图很容易出错有一个能随时输出当前链表状态的函数价值极高。打印四向链表的核心思路是按行遍历每行从左到右输出节点数据行与行之间用换行分隔。但问题是四向链表不一定是从左上角开始的规则网格它可能是一个不规则的形状。所以打印函数需要处理如何确定遍历的起点和范围这个问题。3.2 基于左上角起点的逐行打印最简单的情况是你知道链表的最左上角节点即没有 up 和 left 的节点从这个节点出发先一路向下走到最底部再逐行向右打印。void printGrid(QuadNode* topLeft) { if (topLeft NULL) return; // 先找到最左上角的节点 QuadNode* rowStart topLeft; while (rowStart-up ! NULL) rowStart rowStart-up; while (rowStart-left ! NULL) rowStart rowStart-left; // 逐行打印 QuadNode* rowNode rowStart; while (rowNode ! NULL) { QuadNode* colNode rowNode; while (colNode ! NULL) { printf(%4d, colNode-data); colNode colNode-right; } printf(\n); rowNode rowNode-down; } }这段代码的逻辑是先定位到最左上角然后外层循环沿 down 方向逐行移动内层循环沿 right 方向逐个打印。输出效果就是一个整齐的矩阵。但这里有个隐患如果链表不是规则网格某一行的节点数和其他行不一样打印出来就会参差不齐。对于不规则链表你需要更灵活的打印策略比如按坐标定位输出或者用递归方式逐层打印。3.3 处理不规则形状的打印方案不规则四向链表的打印我推荐用递归加访问标记的方式。核心思路是从任意一个节点出发递归访问它的四个邻居同时记录每个节点的深度和横向位置最后按位置排序输出。void printIrregular(QuadNode* node, int row, int col, int* minRow, int* maxRow, int* minCol, int* maxCol, HashMap* visited) { if (node NULL) return; if (contains(visited, node)) return; add(visited, node); // 更新边界 if (row *minRow) *minRow row; if (row *maxRow) *maxRow row; if (col *minCol) *minCol col; if (col *maxCol) *maxCol col; // 记录节点位置 recordPosition(node, row, col); // 递归四个方向 printIrregular(node-up, row - 1, col, minRow, maxRow, minCol, maxCol, visited); printIrregular(node-down, row 1, col, minRow, maxRow, minCol, maxCol, visited); printIrregular(node-left, row, col - 1, minRow, maxRow, minCol, maxCol, visited); printIrregular(node-right, row, col 1, minRow, maxRow, minCol, maxCol, visited); }这个方案的好处是通用性强不管链表是什么形状都能处理。代价是需要额外的空间来记录访问状态和节点位置。在实际项目中如果链表规模不大几百个节点以内这个方案完全够用。4. 遍历策略从任意节点出发走遍全图4.1 四向链表遍历的本质是图遍历这是整篇文章最核心的部分。四向链表从遍历的角度看本质上就是一个无向图——每个节点最多有四个邻居节点之间的连接是双向的。所以遍历四向链表本质上就是图的遍历问题。既然是图遍历那就绕不开两个经典算法深度优先搜索DFS和广度优先搜索BFS。这两个算法都能实现从任意节点出发遍历整个链表且不重复的目标区别在于访问顺序不同。DFS 用栈递归或显式栈实现沿着一个方向一直走到底再回溯。BFS 用队列实现先访问所有直接邻居再访问邻居的邻居一层层往外扩展。那选哪个取决于你的需求。如果你需要按距离层次处理节点用 BFS如果你只是需要遍历所有节点DFS 更简洁。在四向链表的场景下DFS 的递归写法最直观但如果链表很深比如几万个节点递归可能导致栈溢出这时候需要改成显式栈的迭代写法。4.2 用访问标记避免重复遍历不管用 DFS 还是 BFS不重复的关键都在于访问标记。每访问一个节点就把它标记为已访问后续再遇到这个节点时直接跳过。标记的方式有几种哈希表用节点的内存地址作为 key通用性最强但需要额外的哈希表空间。节点内置标记位在节点结构里加一个visited字段最省事但会污染节点结构而且遍历完后需要重置。外部数组如果节点是连续分配的可以用索引来标记效率最高但只适用于特定场景。我一般推荐用哈希表因为最通用不依赖节点的内存布局。在 C 语言里可以用一个简单的开放寻址哈希表在 Java 里直接用 HashSet在 Python 里用 set。// 用哈希集合记录已访问节点 typedef struct { QuadNode** buckets; int capacity; int size; } HashSet; int hashNode(QuadNode* node, int capacity) { return ((unsigned long)node / sizeof(QuadNode)) % capacity; } int contains(HashSet* set, QuadNode* node) { int idx hashNode(node, set-capacity); while (set-buckets[idx] ! NULL) { if (set-buckets[idx] node) return 1; idx (idx 1) % set-capacity; } return 0; } void add(HashSet* set, QuadNode* node) { int idx hashNode(node, set-capacity); while (set-buckets[idx] ! NULL) { if (set-buckets[idx] node) return; idx (idx 1) % set-capacity; } set-buckets[idx] node; set-size; }4.3 DFS 实现递归与迭代两种写法先看递归版本最简洁void dfsTraverse(QuadNode* node, HashSet* visited, void (*visit)(QuadNode*)) { if (node NULL) return; if (contains(visited, node)) return; add(visited, node); visit(node); dfsTraverse(node-up, visited, visit); dfsTraverse(node-down, visited, visit); dfsTraverse(node-left, visited, visit); dfsTraverse(node-right, visited, visit); }四行递归调用对应四个方向。逻辑清晰代码短。但递归深度等于最长路径长度如果链表是一条长链比如一万个节点排成一条线递归深度就是一万很可能栈溢出。迭代版本用显式栈void dfsTraverseIterative(QuadNode* start, HashSet* visited, void (*visit)(QuadNode*)) { if (start NULL) return; QuadNode** stack (QuadNode**)malloc(10000 * sizeof(QuadNode*)); int top 0; stack[top] start; while (top 0) { QuadNode* node stack[--top]; if (node NULL || contains(visited, node)) continue; add(visited, node); visit(node); // 四个方向入栈顺序无所谓 if (node-up) stack[top] node-up; if (node-down) stack[top] node-down; if (node-left) stack[top] node-left; if (node-right) stack[top] node-right; } free(stack); }迭代版本不会栈溢出但需要手动管理栈空间。实际项目中如果链表规模可控递归版本更省事如果规模不确定用迭代版本更安全。4.4 BFS 实现与层序输出BFS 用队列代码结构类似void bfsTraverse(QuadNode* start, HashSet* visited, void (*visit)(QuadNode*)) { if (start NULL) return; QuadNode** queue (QuadNode**)malloc(10000 * sizeof(QuadNode*)); int front 0, rear 0; queue[rear] start; add(visited, start); while (front rear) { QuadNode* node queue[front]; visit(node); QuadNode* neighbors[4] {node-up, node-down, node-left, node-right}; for (int i 0; i 4; i) { if (neighbors[i] ! NULL !contains(visited, neighbors[i])) { add(visited, neighbors[i]); queue[rear] neighbors[i]; } } } free(queue); }BFS 的一个天然优势是它按距离层次访问节点。从起点出发距离为 1 的节点先访问然后是距离为 2 的以此类推。如果你需要按层输出类似树的层序遍历BFS 是天然的选择。void bfsLevelOrder(QuadNode* start, HashSet* visited) { if (start NULL) return; QuadNode** queue (QuadNode**)malloc(10000 * sizeof(QuadNode*)); int front 0, rear 0; queue[rear] start; add(visited, start); int level 0; while (front rear) { int levelSize rear - front; printf(Level %d: , level); for (int i 0; i levelSize; i) { QuadNode* node queue[front]; printf(%d , node-data); QuadNode* neighbors[4] {node-up, node-down, node-left, node-right}; for (int j 0; j 4; j) { if (neighbors[j] ! NULL !contains(visited, neighbors[j])) { add(visited, neighbors[j]); queue[rear] neighbors[j]; } } } printf(\n); level; } free(queue); }这段代码在标准 BFS 的基础上增加了层的概念。每次处理完当前队列中的所有节点即当前层的所有节点再进入下一层。输出效果就是按距离分层的。5. 从任意节点出发的完整遍历实战5.1 为什么任意节点出发是个真需求在实际项目中你往往不能假设自己总是从左上角或者头节点开始操作。比如在一个棋盘游戏里玩家可能点击了棋盘中间的某个格子你需要从这个格子出发找到所有与它连通的区域。又比如在图像处理中你从某个像素点开始做区域生长需要遍历所有相邻的相似像素。这些场景的共同点是起点是动态的不固定。所以遍历算法必须支持从任意节点出发。好消息是DFS 和 BFS 天然支持任意起点——你只需要把起点传进去就行。真正需要注意的是从任意节点出发时如何确保遍历到的是整个链表而不是链表的一部分。这里有一个前提条件四向链表必须是连通的。如果链表本身不连通存在孤立的子图那从任意节点出发只能遍历到该节点所在的连通分量无法到达其他分量。这是图论的基本结论不是算法能解决的问题。提示如果你的四向链表可能不连通那遍历整个链表这个需求本身就需要重新定义。你需要在遍历完一个连通分量后找到未访问的节点从那里开始新一轮遍历直到所有节点都被访问。5.2 完整代码从任意节点出发的全遍历下面是一个完整的实现包含从任意节点出发、遍历所有连通分量、不重复访问所有节点的逻辑void traverseAll(QuadNode* anyNode, HashSet* visited, void (*visit)(QuadNode*)) { // 第一步从给定节点出发遍历其所在的连通分量 dfsTraverseIterative(anyNode, visited, visit); // 第二步如果链表不连通需要找到未访问的节点继续遍历 // 这一步需要你有一个所有节点的列表或者能够从某个已知节点 // 遍历到所有节点。如果链表是连通的这一步可以省略。 }如果链表是连通的大多数四向链表场景都是连通的那上面的第一步就够了。从任意节点出发DFS 或 BFS 会自动走遍所有节点。让我用一个完整的例子来演示。假设我们有一个 3x4 的网格从中间的节点 (1,1) 出发遍历int main() { // 创建 3x4 网格 QuadNode* topLeft createGrid(3, 4); // 找到中间的节点 (1,1) QuadNode* start topLeft; for (int i 0; i 1; i) start start-down; for (int j 0; j 1; j) start start-right; printf(Start from node: %d\n, start-data); // 初始化访问集合 HashSet* visited createHashSet(100); // 从中间节点出发遍历 printf(DFS traversal: ); dfsTraverseIterative(start, visited, printNode); printf(\n); // 重置访问集合用 BFS 再遍历一次 clearHashSet(visited); printf(BFS traversal: ); bfsTraverse(start, visited, printNode); printf(\n); return 0; }输出结果会显示从节点 5即 (1,1) 位置出发访问了所有 12 个节点且每个节点只访问一次。5.3 遍历顺序的差异与选择依据DFS 和 BFS 的输出顺序差异很大。对于上面的 3x4 网格从 (1,1) 出发DFS 可能会输出5, 1, 0, 4, 8, 9, 10, 11, 7, 6, 2, 3取决于四个方向的入栈顺序BFS 可能会输出5, 1, 4, 6, 9, 0, 2, 8, 10, 3, 7, 11按距离层次两种顺序都是正确的只是访问次序不同。选择哪个取决于你的业务需求需求场景推荐算法原因判断连通性DFS只要能走通就行DFS 代码更简洁按距离处理BFSBFS 天然按距离分层寻找最短路径BFSBFS 第一次到达目标时就是最短路径拓扑排序类需求DFSDFS 的后序遍历有拓扑性质内存受限DFSDFS 栈深度通常小于 BFS 队列宽度避免深递归BFSBFS 用队列不受递归深度限制5.4 性能分析与常见优化四向链表遍历的时间复杂度是 O(V E)其中 V 是节点数E 是边数。对于四向链表每个节点最多有 4 条边所以 E ≤ 4V总时间复杂度是 O(V)。这是最优的因为每个节点至少要被访问一次。空间复杂度取决于算法DFS 递归O(V) 栈空间最坏情况DFS 迭代O(V) 显式栈空间BFSO(V) 队列空间访问标记O(V) 哈希表空间优化的方向主要有两个第一减少哈希表开销。如果节点是连续分配的可以用节点索引代替指针哈希。比如createGrid分配的节点是连续的可以用(node - base) / sizeof(QuadNode)作为索引用一个 bit 数组来标记访问状态空间占用从 O(V) 个指针降到 O(V/8) 个字节。第二提前终止。如果你只需要找到某个特定节点不需要遍历全部可以在访问到目标节点时立即返回。DFS 和 BFS 都支持这种优化。int dfsSearch(QuadNode* node, HashSet* visited, int target) { if (node NULL) return 0; if (contains(visited, node)) return 0; add(visited, node); if (node-data target) return 1; // 找到了立即返回 if (dfsSearch(node-up, visited, target)) return 1; if (dfsSearch(node-down, visited, target)) return 1; if (dfsSearch(node-left, visited, target)) return 1; if (dfsSearch(node-right, visited, target)) return 1; return 0; }这种提前终止在搜索场景下能大幅减少访问节点数平均情况下可能只需要访问一小部分节点就能找到目标。6. 踩过的坑与实战经验6.1 指针未初始化导致的随机崩溃这是最常见的坑。malloc分配的内存不会自动清零如果你忘了把四个指针初始化为 NULL它们就是随机值。后续遍历时访问这些随机指针轻则读到垃圾数据重则直接段错误。我自己的习惯是每次malloc之后立即用memset清零或者用calloc代替malloc。QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); // calloc 会自动把内存清零四个指针都是 NULL这个习惯能帮你避免大量低级错误。多花的那一点点性能和调试崩溃花的时间比起来完全不值一提。6.2 环形引用导致的无限递归四向链表的指针是双向的A 的 right 指向 BB 的 left 指向 A。如果你在遍历时忘了加访问标记或者访问标记的逻辑有 bug就会在 A 和 B 之间无限循环。更隐蔽的情况是访问标记加在了错误的位置。比如你在递归调用之后才标记那在递归调用之前就已经重复访问了。// 错误写法标记太晚 void dfsWrong(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; dfsWrong(node-up, visited); // 这里递归时 node 还没被标记 dfsWrong(node-down, visited); dfsWrong(node-left, visited); dfsWrong(node-right, visited); add(visited, node); // 标记太晚了 } // 正确写法进入节点时立即标记 void dfsCorrect(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; add(visited, node); // 立即标记 dfsCorrect(node-up, visited); dfsCorrect(node-down, visited); dfsCorrect(node-left, visited); dfsCorrect(node-right, visited); }这个细节看起来微不足道但实际调试时能让你抓狂很久。我的建议是把标记作为访问节点的第一个动作养成肌肉记忆。6.3 删除节点时的断链顺序删除四向链表中的节点比插入更复杂。你需要处理四个方向的邻居而且断链的顺序很重要。如果顺序不对可能会丢失对其他节点的引用。假设要删除节点 BB 的四个邻居分别是 U上、D下、L左、R右。正确的断链顺序是先让 U 的 down 指向 D跳过 B再让 D 的 up 指向 U让 L 的 right 指向 R让 R 的 left 指向 L最后释放 B 的内存void removeNode(QuadNode* node) { if (node NULL) return; // 处理上下方向 if (node-up ! NULL) node-up-down node-down; if (node-down ! NULL) node-down-up node-up; // 处理左右方向 if (node-left ! NULL) node-left-right node-right; if (node-right ! NULL) node-right-left node-left; // 最后释放自己 free(node); }注意这里假设删除节点后上下邻居直接相连左右邻居也直接相连。如果你的业务逻辑不是这样比如删除后需要保持某种特殊结构那断链逻辑需要相应调整。注意删除节点后原来指向该节点的所有外部引用都会变成悬空指针。如果你的代码里还有其他地方持有这个节点的指针必须同步清理否则后续访问会出问题。6.4 打印预览时的对齐问题打印四向链表时如果节点数据的宽度不一致比如有的是 1 位数有的是 3 位数输出会参差不齐。解决办法是用固定宽度格式化输出printf(%4d, node-data); // 每个数字占 4 个字符宽度右对齐如果数据是字符串可以用%-10s左对齐或者%10s右对齐。关键是统一宽度让输出看起来整齐。另外如果链表很大比如 100x100直接打印会刷屏。这时候可以加一个范围限制只打印指定区域void printRegion(QuadNode* topLeft, int startRow, int endRow, int startCol, int endCol) { // 先移动到起始行 QuadNode* rowNode topLeft; for (int i 0; i startRow rowNode ! NULL; i) { rowNode rowNode-down; } for (int i startRow; i endRow rowNode ! NULL; i) { QuadNode* colNode rowNode; for (int j 0; j startCol colNode ! NULL; j) { colNode colNode-right; } for (int j startCol; j endCol colNode ! NULL; j) { printf(%4d, colNode-data); colNode colNode-right; } printf(\n); rowNode rowNode-down; } }这个函数只打印指定矩形区域内的节点对于大链表调试非常实用。6.5 泛型实现中的类型擦除问题如果你用 Java 泛型来实现四向链表需要注意类型擦除带来的限制。Java 的泛型在运行时会被擦除你不能用new T[]来创建泛型数组也不能用instanceof T来判断类型。public class QuadNodeT { T data; QuadNodeT up, down, left, right; // 错误不能直接创建泛型数组 // QuadNodeT[] neighbors new QuadNodeT[4]; // 正确用通配符或者强制转换 SuppressWarnings(unchecked) QuadNodeT[] neighbors (QuadNodeT[]) new QuadNode[4]; }在 C 里用模板就没这个问题因为 C 的模板是编译期展开的每个类型都会生成独立的代码。但代价是编译后的二进制体积会变大。选择哪种泛型方案取决于你的项目需求。如果追求运行效率C 模板更好如果追求开发效率和跨平台Java 泛型更方便。7. 四向链表与其他数据结构的对比选型7.1 四向链表 vs 双向链表 vs 十字链表特性双向链表四向链表十字链表指针数量244维度一维二维二维适用场景线性序列网格、邻接关系稀疏矩阵插入复杂度O(1)O(1)O(1)遍历复杂度O(n)O(V)O(V)内存开销低中中高十字链表是四向链表的一个变种专门用于稀疏矩阵存储。它的每个节点有 right 和 down 两个指针分别指向同行和同列的下一个非零元素。和四向链表相比十字链表不存储 up 和 left 指针因为稀疏矩阵的遍历通常只需要向右和向下。如果你需要双向遍历既能向右也能向左既能向上也能向下四向链表更合适。如果只需要单向遍历十字链表更省内存。7.2 什么时候该用四向链表四向链表不是万能药它有明确的适用场景二维邻接关系节点之间的连接是上下左右四个方向且关系是双向的。动态增删节点数量会动态变化不适合用固定大小的二维数组。稀疏结构大部分位置没有节点用二维数组会浪费大量空间。需要双向遍历既需要从 A 走到 B也需要从 B 走回 A。如果你的场景不满足这些条件可能有更合适的数据结构。比如规则网格用二维数组就够了不需要四向链表。又比如只需要单向遍历用十字链表或者邻接表更省事。7.3 实际项目中的选型经验我在一个图像处理项目里用过四向链表来表示像素邻域关系。当时的场景是需要从某个种子像素出发找到所有颜色相近的连通区域。用四向链表的好处是每个像素节点只需要存储四个邻居指针不需要存储坐标信息内存占用比二维数组小很多尤其是图像大部分区域是背景的情况下。但后来发现四向链表的维护成本太高了。每次图像变化比如用户涂抹都需要更新大量节点的指针。最终我们改用了并查集加二维数组的方案虽然内存占用大一些但维护简单得多性能也更好。这个经验告诉我四向链表适合结构相对稳定、增删不频繁的场景。如果增删非常频繁维护指针的成本可能会超过它带来的好处。选型时一定要结合具体的操作频率来评估。8. 完整可运行的代码框架把前面所有的片段整合起来给出一个完整的、可直接编译运行的 C 语言实现框架#include stdio.h #include stdlib.h #include string.h // 节点定义 typedef struct QuadNode { int data; struct QuadNode* up; struct QuadNode* down; struct QuadNode* left; struct QuadNode* right; } QuadNode; // 创建节点 QuadNode* createNode(int data) { QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); node-data data; return node; } // 创建网格 QuadNode* createGrid(int rows, int cols) { QuadNode** grid (QuadNode**)malloc(rows * sizeof(QuadNode*)); for (int i 0; i rows; i) { grid[i] (QuadNode*)calloc(cols, sizeof(QuadNode)); for (int j 0; j cols; j) { grid[i][j].data i * cols j; } } for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (i 0) grid[i][j].up grid[i-1][j]; if (i rows - 1) grid[i][j].down grid[i1][j]; if (j 0) grid[i][j].left grid[i][j-1]; if (j cols - 1) grid[i][j].right grid[i][j1]; } } return grid[0][0]; } // 访问标记简化版用节点内置标记 // 实际项目中建议用哈希表这里为了代码简洁用内置标记 void resetVisited(QuadNode* topLeft, int rows, int cols) { QuadNode* rowNode topLeft; for (int i 0; i rows rowNode ! NULL; i) { QuadNode* colNode rowNode; for (int j 0; j cols colNode ! NULL; j) { colNode-data colNode-data; // 占位实际需要单独的 visited 字段 colNode colNode-right; } rowNode rowNode-down; } } // 打印网格 void printGrid(QuadNode* topLeft) { if (topLeft NULL) return; QuadNode* rowStart topLeft; while (rowStart-up ! NULL) rowStart rowStart-up; while (rowStart-left ! NULL) rowStart rowStart-left; QuadNode* rowNode rowStart; while (rowNode ! NULL) { QuadNode* colNode rowNode; while (colNode ! NULL) { printf(%4d, colNode-data); colNode colNode-right; } printf(\n); rowNode rowNode-down; } } // DFS 遍历用外部数组标记 void dfsTraverse(QuadNode* node, int* visited, int totalNodes, QuadNode* base, void (*visit)(QuadNode*)) { if (node NULL) return; int idx (int)(node - base); if (idx 0 || idx totalNodes) return; if (visited[idx]) return; visited[idx] 1; visit(node); dfsTraverse(node-up, visited, totalNodes, base, visit); dfsTraverse(node-down, visited, totalNodes, base, visit); dfsTraverse(node-left, visited, totalNodes, base, visit); dfsTraverse(node-right, visited, totalNodes, base, visit); } // BFS 遍历 void bfsTraverse(QuadNode* start, int* visited, int totalNodes, QuadNode* base, void (*visit)(QuadNode*)) { if (start NULL) return; QuadNode** queue (QuadNode**)malloc(totalNodes * sizeof(QuadNode*)); int front 0, rear 0; queue[rear] start; visited[(int)(start - base)] 1; while (front rear) { QuadNode* node queue[front]; visit(node); QuadNode* neighbors[4] {node-up, node-down, node-left, node-right}; for (int i 0; i 4; i) { if (neighbors[i] ! NULL) { int idx (int)(neighbors[i] - base); if (idx 0 idx totalNodes !visited[idx]) { visited[idx] 1; queue[rear] neighbors[i]; } } } } free(queue); } // 访问函数 void printNode(QuadNode* node) { printf(%d , node-data); } // 主函数 int main() { int rows 3, cols 4; int totalNodes rows * cols; QuadNode* topLeft createGrid(rows, cols); QuadNode* base topLeft; printf( Grid Preview \n); printGrid(topLeft); // 找到中间节点 (1,1) QuadNode* start topLeft; for (int i 0; i 1; i) start start-down; for (int j 0; j 1; j) start start-right; printf(\nStart node: %d\n, start-data); // DFS 遍历 int* visited (int*)calloc(totalNodes, sizeof(int)); printf(\nDFS: ); dfsTraverse(start, visited, totalNodes, base, printNode); printf(\n); // BFS 遍历 memset(visited, 0, totalNodes * sizeof(int)); printf(BFS: ); bfsTraverse(start, visited, totalNodes, base, printNode); printf(\n); free(visited); return 0; }这个框架可以直接编译运行输出会显示网格预览、DFS 遍历结果和 BFS 遍历结果。你可以基于这个框架扩展自己的业务逻辑。我在实际使用中发现把访问标记从节点内置字段改成外部数组虽然代码稍微复杂一点但好处是遍历完后不需要重置节点状态而且同一个链表可以同时进行多次不同目的的遍历互不干扰。这个设计决策在需要频繁遍历的场景下特别有价值。
