數(shù)據(jù)結(jié)構(gòu)課程設(shè)計—迷宮求解

1、 湖南工業(yè)大學(xué)課 程 設(shè) 計資 料 袋 計算機與通信 學(xué)院（系、部） 2009 2010 學(xué)年第 二 學(xué)期 課程名稱 數(shù)據(jù)結(jié)構(gòu) 指導(dǎo)教師 鄧彬 職稱 學(xué)生姓名 柏云 專業(yè)班級 軟件工程 學(xué)號 09408300134 題 目 編制一個求解迷宮通路的程序 成 績 起止日期 2010年 6 月 28日 2010年 7 月 4 日目 錄 清 單序號材 料 名 稱資料數(shù)量備 注1課程設(shè)計任務(wù)書12課程設(shè)計說明書13課程設(shè)計圖紙1張456 湖南工業(yè)大學(xué)課程設(shè)計任務(wù)書2009 2010 學(xué)年第 二 學(xué)期 計算機與通信 學(xué)院（系、部） 軟件工程 專業(yè) 091 班級課程名稱： 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目： 編制一個求解

2、迷宮通路的程序 完成期限：自 2010 年 6 月 28日至 2010 年 7 月 4 日共 1 周內(nèi)容及任務(wù)一、設(shè)計的主要技術(shù)參數(shù)使用棧機制模擬迷宮的尋路過程, 圖的DFS 自動生成隨機迷宮地圖.二、設(shè)計任務(wù)使用C語言實現(xiàn)各個模塊的功能.三、設(shè)計工作量 汪婷負(fù)責(zé)實現(xiàn)迷宮的尋路算法以及棧機制等的實現(xiàn), 柏云負(fù)責(zé)迷宮地圖自生成算法,以及游戲功能,友好界面等的實現(xiàn).進度安排起止日期工作內(nèi)容2010-6-28-2010-6-29設(shè)計本程序思路2010-6-29-2010-7-1實現(xiàn)子程序模塊函數(shù)2010-7-1 -2010-7-2將子程序和主程序構(gòu)建成完整的C源程序，并且進行相關(guān)編譯調(diào)試2010-7

3、-2 -2010-7-4數(shù)據(jù)測試、形成文檔主要參考資料<<面向?qū)ο驝語言程序設(shè)計>><<數(shù)據(jù)結(jié)構(gòu)（C語言版）>><<圖算法>><<Windows系統(tǒng)編程-第三版>>指導(dǎo)教師（簽字）： 年 月 日系（教研室）主任（簽字）： 年 月 日2數(shù)據(jù)結(jié)構(gòu)設(shè)計說明書數(shù)據(jù)結(jié)構(gòu)課程設(shè)計編制一個求解迷宮通路的程序起止日期： 2010 年 6 月 28日 至 2010年 7 月 4 日學(xué)生姓名柏云班級軟件091班學(xué)號09408300134成績指導(dǎo)教師(簽字)計算機與通信學(xué)院（部）年 月 日湖南工業(yè)大學(xué)課程設(shè)計情況分析表課

4、程設(shè)計名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計周數(shù)17周學(xué)院（部）計算機與通信學(xué)院系（教研室）軟件工程系指導(dǎo)教師鄧彬?qū)W生專業(yè)、班級軟件工程0901選題設(shè)計一個迷宮生成算法成績分布優(yōu)良中及格不及格學(xué)生數(shù)百分比學(xué)生課程設(shè)計存在的主要問題改進措施及建議指導(dǎo)教師（簽字）： 年 月 日系（教研室）主任（簽字）： 年 月 日備注：本表在課程設(shè)計完成后由指導(dǎo)教師填寫，與課程設(shè)計資料一起存檔。 目錄1. 題目及需求分析 VI2. 概要設(shè)計 VII3. 詳細(xì)設(shè)計 X4. 調(diào)試分析 XIX5. 用戶手冊 XXI6. 測試結(jié)果 XXIII7. 附錄 程序清單 XXV題目:編制一個求解迷宮通路的程序.擴展:增加迷宮地圖的隨機生成;增加人工操

5、作游戲功能;可顯示迷宮通路.一 . 需求分析( 1 ) 以二維數(shù)組的形式存儲迷宮地圖, 0 代表通路 , 1 代表墻壁 , 2 代表已走過的足跡 , 3 代表 死路 ,以上 用宏定義如下:( 2 ) 設(shè)計交互界面 , 用戶只需輸入選擇就可做想做的事情.( 3 ) 用戶可以自己輸入迷宮的大小 , 然后由程序自動生成隨機迷宮.( 4 ) 求出迷宮通路并且打印在屏幕上.( 5 ) 用戶可以通過方向鍵控制小人自己走出迷宮.( 6 ) 使用文件存儲迷宮的 矩陣表示 以及 圖形表示.二 . 概要設(shè)計1. 設(shè)定棧的抽象數(shù)據(jù)類型定義 :ADT Stack 數(shù)據(jù)對象 : D=ai|aiADT MazeType

