數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--迷宮問題

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：20 大小：587.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--迷宮問題_第1頁

已閱讀1頁，還剩19頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》　　---課程設(shè)計報告　　設(shè)計題目　　迷宮問題　　需求分析</

2、b>　　1.選題理由　　迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個經(jīng)典問題，迷宮問題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng)用“?！钡乃枷搿τ跅５膬?nèi)容在整個學(xué)期的學(xué)習(xí)中我也有了一

3、定的了解，所以選擇了迷宮這一經(jīng)典問題作為本次課設(shè)的內(nèi)容。 　　2.基本原理分析 　　迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路。棧

4、是一個后進先出的結(jié)構(gòu)，可以用來保存從入口到當(dāng)前位置的路徑。　　以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何一個位置，均約定東、南、西、北四個方向可通。　　3.功能要求 　?。?）以一個

5、二維數(shù)組Maze[m+2][n+2]表示迷宮，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1] (0<=i<=m+1)為做外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為：m,n<=10。　　（2）用戶需用文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第

6、2行至第m+1行（每行n個數(shù)）為迷宮值，用0，1輸入，同行中的兩個數(shù)字之間用空白字符相隔。　　（3）迷宮的入口位置和出口位置可由用戶隨時設(shè)定。　　（4）若設(shè)定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標(biāo)準輸出文件上，其中字符“#”表示障礙，“*”表示路徑，“@”表示曾途經(jīng)該位置但不能到達出口，其余位置用空格符表示。若設(shè)定迷宮不存在通路則報告相應(yīng)信

7、息　　（5）本程序只求出一條成功的通路。　　（6）程序執(zhí)行的命令為：1，創(chuàng)建迷宮；2，求解迷宮；3，輸出迷宮的解。　　三、概要設(shè)計　　本程序包含三個模塊

8、?。?）棧模塊——實現(xiàn)棧抽象數(shù)據(jù)類型　　（2）迷宮模塊——實現(xiàn)迷宮抽象數(shù)據(jù)類型　?。?）主程序模塊：　　void mian()　　{

9、初始化；　　Do{　　接受命令；　　處理命令；　　}while(命令!=“退出”)；<b&

10、gt;　　}　　各模塊之間的調(diào)用關(guān)系如圖一：　　圖一：調(diào)用關(guān)系圖　　函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu)如圖二：　　圖二：函數(shù)的調(diào)用關(guān)系圖　　四、詳細設(shè)

11、計　?。?）棧的抽象數(shù)據(jù)類型　　ADT Stack{　　數(shù)據(jù)對象：D={ai| ai∈CharSet,i=1,2…n,n>=0}　　數(shù)據(jù)關(guān)系：R1={<ai-1, ai >| ai-1, ai∈D,i=2,…n}

12、　　基本操作：　　InitStack(&S)　　操作結(jié)果：構(gòu)造一個空棧S。　　DestroyStack(&S)　　初始條件：棧S已存在。　　操作結(jié)果：銷毀棧

13、S。　　ClearStack(&S)　　初始條件：棧S已存在。　　操作結(jié)果：將S清為空棧。　　StackLength(S)　　初始條件：棧S已存在。　　操作結(jié)果：返回棧S的長度。&

14、lt;/p>　　StackEmpty(S)　　初始條件：棧S已存在。　　操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。　　GetTop(S，&e)　　初始條件：棧S已存在。　　操作結(jié)

15、果：若棧S不空，則以e返回棧頂元素。　　Push(&S， e)　　初始條件：棧S已存在。　　操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。　　Pop(&S，&e)　　初始條件：棧S已存在。

16、　　操作結(jié)果：刪除S的棧頂元素，并以e返回其值。　　StackTraverse（S，visit（））　　初始條件：棧S已存在。　　操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit（）。　　} ADT Stack<

17、;p>　?。?）迷宮的抽象數(shù)據(jù)類型　　ADT maze{　　數(shù)據(jù)對象：D={ai,j| ai,j∈{ ' ','#','@','*'},0<=i<=m+1,0<=j<=n+1,m,n<=10}&

18、lt;p>　　數(shù)據(jù)關(guān)系：R={ROW,COL}　　基本操作：　　InitMaze(&M,a,row,col)　　初始條件：二維數(shù)組a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，

19、以值1表示障礙。　　操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，以字符‘#’表示障礙，并在迷宮四周加上一圈障礙。　　MazePath(&M)　　初始條件：迷宮M已被賦值。　　操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài)：以字符’*’表示路

20、徑上的位置，字符‘@’表示“死胡同”，否則迷宮的狀態(tài)不變。　　PrintMaze（M）　　初始條件：迷宮M已存在。　　操作結(jié)果：以字符形式輸出迷宮。　　} ADT maze　　五、測試數(shù)據(jù)及運行結(jié)果<

