1、精品文檔課程設計說明書數據結構課程設計專 業: 課程名稱: 數據結構課程設計 班級: 設計題目: 走迷宮游戲 設計時間: 2021-2-25 至 2021-3-8 評 語:_評閱成績: 評閱教師: 一、問題描述與需求分析1、問題描述程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規定的時間內走到糧倉處。要求：1) 老鼠形象可識別，可用鍵盤操縱老鼠上下左右移動；2) 迷宮的墻足夠結實，老鼠不能穿墻而過；3) 正確檢測結果，假設老鼠在規定時間內走到糧倉處，提示成功，否那么提示失敗；4) 添加編輯迷宮功能，可修改當前迷宮，修改內容：

2、墻變路、路變墻；5) 找出走出迷宮的所有路徑，以及最短路徑； 6利用序列化功能實現迷宮地圖文件的存盤和讀出等功能。2、 功能需求分析1. 老鼠形象設計，使用圖形化編程，繪制橢圓，填充顏色，繪制線。2. 設置游戲者在探索過程中遇到迷宮邊界和墻時，不可繼續前行，定義好迷宮邊界。3. 使用time函數獲取系統時間，處理游戲所用時間，限定操作時間，對游戲者的位置有準確的判斷，當到達出口時，可以識別，返回提示信息。4. 對于迷宮的所有路徑的求解，比擬最短路徑，最小生成樹算法。5.對迷宮的地圖可將其存儲到二進制文件中，在下次使用時直接調用，讀取文件。二、概要設計1、總體設計思路在程序中，采用二維數組存儲迷

3、宮地圖0：墻 1：路，在探索迷宮過程中采用棧的數據結構存儲探索迷宮時的全部路徑和有效路徑，因棧的“后進先出結構非常適合探索過程中的退步，即可以保證在任何位置都可沿原路退回。在探索迷宮過程中采用的是“窮舉求解的方法，即從入口出發，順某一方向向前探索，假設能走通，那么繼續往前走；否那么沿原路退回，換一個方向在繼續探索，直到所有可能的通路都探索到為止。2、 模塊簡介程序由以下幾個模塊組成：（1） 迷宮地圖隨機生成模塊：入口：int *Maze()出口：return maze;實現功能：該函數使用 new函數為指向二維數組的指針maze 申請存儲空間，分兩步實現，先申請長度等于行數加2 的二級指針，然

4、后為每個二維指針申請存儲空間。調用包含在頭文件 stdlib .h 中的庫函數，隨機數生成器 srand( ),rand( ), 及包含在頭文件time.h 中的系統時間函數time(),srand(unsigned)time(NULL) 使用系統時間，傳入空指針NULL，作為初始化種子，使得在后面調用的rand()%2函數產生不同的隨機數，取余之后為(0和1)，從而實現了迷宮地圖的隨機生成，但使用該方法產生的迷宮地圖中不一定存在一條從入口到出口的路徑。最后使用for循環嵌套給迷宮的上、下、左、右邊界賦值0為墻壁；指定迷宮的入口與出口位置同時賦值為1為通道。因定義了二維指針類型函數，故在其它函

5、數調用該函數時返回指向迷宮地圖的二維指針，使得調用迷宮地圖極為方便。（2） 棧操作實現模塊：該模塊共包含：初始化棧，元素入棧，元素出棧，刪除棧頂元素，棧的遍歷 5個函數。初始化棧入口：int StackTraverse(SqStack *s) 出口：exit(OVERFLOW); return TRUE; 實現功能：初始化一個棧，并為其分配存儲空間初始量。形參為棧類型指針，調用時傳遞實參全局變量realPath Path 地址，調用包含在頭文件 malloc.h 中的庫函數malloc 根據棧的存儲空間初始量及SqStack所占字節為其動態分配內存，最后，將內存地址賦給棧底指針，同時使棧頂指針

6、也指向該內存，棧的大小為存儲空間初始量；當分配失敗時，返回空指針NULL，退出該函數同時輸出錯誤提醒語句，以便調試；分配成功，返回TRUE，說明該函數已執行。這樣做的優點是節省了內存，根據存儲使用量動態分配，在使用結束后可及時釋放該內存。元素入棧入口：int Push(SqStack *s,SElemType e)出口：exit(OVERFLOW); return TRUE;實現功能：向棧中添加新元素。形參為棧類型指針，棧元素類型e ，調用時傳遞實參地址及入棧元素；但需注意的是：在入棧之前要判斷棧是否還有空間容納新元素，如棧滿s->top - s->base >= s->

