建到遍歷：指針維護與DFS/BFS實戰(zhàn))
1. 四向鏈表到底是個什么東西先把概念說清楚。四向鏈表英文一般叫 Quadruple Linked List 或者 Four-way Linked List本質(zhì)上是一種每個節(jié)點持有四個指針的鏈?zhǔn)浇Y(jié)構(gòu)。最常見的定義是每個節(jié)點同時擁有上、下、左、右四個方向的指針分別指向相鄰的四個節(jié)點。它和雙向鏈表prev/next最大的區(qū)別在于雙向鏈表只在一維上串聯(lián)而四向鏈表在二維平面上建立了連接關(guān)系。你可以把它想象成一張稀疏矩陣或者網(wǎng)格地圖。每個節(jié)點就是地圖上的一個格子四個指針就是通往上下左右四個鄰居的路。這種結(jié)構(gòu)在需要表達(dá)二維鄰接關(guān)系的場景里非常有用比如棋盤類游戲的狀態(tài)表示、圖像處理中的像素鄰域關(guān)系、迷宮尋路算法中的節(jié)點建模以及某些稀疏矩陣的存儲方案。那為什么不用二維數(shù)組呢因為二維數(shù)組是稠密的不管你有沒有數(shù)據(jù)空間都得先分配好。而四向鏈表是稀疏的只有實際存在的節(jié)點才會占用內(nèi)存節(jié)點之間的連接通過指針動態(tài)建立。當(dāng)你的二維數(shù)據(jù)非常稀疏、或者節(jié)點數(shù)量動態(tài)變化的時候四向鏈表的優(yōu)勢就體現(xiàn)出來了。不過話說回來四向鏈表也有它自己的麻煩。指針多了維護成本就高。插入一個節(jié)點你可能需要同時修改四個方向的鄰居指針刪除一個節(jié)點同樣要處理四個方向的斷鏈和重連。稍有不慎就會出現(xiàn)懸空指針或者環(huán)形引用。這也是為什么很多人在實現(xiàn)四向鏈表的時候?qū)懼鴮懼蛠y了。提示四向鏈表的核心難點不在創(chuàng)建而在維護。創(chuàng)建只是搭骨架維護才是真正考驗?zāi)銓χ羔樌斫馍疃鹊牡胤?。我見過不少初學(xué)者一上來就急著寫遍歷代碼結(jié)果鏈表本身都沒建對遍歷出來的結(jié)果自然一塌糊涂。所以這篇文章我會從創(chuàng)建開始一步步把四向鏈表的完整實現(xiàn)講透包括打印預(yù)覽、遍歷策略以及最關(guān)鍵的——從任意節(jié)點出發(fā)遍歷整個鏈表且不重復(fù)。2. 節(jié)點結(jié)構(gòu)設(shè)計與創(chuàng)建邏輯2.1 四個指針的命名與語義約定在動手寫代碼之前必須先約定好四個指針的命名和語義。這不是小事命名混亂是后期調(diào)試噩夢的根源。我推薦用 up、down、left、right 這四個名字語義直觀不容易搞混。typedef struct QuadNode { int data; // 節(jié)點存儲的數(shù)據(jù) struct QuadNode* up; // 上鄰居 struct QuadNode* down; // 下鄰居 struct QuadNode* left; // 左鄰居 struct QuadNode* right; // 右鄰居 } QuadNode;如果你用的是 Java 或者 Python思路一樣只是把指針換成引用而已。用泛型的話把 int 換成泛型參數(shù) 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; } }這里有一個設(shè)計決策需要解釋為什么用四個獨立的指針而不是用一個指針數(shù)組QuadNode* neighbors[4]兩種方式都能工作但獨立指針的可讀性更好代碼里寫node-up比寫node-neighbors[0]要清晰得多。當(dāng)然如果你需要循環(huán)處理四個方向數(shù)組會更方便。我的建議是如果四個方向的邏輯差異較大用獨立指針如果需要統(tǒng)一遍歷四個方向用數(shù)組加枚舉索引。2.2 從網(wǎng)格構(gòu)建四向鏈表創(chuàng)建四向鏈表最直觀的方式是從一個二維網(wǎng)格開始。假設(shè)我們有一個 m 行 n 列的網(wǎng)格每個格子對應(yīng)一個節(jié)點然后按行列關(guān)系把指針連起來。QuadNode* createGrid(int rows, int cols) { // 先分配所有節(jié)點 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]; // 返回左上角節(jié)點作為入口 }這段代碼的邏輯很直接第一輪循環(huán)分配內(nèi)存并初始化第二輪循環(huán)建立連接。注意邊界處理——第一行沒有上鄰居最后一行沒有下鄰居第一列沒有左鄰居最后一列沒有右鄰居。這些邊界節(jié)點的對應(yīng)指針保持為 NULL。但這里有個坑上面這種寫法是一次性分配一整塊連續(xù)內(nèi)存grid[i]和grid[i1]之間的地址是連續(xù)的。這在某些場景下沒問題但如果你需要動態(tài)增刪節(jié)點連續(xù)內(nèi)存就不合適了。動態(tài)場景下每個節(jié)點應(yīng)該獨立 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; }然后在需要的時候逐個創(chuàng)建并手動連接。這種方式更靈活但維護成本也更高因為你需要自己追蹤所有已創(chuàng)建的節(jié)點否則容易內(nèi)存泄漏。2.3 動態(tài)插入節(jié)點時的指針維護往已有的四向鏈表里插入一個新節(jié)點是最容易出錯的操作。假設(shè)你要在節(jié)點 A 的右邊插入新節(jié)點 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; } }看起來簡單但實際項目中插入操作往往涉及上下方向的聯(lián)動。比如你在一行中間插入了一個節(jié)點那這個節(jié)點上方的節(jié)點和下方的節(jié)點是否也需要對應(yīng)調(diào)整這取決于你的業(yè)務(wù)邏輯。如果四向鏈表表示的是一個規(guī)則的網(wǎng)格那插入一個節(jié)點意味著整行或整列都要調(diào)整這時候就需要更復(fù)雜的批量操作。注意每次插入或刪除操作后建議立即做一次完整性校驗——檢查每個節(jié)點的四個指針是否自洽。比如node-right-left應(yīng)該等于nodenode-down-up應(yīng)該等于node。這個校驗?zāi)軒湍惚M早發(fā)現(xiàn)指針錯誤。3. 打印預(yù)覽把鏈表可視化出來3.1 為什么打印預(yù)覽比你想的重要很多人覺得打印鏈表就是調(diào)試用的臨時手段不值得花時間。但我的經(jīng)驗恰恰相反一個設(shè)計良好的打印函數(shù)能幫你節(jié)省大量調(diào)試時間。四向鏈表的結(jié)構(gòu)比單鏈表復(fù)雜得多光靠腦子想或者畫圖很容易出錯有一個能隨時輸出當(dāng)前鏈表狀態(tài)的函數(shù)價值極高。打印四向鏈表的核心思路是按行遍歷每行從左到右輸出節(jié)點數(shù)據(jù)行與行之間用換行分隔。但問題是四向鏈表不一定是從左上角開始的規(guī)則網(wǎng)格它可能是一個不規(guī)則的形狀。所以打印函數(shù)需要處理如何確定遍歷的起點和范圍這個問題。3.2 基于左上角起點的逐行打印最簡單的情況是你知道鏈表的最左上角節(jié)點即沒有 up 和 left 的節(jié)點從這個節(jié)點出發(fā)先一路向下走到最底部再逐行向右打印。void printGrid(QuadNode* topLeft) { if (topLeft NULL) return; // 先找到最左上角的節(jié)點 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; } }這段代碼的邏輯是先定位到最左上角然后外層循環(huán)沿 down 方向逐行移動內(nèi)層循環(huán)沿 right 方向逐個打印。輸出效果就是一個整齊的矩陣。但這里有個隱患如果鏈表不是規(guī)則網(wǎng)格某一行的節(jié)點數(shù)和其他行不一樣打印出來就會參差不齊。對于不規(guī)則鏈表你需要更靈活的打印策略比如按坐標(biāo)定位輸出或者用遞歸方式逐層打印。3.3 處理不規(guī)則形狀的打印方案不規(guī)則四向鏈表的打印我推薦用遞歸加訪問標(biāo)記的方式。核心思路是從任意一個節(jié)點出發(fā)遞歸訪問它的四個鄰居同時記錄每個節(jié)點的深度和橫向位置最后按位置排序輸出。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; // 記錄節(jié)點位置 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); }這個方案的好處是通用性強不管鏈表是什么形狀都能處理。代價是需要額外的空間來記錄訪問狀態(tài)和節(jié)點位置。在實際項目中如果鏈表規(guī)模不大幾百個節(jié)點以內(nèi)這個方案完全夠用。4. 遍歷策略從任意節(jié)點出發(fā)走遍全圖4.1 四向鏈表遍歷的本質(zhì)是圖遍歷這是整篇文章最核心的部分。四向鏈表從遍歷的角度看本質(zhì)上就是一個無向圖——每個節(jié)點最多有四個鄰居節(jié)點之間的連接是雙向的。所以遍歷四向鏈表本質(zhì)上就是圖的遍歷問題。既然是圖遍歷那就繞不開兩個經(jīng)典算法深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。這兩個算法都能實現(xiàn)從任意節(jié)點出發(fā)遍歷整個鏈表且不重復(fù)的目標(biāo)區(qū)別在于訪問順序不同。DFS 用棧遞歸或顯式棧實現(xiàn)沿著一個方向一直走到底再回溯。BFS 用隊列實現(xiàn)先訪問所有直接鄰居再訪問鄰居的鄰居一層層往外擴展。那選哪個取決于你的需求。如果你需要按距離層次處理節(jié)點用 BFS如果你只是需要遍歷所有節(jié)點DFS 更簡潔。在四向鏈表的場景下DFS 的遞歸寫法最直觀但如果鏈表很深比如幾萬個節(jié)點遞歸可能導(dǎo)致棧溢出這時候需要改成顯式棧的迭代寫法。4.2 用訪問標(biāo)記避免重復(fù)遍歷不管用 DFS 還是 BFS不重復(fù)的關(guān)鍵都在于訪問標(biāo)記。每訪問一個節(jié)點就把它標(biāo)記為已訪問后續(xù)再遇到這個節(jié)點時直接跳過。標(biāo)記的方式有幾種哈希表用節(jié)點的內(nèi)存地址作為 key通用性最強但需要額外的哈希表空間。節(jié)點內(nèi)置標(biāo)記位在節(jié)點結(jié)構(gòu)里加一個visited字段最省事但會污染節(jié)點結(jié)構(gòu)而且遍歷完后需要重置。外部數(shù)組如果節(jié)點是連續(xù)分配的可以用索引來標(biāo)記效率最高但只適用于特定場景。我一般推薦用哈希表因為最通用不依賴節(jié)點的內(nèi)存布局。在 C 語言里可以用一個簡單的開放尋址哈希表在 Java 里直接用 HashSet在 Python 里用 set。// 用哈希集合記錄已訪問節(jié)點 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 實現(xiàn)遞歸與迭代兩種寫法先看遞歸版本最簡潔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); }四行遞歸調(diào)用對應(yīng)四個方向。邏輯清晰代碼短。但遞歸深度等于最長路徑長度如果鏈表是一條長鏈比如一萬個節(jié)點排成一條線遞歸深度就是一萬很可能棧溢出。迭代版本用顯式棧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); }迭代版本不會棧溢出但需要手動管理?？臻g。實際項目中如果鏈表規(guī)?？煽剡f歸版本更省事如果規(guī)模不確定用迭代版本更安全。4.4 BFS 實現(xiàn)與層序輸出BFS 用隊列代碼結(jié)構(gòu)類似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 的一個天然優(yōu)勢是它按距離層次訪問節(jié)點。從起點出發(fā)距離為 1 的節(jié)點先訪問然后是距離為 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); }這段代碼在標(biāo)準(zhǔn) BFS 的基礎(chǔ)上增加了層的概念。每次處理完當(dāng)前隊列中的所有節(jié)點即當(dāng)前層的所有節(jié)點再進(jìn)入下一層。輸出效果就是按距離分層的。5. 從任意節(jié)點出發(fā)的完整遍歷實戰(zhàn)5.1 為什么任意節(jié)點出發(fā)是個真需求在實際項目中你往往不能假設(shè)自己總是從左上角或者頭節(jié)點開始操作。比如在一個棋盤游戲里玩家可能點擊了棋盤中間的某個格子你需要從這個格子出發(fā)找到所有與它連通的區(qū)域。又比如在圖像處理中你從某個像素點開始做區(qū)域生長需要遍歷所有相鄰的相似像素。這些場景的共同點是起點是動態(tài)的不固定。所以遍歷算法必須支持從任意節(jié)點出發(fā)。好消息是DFS 和 BFS 天然支持任意起點——你只需要把起點傳進(jìn)去就行。真正需要注意的是從任意節(jié)點出發(fā)時如何確保遍歷到的是整個鏈表而不是鏈表的一部分。這里有一個前提條件四向鏈表必須是連通的。如果鏈表本身不連通存在孤立的子圖那從任意節(jié)點出發(fā)只能遍歷到該節(jié)點所在的連通分量無法到達(dá)其他分量。這是圖論的基本結(jié)論不是算法能解決的問題。提示如果你的四向鏈表可能不連通那遍歷整個鏈表這個需求本身就需要重新定義。你需要在遍歷完一個連通分量后找到未訪問的節(jié)點從那里開始新一輪遍歷直到所有節(jié)點都被訪問。5.2 完整代碼從任意節(jié)點出發(fā)的全遍歷下面是一個完整的實現(xiàn)包含從任意節(jié)點出發(fā)、遍歷所有連通分量、不重復(fù)訪問所有節(jié)點的邏輯void traverseAll(QuadNode* anyNode, HashSet* visited, void (*visit)(QuadNode*)) { // 第一步從給定節(jié)點出發(fā)遍歷其所在的連通分量 dfsTraverseIterative(anyNode, visited, visit); // 第二步如果鏈表不連通需要找到未訪問的節(jié)點繼續(xù)遍歷 // 這一步需要你有一個所有節(jié)點的列表或者能夠從某個已知節(jié)點 // 遍歷到所有節(jié)點。如果鏈表是連通的這一步可以省略。 }如果鏈表是連通的大多數(shù)四向鏈表場景都是連通的那上面的第一步就夠了。從任意節(jié)點出發(fā)DFS 或 BFS 會自動走遍所有節(jié)點。讓我用一個完整的例子來演示。假設(shè)我們有一個 3x4 的網(wǎng)格從中間的節(jié)點 (1,1) 出發(fā)遍歷int main() { // 創(chuàng)建 3x4 網(wǎng)格 QuadNode* topLeft createGrid(3, 4); // 找到中間的節(jié)點 (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); // 從中間節(jié)點出發(fā)遍歷 printf(DFS traversal: ); dfsTraverseIterative(start, visited, printNode); printf(\n); // 重置訪問集合用 BFS 再遍歷一次 clearHashSet(visited); printf(BFS traversal: ); bfsTraverse(start, visited, printNode); printf(\n); return 0; }輸出結(jié)果會顯示從節(jié)點 5即 (1,1) 位置出發(fā)訪問了所有 12 個節(jié)點且每個節(jié)點只訪問一次。5.3 遍歷順序的差異與選擇依據(jù)DFS 和 BFS 的輸出順序差異很大。對于上面的 3x4 網(wǎng)格從 (1,1) 出發(fā)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按距離層次兩種順序都是正確的只是訪問次序不同。選擇哪個取決于你的業(yè)務(wù)需求需求場景推薦算法原因判斷連通性DFS只要能走通就行DFS 代碼更簡潔按距離處理BFSBFS 天然按距離分層尋找最短路徑BFSBFS 第一次到達(dá)目標(biāo)時就是最短路徑拓?fù)渑判蝾愋枨驞FSDFS 的后序遍歷有拓?fù)湫再|(zhì)內(nèi)存受限D(zhuǎn)FSDFS 棧深度通常小于 BFS 隊列寬度避免深遞歸BFSBFS 用隊列不受遞歸深度限制5.4 性能分析與常見優(yōu)化四向鏈表遍歷的時間復(fù)雜度是 O(V E)其中 V 是節(jié)點數(shù)E 是邊數(shù)。對于四向鏈表每個節(jié)點最多有 4 條邊所以 E ≤ 4V總時間復(fù)雜度是 O(V)。這是最優(yōu)的因為每個節(jié)點至少要被訪問一次。空間復(fù)雜度取決于算法DFS 遞歸O(V) ?？臻g最壞情況DFS 迭代O(V) 顯式?？臻gBFSO(V) 隊列空間訪問標(biāo)記O(V) 哈希表空間優(yōu)化的方向主要有兩個第一減少哈希表開銷。如果節(jié)點是連續(xù)分配的可以用節(jié)點索引代替指針哈希。比如createGrid分配的節(jié)點是連續(xù)的可以用(node - base) / sizeof(QuadNode)作為索引用一個 bit 數(shù)組來標(biāo)記訪問狀態(tài)空間占用從 O(V) 個指針降到 O(V/8) 個字節(jié)。第二提前終止。如果你只需要找到某個特定節(jié)點不需要遍歷全部可以在訪問到目標(biāo)節(jié)點時立即返回。DFS 和 BFS 都支持這種優(yōu)化。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; }這種提前終止在搜索場景下能大幅減少訪問節(jié)點數(shù)平均情況下可能只需要訪問一小部分節(jié)點就能找到目標(biāo)。6. 踩過的坑與實戰(zhàn)經(jīng)驗6.1 指針未初始化導(dǎo)致的隨機崩潰這是最常見的坑。malloc分配的內(nèi)存不會自動清零如果你忘了把四個指針初始化為 NULL它們就是隨機值。后續(xù)遍歷時訪問這些隨機指針輕則讀到垃圾數(shù)據(jù)重則直接段錯誤。我自己的習(xí)慣是每次malloc之后立即用memset清零或者用calloc代替malloc。QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); // calloc 會自動把內(nèi)存清零四個指針都是 NULL這個習(xí)慣能幫你避免大量低級錯誤。多花的那一點點性能和調(diào)試崩潰花的時間比起來完全不值一提。6.2 環(huán)形引用導(dǎo)致的無限遞歸四向鏈表的指針是雙向的A 的 right 指向 BB 的 left 指向 A。如果你在遍歷時忘了加訪問標(biāo)記或者訪問標(biāo)記的邏輯有 bug就會在 A 和 B 之間無限循環(huán)。更隱蔽的情況是訪問標(biāo)記加在了錯誤的位置。比如你在遞歸調(diào)用之后才標(biāo)記那在遞歸調(diào)用之前就已經(jīng)重復(fù)訪問了。// 錯誤寫法標(biāo)記太晚 void dfsWrong(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; dfsWrong(node-up, visited); // 這里遞歸時 node 還沒被標(biāo)記 dfsWrong(node-down, visited); dfsWrong(node-left, visited); dfsWrong(node-right, visited); add(visited, node); // 標(biāo)記太晚了 } // 正確寫法進(jìn)入節(jié)點時立即標(biāo)記 void dfsCorrect(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; add(visited, node); // 立即標(biāo)記 dfsCorrect(node-up, visited); dfsCorrect(node-down, visited); dfsCorrect(node-left, visited); dfsCorrect(node-right, visited); }這個細(xì)節(jié)看起來微不足道但實際調(diào)試時能讓你抓狂很久。我的建議是把標(biāo)記作為訪問節(jié)點的第一個動作養(yǎng)成肌肉記憶。6.3 刪除節(jié)點時的斷鏈順序刪除四向鏈表中的節(jié)點比插入更復(fù)雜。你需要處理四個方向的鄰居而且斷鏈的順序很重要。如果順序不對可能會丟失對其他節(jié)點的引用。假設(shè)要刪除節(jié)點 BB 的四個鄰居分別是 U上、D下、L左、R右。正確的斷鏈順序是先讓 U 的 down 指向 D跳過 B再讓 D 的 up 指向 U讓 L 的 right 指向 R讓 R 的 left 指向 L最后釋放 B 的內(nèi)存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); }注意這里假設(shè)刪除節(jié)點后上下鄰居直接相連左右鄰居也直接相連。如果你的業(yè)務(wù)邏輯不是這樣比如刪除后需要保持某種特殊結(jié)構(gòu)那斷鏈邏輯需要相應(yīng)調(diào)整。注意刪除節(jié)點后原來指向該節(jié)點的所有外部引用都會變成懸空指針。如果你的代碼里還有其他地方持有這個節(jié)點的指針必須同步清理否則后續(xù)訪問會出問題。6.4 打印預(yù)覽時的對齊問題打印四向鏈表時如果節(jié)點數(shù)據(jù)的寬度不一致比如有的是 1 位數(shù)有的是 3 位數(shù)輸出會參差不齊。解決辦法是用固定寬度格式化輸出printf(%4d, node-data); // 每個數(shù)字占 4 個字符寬度右對齊如果數(shù)據(jù)是字符串可以用%-10s左對齊或者%10s右對齊。關(guān)鍵是統(tǒng)一寬度讓輸出看起來整齊。另外如果鏈表很大比如 100x100直接打印會刷屏。這時候可以加一個范圍限制只打印指定區(qū)域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; } }這個函數(shù)只打印指定矩形區(qū)域內(nèi)的節(jié)點對于大鏈表調(diào)試非常實用。6.5 泛型實現(xiàn)中的類型擦除問題如果你用 Java 泛型來實現(xiàn)四向鏈表需要注意類型擦除帶來的限制。Java 的泛型在運行時會被擦除你不能用new T[]來創(chuàng)建泛型數(shù)組也不能用instanceof T來判斷類型。public class QuadNodeT { T data; QuadNodeT up, down, left, right; // 錯誤不能直接創(chuàng)建泛型數(shù)組 // QuadNodeT[] neighbors new QuadNodeT[4]; // 正確用通配符或者強制轉(zhuǎn)換 SuppressWarnings(unchecked) QuadNodeT[] neighbors (QuadNodeT[]) new QuadNode[4]; }在 C 里用模板就沒這個問題因為 C 的模板是編譯期展開的每個類型都會生成獨立的代碼。但代價是編譯后的二進(jìn)制體積會變大。選擇哪種泛型方案取決于你的項目需求。如果追求運行效率C 模板更好如果追求開發(fā)效率和跨平臺Java 泛型更方便。7. 四向鏈表與其他數(shù)據(jù)結(jié)構(gòu)的對比選型7.1 四向鏈表 vs 雙向鏈表 vs 十字鏈表特性雙向鏈表四向鏈表十字鏈表指針數(shù)量244維度一維二維二維適用場景線性序列網(wǎng)格、鄰接關(guān)系稀疏矩陣插入復(fù)雜度O(1)O(1)O(1)遍歷復(fù)雜度O(n)O(V)O(V)內(nèi)存開銷低中中高十字鏈表是四向鏈表的一個變種專門用于稀疏矩陣存儲。它的每個節(jié)點有 right 和 down 兩個指針分別指向同行和同列的下一個非零元素。和四向鏈表相比十字鏈表不存儲 up 和 left 指針因為稀疏矩陣的遍歷通常只需要向右和向下。如果你需要雙向遍歷既能向右也能向左既能向上也能向下四向鏈表更合適。如果只需要單向遍歷十字鏈表更省內(nèi)存。7.2 什么時候該用四向鏈表四向鏈表不是萬能藥它有明確的適用場景二維鄰接關(guān)系節(jié)點之間的連接是上下左右四個方向且關(guān)系是雙向的。動態(tài)增刪節(jié)點數(shù)量會動態(tài)變化不適合用固定大小的二維數(shù)組。稀疏結(jié)構(gòu)大部分位置沒有節(jié)點用二維數(shù)組會浪費大量空間。需要雙向遍歷既需要從 A 走到 B也需要從 B 走回 A。如果你的場景不滿足這些條件可能有更合適的數(shù)據(jù)結(jié)構(gòu)。比如規(guī)則網(wǎng)格用二維數(shù)組就夠了不需要四向鏈表。又比如只需要單向遍歷用十字鏈表或者鄰接表更省事。7.3 實際項目中的選型經(jīng)驗我在一個圖像處理項目里用過四向鏈表來表示像素鄰域關(guān)系。當(dāng)時的場景是需要從某個種子像素出發(fā)找到所有顏色相近的連通區(qū)域。用四向鏈表的好處是每個像素節(jié)點只需要存儲四個鄰居指針不需要存儲坐標(biāo)信息內(nèi)存占用比二維數(shù)組小很多尤其是圖像大部分區(qū)域是背景的情況下。但后來發(fā)現(xiàn)四向鏈表的維護成本太高了。每次圖像變化比如用戶涂抹都需要更新大量節(jié)點的指針。最終我們改用了并查集加二維數(shù)組的方案雖然內(nèi)存占用大一些但維護簡單得多性能也更好。這個經(jīng)驗告訴我四向鏈表適合結(jié)構(gòu)相對穩(wěn)定、增刪不頻繁的場景。如果增刪非常頻繁維護指針的成本可能會超過它帶來的好處。選型時一定要結(jié)合具體的操作頻率來評估。8. 完整可運行的代碼框架把前面所有的片段整合起來給出一個完整的、可直接編譯運行的 C 語言實現(xiàn)框架#include stdio.h #include stdlib.h #include string.h // 節(jié)點定義 typedef struct QuadNode { int data; struct QuadNode* up; struct QuadNode* down; struct QuadNode* left; struct QuadNode* right; } QuadNode; // 創(chuàng)建節(jié)點 QuadNode* createNode(int data) { QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); node-data data; return node; } // 創(chuàng)建網(wǎng)格 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]; } // 訪問標(biāo)記簡化版用節(jié)點內(nèi)置標(biāo)記 // 實際項目中建議用哈希表這里為了代碼簡潔用內(nèi)置標(biāo)記 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; } } // 打印網(wǎng)格 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 遍歷用外部數(shù)組標(biāo)記 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); } // 訪問函數(shù) void printNode(QuadNode* node) { printf(%d , node-data); } // 主函數(shù) 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); // 找到中間節(jié)點 (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; }這個框架可以直接編譯運行輸出會顯示網(wǎng)格預(yù)覽、DFS 遍歷結(jié)果和 BFS 遍歷結(jié)果。你可以基于這個框架擴展自己的業(yè)務(wù)邏輯。我在實際使用中發(fā)現(xiàn)把訪問標(biāo)記從節(jié)點內(nèi)置字段改成外部數(shù)組雖然代碼稍微復(fù)雜一點但好處是遍歷完后不需要重置節(jié)點狀態(tài)而且同一個鏈表可以同時進(jìn)行多次不同目的的遍歷互不干擾。這個設(shè)計決策在需要頻繁遍歷的場景下特別有價值。 四向鏈表從創(chuàng)建到遍歷：指針維護與DFS/BFS實戰(zhàn)
1. 四向鏈表到底是個什么東西先把概念說清楚。四向鏈表英文一般叫 Quadruple Linked List 或者 Four-way Linked List本質(zhì)上是一種每個節(jié)點持有四個指針的鏈?zhǔn)浇Y(jié)構(gòu)。最常見的定義是每個節(jié)點同時擁有上、下、左、右四個方向的指針分別指向相鄰的四個節(jié)點。它和雙向鏈表prev/next最大的區(qū)別在于雙向鏈表只在一維上串聯(lián)而四向鏈表在二維平面上建立了連接關(guān)系。你可以把它想象成一張稀疏矩陣或者網(wǎng)格地圖。每個節(jié)點就是地圖上的一個格子四個指針就是通往上下左右四個鄰居的路。這種結(jié)構(gòu)在需要表達(dá)二維鄰接關(guān)系的場景里非常有用比如棋盤類游戲的狀態(tài)表示、圖像處理中的像素鄰域關(guān)系、迷宮尋路算法中的節(jié)點建模以及某些稀疏矩陣的存儲方案。那為什么不用二維數(shù)組呢因為二維數(shù)組是稠密的不管你有沒有數(shù)據(jù)空間都得先分配好。而四向鏈表是稀疏的只有實際存在的節(jié)點才會占用內(nèi)存節(jié)點之間的連接通過指針動態(tài)建立。當(dāng)你的二維數(shù)據(jù)非常稀疏、或者節(jié)點數(shù)量動態(tài)變化的時候四向鏈表的優(yōu)勢就體現(xiàn)出來了。不過話說回來四向鏈表也有它自己的麻煩。指針多了維護成本就高。插入一個節(jié)點你可能需要同時修改四個方向的鄰居指針刪除一個節(jié)點同樣要處理四個方向的斷鏈和重連。稍有不慎就會出現(xiàn)懸空指針或者環(huán)形引用。這也是為什么很多人在實現(xiàn)四向鏈表的時候?qū)懼鴮懼蛠y了。提示四向鏈表的核心難點不在創(chuàng)建而在維護。創(chuàng)建只是搭骨架維護才是真正考驗?zāi)銓χ羔樌斫馍疃鹊牡胤?。我見過不少初學(xué)者一上來就急著寫遍歷代碼結(jié)果鏈表本身都沒建對遍歷出來的結(jié)果自然一塌糊涂。所以這篇文章我會從創(chuàng)建開始一步步把四向鏈表的完整實現(xiàn)講透包括打印預(yù)覽、遍歷策略以及最關(guān)鍵的——從任意節(jié)點出發(fā)遍歷整個鏈表且不重復(fù)。2. 節(jié)點結(jié)構(gòu)設(shè)計與創(chuàng)建邏輯2.1 四個指針的命名與語義約定在動手寫代碼之前必須先約定好四個指針的命名和語義。這不是小事命名混亂是后期調(diào)試噩夢的根源。我推薦用 up、down、left、right 這四個名字語義直觀不容易搞混。typedef struct QuadNode { int data; // 節(jié)點存儲的數(shù)據(jù) struct QuadNode* up; // 上鄰居 struct QuadNode* down; // 下鄰居 struct QuadNode* left; // 左鄰居 struct QuadNode* right; // 右鄰居 } QuadNode;如果你用的是 Java 或者 Python思路一樣只是把指針換成引用而已。用泛型的話把 int 換成泛型參數(shù) 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; } }這里有一個設(shè)計決策需要解釋為什么用四個獨立的指針而不是用一個指針數(shù)組QuadNode* neighbors[4]兩種方式都能工作但獨立指針的可讀性更好代碼里寫node-up比寫node-neighbors[0]要清晰得多。當(dāng)然如果你需要循環(huán)處理四個方向數(shù)組會更方便。我的建議是如果四個方向的邏輯差異較大用獨立指針如果需要統(tǒng)一遍歷四個方向用數(shù)組加枚舉索引。2.2 從網(wǎng)格構(gòu)建四向鏈表創(chuàng)建四向鏈表最直觀的方式是從一個二維網(wǎng)格開始。假設(shè)我們有一個 m 行 n 列的網(wǎng)格每個格子對應(yīng)一個節(jié)點然后按行列關(guān)系把指針連起來。QuadNode* createGrid(int rows, int cols) { // 先分配所有節(jié)點 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]; // 返回左上角節(jié)點作為入口 }這段代碼的邏輯很直接第一輪循環(huán)分配內(nèi)存并初始化第二輪循環(huán)建立連接。注意邊界處理——第一行沒有上鄰居最后一行沒有下鄰居第一列沒有左鄰居最后一列沒有右鄰居。這些邊界節(jié)點的對應(yīng)指針保持為 NULL。但這里有個坑上面這種寫法是一次性分配一整塊連續(xù)內(nèi)存grid[i]和grid[i1]之間的地址是連續(xù)的。這在某些場景下沒問題但如果你需要動態(tài)增刪節(jié)點連續(xù)內(nèi)存就不合適了。動態(tài)場景下每個節(jié)點應(yīng)該獨立 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; }然后在需要的時候逐個創(chuàng)建并手動連接。這種方式更靈活但維護成本也更高因為你需要自己追蹤所有已創(chuàng)建的節(jié)點否則容易內(nèi)存泄漏。2.3 動態(tài)插入節(jié)點時的指針維護往已有的四向鏈表里插入一個新節(jié)點是最容易出錯的操作。假設(shè)你要在節(jié)點 A 的右邊插入新節(jié)點 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; } }看起來簡單但實際項目中插入操作往往涉及上下方向的聯(lián)動。比如你在一行中間插入了一個節(jié)點那這個節(jié)點上方的節(jié)點和下方的節(jié)點是否也需要對應(yīng)調(diào)整這取決于你的業(yè)務(wù)邏輯。如果四向鏈表表示的是一個規(guī)則的網(wǎng)格那插入一個節(jié)點意味著整行或整列都要調(diào)整這時候就需要更復(fù)雜的批量操作。注意每次插入或刪除操作后建議立即做一次完整性校驗——檢查每個節(jié)點的四個指針是否自洽。比如node-right-left應(yīng)該等于nodenode-down-up應(yīng)該等于node。這個校驗?zāi)軒湍惚M早發(fā)現(xiàn)指針錯誤。3. 打印預(yù)覽把鏈表可視化出來3.1 為什么打印預(yù)覽比你想的重要很多人覺得打印鏈表就是調(diào)試用的臨時手段不值得花時間。但我的經(jīng)驗恰恰相反一個設(shè)計良好的打印函數(shù)能幫你節(jié)省大量調(diào)試時間。四向鏈表的結(jié)構(gòu)比單鏈表復(fù)雜得多光靠腦子想或者畫圖很容易出錯有一個能隨時輸出當(dāng)前鏈表狀態(tài)的函數(shù)價值極高。打印四向鏈表的核心思路是按行遍歷每行從左到右輸出節(jié)點數(shù)據(jù)行與行之間用換行分隔。但問題是四向鏈表不一定是從左上角開始的規(guī)則網(wǎng)格它可能是一個不規(guī)則的形狀。所以打印函數(shù)需要處理如何確定遍歷的起點和范圍這個問題。3.2 基于左上角起點的逐行打印最簡單的情況是你知道鏈表的最左上角節(jié)點即沒有 up 和 left 的節(jié)點從這個節(jié)點出發(fā)先一路向下走到最底部再逐行向右打印。void printGrid(QuadNode* topLeft) { if (topLeft NULL) return; // 先找到最左上角的節(jié)點 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; } }這段代碼的邏輯是先定位到最左上角然后外層循環(huán)沿 down 方向逐行移動內(nèi)層循環(huán)沿 right 方向逐個打印。輸出效果就是一個整齊的矩陣。但這里有個隱患如果鏈表不是規(guī)則網(wǎng)格某一行的節(jié)點數(shù)和其他行不一樣打印出來就會參差不齊。對于不規(guī)則鏈表你需要更靈活的打印策略比如按坐標(biāo)定位輸出或者用遞歸方式逐層打印。3.3 處理不規(guī)則形狀的打印方案不規(guī)則四向鏈表的打印我推薦用遞歸加訪問標(biāo)記的方式。核心思路是從任意一個節(jié)點出發(fā)遞歸訪問它的四個鄰居同時記錄每個節(jié)點的深度和橫向位置最后按位置排序輸出。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; // 記錄節(jié)點位置 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); }這個方案的好處是通用性強不管鏈表是什么形狀都能處理。代價是需要額外的空間來記錄訪問狀態(tài)和節(jié)點位置。在實際項目中如果鏈表規(guī)模不大幾百個節(jié)點以內(nèi)這個方案完全夠用。4. 遍歷策略從任意節(jié)點出發(fā)走遍全圖4.1 四向鏈表遍歷的本質(zhì)是圖遍歷這是整篇文章最核心的部分。四向鏈表從遍歷的角度看本質(zhì)上就是一個無向圖——每個節(jié)點最多有四個鄰居節(jié)點之間的連接是雙向的。所以遍歷四向鏈表本質(zhì)上就是圖的遍歷問題。既然是圖遍歷那就繞不開兩個經(jīng)典算法深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。這兩個算法都能實現(xiàn)從任意節(jié)點出發(fā)遍歷整個鏈表且不重復(fù)的目標(biāo)區(qū)別在于訪問順序不同。DFS 用棧遞歸或顯式棧實現(xiàn)沿著一個方向一直走到底再回溯。BFS 用隊列實現(xiàn)先訪問所有直接鄰居再訪問鄰居的鄰居一層層往外擴展。那選哪個取決于你的需求。如果你需要按距離層次處理節(jié)點用 BFS如果你只是需要遍歷所有節(jié)點DFS 更簡潔。在四向鏈表的場景下DFS 的遞歸寫法最直觀但如果鏈表很深比如幾萬個節(jié)點遞歸可能導(dǎo)致棧溢出這時候需要改成顯式棧的迭代寫法。4.2 用訪問標(biāo)記避免重復(fù)遍歷不管用 DFS 還是 BFS不重復(fù)的關(guān)鍵都在于訪問標(biāo)記。每訪問一個節(jié)點就把它標(biāo)記為已訪問后續(xù)再遇到這個節(jié)點時直接跳過。標(biāo)記的方式有幾種哈希表用節(jié)點的內(nèi)存地址作為 key通用性最強但需要額外的哈希表空間。節(jié)點內(nèi)置標(biāo)記位在節(jié)點結(jié)構(gòu)里加一個visited字段最省事但會污染節(jié)點結(jié)構(gòu)而且遍歷完后需要重置。外部數(shù)組如果節(jié)點是連續(xù)分配的可以用索引來標(biāo)記效率最高但只適用于特定場景。我一般推薦用哈希表因為最通用不依賴節(jié)點的內(nèi)存布局。在 C 語言里可以用一個簡單的開放尋址哈希表在 Java 里直接用 HashSet在 Python 里用 set。// 用哈希集合記錄已訪問節(jié)點 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 實現(xiàn)遞歸與迭代兩種寫法先看遞歸版本最簡潔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); }四行遞歸調(diào)用對應(yīng)四個方向。邏輯清晰代碼短。但遞歸深度等于最長路徑長度如果鏈表是一條長鏈比如一萬個節(jié)點排成一條線遞歸深度就是一萬很可能棧溢出。迭代版本用顯式棧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); }迭代版本不會棧溢出但需要手動管理?？臻g。實際項目中如果鏈表規(guī)?？煽剡f歸版本更省事如果規(guī)模不確定用迭代版本更安全。4.4 BFS 實現(xiàn)與層序輸出BFS 用隊列代碼結(jié)構(gòu)類似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 的一個天然優(yōu)勢是它按距離層次訪問節(jié)點。從起點出發(fā)距離為 1 的節(jié)點先訪問然后是距離為 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); }這段代碼在標(biāo)準(zhǔn) BFS 的基礎(chǔ)上增加了層的概念。每次處理完當(dāng)前隊列中的所有節(jié)點即當(dāng)前層的所有節(jié)點再進(jìn)入下一層。輸出效果就是按距離分層的。5. 從任意節(jié)點出發(fā)的完整遍歷實戰(zhàn)5.1 為什么任意節(jié)點出發(fā)是個真需求在實際項目中你往往不能假設(shè)自己總是從左上角或者頭節(jié)點開始操作。比如在一個棋盤游戲里玩家可能點擊了棋盤中間的某個格子你需要從這個格子出發(fā)找到所有與它連通的區(qū)域。又比如在圖像處理中你從某個像素點開始做區(qū)域生長需要遍歷所有相鄰的相似像素。這些場景的共同點是起點是動態(tài)的不固定。所以遍歷算法必須支持從任意節(jié)點出發(fā)。好消息是DFS 和 BFS 天然支持任意起點——你只需要把起點傳進(jìn)去就行。真正需要注意的是從任意節(jié)點出發(fā)時如何確保遍歷到的是整個鏈表而不是鏈表的一部分。這里有一個前提條件四向鏈表必須是連通的。如果鏈表本身不連通存在孤立的子圖那從任意節(jié)點出發(fā)只能遍歷到該節(jié)點所在的連通分量無法到達(dá)其他分量。這是圖論的基本結(jié)論不是算法能解決的問題。提示如果你的四向鏈表可能不連通那遍歷整個鏈表這個需求本身就需要重新定義。你需要在遍歷完一個連通分量后找到未訪問的節(jié)點從那里開始新一輪遍歷直到所有節(jié)點都被訪問。5.2 完整代碼從任意節(jié)點出發(fā)的全遍歷下面是一個完整的實現(xiàn)包含從任意節(jié)點出發(fā)、遍歷所有連通分量、不重復(fù)訪問所有節(jié)點的邏輯void traverseAll(QuadNode* anyNode, HashSet* visited, void (*visit)(QuadNode*)) { // 第一步從給定節(jié)點出發(fā)遍歷其所在的連通分量 dfsTraverseIterative(anyNode, visited, visit); // 第二步如果鏈表不連通需要找到未訪問的節(jié)點繼續(xù)遍歷 // 這一步需要你有一個所有節(jié)點的列表或者能夠從某個已知節(jié)點 // 遍歷到所有節(jié)點。如果鏈表是連通的這一步可以省略。 }如果鏈表是連通的大多數(shù)四向鏈表場景都是連通的那上面的第一步就夠了。從任意節(jié)點出發(fā)DFS 或 BFS 會自動走遍所有節(jié)點。讓我用一個完整的例子來演示。假設(shè)我們有一個 3x4 的網(wǎng)格從中間的節(jié)點 (1,1) 出發(fā)遍歷int main() { // 創(chuàng)建 3x4 網(wǎng)格 QuadNode* topLeft createGrid(3, 4); // 找到中間的節(jié)點 (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); // 從中間節(jié)點出發(fā)遍歷 printf(DFS traversal: ); dfsTraverseIterative(start, visited, printNode); printf(\n); // 重置訪問集合用 BFS 再遍歷一次 clearHashSet(visited); printf(BFS traversal: ); bfsTraverse(start, visited, printNode); printf(\n); return 0; }輸出結(jié)果會顯示從節(jié)點 5即 (1,1) 位置出發(fā)訪問了所有 12 個節(jié)點且每個節(jié)點只訪問一次。5.3 遍歷順序的差異與選擇依據(jù)DFS 和 BFS 的輸出順序差異很大。對于上面的 3x4 網(wǎng)格從 (1,1) 出發(fā)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按距離層次兩種順序都是正確的只是訪問次序不同。選擇哪個取決于你的業(yè)務(wù)需求需求場景推薦算法原因判斷連通性DFS只要能走通就行DFS 代碼更簡潔按距離處理BFSBFS 天然按距離分層尋找最短路徑BFSBFS 第一次到達(dá)目標(biāo)時就是最短路徑拓?fù)渑判蝾愋枨驞FSDFS 的后序遍歷有拓?fù)湫再|(zhì)內(nèi)存受限D(zhuǎn)FSDFS 棧深度通常小于 BFS 隊列寬度避免深遞歸BFSBFS 用隊列不受遞歸深度限制5.4 性能分析與常見優(yōu)化四向鏈表遍歷的時間復(fù)雜度是 O(V E)其中 V 是節(jié)點數(shù)E 是邊數(shù)。對于四向鏈表每個節(jié)點最多有 4 條邊所以 E ≤ 4V總時間復(fù)雜度是 O(V)。這是最優(yōu)的因為每個節(jié)點至少要被訪問一次。空間復(fù)雜度取決于算法DFS 遞歸O(V) ?？臻g最壞情況DFS 迭代O(V) 顯式?？臻gBFSO(V) 隊列空間訪問標(biāo)記O(V) 哈希表空間優(yōu)化的方向主要有兩個第一減少哈希表開銷。如果節(jié)點是連續(xù)分配的可以用節(jié)點索引代替指針哈希。比如createGrid分配的節(jié)點是連續(xù)的可以用(node - base) / sizeof(QuadNode)作為索引用一個 bit 數(shù)組來標(biāo)記訪問狀態(tài)空間占用從 O(V) 個指針降到 O(V/8) 個字節(jié)。第二提前終止。如果你只需要找到某個特定節(jié)點不需要遍歷全部可以在訪問到目標(biāo)節(jié)點時立即返回。DFS 和 BFS 都支持這種優(yōu)化。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; }這種提前終止在搜索場景下能大幅減少訪問節(jié)點數(shù)平均情況下可能只需要訪問一小部分節(jié)點就能找到目標(biāo)。6. 踩過的坑與實戰(zhàn)經(jīng)驗6.1 指針未初始化導(dǎo)致的隨機崩潰這是最常見的坑。malloc分配的內(nèi)存不會自動清零如果你忘了把四個指針初始化為 NULL它們就是隨機值。后續(xù)遍歷時訪問這些隨機指針輕則讀到垃圾數(shù)據(jù)重則直接段錯誤。我自己的習(xí)慣是每次malloc之后立即用memset清零或者用calloc代替malloc。QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); // calloc 會自動把內(nèi)存清零四個指針都是 NULL這個習(xí)慣能幫你避免大量低級錯誤。多花的那一點點性能和調(diào)試崩潰花的時間比起來完全不值一提。6.2 環(huán)形引用導(dǎo)致的無限遞歸四向鏈表的指針是雙向的A 的 right 指向 BB 的 left 指向 A。如果你在遍歷時忘了加訪問標(biāo)記或者訪問標(biāo)記的邏輯有 bug就會在 A 和 B 之間無限循環(huán)。更隱蔽的情況是訪問標(biāo)記加在了錯誤的位置。比如你在遞歸調(diào)用之后才標(biāo)記那在遞歸調(diào)用之前就已經(jīng)重復(fù)訪問了。// 錯誤寫法標(biāo)記太晚 void dfsWrong(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; dfsWrong(node-up, visited); // 這里遞歸時 node 還沒被標(biāo)記 dfsWrong(node-down, visited); dfsWrong(node-left, visited); dfsWrong(node-right, visited); add(visited, node); // 標(biāo)記太晚了 } // 正確寫法進(jìn)入節(jié)點時立即標(biāo)記 void dfsCorrect(QuadNode* node, HashSet* visited) { if (node NULL) return; if (contains(visited, node)) return; add(visited, node); // 立即標(biāo)記 dfsCorrect(node-up, visited); dfsCorrect(node-down, visited); dfsCorrect(node-left, visited); dfsCorrect(node-right, visited); }這個細(xì)節(jié)看起來微不足道但實際調(diào)試時能讓你抓狂很久。我的建議是把標(biāo)記作為訪問節(jié)點的第一個動作養(yǎng)成肌肉記憶。6.3 刪除節(jié)點時的斷鏈順序刪除四向鏈表中的節(jié)點比插入更復(fù)雜。你需要處理四個方向的鄰居而且斷鏈的順序很重要。如果順序不對可能會丟失對其他節(jié)點的引用。假設(shè)要刪除節(jié)點 BB 的四個鄰居分別是 U上、D下、L左、R右。正確的斷鏈順序是先讓 U 的 down 指向 D跳過 B再讓 D 的 up 指向 U讓 L 的 right 指向 R讓 R 的 left 指向 L最后釋放 B 的內(nèi)存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); }注意這里假設(shè)刪除節(jié)點后上下鄰居直接相連左右鄰居也直接相連。如果你的業(yè)務(wù)邏輯不是這樣比如刪除后需要保持某種特殊結(jié)構(gòu)那斷鏈邏輯需要相應(yīng)調(diào)整。注意刪除節(jié)點后原來指向該節(jié)點的所有外部引用都會變成懸空指針。如果你的代碼里還有其他地方持有這個節(jié)點的指針必須同步清理否則后續(xù)訪問會出問題。6.4 打印預(yù)覽時的對齊問題打印四向鏈表時如果節(jié)點數(shù)據(jù)的寬度不一致比如有的是 1 位數(shù)有的是 3 位數(shù)輸出會參差不齊。解決辦法是用固定寬度格式化輸出printf(%4d, node-data); // 每個數(shù)字占 4 個字符寬度右對齊如果數(shù)據(jù)是字符串可以用%-10s左對齊或者%10s右對齊。關(guān)鍵是統(tǒng)一寬度讓輸出看起來整齊。另外如果鏈表很大比如 100x100直接打印會刷屏。這時候可以加一個范圍限制只打印指定區(qū)域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; } }這個函數(shù)只打印指定矩形區(qū)域內(nèi)的節(jié)點對于大鏈表調(diào)試非常實用。6.5 泛型實現(xiàn)中的類型擦除問題如果你用 Java 泛型來實現(xiàn)四向鏈表需要注意類型擦除帶來的限制。Java 的泛型在運行時會被擦除你不能用new T[]來創(chuàng)建泛型數(shù)組也不能用instanceof T來判斷類型。public class QuadNodeT { T data; QuadNodeT up, down, left, right; // 錯誤不能直接創(chuàng)建泛型數(shù)組 // QuadNodeT[] neighbors new QuadNodeT[4]; // 正確用通配符或者強制轉(zhuǎn)換 SuppressWarnings(unchecked) QuadNodeT[] neighbors (QuadNodeT[]) new QuadNode[4]; }在 C 里用模板就沒這個問題因為 C 的模板是編譯期展開的每個類型都會生成獨立的代碼。但代價是編譯后的二進(jìn)制體積會變大。選擇哪種泛型方案取決于你的項目需求。如果追求運行效率C 模板更好如果追求開發(fā)效率和跨平臺Java 泛型更方便。7. 四向鏈表與其他數(shù)據(jù)結(jié)構(gòu)的對比選型7.1 四向鏈表 vs 雙向鏈表 vs 十字鏈表特性雙向鏈表四向鏈表十字鏈表指針數(shù)量244維度一維二維二維適用場景線性序列網(wǎng)格、鄰接關(guān)系稀疏矩陣插入復(fù)雜度O(1)O(1)O(1)遍歷復(fù)雜度O(n)O(V)O(V)內(nèi)存開銷低中中高十字鏈表是四向鏈表的一個變種專門用于稀疏矩陣存儲。它的每個節(jié)點有 right 和 down 兩個指針分別指向同行和同列的下一個非零元素。和四向鏈表相比十字鏈表不存儲 up 和 left 指針因為稀疏矩陣的遍歷通常只需要向右和向下。如果你需要雙向遍歷既能向右也能向左既能向上也能向下四向鏈表更合適。如果只需要單向遍歷十字鏈表更省內(nèi)存。7.2 什么時候該用四向鏈表四向鏈表不是萬能藥它有明確的適用場景二維鄰接關(guān)系節(jié)點之間的連接是上下左右四個方向且關(guān)系是雙向的。動態(tài)增刪節(jié)點數(shù)量會動態(tài)變化不適合用固定大小的二維數(shù)組。稀疏結(jié)構(gòu)大部分位置沒有節(jié)點用二維數(shù)組會浪費大量空間。需要雙向遍歷既需要從 A 走到 B也需要從 B 走回 A。如果你的場景不滿足這些條件可能有更合適的數(shù)據(jù)結(jié)構(gòu)。比如規(guī)則網(wǎng)格用二維數(shù)組就夠了不需要四向鏈表。又比如只需要單向遍歷用十字鏈表或者鄰接表更省事。7.3 實際項目中的選型經(jīng)驗我在一個圖像處理項目里用過四向鏈表來表示像素鄰域關(guān)系。當(dāng)時的場景是需要從某個種子像素出發(fā)找到所有顏色相近的連通區(qū)域。用四向鏈表的好處是每個像素節(jié)點只需要存儲四個鄰居指針不需要存儲坐標(biāo)信息內(nèi)存占用比二維數(shù)組小很多尤其是圖像大部分區(qū)域是背景的情況下。但后來發(fā)現(xiàn)四向鏈表的維護成本太高了。每次圖像變化比如用戶涂抹都需要更新大量節(jié)點的指針。最終我們改用了并查集加二維數(shù)組的方案雖然內(nèi)存占用大一些但維護簡單得多性能也更好。這個經(jīng)驗告訴我四向鏈表適合結(jié)構(gòu)相對穩(wěn)定、增刪不頻繁的場景。如果增刪非常頻繁維護指針的成本可能會超過它帶來的好處。選型時一定要結(jié)合具體的操作頻率來評估。8. 完整可運行的代碼框架把前面所有的片段整合起來給出一個完整的、可直接編譯運行的 C 語言實現(xiàn)框架#include stdio.h #include stdlib.h #include string.h // 節(jié)點定義 typedef struct QuadNode { int data; struct QuadNode* up; struct QuadNode* down; struct QuadNode* left; struct QuadNode* right; } QuadNode; // 創(chuàng)建節(jié)點 QuadNode* createNode(int data) { QuadNode* node (QuadNode*)calloc(1, sizeof(QuadNode)); node-data data; return node; } // 創(chuàng)建網(wǎng)格 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]; } // 訪問標(biāo)記簡化版用節(jié)點內(nèi)置標(biāo)記 // 實際項目中建議用哈希表這里為了代碼簡潔用內(nèi)置標(biāo)記 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; } } // 打印網(wǎng)格 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 遍歷用外部數(shù)組標(biāo)記 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); } // 訪問函數(shù) void printNode(QuadNode* node) { printf(%d , node-data); } // 主函數(shù) 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); // 找到中間節(jié)點 (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; }這個框架可以直接編譯運行輸出會顯示網(wǎng)格預(yù)覽、DFS 遍歷結(jié)果和 BFS 遍歷結(jié)果。你可以基于這個框架擴展自己的業(yè)務(wù)邏輯。我在實際使用中發(fā)現(xiàn)把訪問標(biāo)記從節(jié)點內(nèi)置字段改成外部數(shù)組雖然代碼稍微復(fù)雜一點但好處是遍歷完后不需要重置節(jié)點狀態(tài)而且同一個鏈表可以同時進(jìn)行多次不同目的的遍歷互不干擾。這個設(shè)計決策在需要頻繁遍歷的場景下特別有價值。