6、, i = 0,1,2n , n0數(shù)據(jù)關(guān)系 : R1= <ai-1,ai> | ai-1,ai D,i=2,n 基本操作 :InitStack(SqStack &s)操作結(jié)果 : 構(gòu)造一個空棧GetTop(SqStack s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 獲取棧頂元素Push(SqStack &s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 在棧頂插入新元素Pop(SqStack &s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 刪除棧頂元素,并刪除

7、e值StackEmpty(SqStack s)初始條件 : 棧 s 以存在操作結(jié)果 : 判斷棧是否為空ClearStack(SqStack &s)初始條件 : 棧 s 以存在操作結(jié)果 : 將棧置為空棧 ADT SqStack;2. 設(shè)定迷宮的抽象數(shù)據(jù)類型ADT MazeType數(shù)據(jù)對象 : D=ai,j|ai,j ,#、*，0<=i<=m+1, 0<=j<=n+1,m,n<=10數(shù)據(jù)關(guān)系 : R=ROW,COLROW=<a i-1,j,ai,j>|ai-1,j,ai,jD,i=1,m+1,j=0,n+1COW=<a i-1,j,ai,j&

8、gt;|ai-1,j,ai,jD,i=1,m+1,j=0,n+1基本操作 :Status InitMaze(MazeType &maze,int a,int row,int col)初始條件: 數(shù)組a 中存放了迷宮的矩陣表示,row 和 col 為迷宮的大小操作結(jié)果: 將數(shù)組 a 復(fù)制到迷宮類型的 數(shù)組 arr 中,并保存迷宮的行和列Status Pass(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 如果可通,返回真,否則為假Status FootPrint(MazeType &am

9、p;maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 將當(dāng)前坐標(biāo)curpos處的arr值記為 足跡Status MarkPrint(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 將當(dāng)前坐標(biāo)curpos處的arr值記為 死路SElemType CreateSElem(int step,PosType pos,DirectiveType di)初始條件: 各參數(shù)值都已經(jīng)定義操作結(jié)果: 為要走的當(dāng)前位置生成一個棧元素類型PosTy

10、pe &NextPos(PosType curpos,DirectiveType di)初始條件: 各參數(shù)值已經(jīng)定義操作結(jié)果: 求得以當(dāng)前位置為棧頂?shù)南乱粋€方向的元素的坐標(biāo)Status PosEquare(PosType pos1,PosType pos2)初始條件: 個參數(shù)值已經(jīng)定義操作結(jié)果: 判斷是否為同一位置,是則返回真, 否則為假.void PrintMaze(MazeType maze)初始條件: maze 存在迷宮地圖操作結(jié)果: 在屏幕上打印出迷宮的可用路徑Status MazePath(MazeType &maze,PosType start,PosType en

11、d) 初始條件: maze 存在迷宮地圖操作結(jié)果: 為建立的迷宮找到一條路徑ADT MazeType;3. 本程序包含6個模塊1) 主程序模塊:int main()主菜單函數(shù), 實現(xiàn)時間循環(huán).return 0;/主函數(shù)2) 棧模塊-實現(xiàn)棧抽象數(shù)據(jù)類型3) 迷宮模塊-實現(xiàn)迷宮抽象數(shù)據(jù)類型4) 迷宮隨機地圖生成模塊-用戶自定義迷宮地圖的生成5) 菜單模塊-實現(xiàn)與用戶交互菜單6) 游戲模塊-實現(xiàn)游戲功能各模塊之間的調(diào)用如下:主程序模塊 菜單模塊游戲模塊迷宮模塊迷宮生成模塊 棧模塊4. 求解迷宮通路的偽碼算法:設(shè)定當(dāng)前位置的初值為入口位置;Do若當(dāng)前位置可通,則將當(dāng)前位置插入棧頂;/納入路徑若該位置為

12、出口位置,則結(jié)束;/求的路徑存放在棧中否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置;否則若棧不空且棧頂位置還有其他位置沒有被探索,則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊.若棧不空但棧頂位置的四周均不可通,則刪去棧頂位置;/后退一步,從路徑中刪去該通道快若棧不空,則重新測試新的棧頂位置,直到找到一個可通的相鄰塊或出棧至空棧;while ( 棧不空 ); ?？照f明沒有路徑存在 三. 詳細(xì)設(shè)計工程文件視圖: 類視圖:-頭文件設(shè)計-1. my_Stack.h 文件 #ifndef MY_STACK_H#define MY_STACK_H#define TURE 1#define F

