簡介這份C數(shù)據(jù)結(jié)構(gòu)課設(shè)資源圍繞“老鼠走迷宮”展開面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、需要完成課程設(shè)計(jì)或想通過實(shí)戰(zhàn)鞏固搜索算法的學(xué)生與開發(fā)者。項(xiàng)目以二維數(shù)組抽象迷宮用0和1區(qū)分通路與墻壁并借助深度優(yōu)先搜索實(shí)現(xiàn)隨機(jī)迷宮生成與路徑求解幫助讀者理解圖、棧、隊(duì)列等結(jié)構(gòu)在實(shí)際問題中的落地方式。壓縮包共27個(gè)文件約148.59MB包含cpp與h源碼、sln與vcxproj工程文件、exe可執(zhí)行程序、mp4使用說明與素材替換視頻、png與jpg示意圖以及pdb、ilk、obj等調(diào)試編譯中間文件另附txt說明文檔便于直接運(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)的回溯有沒有問題全憑腦補(bǔ)。這個(gè)“老鼠走迷宮”項(xiàng)目就是來解決這個(gè)痛點(diǎn)的它把經(jīng)典的迷宮求解問題做成了可視化演示用 C 實(shí)現(xiàn)核心是棧和隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)的對(duì)比應(yīng)用。DFS 用棧實(shí)現(xiàn)BFS 用隊(duì)列實(shí)現(xiàn)兩條路徑同時(shí)跑誰長誰短一目了然。適合正在做課設(shè)的本科生、想復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的同學(xué)以及需要一份能直接編譯運(yùn)行的 C 項(xiàng)目參考的開發(fā)者。整個(gè)項(xiàng)目不依賴任何第三方圖形庫純控制臺(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ù)組來存儲(chǔ)0 表示墻壁1 表示通路這樣初始化簡單調(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 找到的第一條路徑長什么樣。如果先走上再走右老鼠會(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 的核心思想是“一條路走到黑走不通就退回來換方向”。遞歸寫法最直觀但課設(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表示已訪問 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) { // 是通路且未訪問 maze[nx][ny] 2; // 標(biāo)記已訪問 top; stack[top] {nx, ny, 0}; moved true; break; } } // 四個(gè)方向都走不通出?；厮?if (!moved) { top--; } } return false; // 棧空還沒到終點(diǎn)無解 }這段代碼有幾個(gè)關(guān)鍵點(diǎn)。第一棧里存的不是簡單的坐標(biāo)而是StackNode多了一個(gè)dir字段。這個(gè)字段記錄當(dāng)前節(jié)點(diǎn)已經(jīng)嘗試到第幾個(gè)方向了回溯回來的時(shí)候不用從頭再試直接從上次的位置繼續(xù)。第二maze[nx][ny] 2這個(gè)標(biāo)記很關(guān)鍵它防止老鼠在原地打轉(zhuǎn)。第三cur用了引用StackNode cur stack[top]這樣修改cur.dir就是直接改棧頂元素不需要出棧再入棧。參數(shù)說明startX, startY是起點(diǎn)坐標(biāo)endX, endY是終點(diǎn)坐標(biāo)。返回值bool表示是否找到路徑。如果找到棧里從底到頂就是完整路徑如果沒找到棧會(huì)逐步清空。DFS 找到的路徑不一定最短這是它的固有特性。在迷宮這種場(chǎng)景下它可能繞很大一圈才到終點(diǎn)。但 DFS 的優(yōu)勢(shì)是實(shí)現(xiàn)簡單空間開銷小——棧的最大深度不會(huì)超過通路格子總數(shù)。2.3 BFS 尋路隊(duì)列逐層擴(kuò)展保證最短路徑BFS 的思路是“一層一層往外擴(kuò)”用隊(duì)列實(shí)現(xiàn)。每從隊(duì)頭取出一個(gè)節(jié)點(diǎn)就把它的所有未訪問鄰居加入隊(duì)尾。這樣保證第一次到達(dá)終點(diǎn)時(shí)走過的步數(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)通過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ù)索引來追溯。找到終點(diǎn)后從終點(diǎn)節(jié)點(diǎn)開始沿著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ì)列爆炸式增長內(nèi)存直接爆掉。這是 BFS 實(shí)現(xiàn)中最常見的坑。BFS 的空間開銷比 DFS 大因?yàn)殛?duì)列里可能同時(shí)存著很多層的節(jié)點(diǎn)。但在迷宮問題里格子總數(shù)有限這個(gè)開銷完全可以接受。換來的好處是路徑一定最短這在很多實(shí)際場(chǎng)景下比省內(nèi)存更重要。2.4 路徑回溯與可視化輸出找到路徑后需要把路徑標(biāo)記出來并打印。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; } }可視化輸出用字符畫#表示墻*表示路徑空格表示可走但沒走的通路。這樣在控制臺(tái)里一眼就能看出路徑形態(tài)。如果想更直觀可以在路徑上加上方向箭頭但課設(shè)通常字符畫就夠了。路徑回溯時(shí)要注意DFS 的棧里存的是從起點(diǎn)到終點(diǎn)的順序直接遍歷即可。BFS 需要從終點(diǎn)節(jié)點(diǎn)開始不斷找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)很簡單適合課設(shè)提交。常見做法是分成三個(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)證。常見做法是準(zhǔn)備幾個(gè)不同形態(tài)的迷宮簡單直路、多岔路、有環(huán)、無解。// 測(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é)果一樣長說明迷宮沒有岔路如果 DFS 更長說明 BFS 確實(shí)找到了更優(yōu)解。無解迷宮也要測(cè)。把終點(diǎn)用墻圍死看程序是否正常返回“無解”而不是死循環(huán)。DFS 在無解時(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)排序但沒必要。BFS 的路徑長度不受方向順序影響但路徑具體走法可能不同。因?yàn)橥粚拥墓?jié)點(diǎn)擴(kuò)展順序變了到達(dá)終點(diǎn)時(shí)可能有多條等長路徑先被擴(kuò)展到的會(huì)被記錄。提示修改方向順序后記得重新跑一遍測(cè)試用例確認(rèn)路徑仍然合法。有時(shí)候方向順序變了某些邊界條件會(huì)暴露出來。4. 避坑與排查課設(shè)里最容易翻車的幾個(gè)點(diǎn)4.1 死循環(huán)標(biāo)記時(shí)機(jī)不對(duì)現(xiàn)象程序跑起來卡住不動(dòng)CPU 占用飆升等半天不出結(jié)果。原因DFS 里忘記標(biāo)記已訪問或者 BFS 里出隊(duì)才標(biāo)記。老鼠在兩個(gè)格子之間來回走永遠(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)象打印出來的路徑從終點(diǎn)到起點(diǎn)或者路徑中間斷開了。原因BFS 回溯時(shí)從終點(diǎn)往起點(diǎn)找收集到的坐標(biāo)是反的忘記反轉(zhuǎn)?；蛘?DFS 棧里存的路徑順序理解錯(cuò)了。解決BFS 回溯后一定要反轉(zhuǎn)數(shù)組。DFS 的棧底是起點(diǎn)棧頂是終點(diǎn)從棧底遍歷到棧頂就是正確順序。可以在打印前加一句輸出路徑長度和預(yù)期對(duì)比。4.3 數(shù)組越界邊界檢查漏了現(xiàn)象程序崩潰報(bào)段錯(cuò)誤或者輸出亂碼。原因迷宮外圍沒有留墻壁老鼠走到邊界時(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)就崩潰。原因遞歸深度等于路徑長度迷宮 100x100 時(shí)遞歸深度可能上千默認(rèn)棧空間不夠。解決改用棧模擬遞歸就是 2.2 節(jié)的做法。如果堅(jiān)持用遞歸可以調(diào)大?？臻g但課設(shè)通常不允許改編譯選項(xiàng)。棧模擬是更穩(wěn)妥的方案。4.5 結(jié)果不一致BFS 和 DFS 路徑長度比較現(xiàn)象BFS 和 DFS 輸出的路徑長度一樣懷疑 BFS 沒起作用。原因迷宮太簡單沒有岔路或者岔路都是死路兩種算法找到的是同一條路。解決換一個(gè)有多條等長路徑的迷宮測(cè)試。比如一個(gè) 3x3 的方格從左上到右下有兩條路BFS 會(huì)選其中一條DFS 可能選另一條但長度一樣。要驗(yàn)證 BFS 的最短性需要找一個(gè) DFS 會(huì)繞遠(yuǎn)的迷宮比如有長死胡同的。5. 二次開發(fā)把課設(shè)變成能拿得出手的項(xiàng)目課設(shè)做完只是起點(diǎn)如果想讓它更有說服力可以在這幾個(gè)方向改造。第一個(gè)方向是加圖形界面。用 EasyX 或者 SDL2 把字符畫換成真正的圖形墻壁畫方塊路徑畫線老鼠用一個(gè)小圓點(diǎn)表示。這樣演示效果直接提升一個(gè)檔次。EasyX 在 Windows 上配置簡單適合課設(shè)答辯。改造時(shí)把printMaze換成繪圖函數(shù)其他邏輯不動(dòng)。第二個(gè)方向是支持從文件讀迷宮。定義一個(gè)簡單的文本格式第一行是行列數(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ù)說“BFS 擴(kuò)展節(jié)點(diǎn)更多但路徑更短DFS 擴(kuò)展少但路徑可能更長”比空口說更有說服力。第四個(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è)試用例。我見過太多人一口氣改了三四個(gè)功能結(jié)果跑不起來不知道是哪個(gè)改壞了。用 git 管理代碼每改完一個(gè)功能就 commit 一次出問題直接回滾。從那以后我每次做課設(shè)改造都強(qiáng)制走一遍“改一處、編一次、跑一遍”的流程再也不敢攢著一起改。希望這個(gè)項(xiàng)目能幫你把數(shù)據(jù)結(jié)構(gòu)課設(shè)順利跑通也能成為你后續(xù)改造的起點(diǎn)。本文還有配套的精品資源點(diǎn)擊獲取