21、p>　　1、調(diào)試分析：　?。?）本程序有一個核心算法，即求迷宮的路徑，在調(diào)試的時候，出現(xiàn)了兩個問題：沒有想到要用‘@’記號，導(dǎo)致迷宮走不出來；沒有設(shè)置‘found’，不知何時跳出。　?。?）原本棧的元素e中除了di—往下一坐標(biāo)位置的方向和seat—當(dāng)前的坐標(biāo)位置，還有一個step—當(dāng)前位置在路徑上的序號，后來發(fā)

22、現(xiàn)step沒什么用，就刪掉了。　?。?）函數(shù)ReadCommand中，cmd=getchar();的位置找不準，最后是試出來的。　?。?）調(diào)試的時候多次出現(xiàn)，沒有錯誤，但是dos環(huán)境下就是執(zhí)行不起來，所以采用了一些輸出變量，判斷到底是哪里出了問題。 　?。?）本程序中三個主要的算法：InitMaze，

23、MazePath和MarkPrint的時間復(fù)雜度均為O（m*n）, 本程序的空間復(fù)雜度也為O（m*n）（棧所占最大空間）　　使用說明和運行結(jié)果：　?。?）首先以文件形式輸入迷宮數(shù)據(jù)，如圖三：　　圖三　?。?）進入演示程序后，會出現(xiàn)以下

24、界面如圖四： 　　圖四0 　　進入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數(shù)據(jù)的文件名，結(jié)束符為“回車符”，該命令執(zhí)行之后輸出“迷宮建立完成”，且輸出下面可執(zhí)行的操作。如圖五：　　圖五　　進入“執(zhí)行迷

25、宮”的命令后，即提示輸入迷宮入口，出口的坐標(biāo)，結(jié)束符為“回車符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路徑。請注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經(jīng)改變，若要重復(fù)執(zhí)行此命令，需重新輸入迷宮數(shù)據(jù)。如圖六：　　圖六　　進入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)?！?’表示障礙，‘@’ 表示

26、曾走過但不通，‘*’表示路徑。如圖七：　　圖七　　進入“退出”的命令后，按任意鍵結(jié)束。如圖八：　　圖八　　缺點與改進：

27、;　　在定義函數(shù)Mazepath的時候，開始的循環(huán)語句的結(jié)束條件不對，沒有出路時，導(dǎo)致一直出現(xiàn)了不正確的結(jié)果，最后沒有新位置入棧，則返回上一個位置，否則沒有路徑。　　只是以文件形式輸入迷宮，如果迷宮數(shù)據(jù)量大時，要先建好文件還是很浪費時間，如果以隨機產(chǎn)生函數(shù)自動產(chǎn)生迷宮會更好。　　六、源程序:

28、　　#include <stdio.h>　　#include <stdlib.h>　　#include <string.h>　　#define MAXLEN 10//迷宮包括外墻最大行列數(shù)目　　#define TRU

29、E 1　　#define FALSE 0　　#define OK 1　　#define ERROR 0　　typedef int Status;　　// 坐標(biāo)位置類型 　　typ

30、edef struct{　　int r,c;　　} PosType;//迷宮中r行c列的位置　　//迷宮類型 　　typedef struct {

31、;　　int r;　　int c;　　char arr[MAXLEN][MAXLEN];//可取' ','*','@','#'　　}MazeType;

32、 　　typedef struct{　　//int step; // 當(dāng)前位置在路徑上的“序號”　　PosType seat; //當(dāng)前的坐標(biāo)位置　　int di; //往下一坐標(biāo)位置的方向　　}SElemType;</p&

33、gt;　　//結(jié)點類型　　typedef struct NodeType{　　SElemType data;　　NodeType *next;　　}NodeType,*LinkType;&

34、lt;p>　　//棧類型 　　typedef struct { 　　LinkType top;　　int stacksize;　　}SqStack; 　　PosType sta

35、rt;　　PosType end;　　MazeType maze;　　bool found;　　//創(chuàng)建棧　　Status InitStack(SqStack &S)

36、;　　{　　S.top=(LinkType)malloc(sizeof(NodeType));　　S.top->next=NULL;　　S.stacksize=0;　　return OK;

37、;　　}　　//進棧　　Status Push(SqStack &S,SElemType &e)　　{　　LinkTyp

38、e p;　　p=(NodeType*)malloc(sizeof(NodeType));　　p->data=e;　　p->next=S.top;　　S.top=p;　　S.stac

39、ksize++;　　return OK;　　}　　//判斷是否為?？?lt;/b>　　Status StackEmpty(SqStack S)　　{&