7、;stackSize那么應使用 realloc 函數為棧分配存儲空間增量STACKINCREMENT，在棧底指針base 之后追加增量，同時將新的地址賦給base，此時應重新定位棧頂指針s->top = s->base + s->stacksize;，因重新分配了空間base值已改變，所以top值也就相應的改變，才能指向新的元素；如存儲分配失敗，那么輸出提醒語句，退出函數；否那么，新元素e 入棧，棧頂指針top+ ，返回TRUE ，函數正常退出。元素出棧入口：SElemType GetTop(SqStack *s) 出口：exit(ERROR); return *(s->

8、;top - 1);實現功能：假設棧非空，獲取棧頂元素，并返回其值。因函數類型為棧元素類型，故可直接返回棧頂元素，需注意的是：在出棧之前要判斷棧是否非空s->top = s->base，假設base 值等于 top 值，那么說明棧空，輸出錯誤提醒語句，強制退出函數；否那么，top 值減 1 ，返回棧頂元素，此時函數正常退出。刪除棧頂元素入口：int Pop(SqStack *s) 出口： exit(ERROR); return TRUE;實現功能：假設棧非空，那么刪除棧頂元素。同樣，在刪除元素之前需判斷棧是否非空，是，那么棧頂指針 top - - 返回TRUE ，函數正常退出；否s

9、->top = s->base，那么輸出錯誤提醒語句，強制退出函數。棧的遍歷入口：int StackTraverse(SqStack *s)出口：return TRUE;實現功能：逆序遍歷棧，先指向棧底元素，以后依次向上增 1 ，輸出迷宮從入口到出口的路徑。當base 值小于top - 1 時執行 while 循環，由棧底依次向上輸出棧中元素，s -> base + ，不滿足條件時跳出 while 循環，此時棧底指針指向棧頂元素，輸出棧中最后一個元素，即迷宮通道中的出口位置。（3） 探索迷宮操作模塊：該模塊共包含：判斷當前位置是否走過，獲取東面相鄰位置，獲取南面相鄰位置，獲取

10、西面相鄰位置，獲取北面相鄰位置，獲取下一可通行位置，以及獲取迷宮路徑函數 7個函數，其中獲取迷宮路徑函數為主要函數，調用其他函數以實現獲取迷宮路徑，并將其存儲到棧中。判斷當前位置是否走過入口：int UnPass(SqStack path, SElemType e);出口：return flag;實現功能：在探索迷宮時，調用該函數，判斷當前位置是否走過。形參為棧類型 path ，棧元素類型 e ，在調用時傳遞全局變量Path ，即存儲探索迷宮時走過的所有路徑的棧，當前位置的棧元素類型；在該函數中，定義整型數 flag = 1 作為標記，當棧Path 非空時執行 while 循環，比擬當前位置對

11、應坐標是否與出棧元素的坐標相等，即判斷當前位置是否在Path 的路徑中出現過，假設滿足條件，標記flag = 0 ，Path.top - ，即每執行一次循環，頭指針下移一個位置，直到不滿足條件時跳出循環，即將Path 中所有元素都與當前位置作了比擬；假設有符合要求的，返回標記flag = 0 ，說明該位置走過；否那么，返回標記flag=1，該位置未曾走過。獲取東面相鄰位置入口：SElemType getEast(int *m,SElemType e)出口：return e;實現功能：獲取東面相鄰位置信息，返回棧元素類型，包含位置坐標，方向。形參為二維指針m ，棧元素類型 e ，調用時傳遞指向迷

12、宮地圖的二維指針，及當前位置；注：以屏幕左上角為坐標原點，水平向右為 y 軸正方向，豎直向下為 x 軸正方向。判斷當前位置未到迷宮右東邊界時，當前位置 y 坐標加 1e.curpos.y += 1;，將東面相鄰位置在迷宮地圖中的值賦給當前位置e.curpos.val = me.curpos.xe.curpos.y; ，返回 e ，從而實現了獲取當前位置的東面相鄰位置信息。獲取南面相鄰位置入口：SElemType getSouth(int *m,SElemType e)出口：return e;實現功能：獲取南面相鄰位置信息。需判斷當前位置是否已到迷宮下南邊界。x 位置坐標加 1e.curpos.

13、x += 1;獲取西面相鄰位置入口：SElemType getWest(int *m,SElemType e)出口：return e;實現功能：獲取西面相鄰位置信息。需判斷當前位置是否已到迷宮左西邊界。y 位置坐標加 1e.curpos.y += 1;獲取北面相鄰位置入口：SElemType getNorth(int *m,SElemType e)出口：return e;實現功能：獲取北面相鄰位置信息。需判斷當前位置是否已到迷宮上北邊界。x 位置坐標減 1e.curpos.x -= 1;獲取下一可通行位置入口：SElemType NextPos(SElemType e)出口：return ne

14、xt;實現功能：在當前位置，向四個方向東、南、西、北探索，調用、函數，假設相鄰位置可行走，且未曾走過，那么返回該位置信息，將當前位置切換到下一位置。獲取迷宮路徑函數入口：int MazePath(Position start,Position end);出口：return TRUE; return FALSE;實現功能：假設迷宮Maze 中存在從入口 start 到出口 end 的通道，那么求得一條存放在棧中realPath(從棧底到棧頂)，并返回 TRUE ；否那么返回 FALSE 。（4） 輔助函數模塊：輸出迷宮地圖入口：int PrintMap(int *temp);出口：return

