數(shù)據(jù)結(jié)構課程設計報告--迷宮

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構課程設計報告　　題目：迷宮問題　　姓名：　　學號：　　班級：<

2、;p>　　指導教師：　　2012年6月6日　　問題描述　　輸入任意大小的迷宮數(shù)據(jù)，用遞歸和非遞歸方法求出一條走出迷宮的路徑，并將路徑輸出。<b&g

3、t;　　設計思路　　以 0和1分別表示迷宮中的通路和障礙，沒有通路則不顯示。未顯示為得出沒有通路的結(jié)論；　　走迷宮的方式是一個一個的線路去試如果是死路的話就退回去，類似數(shù)據(jù)結(jié)構中棧的先進后出，所以可以用棧這種結(jié)構表示迷宮，通過不斷的試驗當試出最后的路線時輸出棧即可，由于它是不斷循環(huán)的實驗，所以可以采用鏈棧實現(xiàn)迷宮的求解。同時因為迷宮

4、需要不斷重復的試驗，可以看成反復的調(diào)用“迷宮“這個函數(shù)，這是典型的遞歸問題，所以也可以使用遞歸解決問題。另外由于數(shù)據(jù)對象是迷宮所以可以用0和1構建不同類型的迷宮更符合實際也更有樂趣。　　數(shù)據(jù)結(jié)構設計　　前面提到要用到鏈棧和遞歸兩種方式操作；為了更好的以鏈表作存儲結(jié)構的棧，可以用二維數(shù)組存儲迷宮信息，同時通路以三元組（

5、i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一個坐標的方向。這樣是路徑更加明顯，具體的數(shù)據(jù)結(jié)構為：　　#define maxsize 100　　#define NULL 0　　typedef struct//定義迷宮<b&g

6、t;　　{　　int Maze[maxsize][maxsize];//二維數(shù)組存放迷宮信息　　int maze_x,maze_y;//迷宮的行數(shù)和列數(shù)　　}maze;　　typedef struct

7、point//鏈棧的每個結(jié)點定義　　{　　int vex_x,vex_y;//結(jié)點的橫縱坐標　　int direction;//下一個結(jié)點的方向　　struct point *next;//指向下一個

8、結(jié)點　　}Point;　　遞歸法像一位手握大權的領導。當他站在迷宮入口處時，他才懶得親自去走，這時這位領導會吩咐他的手下，讓他們分別向著迷宮的各個方向去探索；當遇到岔路口時留一個人守在這里，再分出幾股人，朝著每個方向繼續(xù)探索；最后總會有一個人發(fā)現(xiàn)出口。發(fā)現(xiàn)出口的這個人將出口的位置報告給離他最近的路口處留守的人，再由這

9、個人報告給上一個路口的人，依次層層上報，最后消息傳到了領導那里，于是這位領導就順著這條畫好的通路大搖大擺地通過了迷宮。所以具體的數(shù)據(jù)結(jié)構為：　　#include<stdio.h>　　#include<malloc.h>　　#define maxsize 100<

10、;p>　　#define NULL 0　　typedef struct//定義迷宮　　{　　int Maze[maxsize][maxsize];//二維數(shù)組存放迷宮信息　　int maze_x,maze_y;

11、//迷宮的行數(shù)和列數(shù)　　}maze;　　maze a;　　typedef struct point//鏈棧的每個結(jié)點定義　　{

12、;　　int vex_x,vex_y;//結(jié)點的橫縱坐標　　int direction;//下一個結(jié)點的方向　　struct point *next;//指向下一個結(jié)點　　}Point;

13、　　4.功能函數(shù)設計　　<1>一個用于存放迷宮信息的二維數(shù)組maze[][]　　相關操作：　　a.二維數(shù)組的初始化maze creat()　　b.數(shù)組以指針形式在各個函數(shù)中傳遞。<

14、;/p>　　c.可以改變數(shù)組中的行數(shù)和列數(shù)。　　<2>結(jié)構體point *next：指向下一個結(jié)點　　<3>結(jié)構體printmazepath：輸出迷宮路徑。　　<4>結(jié)構體secret：搜索迷宮路徑。<

15、b>　　5.編碼實現(xiàn)　　非遞歸：　　#include<stdio.h>　　#include<malloc.h>　　#define maxsize 100<