40、lt;/b>　　if(S.top->next==NULL) return OK;　　return ERROR; 　　}　　//出棧　　Stat

41、us Pop(SqStack &S,SElemType &e)　　{　　LinkType p;　　if(StackEmpty(S)) return ERROR;　　p=S.top;

42、　　e=p->data;　　S.top=S.top->next;　　S.stacksize--;　　free(p);　　return OK;

43、;　　}　　//銷毀棧　　Status DestroyStack(SqStack &S)　　{　　LinkType p;<

44、;p>　　while(S.top!=NULL)　　{　　p=S.top;　　S.top=S.top->next;　　free(p);</p&

45、gt;　　}//一個一個刪除　　if(S.top==NULL) return OK;　　else return ERROR;　　}　　//曾走過但不是通路標(biāo)記并返回OK<

46、;/p>　　Status MarkPrint(MazeType &maze,PosType curpos)　　{　　maze.arr[curpos.r][curpos.c]='@';//"@"表示曾走過但不通<p&g

47、t;　　return OK;　　}　　//曾走過而且是通路標(biāo)記并返回OK　　Status FootPrint(MazeType &maze,PosType curpos)　　{</p

48、>　　maze.arr[curpos.r][curpos.c]='*';//"*"表示可通　　return OK;　　}　　//選擇下一步的方向　　PosType Nex

49、tPos(PosType &curpos,int i)　　{　　PosType cpos;　　cpos=curpos;　　switch(i){

50、 //1.2.3.4分別表示東,南,西,北方向　　case 1 : cpos.c+=1; 　　break;　　case 2 : cpos.r+=1; 　　break;<

51、;p>　　case 3 : cpos.c-=1; 　　break;　　case 4 : cpos.r-=1; 　　break;　　}

52、　　return cpos;　　}　　//判斷當(dāng)前位置是否可通 　　Status Pass(MazeType &maze, PosType curpos)　　{<

53、;/p>　　if(maze.arr[curpos.r][curpos.c]==' ') return TRUE;　　else return FALSE;　　}　　//創(chuàng)建迷宮

54、　　//按照用戶輸入的二維數(shù)組（0或1），設(shè)置迷宮maze的初值，包括加上邊緣一圈的值　　void InitMaze(MazeType &maze, char a[MAXLEN][MAXLEN], int row, int col)　　{　　ma

55、ze.r=row;　　maze.c=col;　　for(int i=0;i<=col+1;i++){　　a[0][i]='1';　　a[row+1][i]='1';　　}&l

56、t;/b>　　for(i=0;i<=row+1;i++){　　a[i][0]='1';　　a[i][col+1]='1';　　}　　for(i=0;

57、i<=maze.r+2;i++){　　for(int j=0;j<maze.c+2;j++){　　if(a[i][j]=='1') maze.arr[i][j]='#';　　else maze.arr[i][j]=' ';<

58、p>　　}　　}　　}　　//求迷宮路徑的偽碼算法：　　Status MazePath(MazeType &maze,PosType start

