簡(jiǎn)介這份C數(shù)據(jù)結(jié)構(gòu)課設(shè)資源圍繞“老鼠走迷宮”展開(kāi)面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、需要完成課程設(shè)計(jì)或想通過(guò)實(shí)戰(zhàn)鞏固搜索算法的學(xué)生與開(kāi)發(fā)者。項(xiàng)目以二維數(shù)組抽象迷宮用0和1區(qū)分通路與墻壁并借助深度優(yōu)先搜索實(shí)現(xiàn)隨機(jī)迷宮生成與路徑求解幫助讀者理解圖、棧、隊(duì)列等結(jié)構(gòu)在實(shí)際問(wèn)題中的落地方式。壓縮包共27個(gè)文件約148.59MB包含cpp與h源碼、sln與vcxproj工程文件、exe可執(zhí)行程序、mp4使用說(shuō)明與素材替換視頻、png與jpg示意圖以及pdb、ilk、obj等調(diào)試編譯中間文件另附txt說(shuō)明文檔便于直接運(yùn)行和二次修改。目前已有1391人學(xué)習(xí)下載。資源提供完整源碼、隨機(jī)迷宮生成邏輯、路徑搜索實(shí)現(xiàn)與操作錄屏讀者可據(jù)此掌握DFS遞歸與回溯、迷宮數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及C工程組織方法適合作為課設(shè)參考與算法練習(xí)素材。1. 老鼠走迷宮一個(gè)把棧和隊(duì)列跑出畫面的數(shù)據(jù)結(jié)構(gòu)課設(shè)很多同學(xué)做數(shù)據(jù)結(jié)構(gòu)課設(shè)最頭疼的不是寫不出代碼而是寫完了不知道對(duì)錯(cuò)——控制臺(tái)黑框里跑出一堆坐標(biāo)到底哪條路徑是最優(yōu)的回溯有沒(méi)有問(wèn)題全憑腦補(bǔ)。這個(gè)“老鼠走迷宮”項(xiàng)目就是來(lái)解決這個(gè)痛點(diǎn)的它把經(jīng)典的迷宮求解問(wèn)題做成了可視化演示用 C 實(shí)現(xiàn)核心是棧和隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)的對(duì)比應(yīng)用。DFS 用棧實(shí)現(xiàn)BFS 用隊(duì)列實(shí)現(xiàn)兩條路徑同時(shí)跑誰(shuí)長(zhǎng)誰(shuí)短一目了然。適合正在做課設(shè)的本科生、想復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及需要一份能直接編譯運(yùn)行的 C 項(xiàng)目參考的開(kāi)發(fā)者。整個(gè)項(xiàng)目不依賴任何第三方圖形庫(kù)純控制臺(tái)字符畫輸出拿到源碼就能跑。2. 核心架構(gòu)拆解棧與隊(duì)列如何驅(qū)動(dòng)兩種尋路策略2.1 迷宮的數(shù)據(jù)表示與坐標(biāo)系統(tǒng)迷宮本質(zhì)上是一個(gè)二維網(wǎng)格每個(gè)格子有兩種狀態(tài)可走通路和不可走墻壁。項(xiàng)目里用二維數(shù)組來(lái)存儲(chǔ)0 表示墻壁1 表示通路這樣初始化簡(jiǎn)單調(diào)試時(shí)也方便直接看。// 迷宮最大尺寸可根據(jù)需要調(diào)整 const int MAX_ROW 20; const int MAX_COL 20; // 迷宮地圖0-墻壁1-通路 int maze[MAX_ROW][MAX_COL]; // 方向數(shù)組上、右、下、左順時(shí)針 // 注意這里順序會(huì)影響DFS的搜索路徑形態(tài) const int dx[4] {-1, 0, 1, 0}; const int dy[4] {0, 1, 0, -1};方向數(shù)組dx和dy是這類題目的標(biāo)配四個(gè)方向分別對(duì)應(yīng)行減一、列加一、行加一、列減一。這里有個(gè)細(xì)節(jié)方向的遍歷順序會(huì)直接影響 DFS 找到的第一條路徑長(zhǎng)什么樣。如果先走上再走右老鼠會(huì)傾向于貼著上邊界走如果先走右再走下路徑形態(tài)完全不同。這不是 bug是 DFS 的特性——它只保證找到一條路不保證最短。BFS 則不受方向順序影響因?yàn)樗侵饘訑U(kuò)展的第一次到達(dá)終點(diǎn)時(shí)一定是最短路徑。坐標(biāo)用(row, col)表示起點(diǎn)通常設(shè)在左上角(1,1)終點(diǎn)設(shè)在右下角(MAX_ROW-2, MAX_COL-2)。迷宮外圍留一圈墻壁這樣在判斷越界時(shí)只需要檢查數(shù)組下標(biāo)是否在[0, MAX_ROW)范圍內(nèi)不用額外處理邊界條件少寫一堆 if。2.2 DFS 尋路用棧模擬遞歸回溯DFS 的核心思想是“一條路走到黑走不通就退回來(lái)?yè)Q方向”。遞歸寫法最直觀但課設(shè)通常要求用棧手動(dòng)模擬因?yàn)橐疾鞂?duì)棧的理解。// 棧節(jié)點(diǎn)記錄當(dāng)前位置和已嘗試的方向編號(hào) struct StackNode { int x, y; // 當(dāng)前坐標(biāo) int dir; // 下一個(gè)要嘗試的方向索引(0-3) }; // 用數(shù)組模擬棧 StackNode stack[MAX_ROW * MAX_COL]; int top -1; bool dfsWithStack(int startX, int startY, int endX, int endY) { // 入棧起點(diǎn) top; stack[top] {startX, startY, 0}; maze[startX][startY] 2; // 2表示已訪問(wèn) while (top 0) { StackNode cur stack[top]; // 到達(dá)終點(diǎn) if (cur.x endX cur.y endY) { return true; } // 嘗試下一個(gè)方向 bool moved false; while (cur.dir 4) { int nx cur.x dx[cur.dir]; int ny cur.y dy[cur.dir]; cur.dir; // 當(dāng)前節(jié)點(diǎn)方向指針后移 if (maze[nx][ny] 1) { // 是通路且未訪問(wèn) maze[nx][ny] 2; // 標(biāo)記已訪問(wèn) top; stack[top] {nx, ny, 0}; moved true; break; } } // 四個(gè)方向都走不通出?；厮?if (!moved) { top--; } } return false; // ?？者€沒(méi)到終點(diǎn)無(wú)解 }這段代碼有幾個(gè)關(guān)鍵點(diǎn)。第一棧里存的不是簡(jiǎn)單的坐標(biāo)而是StackNode多了一個(gè)dir字段。這個(gè)字段記錄當(dāng)前節(jié)點(diǎn)已經(jīng)嘗試到第幾個(gè)方向了回溯回來(lái)的時(shí)候不用從頭再試直接從上次的位置繼續(xù)。第二maze[nx][ny] 2這個(gè)標(biāo)記很關(guān)鍵它防止老鼠在原地打轉(zhuǎn)。第三cur用了引用StackNode cur stack[top]這樣修改cur.dir就是直接改棧頂元素不需要出棧再入棧。參數(shù)說(shuō)明startX, startY是起點(diǎn)坐標(biāo)endX, endY是終點(diǎn)坐標(biāo)。返回值bool表示是否找到路徑。如果找到棧里從底到頂就是完整路徑如果沒(méi)找到棧會(huì)逐步清空。DFS 找到的路徑不一定最短這是它的固有特性。在迷宮這種場(chǎng)景下它可能繞很大一圈才到終點(diǎn)。但 DFS 的優(yōu)勢(shì)是實(shí)現(xiàn)簡(jiǎn)單空間開(kāi)銷小——棧的最大深度不會(huì)超過(guò)通路格子總數(shù)。2.3 BFS 尋路隊(duì)列逐層擴(kuò)展保證最短路徑BFS 的思路是“一層一層往外擴(kuò)”用隊(duì)列實(shí)現(xiàn)。每從隊(duì)頭取出一個(gè)節(jié)點(diǎn)就把它的所有未訪問(wèn)鄰居加入隊(duì)尾。這樣保證第一次到達(dá)終點(diǎn)時(shí)走過(guò)的步數(shù)一定是最少的。// 隊(duì)列節(jié)點(diǎn)記錄坐標(biāo)和父節(jié)點(diǎn)在隊(duì)列中的索引 struct QueueNode { int x, y; int parent; // 父節(jié)點(diǎn)在隊(duì)列數(shù)組中的下標(biāo)用于回溯路徑 }; QueueNode queue[MAX_ROW * MAX_COL]; int front 0, rear 0; bool bfsWithQueue(int startX, int startY, int endX, int endY) { // 起點(diǎn)入隊(duì) queue[rear] {startX, startY, -1}; rear; maze[startX][startY] 2; while (front rear) { QueueNode cur queue[front]; int curIndex front; front; // 到達(dá)終點(diǎn)通過(guò)parent回溯路徑 if (cur.x endX cur.y endY) { return true; } // 嘗試四個(gè)方向 for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (maze[nx][ny] 1) { maze[nx][ny] 2; queue[rear] {nx, ny, curIndex}; rear; } } } return false; }BFS 的隊(duì)列節(jié)點(diǎn)多了一個(gè)parent字段記錄父節(jié)點(diǎn)在隊(duì)列數(shù)組中的下標(biāo)。因?yàn)殛?duì)列是用數(shù)組模擬的每個(gè)節(jié)點(diǎn)的下標(biāo)就是它在數(shù)組中的位置所以可以用整數(shù)索引來(lái)追溯。找到終點(diǎn)后從終點(diǎn)節(jié)點(diǎn)開(kāi)始沿著parent一路往回找就能還原出完整路徑。這里有個(gè)容易翻車的地方maze[nx][ny] 2必須在入隊(duì)時(shí)就標(biāo)記不能等出隊(duì)再標(biāo)記。如果等出隊(duì)才標(biāo)記同一個(gè)格子可能被多個(gè)節(jié)點(diǎn)重復(fù)加入隊(duì)列導(dǎo)致隊(duì)列爆炸式增長(zhǎng)內(nèi)存直接爆掉。這是 BFS 實(shí)現(xiàn)中最常見(jiàn)的坑。BFS 的空間開(kāi)銷比 DFS 大因?yàn)殛?duì)列里可能同時(shí)存著很多層的節(jié)點(diǎn)。但在迷宮問(wèn)題里格子總數(shù)有限這個(gè)開(kāi)銷完全可以接受。換來(lái)的好處是路徑一定最短這在很多實(shí)際場(chǎng)景下比省內(nèi)存更重要。2.4 路徑回溯與可視化輸出找到路徑后需要把路徑標(biāo)記出來(lái)并打印。DFS 的路徑直接在棧里從棧底到棧頂就是完整路徑。BFS 的路徑需要從終點(diǎn)沿著parent往回找找到后反轉(zhuǎn)一下。// 打印迷宮路徑用 * 表示 void printMaze(int pathX[], int pathY[], int pathLen) { // 先把路徑坐標(biāo)標(biāo)記到迷宮上 for (int i 0; i pathLen; i) { maze[pathX[i]][pathY[i]] 3; // 3表示路徑 } for (int i 0; i MAX_ROW; i) { for (int j 0; j MAX_COL; j) { if (maze[i][j] 0) cout # ; // 墻壁 else if (maze[i][j] 3) cout * ; // 路徑 else cout ; // 通路 } cout endl; } }可視化輸出用字符畫#表示墻*表示路徑空格表示可走但沒(méi)走的通路。這樣在控制臺(tái)里一眼就能看出路徑形態(tài)。如果想更直觀可以在路徑上加上方向箭頭但課設(shè)通常字符畫就夠了。路徑回溯時(shí)要注意DFS 的棧里存的是從起點(diǎn)到終點(diǎn)的順序直接遍歷即可。BFS 需要從終點(diǎn)節(jié)點(diǎn)開(kāi)始不斷找parent直到parent -1然后把收集到的坐標(biāo)反轉(zhuǎn)。反轉(zhuǎn)可以用一個(gè)臨時(shí)數(shù)組也可以用std::reverse。3. 從源碼到運(yùn)行編譯、測(cè)試與參數(shù)調(diào)整3.1 項(xiàng)目文件結(jié)構(gòu)與編譯命令這個(gè)項(xiàng)目結(jié)構(gòu)很簡(jiǎn)單適合課設(shè)提交。常見(jiàn)做法是分成三個(gè)文件maze.h放數(shù)據(jù)結(jié)構(gòu)和函數(shù)聲明maze.cpp放具體實(shí)現(xiàn)main.cpp放測(cè)試入口。也可以直接寫成一個(gè).cpp文件看課設(shè)要求。# 單文件編譯 g -o maze maze.cpp -stdc11 # 多文件編譯 g -o maze main.cpp maze.cpp -stdc11 # 運(yùn)行 ./mazeWindows 下用 MinGW 或者 Visual Studio 都可以。Visual Studio 建空項(xiàng)目把.cpp文件加進(jìn)去直接 F5 就行。注意如果用了std::reverse需要#include algorithm。編譯時(shí)建議加上-Wall看警告有些數(shù)組越界或者未初始化變量編譯器會(huì)提醒。課設(shè)代碼雖然不要求工業(yè)級(jí)健壯性但能跑對(duì)是底線。3.2 測(cè)試用例設(shè)計(jì)與手動(dòng)驗(yàn)證迷宮數(shù)據(jù)可以硬編碼在代碼里也可以從文件讀。硬編碼適合快速測(cè)試文件讀入適合批量驗(yàn)證。常見(jiàn)做法是準(zhǔn)備幾個(gè)不同形態(tài)的迷宮簡(jiǎn)單直路、多岔路、有環(huán)、無(wú)解。// 測(cè)試用例一個(gè) 10x10 的迷宮 int testMaze[10][10] { {0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,0,0,1,0,1,0,1,0}, {0,1,1,1,1,0,1,1,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,0,0,0,0,0,1,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,0} };手動(dòng)驗(yàn)證時(shí)先自己走一遍數(shù)一數(shù)最短路徑多少步。然后跑 BFS看輸出的路徑步數(shù)是否一致。再跑 DFS看路徑是否合法每一步都是相鄰格子不穿墻。如果 BFS 和 DFS 結(jié)果一樣長(zhǎng)說(shuō)明迷宮沒(méi)有岔路如果 DFS 更長(zhǎng)說(shuō)明 BFS 確實(shí)找到了更優(yōu)解。無(wú)解迷宮也要測(cè)。把終點(diǎn)用墻圍死看程序是否正常返回“無(wú)解”而不是死循環(huán)。DFS 在無(wú)解時(shí)會(huì)遍歷所有可達(dá)格子然后?？胀顺鯞FS 會(huì)隊(duì)列空退出都不會(huì)死循環(huán)但前提是標(biāo)記邏輯寫對(duì)了。3.3 參數(shù)調(diào)整迷宮尺寸與方向順序迷宮尺寸由MAX_ROW和MAX_COL控制改大之后棧和隊(duì)列的數(shù)組也要跟著改。如果不想手動(dòng)改可以用std::vector動(dòng)態(tài)分配但課設(shè)通常要求用原生數(shù)組考察靜態(tài)內(nèi)存管理。方向順序影響 DFS 路徑形態(tài)。把dx和dy的順序換一下比如改成下、右、上、左DFS 找到的路徑會(huì)完全不同。這不是錯(cuò)誤是 DFS 的非確定性。如果想固定路徑形態(tài)可以在找到路徑后按坐標(biāo)排序但沒(méi)必要。BFS 的路徑長(zhǎng)度不受方向順序影響但路徑具體走法可能不同。因?yàn)橥粚拥墓?jié)點(diǎn)擴(kuò)展順序變了到達(dá)終點(diǎn)時(shí)可能有多條等長(zhǎng)路徑先被擴(kuò)展到的會(huì)被記錄。提示修改方向順序后記得重新跑一遍測(cè)試用例確認(rèn)路徑仍然合法。有時(shí)候方向順序變了某些邊界條件會(huì)暴露出來(lái)。4. 避坑與排查課設(shè)里最容易翻車的幾個(gè)點(diǎn)4.1 死循環(huán)標(biāo)記時(shí)機(jī)不對(duì)現(xiàn)象程序跑起來(lái)卡住不動(dòng)CPU 占用飆升等半天不出結(jié)果。原因DFS 里忘記標(biāo)記已訪問(wèn)或者 BFS 里出隊(duì)才標(biāo)記。老鼠在兩個(gè)格子之間來(lái)回走永遠(yuǎn)走不到終點(diǎn)。解決DFS 在入棧時(shí)標(biāo)記maze[nx][ny] 2BFS 在入隊(duì)時(shí)標(biāo)記。標(biāo)記之后這個(gè)格子就不會(huì)再被其他節(jié)點(diǎn)加入。記住一個(gè)原則什么時(shí)候把這個(gè)格子放進(jìn)數(shù)據(jù)結(jié)構(gòu)就什么時(shí)候標(biāo)記。4.2 路徑錯(cuò)誤回溯時(shí)坐標(biāo)順序反了現(xiàn)象打印出來(lái)的路徑從終點(diǎn)到起點(diǎn)或者路徑中間斷開(kāi)了。原因BFS 回溯時(shí)從終點(diǎn)往起點(diǎn)找收集到的坐標(biāo)是反的忘記反轉(zhuǎn)。或者 DFS 棧里存的路徑順序理解錯(cuò)了。解決BFS 回溯后一定要反轉(zhuǎn)數(shù)組。DFS 的棧底是起點(diǎn)棧頂是終點(diǎn)從棧底遍歷到棧頂就是正確順序?？梢栽诖蛴∏凹右痪漭敵雎窂介L(zhǎng)度和預(yù)期對(duì)比。4.3 數(shù)組越界邊界檢查漏了現(xiàn)象程序崩潰報(bào)段錯(cuò)誤或者輸出亂碼。原因迷宮外圍沒(méi)有留墻壁老鼠走到邊界時(shí)nx或ny超出數(shù)組范圍。解決初始化迷宮時(shí)最外圈全部設(shè)為 0墻壁。這樣任何從內(nèi)部格子出發(fā)的移動(dòng)最多走到外圈墻壁就被擋住了不會(huì)越界。如果迷宮是從文件讀的讀入后手動(dòng)把外圈覆蓋成 0。4.4 棧溢出遞歸 DFS 深度太大現(xiàn)象用遞歸寫 DFS 時(shí)迷宮稍微大一點(diǎn)就崩潰。原因遞歸深度等于路徑長(zhǎng)度迷宮 100x100 時(shí)遞歸深度可能上千默認(rèn)?？臻g不夠。解決改用棧模擬遞歸就是 2.2 節(jié)的做法。如果堅(jiān)持用遞歸可以調(diào)大棧空間但課設(shè)通常不允許改編譯選項(xiàng)。棧模擬是更穩(wěn)妥的方案。4.5 結(jié)果不一致BFS 和 DFS 路徑長(zhǎng)度比較現(xiàn)象BFS 和 DFS 輸出的路徑長(zhǎng)度一樣懷疑 BFS 沒(méi)起作用。原因迷宮太簡(jiǎn)單沒(méi)有岔路或者岔路都是死路兩種算法找到的是同一條路。解決換一個(gè)有多條等長(zhǎng)路徑的迷宮測(cè)試。比如一個(gè) 3x3 的方格從左上到右下有兩條路BFS 會(huì)選其中一條DFS 可能選另一條但長(zhǎng)度一樣。要驗(yàn)證 BFS 的最短性需要找一個(gè) DFS 會(huì)繞遠(yuǎn)的迷宮比如有長(zhǎng)死胡同的。5. 二次開(kāi)發(fā)把課設(shè)變成能拿得出手的項(xiàng)目課設(shè)做完只是起點(diǎn)如果想讓它更有說(shuō)服力可以在這幾個(gè)方向改造。第一個(gè)方向是加圖形界面。用 EasyX 或者 SDL2 把字符畫換成真正的圖形墻壁畫方塊路徑畫線老鼠用一個(gè)小圓點(diǎn)表示。這樣演示效果直接提升一個(gè)檔次。EasyX 在 Windows 上配置簡(jiǎn)單適合課設(shè)答辯。改造時(shí)把printMaze換成繪圖函數(shù)其他邏輯不動(dòng)。第二個(gè)方向是支持從文件讀迷宮。定義一個(gè)簡(jiǎn)單的文本格式第一行是行列數(shù)后面是 0/1 矩陣。這樣不用改代碼就能換迷宮測(cè)試方便很多。讀文件時(shí)注意處理行末換行符和空格。// 從文件讀迷宮 bool loadMaze(const string filename) { ifstream fin(filename); if (!fin) return false; int rows, cols; fin rows cols; for (int i 0; i rows; i) for (int j 0; j cols; j) fin maze[i][j]; return true; }第三個(gè)方向是加性能統(tǒng)計(jì)。記錄兩種算法擴(kuò)展了多少個(gè)節(jié)點(diǎn)、耗時(shí)多少毫秒。用clock()函數(shù)就能測(cè)。這樣在答辯時(shí)可以拿出數(shù)據(jù)說(shuō)“BFS 擴(kuò)展節(jié)點(diǎn)更多但路徑更短DFS 擴(kuò)展少但路徑可能更長(zhǎng)”比空口說(shuō)更有說(shuō)服力。第四個(gè)方向是支持多起點(diǎn)多終點(diǎn)。把起點(diǎn)和終點(diǎn)做成數(shù)組循環(huán)調(diào)用尋路函數(shù)輸出每一對(duì)的最短路徑。這個(gè)改造能體現(xiàn)對(duì)算法接口的抽象能力。改造時(shí)有個(gè)血淚經(jīng)驗(yàn)每次只改一個(gè)地方改完立刻跑測(cè)試用例。我見(jiàn)過(guò)太多人一口氣改了三四個(gè)功能結(jié)果跑不起來(lái)不知道是哪個(gè)改壞了。用 git 管理代碼每改完一個(gè)功能就 commit 一次出問(wèn)題直接回滾。從那以后我每次做課設(shè)改造都強(qiáng)制走一遍“改一處、編一次、跑一遍”的流程再也不敢攢著一起改。希望這個(gè)項(xiàng)目能幫你把數(shù)據(jù)結(jié)構(gòu)課設(shè)順利跑通也能成為你后續(xù)改造的起點(diǎn)。本文還有配套的精品資源點(diǎn)擊獲取