13、ALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int DirectiveType; typedef struct int row;int col;PosType;typedef struct /棧中的數(shù)據(jù)元素類型int step;PosType seat;DirectiveType di;SElemType;typedef struct /

14、棧結(jié)構(gòu)SElemType *base;SElemType *top;int stacksize;SqStack; /-棧的基本操作-/初始化Status InitStack(SqStack &s);/得到棧頂元素Status GetTop(SqStack s,SElemType &e);/入棧Status Push(SqStack &s,SElemType &e);/出棧Status Pop(SqStack &s,SElemType &e);/判斷棧是否為空int StackEmpty(SqStack s);/清空棧Status ClearSta

15、ck(SqStack &s);#endif2. my_Maze_Create.h 文件#ifndef MY_MAZE_CREATE_H#define MY_MAZE_CREATE_H#define MAZE_MAX 155/路徑查找int search(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y);/迷宮生成void Make_Maze(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y);/生成迷宮文件void Maze_File_Make (int mazeMapMAZE_MAX * 2MAZE_MAX * 2,int

16、 x,int y );#endif3. my_Maze.h 文件#ifndef MY_MAZE_H#define MY_MAZE_H#include "my_Stack.h"#include "my_Maze_Create.h"#define RANGE 300 /迷宮最大限制#define ROAR 0/迷宮中點可通點#define WALL 1/墻#define ETR 2/已走過的足跡#define JAM 3/死路typedef struct int x,y; /迷宮的實際行、列int arrRANGERANGE; /迷宮最多的行列，限定作用Ma

17、zeType;/-迷宮的基本操作-/初始化迷宮Status InitMaze(MazeType &maze,int aMAZE_MAX * 2MAZE_MAX * 2,int row,int col);/判斷當(dāng)前位置是否可通Status Pass(MazeType &maze,PosType curpos);/可通標(biāo)記 Status FootPrint(MazeType &maze,PosType curpos);/不可通標(biāo)記 Status MarkPrint(MazeType &maze,PosType curpos);/為要走的當(dāng)前位置生成一個棧元素類型SE

18、lemType CreateSElem(int step,PosType pos,DirectiveType di);/求得以當(dāng)前位置為棧頂?shù)南乱粋€方向的元素的坐標(biāo)PosType &NextPos(PosType curpos,DirectiveType di);/判斷是否為同一位置Status PosEquare(PosType pos1,PosType pos2);/打印迷宮void PrintMaze(MazeType maze);/為建立的迷宮找到一條路徑Status MazePath(MazeType &maze,PosType start,PosType end)

19、;#endif4. MazePlay.h 文件#ifndef MAZEPLAY_H#define MAZEPLAY_H/獲取 方向鍵 響應(yīng)事件int getPos();/移動 小人 的位置Status MovePos ( MazeType &maze, int pos );/判斷按鍵方向是否可以移動bool isMoveable ( MazeType &maze ,PosType pos);/顯示 當(dāng)前位置的狀態(tài)1void disPlay ( MazeType &maze, PosType pos );/顯示 當(dāng)前位置的狀態(tài)2void disPlay_2 ( MazeT

20、ype &maze, PosType pos );/游戲主事件int playMain ( MazeType &maze );#endif5. Main_Menu.h 文件#ifndef MAIN_MENU_H#define MAIN_MENU_Htypedef struct PosType start;PosType end;EtrANdOutPos;/菜單顯示1void displayMenu_1 ();/菜單顯示2void displayMenu_2 ();/菜單調(diào)節(jié)void displayMenu_3 ();/自定義迷宮EtrANdOutPos creatPsnMaze

21、 (int mazeMapMAZE_MAX * 2MAZE_MAX * 2 , MazeType &maze );/主選擇菜單int MainChoiceMenu();/光標(biāo)移動void gotoxy(int x, int y);#endif6. myHeader.h 主包含頭文件#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>#include <time.h>#include <memory.h>#include

22、<windows.h>#include "my_Stack.h"#include "my_Maze.h"#include "my_Maze_Create.h"#include "Main_Menu.h"#include "MazePlay.h"#include <iostream>#include <fstream>using namespace std;-實現(xiàn)文件(部分)-1. my_Maze_Create.cpp 文件#include "myHe