59、,PosType end)　　{　　//求解迷宮maze中，從入口start到出口end的一條路徑，若存在，返回TRUE,否則返回FALSE　　PosType curpos;　　SqStack S;<p&

60、gt;　　SElemType e;　　InitStack(S);　　curpos=start;//設(shè)定“當(dāng)前位置”為“入口位置”　　//curstep=1; //探索第一步　　found=false;　　do{&

61、lt;/b>　　if(Pass(maze,curpos))　　{　　//當(dāng)前位置可以通過，即是未曾走到過的通道塊留下足跡　　FootPrint(maze,curpos);//做可以通過的標(biāo)識<p&g

62、t;　　//e.step=curstep;　　e.seat=curpos; 　　e.di=1; //為棧頂元素賦值　　Push(S,e); //加入路徑<

63、p>　　if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到達終點返回true　　else{　　curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置的東鄰

64、}　　}　　else //當(dāng)前位置不能通過　　if(!StackEmpty(S)){　　Pop(S,e);

65、while(e.di==4 && !StackEmpty(S)){　　MarkPrint(maze,e.seat); //留下不能通過的標(biāo)記　　Pop(S,e);　　}

66、　　if(e.di<4){　　e.di++; //換下個方向　　Push(S,e); &

67、#160; //　　curpos=NextPos(e.seat,e.di); //進行探索　　}　　}　　}while(!StackEm

68、pty(S)&&!found);　　DestroyStack(S);　　return found;　　}　　//將標(biāo)記路徑信息的迷宮（字符型方陣）輸出到終端(包括外墻)　　vo

69、id PrintMaze(MazeType &maze)　　{　　for(int i=0;i<=maze.r+2;i++){　　for(int j=0;j<=maze.c+2;j++){　　printf("

70、; %c",maze.arr[i][j]);//輸出迷宮 　　}　　printf("\n");　　}

71、　　}　　//系統(tǒng)初始化　　void Initialization()　　{　　system("cls&q

72、uot;); 　　printf(" welcome to the game!!! "); 　　printf("\n********************

73、****************************");　　printf("\n*創(chuàng)建迷宮--c 執(zhí)行迷宮--m 輸出迷宮--p 退出--q*");　　printf("\n************************************************");&l

74、t;/p>　　printf("\n\n 操作:-");　　}　　//讀入操作命令符，顯示提示信息　　void ReadCommand(char &cmd)<

75、;p>　　{　　do{　　if(cmd=='c')　　{　　printf("\n***********************

76、*******************");　　printf("\n*選擇操作 :執(zhí)行迷宮--m *");　　printf("\n* 退出--:q

77、*");　　printf("\n******************************************");　　printf("\n\n 操作:-");　　}

78、　　else if(cmd=='m'){　　printf("\n******************************************");　　printf("\n*選擇操作 :輸出迷宮--p

79、0; *");　　printf("\n* 退出--:q *");　　printf("\n******************************************");</p

80、>　　printf("\n\n 操作:-");　　}　　else if(cmd=='p'){　　printf("\n******************************************&

81、quot;);　　printf("\n*選擇操作 :執(zhí)行迷宮--c *");　　printf("\n* 退出-

82、-:q *");　　printf("\n******************************************");　　printf("\n\n &

83、#160; 操作:-");　　}　　cmd=getchar();　　}while(!(cmd=='c'||cmd=='m'||cmd=='p'||cmd=='q'));

84、　　}　　//解釋cmd--具體執(zhí)行　　void Interpre(char cmd)　　{　　switch(cmd){　　case

85、'c':{　　int rnum, cnum, i=0,m=1,n=1;　　char a2[MAXLEN][MAXLEN];　　char input[1];　　char data[1000];　　printf(&qu

86、ot;\n請輸入迷宮數(shù)據(jù)文件名！\n");　　scanf("%s",input);　　FILE *fp;　　fp=fopen(input,"r");　　if(!fp)

87、　　{ 　　printf("\n不能打開文件\n"); 　　break; 　　}<p&g

88、t;　　while(!feof(fp))　　{　　fscanf(fp,"%s",&data[i]);　　if(i==0)　　{&l

89、t;/p>　　rnum=(int)data[i]-(int)'0';　　}　　if(i==1)　　{　　cnum=

90、(int)data[i]-(int)'0';　　}　　if(i>=2)　　{　　if(n>cnum){m++;n=1;}</

91、p>　　a2[m][n]=data[i];　　n++;　　}　　i++;　　}</p&

92、gt;　　fclose(fp);　　InitMaze(maze, a2, rnum, cnum);　　printf("\n迷宮建立完成?。n");　　break;　　}&l

93、t;/b>　　case 'm':{　　printf("\n請輸入迷宮入口的坐標(biāo)，以空格為間隔:--");　　scanf("%d %d",&start.r,&start.c);　　printf(&

94、quot;\n請輸入迷宮出口的坐標(biāo)，以空格為間隔:--");　　scanf("%d %d",&end.r,&end.c);　　MazePath(maze, start, end);　　break;<p

95、>　　}　　case 'p':{　　if(found)　　{　　printf("\n求解迷宮的結(jié)果如下--\n");

96、　　PrintMaze(maze);　　}　　else printf("\n找不到路徑！\n");　　}　　} &l

97、t;/b>　　}　　void main()　　{　　char cmd;　　Initialization();&

98、lt;/p>　　do{　　ReadCommand(cmd); //讀入一個操作符命令　　Interpre(cmd); //解釋執(zhí)行命令操作符

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--迷宮問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--迷宮問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載