數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--迷宮

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告　　題目：迷宮問題　　姓名：　　學(xué)號：　　班級：<

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

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

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

5、i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。這樣是路徑更加明顯，具體的數(shù)據(jù)結(jié)構(gòu)為：　　#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//鏈棧的每個(gè)結(jié)點(diǎn)定義　　{　　int vex_x,vex_y;//結(jié)點(diǎn)的橫縱坐標(biāo)　　int direction;//下一個(gè)結(jié)點(diǎn)的方向　　struct point *next;//指向下一個(gè)

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

9、個(gè)人報(bào)告給上一個(gè)路口的人，依次層層上報(bào)，最后消息傳到了領(lǐng)導(dǎo)那里，于是這位領(lǐng)導(dǎo)就順著這條畫好的通路大搖大擺地通過了迷宮。所以具體的數(shù)據(jù)結(jié)構(gòu)為：　　#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//鏈棧的每個(gè)結(jié)點(diǎn)定義　　{

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

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

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

15、b>　　5.編碼實(shí)現(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.運(yùn)行與測試<

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； 　　運(yùn)行結(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ùn)

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

溫馨提示

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)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--迷宮

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--迷宮

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載