23、ader.h"int mapMAZE_MAX+2MAZE_MAX+2;int search(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y)static int d42=0,1,1,0,0,-1,-1,0; int zx=x*2,zy=y*2,next,turn,i; mapzxzy=1;turn = rand()%2 ? 1 : 3; for(i=0,next=rand()%4; i<4; i+,next=(next+turn)%4) if(mapzx+2*dnext0zy+2*dnext1=0) mapzx+dnext0zy+dnext1=1

24、;search(map,x+dnext0,y+dnext1);return 0;void Make_Maze(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y) int z1,z2; for(z1=0,z2=2*y+2;z1<=2*x+2;z1+)mapz10=1,mapz1z2=1; for(z1=0,z2=2*x+2;z1<=2*y+2;z1+)map0z1=1,mapz2z1=1; map12=1;map2*x+12*y=1;srand(unsigned)time(NULL); search(map,rand()%x+1,rand()%y+1);

25、map10 = '1'mapx-2y-1 = '1'/生成迷宮文件 C 實現(xiàn)void Maze_File_Make (int mazeMapMAZE_MAX * 2MAZE_MAX * 2,int x,int y )生成隨機迷宮地圖文件并讀取;2. my_Maze.cpp文件/打印迷宮void PrintMaze(MazeType maze)打印迷宮路徑地圖;/為建立的迷宮找到一條路徑Status MazePath(MazeType &maze,PosType start,PosType end)SqStack s;SElemType e;InitSta

26、ck(s);PosType curpos=start;curstep = 1;doif(Pass(maze,curpos)FootPrint(maze,curpos);e=CreateSElem(curstep,curpos,1);Push(s,e);if(PosEquare(curpos,end)return TURE;curpos=NextPos(curpos,1);curstep+;elseif(!StackEmpty(s)Pop(s,e);while(e.di = 4 && !StackEmpty(s)MarkPrint(maze,e.seat);Pop(s,e);cu

27、rstep-;if( e.di < 4 )e.di +;Push(s,e);curpos=NextPos(e.seat,e.di);while(!StackEmpty(s);return FALSE;3. MazePlay.cpp文件#include "myHeader.h"PosType start;PosType end;PosType curPos;PosType prePos;int getPos()pos = 鍵位標(biāo)識符;return pos;Status MovePos ( MazeType &maze, int pos )switch(pos)c

28、ase : 向pos方向移動;return 0;bool isMoveable ( MazeType &maze ,PosType pos)if ( maze.arrpos.rowpos.col = 1 )return false;return true;void disPlay ( MazeType &maze, PosType pos )顯示迷宮; void disPlay_2 ( MazeType &maze, PosType pos )顯示小人的當(dāng)前位置;4. main.cpp 主函數(shù)#include "myHeader.h"int main

29、()/主菜單MainChoiceMenu();return 0;/主函數(shù)函數(shù)調(diào)用關(guān)系圖如下:四: 調(diào)試分析1. 本次作業(yè)比較簡單 , 只是后期在原來的程序上做了許多擴展, 如實現(xiàn)隨機迷宮地圖的自動生成 和 游戲模式. 初期的調(diào)試總是輸出 “沒有找到路徑”, 但是迷宮的路徑確實是存在的,后來發(fā)現(xiàn)是由于迷宮的自生成算法與輸入有些不一致, 更正了行列順序后,程序能正常運行.2. 在設(shè)計迷宮初始化函數(shù)的時候,參數(shù)的傳遞出現(xiàn)錯誤,主要是對指針和引用的理解出現(xiàn)混淆,通過查閱相關(guān)資料, 弄清楚了兩者之間的區(qū)別,指針是用于指向一個變量的地址,而引用只是對一個已存在變量的一個重命名.3. 在調(diào)試過程中使用printf函數(shù)輸出標(biāo)志信息跟蹤函數(shù)調(diào)用,收到了顯著的效果,大大提高了調(diào)試效率,有利于以后的代碼調(diào)試.4. 使用了小部分的win32 API,發(fā)現(xiàn)使用局部句柄時,調(diào)用的winAPI不能正常運行,改成全局后問題解決.5. 程序源代碼中仍有部分重復(fù)代碼,可以模塊化,實現(xiàn)代碼重用.6. 在實現(xiàn)游戲功能時發(fā)現(xiàn),每次調(diào)用disPlay 函數(shù)時都進行清屏操作,屏幕的閃動幅度非常大,眼睛很容易疲勞, 第一次改進后, 去除了清屏操作,而采用覆蓋式的輸出 ,即在原來已有的畫面上再次打印.經(jīng)過這次改進, 界面趨向與穩(wěn)定,但是,在進行高頻率按鍵時,仍然可以發(fā)現(xiàn)有較小的閃動現(xiàn)象.經(jīng)過思考,發(fā)現(xiàn)迷宮地圖是不變的,只