簡介杭電數據結構課程設計已通過驗收的完整實踐資料包含停車場管理問題和校園導航咨詢系統(tǒng)兩個項目。資源面向正在完成數據結構課程設計的高校學生尤其適合需要參考完整實現與實驗報告格式的讀者兩個項目分別涉及棧、隊列、鏈表、圖等核心結構并應用最短路徑等算法體現理論與實踐結合。壓縮包共十一個文件大小約九百三十千字節(jié)涵蓋源碼文件、頭文件、實驗報告、地圖數據、矩陣表格、示意圖以及可執(zhí)行程序覆蓋代碼、文檔、數據與演示的完整鏈路。目前已有四百六十人學習讀者可獲得可運行的停車場管理模擬程序與校園導航系統(tǒng)、完整的課程設計報告以及各模塊的代碼組織與算法實現思路便于對照驗收標準優(yōu)化自己的作品。1. 這不是算法題是“帶著代碼去答辯”HDU 的數據結構課程設計跟平時刷杭電 OJ 那道坎完全是兩碼事。OJ 題錯了就錯了改到 AC 為止沒人問你為什么這么寫課程設計要過驗收你得拿著一個能跑的 .exe當著老師的面演示功能然后回答“為什么用鄰接表不用鄰接矩陣”“這個排序在最壞情況下是什么復雜度”“輸入一萬條數據會不會崩”。很多同學代碼寫完了一進驗收教室被問三句話就卡殼最后得了個合格但心里沒底。這篇筆記就是按“能跑、能講、能過驗收”的標準來講的方向是數據結構與算法落地里最常見的那套圖的遍歷與最短路徑、二叉樹操作、排序與查找以及一套完整的交互界面。標題里的“通過驗收”才是真正的主菜。代碼只是入場券驗收看的是你的選題夠不夠粒度、需求分析有沒有邊界、測試數據能不能自圓其說、答辯時原理講不講得清。下面我會把我做這個課設的完整思路拆給你怎么選題目、怎么定數據結構、代碼怎么從主函數往下長出來、以及驗收前那個晚上到底該檢查什么。新手能照著一路做到提交熟手可以直接跳到第 5 章看踩坑清單和答辯問法。2. 選題與需求分析決定你后面兩個星期過得好不好2.1 常見選題的分類與能力匹配杭電數據結構課設的題目池每年都在換但翻來覆去就是那幾類。我按“數據結構的核心程度”幫你分個類你看自己適合哪類。第一類是“圖的算法型”比如校園導航、城市交通查詢、迷宮求解。核心是圖的存儲與遍歷Dijkstra 或者 Floyd 必考其一。這類題目數據結構感最強答辯時能講的東西多但代碼量也最大。第二類是“線性結構應用型”比如學生信息管理、圖書借閱管理、員工工資查詢。核心是結構體數組或鏈表配合多關鍵字排序和查找。這類題目好寫但要過得漂亮得在“查找算法對比”和“數據量增大時的性能變化”上做文章不能只會個冒泡排序。第三類是“樹型應用”比如哈夫曼編碼/譯碼、表達式求值、二叉排序樹。哈夫曼是經典中的經典因為編碼過程能可視化出哈夫曼樹答辯時有圖可看表達式求值則是棧和二叉樹兩個知識點一起考了。我不建議選那種“系統(tǒng)管理”味太重的題比如“超市收銀系統(tǒng)”“圖書館管理系統(tǒng)”。這些題目聽著實用但其實數據結構濃度不夠——你說你是用順序表還是鏈表老師一問“那順序表和鏈表各自的適用場景是什么”你只能說“都可以”這就很被動。我當時的選題是一個“基于圖的最短路徑查詢系統(tǒng)”圖的頂點是校園建筑邊是路徑距離。為什么選它因為圖這個數據結構在課設里表現力最強鄰接矩陣存起來直觀Dijkstra 講起來有條理還能順手做一個 DFS 遍歷把“可達性查詢”也囊括進來一個題目覆蓋多個考點驗收時老師可問的點多你展示的空間也大。2.2 拿到題目的第一個小時把需求寫成一頁紙別急著開 IDE。你拿到題目后最該做的是把“人話需求”翻譯成“數據結構語言”。我給你一個模板照著填就行。系統(tǒng)名稱校園建筑最短路徑查詢系統(tǒng)輸入源建筑編號、目的建筑編號輸出最短路徑長度、途經建筑序列額外功能顯示所有建筑列表、查詢某建筑可直達哪些建筑邊界情況源和目的相同、圖不連通、非法編號輸入這一頁紙就是你的需求說明書初稿。后面寫中期報告、課程設計報告的時候直接把這份內容擴寫就行不用再絞盡腦汁想“我做了什么”。然后做一件事畫出數據的組織方式。用表格列出來建筑信息放哪、邊信息放哪、路徑輸出時用到的輔助數組放哪。這一步能幫你發(fā)現很多問題——比如你想用 Floyd 而不是 Dijkstra那就要多一個二維路徑矩陣如果想支持按距離排序輸出全部路線那就要考慮怎么在多條路徑里做比較。這些都是后面代碼里繞不開的決策現在想清楚比寫完了再推倒重來省力得多。2.3 驗收視角的需求補充老師想在你的演示里看到什么前面那頁紙是“功能需求”但課設驗收還有一層“展示需求”。老師一天要看幾十個組不會仔細讀你的代碼他主要通過幾分鐘的演示來判斷你這個課設“做沒做到位”。所以你的需求分析里至少要包含三個能“看得見”的點。第一初始化過程可視化——啟動程序時打印出讀入了多少個頂點、多少條邊讓老師確定你的數據是加載進來的不是寫死在代碼里的。第二一個足夠復雜的測試用例——選一條明顯不是最短的路徑讓程序算出來后老師能肉眼驗證結果是對的。第三異常輸入的優(yōu)雅處理——故意輸一個不存在的編號程序不能崩潰不能死循環(huán)要輸出一句人能看懂的提示。這三條就是驗收現場的高光時刻。很多同學代碼沒問題敗就敗在演示時輸入了“5”結果編號只有 0 到 3程序直接數組越界崩了老師眉頭一皺后面答辯你心里就慌了。這些都是你在需求分析階段就該寫進“邊界情況”里的東西。3. 核心數據結構與算法選型把“要用什么”焊死在設計文檔里3.1 鄰接矩陣還是鄰接表別只看教材怎么說圖的最短路查詢系統(tǒng)第一個決策就是圖的存儲結構。教材上會告訴你稀疏圖用鄰接表稠密圖用鄰接矩陣。這個結論沒錯但課設場景下你要多想一層。課設的數據量就那么大你錄入 20 個建筑、40 條路鄰接矩陣也就是一個 20×20 的二維數組400 個 int占 1600 字節(jié)。這個量級談性能優(yōu)化沒有意義。此時你應該優(yōu)先考慮“哪個寫起來不容易錯、答辯時更好講”。我用的鄰接矩陣。原因有三個第一Dijkstra 算法用鄰接矩陣寫代碼形態(tài)跟教材偽代碼一一對應你背得住也講得清第二答辯時老師讓你“把圖結構畫出來”鄰接矩陣直接在紙上畫個方格子填 0 和 ∞ 就行特別直觀第三檢查圖的連通性、查一條邊是否存在矩陣是 O(1) 的你演示“查詢兩棟建筑是否直接相連”這個功能時代碼不用繞彎子。鄰接表當然也可以。如果你選的題目是“微博關注關系分析”那必須用鄰接表——因為十萬個頂點、百萬條邊用矩陣就是災難。選哪個不是看哪個高級而是看數據長什么樣。我一般建議頂點數預期超過 100 或者邊特別稀疏不到完全圖的 10%考慮鄰接表否則就鄰接矩陣省心。3.2 Dijkstra 的課設版本記錄路徑而不只是距離教材上的 Dijkstra 通常只求最短路徑長度用一個 dist[] 數組搞定。但課設演示需要輸出完整路徑所以你還得維護一個 prev[] 數組記錄每個頂點的前驅頂點。這是課設版 Dijkstra 和算法題版 Dijkstra 最大的區(qū)別。#define MAXVEX 20 #define INF 65535 typedef struct { char name[20]; // 建筑名稱 int id; // 建筑編號 } Vertex; typedef struct { int edges[MAXVEX][MAXVEX]; // 鄰接矩陣INF 表示不連通 int numVertexes, numEdges; // 實際頂點數和邊數 Vertex vexs[MAXVEX]; // 頂點數組 } MGraph; // Dijkstra 算法求 start 到所有點的最短路徑 // dist: 輸出最短路徑長度 // prev: 輸出前驅頂點數組用于回溯路徑 void Dijkstra(MGraph *G, int start, int dist[], int prev[]) { int final[MAXVEX] {0}; // final[i]1 表示頂點 i 已確定最短路徑 int i, j, k, min; for (i 0; i G-numVertexes; i) { dist[i] G-edges[start][i]; prev[i] (dist[i] INF) ? start : -1; } final[start] 1; dist[start] 0; for (i 1; i G-numVertexes; i) { min INF; k -1; for (j 0; j G-numVertexes; j) { if (!final[j] dist[j] min) { min dist[j]; k j; } } if (k -1) break; // 剩余頂點不可達提前結束 final[k] 1; for (j 0; j G-numVertexes; j) { if (!final[j] min G-edges[k][j] dist[j]) { dist[j] min G-edges[k][j]; prev[j] k; } } } }這段代碼里最關鍵的設計是prev數組的初始化prev[i] (dist[i] INF) ? start : -1。這里把“直接與起點相連”和“不與起點相連”兩種情況區(qū)分開不然后面回溯路徑時會把不相連的頂點錯誤地串進來。k -1那個 break 也是實際測試逼出來的——如果圖本身不連通沒有這個判斷內層循環(huán)會把k留在 -1下一輪final[-1]就是數組越界。你寫代碼時一定要加上這種防御性判斷尤其是課設這種“演示時輸入不可控”的場景。回溯路徑的代碼也要單獨寫一個函數不要在 Dijkstra 里順手打印否則你的 Dijkstra 就不純凈了——它既要算距離又要做 IO答辯時不好講清楚。void PrintPath(int start, int end, int prev[]) { // 用棧逆序輸出前驅鏈避免遞歸深度不確定 int stack[MAXVEX], top 0; int cur end; while (cur ! -1) { stack[top] cur; if (cur start) break; cur prev[cur]; } // 此時棧頂是 start依次出棧即為路徑 while (top 0) { printf(%s, vexs[stack[--top]].name); if (top 0) printf( - ); } printf(\n); }為什么用棧不用遞歸因為課設程序的路徑長度最長可能等于頂點數遞歸層數雖然不多但老師可能會問“如果有一千個頂點這個遞歸會不會爆?！薄Ｄ阌脳懸环矫嬲故玖恕坝脭祿Y構解決問題”的意識另一方面徹底規(guī)避了遞歸深度的爭議。答辯時這句話可以直接說我用棧來逆序前驅鏈是為了不依賴遞歸避免最壞情況下頂點數較大時的棧溢出風險。3.3 排序與查找第二考點不能瘸腿只做最短路課設撐不起來。老師會問你這個系統(tǒng)里還有沒有別的數據結構知識點所以你得主動在系統(tǒng)里塞一個“排序”功能。我當時的做法是支持按建筑名稱的字典序輸出全部建筑列表以及按距離排序輸出“從一個建筑出發(fā)的所有可達路徑”。// 按距離從小到大排序所有從 start 出發(fā)的邊 // 用結構體數組 qsort避免手寫冒泡的尷尬 typedef struct { int adjvex; // 鄰接頂點編號 int weight; // 邊權距離 } EdgeInfo; int cmpEdge(const void *a, const void *b) { return ((EdgeInfo*)a)-weight - ((EdgeInfo*)b)-weight; } void SortEdgesByWeight(MGraph *G, int start) { EdgeInfo edges[MAXVEX]; int n 0; for (int i 0; i G-numVertexes; i) { if (G-edges[start][i] ! INF) { edges[n].adjvex i; edges[n].weight G-edges[start][i]; n; } } qsort(edges, n, sizeof(EdgeInfo), cmpEdge); printf(從 %s 出發(fā)的路徑按距離排序\n, G-vexs[start].name); for (int i 0; i n; i) { printf( %s (%d 米)\n, G-vexs[edges[i].adjvex].name, edges[i].weight); } }這里刻意用了qsort而不是自己寫快排是留了答辯余地的如果老師問你“你自己實現過排序嗎”你就說“課設里我用了 C 標準庫的 qsort 來處理數據排序因為它的比較器接口清晰、性能穩(wěn)定我在平時練習時也手寫過快速排序和歸并排序能講清楚分治思路。” 這比你在課設里貼一個自己寫的、邊界都處理不對的快排要安全得多。課設不是算法競賽不要在核心業(yè)務里冒險。查找方面因為頂點數量少順序查找就夠。但答辯可能會問“為什么不用二分查找”你得能答上來順序查找適用于無序列表而建筑名稱列表如果允許增刪就不保持有序性所以二分查找不適用如果想要 O(log n) 查找可以在初始化時維護一個按名稱排序的索引數組。你看這個問題你一答老師就知道你是真懂查找的適用條件而不是背了個二分模板。4. 從主函數長出來的完整代碼可復現的骨架與七個必經步驟4.1 先寫 main 的骨架菜單循環(huán)是課設的臉面課程設計不是寫一個被調用的庫函數而是一個能交互的程序。你的 main 要是一個循環(huán)打印菜單、接收輸入、分發(fā)任務的結構。這一步別寫在最后第一步就寫。int main() { MGraph G; int choice; int start, end; InitGraph(G); // 從文件讀入數據初始化圖 PrintWelcome(); // 打印系統(tǒng)名稱和作者信息 while (1) { PrintMenu(); // 打印功能菜單 scanf(%d, choice); while (getchar() ! \n); // 清空輸入緩沖防止殘留換行 switch (choice) { case 1: ListAllBuildings(G); break; case 2: QueryShortestPath(G); break; case 3: SortEdgesByWeight(G); break; case 4: DFS_Traverse(G); break; case 0: printf(感謝使用再見\n); return 0; default: printf(輸入錯誤請重新選擇\n); break; } } return 0; }這段骨架里有幾個細節(jié)是血淚經驗。第一while (getchar() ! \n)這一行必須有不然你輸入完數字按回車殘留的換行會被下一個 %c 或 %s 吃掉然后你的菜單就亂跳了。第二case 0和default必須分開0 是正常退出其他數字是錯誤輸入這兩件事不能用同一個分支否則老師會覺得你程序的控制流不清晰。第三每個 case 末尾都要有 break這不用我說你也知道但漏 break 恰恰是課設代碼里最常見的問題因為 CtrlC 復制上一段的時候很容易連著 break 一起刪掉。菜單函數本身要打印清楚每個數字對應什么功能別用“1.xxx 2.xxx”這種緊湊格式要把邊界情況也寫上去比如“0. 退出”讓使用者不困惑。4.2 數據的正確打開方式文件讀取而不是交互錄入用 scanf 一個頂點一個頂點地錄入圖數據是一種自虐行為——演示時你光輸入數據就要兩三分鐘老師早就失去耐心了。正確做法是把數據放在文本文件里程序啟動時一次性讀取進來。#define MAX_NAME 20 void InitGraph(MGraph *G) { FILE *fp fopen(graph_data.txt, r); if (fp NULL) { printf(錯誤找不到 graph_data.txt 文件\n); printf(請確認數據文件與程序在同一目錄下。\n); exit(1); } fscanf(fp, %d %d, G-numVertexes, G-numEdges); for (int i 0; i G-numVertexes; i) { fscanf(fp, %d %s, G-vexs[i].id, G-vexs[i].name); } // 初始化鄰接矩陣 for (int i 0; i G-numVertexes; i) { for (int j 0; j G-numVertexes; j) { if (i j) G-edges[i][j] 0; else G-edges[i][j] INF; } } // 讀取邊 int v1, v2, weight; for (int i 0; i G-numEdges; i) { fscanf(fp, %d %d %d, v1, v2, weight); G-edges[v1][v2] weight; G-edges[v2][v1] weight; // 無向圖 } fclose(fp); printf(初始化成功共 %d 個建筑%d 條道路。\n, G-numVertexes, G-numEdges); }數據文件 graph_data.txt 的格式是有講究的按行讀的別用逗號分隔fscanf 的空格分隔最不容易出錯6 6 0 圖書館 1 第一教學樓 2 第二教學樓 3 學生食堂 4 體育館 5 宿舍區(qū) 0 1 200 0 2 350 1 3 180 2 3 250 3 4 300 4 5 150這里有個坑頂點的 id 必須和數組下標完全一致。如果你從 1 開始編號那數組就要多開一位或者讀入時id--。我的建議是數據文件里就從 0 開始編號和數組下標天然對齊省去所有轉換邏輯。這看起來不優(yōu)雅但課設不需要優(yōu)雅需要的是少一個出錯的可能。4.3 手動模擬一遍 Dijkstra把 prev 數組畫出來給你看代碼可以打印算法流程光看代碼是不容易“懂”的。我建議你寫完 Dijkstra 函數后拿上面這個 6 頂點的小圖手動跑一遍把 dist 和 prev 的變化寫在一張表上。以頂點 0圖書館為起點初始時dist [0, 200, 350, INF, INF, INF]prev [0, 0, 0, -1, -1, -1]。第一輪找到未確定點中 dist 最小的是頂點 1dist200。確定它。然后更新與 1 相鄰的點頂點 3 的 dist 從 INF 變成 200180380prev[3]1。第二輪未確定點中 dist 最小的是頂點 2dist350。確定它。更新頂點 3380 與 350250600 比較380 更小所以 prev[3] 保持 1dist[3] 不動。第三輪頂點 3dist380確定。更新頂點 4dist680prev[4]3。第四輪頂點 4dist680確定。更新頂點 5dist830prev[5]4。第五輪頂點 5 確定結束。如果你要查從圖書館到宿舍區(qū)的路徑從 prev[5]4prev[4]3prev[3]1prev[1]0反推得到路徑0 - 1 - 3 - 4 - 5也就是圖書館 - 第一教學樓 - 學生食堂 - 體育館 - 宿舍區(qū)總長度 200180300150 830 米。把這張表放在你的課程設計報告里比貼代碼有用得多。老師看報告時看到你能把算法的運行過程畫出來就證明你真的會 Dijkstra而不是從網上找了一段代碼改改名。4.4 菜單功能與代碼文件的劃分沒有第三人稱的項目結構課設代碼不建議寫完丟在一個 main.c 里也不建議拆成一百個文件。推薦結構是graph.h 放結構體定義和函數聲明graph.c 放圖的初始化、Dijkstra、排序等核心實現main.c 放交互邏輯。// graph.h #ifndef GRAPH_H #define GRAPH_H #define MAXVEX 20 #define INF 65535 typedef struct { char name[20]; int id; } Vertex; typedef struct { int edges[MAXVEX][MAXVEX]; int numVertexes, numEdges; Vertex vexs[MAXVEX]; } MGraph; void InitGraph(MGraph *G); void Dijkstra(MGraph *G, int start, int dist[], int prev[]); void PrintPath(int start, int end, int prev[]); void ListAllBuildings(MGraph *G); void QueryShortestPath(MGraph *G); void SortEdgesByWeight(MGraph *G); void DFS_Traverse(MGraph *G); #endif頭文件里必須寫#ifndef防重復包含。這個習慣在課設里體現不出來因為你的代碼就三四個文件但老師看代碼時會注意到。你可以在答辯時說我用條件編譯宏防止頭文件被重復包含這是大型項目里必須養(yǎng)成的習慣。這句話雖然簡單但能瞬間把你和那些所有代碼懟在一個文件里的同學區(qū)分開。queryShortestPath 是連接 Dijkstra 和交互界面的樞紐邏輯是輸入兩個編號 - 檢查合法性 - 調 Dijkstra - 輸出路徑。這里檢查合法性必須在調用算法之前做不能等 Dijkstra 算完再檢查因為 Dijkstra 遇到非法編號就是數組越界。void QueryShortestPath(MGraph *G) { int start, end; int dist[MAXVEX], prev[MAXVEX]; printf(請輸入起點建筑編號); scanf(%d, start); printf(請輸入終點建筑編號); scanf(%d, end); if (start 0 || start G-numVertexes || end 0 || end G-numVertexes) { printf(編號超出范圍請重新輸入\n); return; } if (start end) { printf(起點和終點相同距離為 0。\n); return; } Dijkstra(G, start, dist, prev); if (dist[end] INF) { printf(兩棟建筑之間不存在可達路徑。\n); } else { printf(最短路徑長度%d 米\n, dist[end]); printf(路徑); PrintPath(start, end, prev); } }注意里面兩個特殊分支起點等于終點的處理以及路徑不存在時的處理。這兩個分支對應的就是需求分析時寫的“邊界情況”。你不寫這兩個分支程序一般也不會崩但輸出會非常難看——起點終點相同時路徑打印可能輸出一個空串或一個孤立節(jié)點老師會問“你這算對嗎”。你提前處理好了演示時就可以主動輸入這兩個邊界情況展示程序的健壯性這是加分的。4.5 初始化后的第一輪自測功能全綠再往下走代碼寫到能編譯通過別急著去找驗收老師先自己當一遍“驗收老師”。按照下面的清單過一遍每一條都要真的跑一遍看輸出正常路徑查詢選一條明顯繞遠的路看程序算出來的最短路徑是不是你的手算結果。起點終點相同輸出“距離為 0”沒有多余路徑輸出。不存在的編號輸入 -1 或 99程序輸出提示語不崩潰。不連通節(jié)點對如果數據文件里有孤立的建筑查詢它和其他建筑時輸出“不存在可達路徑”。菜單輸入錯誤輸入 8 或者 abc程序回到菜單而不是陷入死循環(huán)。圖數據文件缺失刪掉 graph_data.txt 后運行程序看程序是否給了明確提示。第 5 條有個隱藏坑如果輸入的是字母而不是數字scanf 會返回 0但變量里保留的是舊值或者未初始化的值程序可能進入死循環(huán)。簡單的處理方式是檢查 scanf 的返回值如果等于 0 就清空輸入緩沖并提示重新輸入if (scanf(%d, choice) ! 1) { printf(請輸入數字\n); while (getchar() ! \n); // 把錯誤輸入全部清掉 continue; }這一步檢查在課設里尤其重要。演示時你緊張了、手誤了輸入了一個字母程序直接卡死你對著黑窗口不知所措——這種場景每年驗收都在上演你提前把防護做好就不至于翻車。5. 避坑清單驗收前最容易翻車的 5 個位置5.1 編譯環(huán)境差異Windows 下能跑換臺機器就崩現象在自己電腦上編譯運行一切正常拿到實驗室或答辯機器上編譯報一堆錯誤或者運行時閃退。原因課設最常見的環(huán)境是 Dev-C但它的 MinGW 編譯器版本可能比你在 VS Code 里用的 GCC 舊對 C 標準支持不到位。比如你在代碼里用了for (int i 0; ...)在 C89 標準下就不允許在 for 循環(huán)里聲明變量。還有//注釋之外如果你混用了 C 和 C 代碼比如用new或// 單行注釋嚴格模式下編譯直接卡死。解決寫代碼時統(tǒng)一用 C 語言語法變量聲明一律放在語句塊開頭換行注釋沒問題但不要用 C 的特性。另外提交前最后用 Dev-C 打開項目重新編譯一次確認沒有警告。警告里經常藏著大坑比如“隱式聲明函數”——那就是說你調了一個函數但沒包含它的頭文件你自己的編譯器可能因為自動鏈接或舊 libc 而放過但答辯機器上就會鏈接失敗。5.2 scanf 輸入殘留菜單第二次輸入直接跳過現象輸入菜單選項后按回車程序不會等待輸入下一次選項直接“吃掉”了殘留的換行符菜單飛速跳轉。原因scanf(%d)只讀取數字把輸入緩沖區(qū)里的換行符留下。下一次循環(huán)里如果碰到scanf(%c)或gets()會立即讀到這個換行符導致輸入跳過。解決判斷輸入是數字還是字符后用while (getchar() ! \n)清空緩沖或者在每個輸入語句后統(tǒng)一加一行fflush(stdin)。但注意——fflush(stdin) 在 C 標準里是未定義行為在 Windows 下的 Dev-C 里能用在 Linux 的 GCC 下沒用。所以我建議用 getchar 清緩沖的寫法兼容性更好也體現你知道輸入緩沖區(qū)的運作方式答辯時可以主動講這個細節(jié)。5.3 無窮大 INF 參與運算Dijkstra 松弛時整數溢出現象圖里有不連通的頂點程序輸出的最短路徑長度是一個莫名其妙的負數或者路徑序列里出現連續(xù)的 -1。原因INF 用 65535 定義時如果一行里兩個 INF 相加——比如min G-edges[k][j]兩個都是 INF——結果超過 int 上限的溢出是小事更常見的是 65535 65535 131070沒有溢出但 result 是 131070然后你把 131070 和另一個 INF65535 比較131070 不小于 INF所以不更新——這沒錯。但如果前面 min 被算成了 32767 之類的更大值或者 INF 定義成0x7fffffff那兩個 INF 相加就直接變成負數負數是小于正數 INF 的于是松弛條件永遠成立dist 被反復更新成負數輸出徹底亂了。解決在松弛操作前加判斷兩個值都必須小于 INF 才做加法比較if (!final[j] min G-edges[k][j] min) // 這行有問題正確寫法是if (!final[j] G-edges[k][j] ! INF min G-edges[k][j] dist[j]) { dist[j] min G-edges[k][j]; prev[j] k; }先把 INF 的邊排除掉再做加法。這是一個典型的防御性編程問題代碼里處理不好一旦圖里有一個不連通點你的 Dijkstra 輸出就全錯這種 bug 往往到驗收前才被發(fā)現改起來牽一發(fā)動全身血淚教訓。5.4 DFS 遞歸深度圖的頂點多了一層就可能崩現象在圖的遍歷功能里用遞歸實現 DFS圖有 15 個頂點時正常你為了演示加到 20 個頂點程序在遍歷到深處時突然崩潰退出。原因遞歸函數DFS(int v)每次調用都在棧上分配新的棧幀圖的深度太大時堆棧溢出。課設的頂點數一般不會上萬但運行時棧大小只有 1MB 左右如果遞歸層數上百層就可能爆棧。解決把 DFS 改成顯式棧實現。用一個輔助數組標記訪問狀態(tài)配一個棧來模擬系統(tǒng)調用棧。void DFS_Traverse(MGraph *G) { int visited[MAXVEX] {0}; int stack[MAXVEX], top 0; int v, i; printf(DFS 遍歷結果); for (v 0; v G-numVertexes; v) { if (!visited[v]) { visited[v] 1; printf( %s, G-vexs[v].name); stack[top] v; while (top 0) { int cur stack[--top]; for (i 0; i G-numVertexes; i) { if (G-edges[cur][i] ! INF !visited[i]) { visited[i] 1; printf( %s, G-vexs[i].name); stack[top] i; } } } } } printf(\n); }這里我用的是“右入棧、先訪問標記再入?！钡膶懛ū苊饬酥貜痛蛴栴}。實際上這段代碼的遍歷輸出順序和遞歸版 DFS 會略有差異但課設里沒有任何人關心輸出順序是和遞歸版一模一樣還是略有偏差只要“每個頂點都被訪問且輸出正確”就沒問題。這趟換棧的收益是即使頂點數幾百個也絕對不崩你答辯時可以說“這里為了避免遞歸棧溢出我用了顯式棧實現 DFS”這一句話就把整段代碼的分量抬起來了。5.5 報告里的運行截圖截圖不清晰是最虧的丟分點現象課程設計報告里貼了運行截圖但截圖分辨率過低或者窗口被拉伸老師看不清輸出的文字內容只能看到模糊的色塊。原因屏幕縮放比例太高或者截圖時只截了窗口的一小塊報告排版時又把圖片拉大了字就變成了“馬賽克”。解決截圖時用 WinShiftS 選擇窗口區(qū)域不要把整個屏幕截進來截圖后用畫圖工具把圖片裁剪到只留窗口黑色區(qū)域保證截圖里字體大小用默認的 16 號以上不要為了多放內容把窗口縮得很小。另外每張截圖下方要有一行說明文字“圖 3-1 最短路徑查詢結果”這對應報告里的“運行結果與分析”章節(jié)。文字說明里要寫清楚輸入了什么數據、看到了什么輸出、結果是否符合預期。這一條不是代碼問題但很多代碼寫得好的人在這里翻車報告分上不去很可惜。6. 答辯與驗收從“代碼能跑”到“老師點頭”的最后一公里到了驗收環(huán)節(jié)代碼已經沒得改了。這時候拼的是兩樣東西你怎么講以及你怎么應對提問。我這里說三個我最常用的答辯技巧都是實戰(zhàn)里驗證過有用的。第一個是“演示腳本”。不要到了現場憑感覺操作提前寫好一個三分鐘的演示流程啟動程序順手點開數據文件說明“這是圖的數據文件共 6 個頂點 6 條邊”然后查詢從“圖書館”到“學生食堂”的最短路徑故意先說一句“如果走第二教學樓會更近但實際最短路徑是先到第一教學樓”——這句話的作用是讓老師知道你理解“最短”的含義你不是只會跑程序。然后展示按距離排序和 DFS 遍歷最后演示輸入非法編號程序提示錯誤并返回菜單。三分鐘結束每個功能都被驗證過而且不會冷場。第二個是“高頻問題預案”。按我的經驗老師最愛問的問題固定就那么幾個你提前把答案準備好背熟現場就不卡殼。問Dijkstra 算法為什么不能處理負權邊答因為 Dijkstra 基于貪心每次確定一個距離最小的頂點就不再更新。如果存在負權邊某個頂點可能在確定之后通過負權邊被更短地發(fā)現但算法已經不會回頭更新它了。所以負權圖得用 SPFA 或 Bellman-Ford。問你的圖是無向的如果改成有向圖代碼哪里要改答讀取邊時只賦一個方向的權值G-edges[v1][v2] weight去掉回賦的那一行。另外 DFS 遍歷時也要按有向邊來訪問鄰接點。問為什么鄰接矩陣的 INF 用 65535 而不是 32767答65535 是 2 的 16 次方減 1在 int 范圍內而且足夠大任何兩個 INF 相加也不會溢出 int6553565535131070遠小于 2^31確保松弛比較時不被意外“污染”。這三個問題你答得順老師對你的印象分就會往上走。最怕的是背了答案但沒理解老師追問一層就露餡。所以預案里的答案一定要自己先弄懂別硬背。第三個是“報告與演示的一致性”。你課程設計報告里寫的是什么數據結構、什么算法流程演示時就必須是什么。有些同學報告里寫“本系統(tǒng)采用鄰接表存儲圖結構”但代碼里用的是鄰接矩陣——這種情況老師一旦發(fā)現印象分直接清零。報告和代碼必須對口。我一般建議在報告里專門畫一張“系統(tǒng)功能框圖”——但這個不用畫得很復雜用方框和箭頭把功能模塊和數據結構之間的關系標示出來即可。最后一個技巧是關于“求幫助”的。如果現場真的遇到突發(fā)狀況程序起不來——這不是你的錯但別愣著。你可說“我先把數據文件路徑檢查一下”然后打開當前目錄確認文件在不在。如果還是不行就誠懇一點“正常情況下這個功能是好的可能是當前環(huán)境的字符編碼問題導致文件沒有正確讀取?！?說實話這個責任其實不在你——你答辯前沒在答辯機器上跑過一遍誰知道這機器少了什么運行庫。所以我的習慣是答辯前一天借一臺跟答辯環(huán)境最接近的電腦裝上相同的編譯器完整跑一遍演示流程。這個動作能排掉 80% 的“機器差異”導致的尷尬。希望幫到你。本文還有配套的精品資源點擊獲取