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