16、p>　　#define NULL 0　　typedef struct　　{　　int Maze[maxsize][maxsize];　　int maze_x,maze_y;<b&g

17、t;　　}maze;　　typedef struct point 　　{　　int vex_x,vex_y; 　　int direction;

18、 　　struct point *next; 　　}Point;　　maze creat()　　{　　i

19、nt i,j;　　maze a;　　printf("hang shu he lei shu:");　　scanf("%d%d",&a.maze_x,&a.maze_y);<

20、;p>　　for(i=1;i<=a.maze_x;i++)　　{　　printf("shu ru %d hang:",i);　　for(j=1;j<=a.maze_y;j++)　　scanf(&q

21、uot;%d",&a.Maze[i][j]);　　}　　return a;　　}　　int found(int x,int y,Point

22、*head) {　　Point *p=head;　　while(p)　　{　　if(x==p->vex_x&&y==p->vex_y)<p

23、>　　return 1;　　p=p->next;　　}　　return 0;　　}&

24、lt;p>　　Point *secret(maze a) 　　{　　Point *top,*p; 　　int j,m,x,y;　　p=(Point *)

25、malloc(sizeof(Point));　　p->vex_x=1;　　p->vex_y=1;　　p->next=NULL;　　top=p;　　j=1;&

26、lt;/b>　　do　　{　　while(j<=4)　　{　　m=0;</b&g

27、t;　　x=top->vex_x;　　y=top->vex_y;　　switch(j)　　{　　case 1:if(y+1<=a.maz

28、e_y&&!a.Maze[x][y+1]&&!found(x,y+1,top))　　{　　p=(Point *)malloc(sizeof(Point));　　p->vex_x=x;p->vex_y=y+1;

29、　　p->next=top;　　top->direction=j;　　top=p;m=1;　　}　　break;　　case

30、 2:if(x+1<=a.maze_x&&!a.Maze[x+1][y]&&!found(x+1,y,top))　　{　　p=(Point *)malloc(sizeof(Point));　　p->vex_x=x+1;p->v

31、ex_y=y;　　p->next=top;　　top->direction=j;　　top=p;m=1;　　}　　break;</p&g

32、t;　　case 3:if(y-1<=a.maze_y&&!a.Maze[x][y-1]&&!found(x,y-1,top))　　{　　p=(Point *)malloc(sizeof(Point));　　p-&g

33、t;vex_x=x;p->vex_y=y-1;　　p->next=top;　　top->direction=j;　　top=p;m=1;　　}　　break

34、;　　case 4:if(x-1<=a.maze_x&&!a.Maze[x-1][y]&&!found(x-1,y,top))　　{　　p=(Point *)malloc(sizeof(Point));</p&g

35、t;　　p->vex_x=x-1;p->vex_y=y;　　p->next=top;　　top->direction=j;　　top=p;m=1;　　}<p&

36、gt;　　break;　　}　　if(m!=0)　　{j=1;break;}　　else j++;

37、　　}　　if(j>4)　　{　　if(top!=NULL)　　{&l

38、t;p>　　top=top->next;　　if(top==NULL)return NULL;　　j=top->direction+1;top->direction=j;　　}　　}</

39、b>　　}while(top->vex_x!=a.maze_x||top->vex_y!=a.maze_y);　　if(top->vex_x==a.maze_x&&top->vex_y==a.maze_y)top->direction=0;　　return to

40、p;　　}　　int print(Point *p)　　{　　int i=0,top=0;　　Point *stack[maxsize];</p&g

41、t;　　if(p==NULL) 　　{　　printf("bu neng dao da lu kou!\n");　　return 0;

42、　}　　else　　{　　printf("shu chu lu jing（san yuan zu biao shi）：\n");　　while(p!=NUL

43、L)　　{　　stack[top++]=p;　　p=p->next;　　}　　while(top>0)

44、;　　{　　top--;　　printf("(%d,%d,%d)",stack[top]->vex_x,stack[top]->vex_y,stack[top]->direction);<b&g

45、t;　　i++;　　if(i%8==0)printf("\n");　　}　　}　　printf("\n");&l

46、t;p>　　return 1;　　}　　void printmazepath(Point *p,maze road)　　{　　int

47、i,j;　　char m[maxsize][maxsize];　　printf("lu jing tu shi:\n");　　for(i=1;i<=road.maze_x;i++)　　for(j=1;j<=road.ma

48、ze_y;j++)　　{　　if(road.Maze[i][j])m[i][j]='1';　　else m[i][j]='0';　　}<

49、;p>　　while(p)　　{　　switch(p->direction)　　{　　case 0:m[p->vex_x][p->ve

50、x_y]=1;break;　　case 1:m[p->vex_x][p->vex_y]=26;break;　　case 2:m[p->vex_x][p->vex_y]=25;break;　　case 3:m[p->vex_x][p->vex_y]=27;break;</p

51、>　　case 4:m[p->vex_x][p->vex_y]=24;break;　　}　　p=p->next;　　}　　for(i=1;i<=

52、road.maze_x;i++)　　for(j=1;j<=road.maze_y;j++)　　{　　printf("%c",m[i][j]);　　if(j<road.maze_y)printf(&quo

53、t; ");　　else printf("\n");　　}　　}　　void main()　　{</

54、b>　　maze road;　　Point *p;　　road=creat();　　p=secret(road);　　if(print(p))printmazepath(p,road);

55、　　getch();　　}　　遞歸　　#include<stdio.h>　　#include<ma

56、lloc.h>　　#define maxsize 100　　#define NULL 0　　typedef struct　　{　　int Maze[maxsize][maxsize];&

57、lt;/p>　　int maze_x,maze_y;　　}maze;　　maze a;　　typedef struct point　　{</b&

58、gt;　　int vex_x,vex_y;　　int direction;　　struct point *next;　　}Point;　　maze creat()<

59、;p>　　{　　int i,j;　　maze a;　　printf("shu ru hang he lie:");　　scanf(&

60、quot;%d%d",&a.maze_x,&a.maze_y);　　for(i=1;i<=a.maze_x;i++)　　{　　printf("shu ru di %d hang:",i);<p&

61、gt;　　for(j=1;j<=a.maze_y;j++)　　scanf("%d",&a.Maze[i][j]);　　}　　return a;

62、　}　　int found(int x,int y,Point *head)　　{　　Point *p=head;　　while(p)

63、　　{　　if(x==p->vex_x&&y==p->vex_y)　　return 1;　　p=p->next;　　}<

64、;/p>　　return 0;　　}　　int k=1;　　int print(Point *p)　　{<

65、/b>　　int i=0,top=0;　　Point *stack[maxsize];　　if(p==NULL) {printf("bu neng dao da!\n");return 0;}　　else&l

66、t;/p>　　{　　printf("shu chu di %d tiao mi gong lu jing(san yuan zu):\n",k++);　　while(p!=NULL)　　{&

67、lt;/p>　　stack[top++]=p;if(top==1)stack[top-1]->direction=0;　　p=p->next;　　}　　while(top>0)<b&

68、gt;　　{　　top--;　　printf("(%d,%d,%d)",stack[top]->vex_x,stack[top]->vex_y,stack[top]->direction);　　i++

69、;　　if(i%8==0)printf("\n");　　}　　}　　printf("\n");

70、　　return 1;　　}　　void printmazepath(Point *p,maze road)　　{　　int i,j;<

71、;/b>　　char m[maxsize][maxsize];　　printf("mi gong lu jing tu shi :\n");　　for(i=1;i<=road.maze_x;i++)　　for(j=1;j<=road.

72、maze_y;j++)　　{　　if(road.Maze[i][j])m[i][j]='1';　　else m[i][j]='0';　　}&

73、lt;p>　　while(p)　　{　　switch(p->direction)　　{　　case 0:m[p->vex_x][p->

74、vex_y]=1;break;　　case 1:m[p->vex_x][p->vex_y]=26;break;　　case 2:m[p->vex_x][p->vex_y]=25;break;　　case 3:m[p->vex_x][p->vex_y]=27;break;<

75、/p>　　case 4:m[p->vex_x][p->vex_y]=24;break;　　}　　p=p->next;　　}　　for(i=1;i<

76、;=road.maze_x;i++)　　for(j=1;j<=road.maze_y;j++)　　{　　printf("%c",m[i][j]);　　if(j<road.maze_y)printf(&q

77、uot; ");　　else printf("\n");　　}　　printf("\n");　　}　　i

78、nt sign=0;　　void mazepath(Point *p,int j)　　{　　int x,y,i;　　Point *q;　　x=p->

79、vex_x;y=p->vex_y;　　switch(j)　　{　　case 1:　　if(y+1<=a.maze_y&&!foun

80、d(x,y+1,p)&&!a.Maze[x][y+1])　　{　　q=(Point*)malloc(sizeof(Point));　　q->vex_x=x;q->vex_y=y+1;q->next=p;

81、;　　p->direction=j;　　if(q->vex_x==a.maze_x&&q->vex_y==a.maze_y)　　{　　if(print(q))printmazepath(q,a);sign=1;<

82、p>　　}　　else for(i=1;i<=4;i++)　　mazepath(q,i);　　}　　break;<p

83、>　　case 2:　　if(x+1<=a.maze_x&&!found(x+1,y,p)&&!a.Maze[x+1][y])　　{　　q=(Point*)malloc(sizeof(Point

84、));　　q->vex_x=x+1;q->vex_y=y;q->next=p;　　p->direction=j;　　if(q->vex_x==a.maze_x&&q->vex_y==a.maze_y)

85、　{　　if(print(q))printmazepath(q,a);sign=1;　　}　　else for(i=1;i<=4;i++)　　mazepath(q,i);<p&g

86、t;　　}　　break;　　case 3:　　if(y-1>=1&&!found(x,y-1,p)&&!a.Maze[x][y-1])&

87、lt;p>　　{　　q=(Point*)malloc(sizeof(Point));　　q->vex_x=x;q->vex_y=y-1;q->next=p;　　p->direction=j;　　if(q-

88、>vex_x==a.maze_x&&q->vex_y==a.maze_y)　　{　　if(print(q))printmazepath(q,a);sign=1;　　}

89、　else for(i=1;i<=4;i++)　　mazepath(q,i);　　}　　break;　　case 4:<p

90、>　　if(x-1>=1&&!found(x-1,y,p)&&!a.Maze[x-1][y])　　{　　q=(Point*)malloc(sizeof(Point));　　q->vex_x=x-1;q->vex_y=y;

91、q->next=p;　　p->direction=j;　　if(q->vex_x==a.maze_x&&q->vex_y==a.maze_y)　　{　　if(print(q))printmaze

92、path(q,a);sign=1;　　}　　else for(i=1;i<=4;i++)　　mazepath(q,i);　　}

93、break;　　}　　}　　void main()　　{　　int i;<

94、;/b>　　Point *p;　　a=creat();　　p=(Point*)malloc(sizeof(Point));　　p->vex_x=1;p->vex_y=1;p->next=NULL;</p&

95、gt;　　printf("\n di gui qiu de mi gong mei you ke neng de lu xian\n");　　for(i=1;i<=4;i++)　　mazepath(p,i);　　if(sign==0)<

96、;p>　　printf("bu neng dao da chu kou\n");　　getch();　　}　　6.運行與測試<

97、b>　　非遞歸：　　首先輸入行數(shù)和列數(shù)，然后按行輸入迷宮信息我輸入的是：　　行數(shù)6，列數(shù)8:；　　迷宮信息為：0 1 1 1 0 1 1 1；0 0 0 0 1 1 1 1；0 1 0 0 0 0 0 1；0 1 1 1 0 0 1 1；</p

98、>　　1 0 0 1 1 0 0 0；0 1 1 0 0 1 1 0； 　　運行結(jié)果為：　　、 　　遞歸：　　首先輸入行數(shù)和列數(shù)，然后按行輸入迷宮

99、信息我輸入的是：　　輸入6行8列的迷宮信息：　　0 1 1 1 0 1 1 1；0 0 0 0 1 1 1 1；0 1 0 0 0 0 0 1；0 1 1 1 0 0 1 1；　　1 0 0 1 1 0 0 0；0 1 1 0 0 1 1 0； 　　運

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

溫馨提示

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

數(shù)據(jù)結(jié)構課程設計報告--迷宮

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構課程設計報告--迷宮

文檔簡介

溫馨提示

最新文檔

評論

免費下載