數(shù)據(jù)結構課程設計-走迷宮游戲

hhhhhh課程設計說明書（數(shù)據(jù)結構課程設計）專業(yè):課程名稱:數(shù)據(jù)結構課程設計班級:設計題目:走迷宮游戲設計時間:2013-2-25至2013-3-8評語:_____________________________________________________________________________________________________________________________________________________________________________________________________評閱成績:＿＿＿＿評閱教師:＿＿hhhhhh一、問題描述與需求分析1、問題描述程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。要求：老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；迷宮的墻足夠結實，老鼠不能穿墻而過；正確檢測結果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失??；添加編輯迷宮功能，可修改當前迷宮，修改內(nèi)容：墻變路、路變墻；找出走出迷宮的所有路徑，以及最短路徑；6）利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能。功能需求分析老鼠形象設計，使用圖形化編程，繪制橢圓，填充顏色，繪制線。設置游戲者在探索過程中遇到迷宮邊界和墻時，不可繼續(xù)前行，定義好迷宮邊界。使用time函數(shù)獲取系統(tǒng)時間，處理游戲所用時間，限定操作時間，對游戲者的位置有準確的判斷，當?shù)竭_出口時，可以識別，返回提示信息。對于迷宮的所有路徑的求解，比較最短路徑，最小生成樹算法。5.對迷宮的地圖可將其存儲到二進制文件中，在下次使用時直接調(diào)用，讀取文件。二、概要設計1、總體設計思路在程序中，采用二維數(shù)組存儲迷宮地圖（0：墻1：路），在探索迷宮過程中采用棧的數(shù)據(jù)結構存儲探索迷宮時的全部路徑和有效路徑，因棧的“后進先出”結構非常適合探索過程中的退步，即可以保證在任何位置都可沿原路退回。在探索迷宮過程中采用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向在繼續(xù)探索，直到所有可能的通路都探索到為止。hhhhhh2、模塊簡介程序由以下幾個模塊組成：迷宮地圖隨機生成模塊：入口：int**Maze()出口：returnmaze;實現(xiàn)功能：該函數(shù)使用new函數(shù)為指向二維數(shù)組的指針maze申請存儲空間，分兩步實現(xiàn)，先申請長度等于行數(shù)加2的二級指針，然后為每個二維指針申請存儲空間。調(diào)用包含在頭文件stdlib.h中的庫函數(shù)，隨機數(shù)生成器srand(),rand(),及包含在頭文件time.h中的系統(tǒng)時間函數(shù)time(),srand((unsigned)time(NULL))使用系統(tǒng)時間，傳入空指針NULL，作為初始化種子，使得在后面調(diào)用的rand()%2函數(shù)產(chǎn)生不同的隨機數(shù)，取余之后為(0和1)，從而實現(xiàn)了迷宮地圖的隨機生成，但使用該方法產(chǎn)生的迷宮地圖中不一定存在一條從入口到出口的路徑。最后使用for循環(huán)嵌套給迷宮的上、下、左、右邊界賦值0（為墻壁）；指定迷宮的入口與出口位置同時賦值為1（為通道）。因定義了二維指針類型函數(shù)，故在其它函數(shù)調(diào)用該函數(shù)時返回指向迷宮地圖的二維指針，使得調(diào)用迷宮地圖極為方便。棧操作實現(xiàn)模塊：該模塊共包含：①初始化棧，②元素入棧，③元素出棧，④刪除棧頂元素，⑤棧的遍歷5個函數(shù)。①初始化棧入口：intStackTraverse(SqStack*s)出口：exit(OVERFLOW);returnTRUE;實現(xiàn)功能：初始化一個棧，并為其分配存儲空間初始量。形參為棧類型指針，調(diào)用時傳遞實參全局變量realPathPath地址，調(diào)用包含在頭文件malloc.h中的庫函數(shù)malloc根據(jù)棧的存儲空間初始量及SqStack所占字節(jié)為其動態(tài)分配內(nèi)存，最后，將內(nèi)存地址賦給棧底指針，同時使棧頂指針也指向該內(nèi)存，棧的大小為存儲空間初始量；當分配失敗時，返回空指針NULL，退出該函數(shù)同時輸出錯誤提醒語句，以便調(diào)試；分配成功，返回TRUE，表明該函數(shù)已執(zhí)行。hhhhhh這樣做的優(yōu)點是節(jié)省了內(nèi)存，根據(jù)存儲使用量動態(tài)分配，在使用結束后可及時釋放該內(nèi)存。②元素入棧入口：intPush(SqStack*s,SElemTypee)出口：exit(OVERFLOW);returnTRUE;實現(xiàn)功能：向棧中添加新元素。形參為棧類型指針，棧元素類型e，調(diào)用時傳遞實參地址及入棧元素；但需注意的是：在入棧之前要判斷棧是否還有空間容納新元素，如棧滿（s->top-s->base>=s->stackSize）則應使用realloc函數(shù)為棧分配存儲空間增量（STACKINCREMENT），在棧底指針base之后追加增量，同時將新的地址賦給base，此時應重新定位棧頂指針（s->top=s->base+s->stacksize;），因重新分配了空間base值已改變，所以top值也就相應的改變，才能指向新的元素；如存儲分配失敗，則輸出提醒語句，退出函數(shù)；否則，新元素e入棧，棧頂指針top++，返回TRUE，函數(shù)正常退出。③元素出棧入口：SElemTypeGetTop(SqStack*s)出口：exit(ERROR);return*(s->top-1);實現(xiàn)功能：若棧非空，獲取棧頂元素，并返回其值。因函數(shù)類型為棧元素類型，故可直接返回棧頂元素，需注意的是：在出棧之前要判斷棧是否非空（s->top==s->base），若base值等于top值，則表明?？?，輸出錯誤提醒語句，強制退出函數(shù)；否則，top值減1，返回棧頂元素，此時函數(shù)正常退出。④刪除棧頂元素入口：intPop(SqStack*s)出口：exit(ERROR);returnTRUE;實現(xiàn)功能：若棧非空，則刪除棧頂元素。同樣，在刪除元素之前需判斷棧是否非空，是，則棧頂指針top--返回TRUE，函數(shù)正常退出；否（s->top==s->base），則輸出錯誤提醒語句，強制退出函數(shù)。hhhhhh⑤棧的遍歷入口：intStackTraverse(SqStack*s) 出口：returnTRUE;實現(xiàn)功能：逆序遍歷棧，先指向棧底元素，以后依次向上增1，輸出迷宮從入口到出口的路徑。當base值小于top-1時執(zhí)行while循環(huán)，由棧底依次向上輸出棧中元素，s->base++，不滿足條件時跳出while循環(huán)，此時棧底指針指向棧頂元素，輸出棧中最后一個元素，即迷宮通道中的出口位置。探索迷宮操作模塊：該模塊共包含：①判斷當前位置是否走過，②獲取東面相鄰位置，③獲取南面相鄰位置，④獲取西面相鄰位置，⑤獲取北面相鄰位置，⑥獲取下一可通行位置，以及⑦獲取迷宮路徑函數(shù)7個函數(shù)，其中獲取迷宮路徑函數(shù)為主要函數(shù)，調(diào)用其他函數(shù)以實現(xiàn)獲取迷宮路徑，并將其存儲到棧中。①判斷當前位置是否走過入口：intUnPass(SqStackpath,SElemTypee);出口：returnflag;實現(xiàn)功能：在探索迷宮時，調(diào)用該函數(shù)，判斷當前位置是否走過。形參為棧類型path，棧元素類型e，在調(diào)用時傳遞全局變量Path，即存儲探索迷宮時走過的所有路徑的棧，當前位置的棧元素類型；在該函數(shù)中，定義整型數(shù)flag=1作為標記，當棧Path非空時執(zhí)行while循環(huán)，比較當前位置對應坐標是否與出棧元素的坐標相等，即判斷當前位置是否在Path的路徑中出現(xiàn)過，若滿足條件，標記flag=0，Path.top--，即每執(zhí)行一次循環(huán)，頭指針下移一個位置，直到不滿足條件時跳出循環(huán)，即將Path中所有元素都與當前位置作了比較；若有符合要求的，返回標記flag=0，表明該位置走過；否則，返回標記flag=1，該位置未曾走過。②獲取東面相鄰位置入口：SElemTypegetEast(int**m,SElemTypee)出口：returne;實現(xiàn)功能：獲取東面相鄰位置信息，返回棧元素類型，包含位置坐標，方向。形參為二維指針m，棧元素類型e，調(diào)用時傳遞指向迷宮地圖的二維指針，及當前位置；hhhhhh注：以屏幕左上角為坐標原點，水平向右為y軸正方向，豎直向下為x軸正方向。判斷當前位置未到迷宮右（東）邊界時，當前位置y坐標加1（e.curpos.y+=1;），將東面相鄰位置在迷宮地圖中的值賦給當前位置（e.curpos.val=m[e.curpos.x][e.curpos.y];），返回e，從而實現(xiàn)了獲取當前位置的東面相鄰位置信息。③獲取南面相鄰位置入口：SElemTypegetSouth(int**m,SElemTypee)出口：returne;實現(xiàn)功能：獲取南面相鄰位置信息。需判斷當前位置是否已到迷宮下（南）邊界。x位置坐標加1（e.curpos.x+=1;）④獲取西面相鄰位置入口：SElemTypegetWest(int**m,SElemTypee)出口：returne;實現(xiàn)功能：獲取西面相鄰位置信息。需判斷當前位置是否已到迷宮左（西）邊界。y位置坐標加1（e.curpos.y+=1;）⑤獲取北面相鄰位置入口：SElemTypegetNorth(int**m,SElemTypee)出口：returne;實現(xiàn)功能：獲取北面相鄰位置信息。需判斷當前位置是否已到迷宮上（北）邊界。x位置坐標減1（e.curpos.x-=1;）⑥獲取下一可通行位置入口：SElemTypeNextPos(SElemTypee)出口：returnnext;實現(xiàn)功能：在當前位置，向四個方向（東、南、西、北）探索，調(diào)用②、③、④、⑤函數(shù)，若相鄰位置可行走，且未曾走過，則返回該位置信息，將當前位置切換到下一位置。⑦獲取迷宮路徑函數(shù)hhhhhh入口：intMazePath(Positionstart,Positionend);出口：returnTRUE;returnFALSE;實現(xiàn)功能：若迷宮Maze中存在從入口start到出口end的通道，則求得一條存放在棧中realPath(從棧底到棧頂)，并返回TRUE；否則返回FALSE。輔助函數(shù)模塊：①輸出迷宮地圖入口：intPrintMap(int**temp);出口：returnTRUE;實現(xiàn)功能：在主函數(shù)中調(diào)用，傳遞實參指向迷宮地圖的二維指針，使用for循環(huán)嵌套輸出迷宮地圖。②錯誤消息提示入口：interrormessage() 出口：returnTRUE;實現(xiàn)功能：錯誤消息提示主函數(shù)模塊：入口：intmain()出口：return0;實現(xiàn)功能：程序執(zhí)行的入口，在主函數(shù)中調(diào)用各個模塊，實現(xiàn)程序的運行。初始化棧，Path用于存放探索迷宮時的全部路徑，realPath用于存放迷宮入口到出口的有效路徑；初始化游戲參數(shù)，對全局變量map入口、出口位置坐標、對應地圖值（為1）進行賦值；調(diào)用迷宮地圖輸出函數(shù)，輸出迷宮；調(diào)用獲取迷宮路徑函數(shù)，若存在一條路徑，則存放到棧realPath；調(diào)用遍歷棧函數(shù)，逆序輸出棧中元素（從棧底到棧頂），即從入口位置到出口位置的一條路徑。return0;主函數(shù)結束，程序運行結束。三、詳細設計1、數(shù)據(jù)結構設計（1）程序中定義了迷宮的位置坐標，結構體類型Position，包含整型數(shù)x,y存儲迷宮地圖二維數(shù)組對應的行和列坐標，整型數(shù)val用于存儲迷宮地圖的值，如0和1。hhhhhh特別說明：val值是作為迷宮探索時的重要判斷標記，若當前位置的四面為墻（0）或已走過，則在切換下一位置的函數(shù)NextPos中所返回val的值為-1。詳細定義如下：typedefstruct{ intx;//二維數(shù)組maze下標 inty; intval;//maze[x][y]的值}Position;//游戲中的位置坐標程序中定義了結構體類型MapCfg,及對應該結構體類型全局變量map，包含上一結構體類型Position變量start,end,即迷宮的起始位置與結束位置，在調(diào)用探索迷宮函數(shù)時，傳遞實參起始位置，結束位置為全局變量直接調(diào)用，從而使得在判斷結束位置時更加方便，但需注意的一點是：在調(diào)用之前要給起始、結束位置坐標變量賦初值。詳細定義如下：typedefstruct{ Positionstart;//起始位置 Positionend;//結束位置}MapCfg;MapCfgmap;程序中定義了迷宮中路徑（單獨每一通道塊）所存儲的結構體類型，包含當前位置坐標，及從該通道塊走向下一通道塊的“方向”，如：1：東，2：南，3：西，4：北。注：為存儲迷宮路徑的數(shù)據(jù)結構棧的元素類型。詳細定義如下：typedefstruct{ Positioncurpos;//通道塊在迷宮中的位置坐標 intdi;//從此通道塊走向下一通道塊的"方向"}SElemType;程序中定義了探索迷宮、和從入口start到出口end的通道,所存儲的數(shù)據(jù)結構棧，為全局變量Path,realPath,其存儲方式為順序棧，包含指向棧元素類型的棧底base和棧頂top指針，及棧的存儲空間stacksize，需注意的是：在初始化棧時要分配給存儲空間初始量，在后續(xù)使用過程中可為其分配增量，以滿足存儲要求。hhhhhh詳細定義如下：typedefstruct{ SElemType*base;//棧底指針 SElemType*top;//棧頂指針 intstacksize;//棧的大小}SqStack;SqStackrealPath;//存放路徑SqStackPath; //探索迷宮2、算法分析與實現(xiàn)主要功能模塊的算法設計分析。intMazePath(Positionstart,Positionend){ int**temp=Maze(); SElemTypee; e.curpos.x=map.start.x; //設定"當前位置"為"入口位置" e.curpos.y=map.start.y; e.curpos.val=temp[map.start.x][map.start.y]; do { if(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);hhhhhh Push(&Path,e); StackTraverse(&Path); returnTRUE; } elseif(e.curpos.val==-1) { //當前位置的四面或為墻或已走過Pop(&realPath); //刪除真實路徑的棧頂元素e=GetTop(&realPath); //令e指向棧頂元素} }else {//如果當前位置已經(jīng)走過,說明原來測試的方向不對,現(xiàn)在嘗試其它方向e=NextPos(e);if(e.curpos.val==-1) { //仍不通,刪除真實路徑的棧頂元素 Pop(&realPath); e=GetTop(&realPath); //令cur指向棧頂元素} }}while(e.curpos.x!=end.x||e.curpos.y!=end.y);returnFALSE;}四、運行結果和調(diào)試分析程序運行結果圖：1.計算機“窮舉求解法”，輸出迷宮入口到出口路徑。hhhhhh2.用二維數(shù)組表示迷宮地圖，0為墻，1為道路。在程序調(diào)試過程中遇到變量不能被賦值的問題，后來經(jīng)過按F5進行斷點調(diào)試，根據(jù)錯誤提醒，發(fā)現(xiàn)了問題所在，得到了及時的修改。在本程序中對于迷宮當前位置是否走過的判斷，需要對存儲所有路徑的realPath一一訪問，對比當前位置是否被訪問過，追其原因，是由于探索過程中并沒有做好該位置已被訪問的標記，導致每一位置都需重新定位，進行判斷，浪費了時間與存儲空間。改進：在棧元素類型，即迷宮中每一位置，增加flag標記，若已訪問則標記-1，下次獲得該位置坐標后便可得知該位置是否被訪