15、TRUE;實現功能：在主函數中調用，傳遞實參指向迷宮地圖的二維指針，使用 for 循環嵌套輸出迷宮地圖。錯誤消息提示入口：int errormessage()出口：return TRUE;實現功能：錯誤消息提示（5） 主函數模塊：入口：int main() 出口：return 0;實現功能：程序執行的入口，在主函數中調用各個模塊，實現程序的運行。初始化棧，Path 用于存放探索迷宮時的全部路徑，realPath 用于存放迷宮入口到出口的有效路徑；初始化游戲參數，對全局變量map入口、出口位置坐標、對應地圖值為1進行賦值；調用迷宮地圖輸出函數，輸出迷宮；調用獲取迷宮路徑函數，假設存在一條路徑，那

16、么存放到棧realPath ；調用遍歷棧函數，逆序輸出棧中元素從棧底到棧頂，即從入口位置到出口位置的一條路徑。return 0; 主函數結束，程序運行結束。三、詳細設計1、數據結構設計1程序中定義了迷宮的位置坐標，結構體類型Position ，包含整型數 x , y 存儲迷宮地圖二維數組對應的行和列坐標，整型數 val 用于存儲迷宮地圖的值，如0和1。特別說明： val 值是作為迷宮探索時的重要判斷標記，假設當前位置的四面為墻0或已走過，那么在切換下一位置的函數NextPos中所返回val的值為-1。詳細定義如下：typedef struct int x; /二維數組maze下標 int y;

17、int val; /mazexy的值Position; /游戲中的位置坐標（2） 程序中定義了結構體類型MapCfg ,及對應該結構體類型全局變量map，包含上一結構體類型Position變量start, end,即迷宮的起始位置與結束位置，在調用探索迷宮函數時，傳遞實參起始位置，結束位置為全局變量直接調用，從而使得在判斷結束位置時更加方便，但需注意的一點是：在調用之前要給起始、結束位置坐標變量賦初值。詳細定義如下：typedef structPosition start; /起始位置Position end; /結束位置MapCfg;MapCfg map;（3） 程序中定義了迷宮中路徑單獨每

18、一通道塊所存儲的結構體類型，包含當前位置坐標，及從該通道塊走向下一通道塊的“方向，如：1：東，2：南，3：西，4：北。注：為存儲迷宮路徑的數據結構棧的元素類型。詳細定義如下：typedef structPosition curpos; /通道塊在迷宮中的位置坐標int di; /從此通道塊走向下一通道塊的"方向"SElemType;（4） 程序中定義了探索迷宮、和從入口 start 到出口 end 的通道,所存儲的數據結構棧，為全局變量Path,realPath ,其存儲方式為順序棧，包含指向棧元素類型的棧底base和棧頂top指針，及棧的存儲空間stacksize ，需注

19、意的是：在初始化棧時要分配給存儲空間初始量，在后續使用過程中可為其分配增量，以滿足存儲要求。詳細定義如下：typedef structSElemType* base; /棧底指針SElemType* top; /棧頂指針int stacksize; /棧的大小SqStack;SqStack realPath; /存放路徑SqStack Path; /探索迷宮2、 算法分析與實現主要功能模塊的算法設計分析。int MazePath(Position start,Position end) int *temp = Maze();SElemType e;e.curpos.x = map.start.

20、x; /設定"當前位置"為"入口位置"e.curpos.y = map.start.y;e.curpos.val = tempmap.start.xmap.start.y;doif( UnPass(Path, e) ) /當前位置可以通過,即是未曾走過的通道塊Push(&realPath,e); Push(&Path,e); e = NextPos(e);if(e.curpos.x = map.end.x && e.curpos.y = map.end.y) /到達終點(出口)Push(&realPath,e);P

21、ush(&Path,e);StackTraverse(&Path);return TRUE;else if(e.curpos.val = -1)/當前位置的四面或為墻或已走過 Pop(&realPath);/刪除真實路徑的棧頂元素 e = GetTop(&realPath);/令e指向棧頂元素 else/如果當前位置已經走過,說明原來測試的方向不對,現在嘗試其它方向 e = NextPos(e); if (e.curpos.val = -1) /仍不通,刪除真實路徑的棧頂元素 Pop(&realPath); e = GetTop(&realPat

22、h);/令cur指向棧頂元素 while(e.curpos.x != end.x | e.curpos.y != end.y);return FALSE;四、運行結果和調試分析程序運行結果圖：1.計算機“窮舉求解法，輸出迷宮入口到出口路徑。 2.用二維數組表示迷宮地圖，0 為墻，1 為道路。在程序調試過程中遇到變量不能被賦值的問題，后來經過按F5進行斷點調試，根據錯誤提醒，發現了問題所在，得到了及時的修改。在本程序中對于迷宮當前位置是否走過的判斷，需要對存儲所有路徑的realPath 一一訪問，比照當前位置是否被訪問過，追其原因，是由于探索過程中并沒有做好該位置已被訪問的標記，導致每一位置都需重新定位，進行判斷，浪費了時間與存儲空間。改良：在棧元素類型，即迷宮中每一位置，增加flag 標記，假設已訪問那么標記 -1 ，下次獲得該位置坐標后便可得知該位置是否被訪問過的信息。五、總結體會在這次數據結構課程設計中，我并沒有很好的完成所選題目的要求，如圖形化的編程，以及windows 窗口的編程，還有對于鍵盤操縱游戲者。在