數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言課程設(shè)計(jì)報(bào)告之迷宮

1、<p>　　C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　學(xué) 號(hào) **  </p><p>　　姓 名 ** </p><p>　　課程設(shè)計(jì)題目 迷 宮 求 解 </p><p><b>　　2012 年 5月</b&g

2、t;</p><p><b>　　目 錄</b></p><p>　　1 需求分析 </p><p>　　1.1 功能與數(shù)據(jù)需求 </p>

3、<p>　　1.1.1 題目要求的功能 </p><p>　　1.1.2 擴(kuò)展功能 </p><p>　　1.2 界面需求

4、 </p><p>　　1.3 開(kāi)發(fā)環(huán)境與運(yùn)行需求 </p><p>　　2 概要設(shè)計(jì) </p><p><b>　　2.1主要數(shù)據(jù)結(jié)構(gòu)</b>&

5、lt;/p><p><b>　　2.2程序總體結(jié)構(gòu)</b></p><p>　　2.3各模塊函數(shù)說(shuō)明</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1算法分析與設(shè)計(jì)</p><p>　　3.2主要程序段設(shè)計(jì)</p><p>&l

6、t;b>　　4 測(cè)試</b></p><p><b>　　5 使用說(shuō)明</b></p><p>　　5.1應(yīng)用程序功能的詳細(xì)說(shuō)明</p><p>　　5.2應(yīng)用程序運(yùn)行環(huán)境要求</p><p>　　5.5輸入數(shù)據(jù)類(lèi)型、格式和內(nèi)容限制</p><p><b>　　6 總結(jié)

7、提高</b></p><p><b>　　6.1課程設(shè)計(jì)總結(jié)</b></p><p>　　6.2開(kāi)發(fā)中遇到的問(wèn)題和解決方法</p><p>　　6.3 對(duì)自己完成課設(shè)完成情況的評(píng)價(jià)</p><p>　　6.4《C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程的意見(jiàn)與建議</p><p><b>

8、;　　附錄：程序源代碼</b></p><p>　　1 需求分析 </p><p>　　1.1 功能與數(shù)據(jù)需求 </p><p><b>　　迷宮求解<

9、;/b></p><p>　　問(wèn)題描述：以一個(gè)m×n的長(zhǎng)方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。</p><p>　　1.1.1 題目要求的功能 </p><p>　　基本要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路

10、以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1）, （1,2,2）, （2,2,2）</p><p>　?。?,2,3）, （3,1,2）,…。</p><p>　　測(cè)試數(shù)據(jù)：迷宮的測(cè)試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（9,8）為出口。</p><p>

11、　　1 2 3 4 5 6 7 8</p><p>　　1.1.2 擴(kuò)展功能</p><p>　?。?）編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路；</p><p>　?。?）以方陣形式輸出迷宮及其通路</p><p><b>　　1.2 界面需求</b></p><p><

12、b>　　請(qǐng)求輸入進(jìn)入程序</b></p><p><b>　　請(qǐng)求輸入起始位置</b></p><p><b>　　請(qǐng)求輸入終點(diǎn)位置</b></p><p><b>　　輸出方陣迷宮</b></p><p><b>　　輸出路徑</b>&

13、lt;/p><p><b>　　輸出方陣路徑</b></p><p>　　1.3 開(kāi)發(fā)環(huán)境與運(yùn)行需求</p><p>　　Visual C++6.0</p><p><b>　　2 概要設(shè)計(jì) </b></p><p><b>　　2.1主要數(shù)據(jù)結(jié)構(gòu)</b>

14、</p><p>　　2.3各模塊函數(shù)說(shuō)明</p><p>　　typedef struct{ </p><p>　　int pos_x[length];//進(jìn)棧坐標(biāo)</p><p>　　int pos_y[length];</p><p><b>　　int top; </b></p>

15、;<p>　　int base; </p><p>　　}Stack; //新建結(jié)構(gòu)體</p><p>　　void initStack(Stack *p) //初始化棧</p><p>　　Push(Stack *p,int x,int y,int d) //入棧具體操作 Pop(Stack *p,int read[2],int d) //出

16、棧并讀出前一步的坐標(biāo) initMaze(int Maze[10][9])//建立迷宮</p><p>　　Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具體路徑的求解 menu();//調(diào)用菜單函數(shù) main();//實(shí)現(xiàn)迷宮求解的主函數(shù)</

17、p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　迷宮的過(guò)程可以模擬為一個(gè)搜索的過(guò)程：每到一處，總讓它按左、右、上、下4個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過(guò)，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果4方向都走不通或曾經(jīng)到達(dá)過(guò)，則退回一步，在原來(lái)的位置上繼續(xù)試探下一位置。</p><p>　　每前進(jìn)或后退一步，都

18、要進(jìn)行判斷：若前進(jìn)到了出口處，則說(shuō)明找到了一條合適的通路；若退回到了入口處，則說(shuō)明不存在合法的通路到達(dá)出口。</p><p>　　用一個(gè)二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點(diǎn)在位置（1，1）處，出口點(diǎn)在位置（m,n）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。</p><p>　　二維數(shù)組的第0行、第m+1行、

19、第0列、第m+1列元素全置成“1”， 表示迷宮的外墻；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；假設(shè)當(dāng)前所在位置是（x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有4。</p><p><b>　　4 測(cè)試</b></p><p><b>　　5 使用說(shuō)明</b></p><p>　　5.1

20、應(yīng)用程序功能的詳細(xì)說(shuō)明</p><p>　　按提示輸入數(shù)字1進(jìn)入迷宮，輸入迷宮入口，迷宮出口</p><p>　　5.2應(yīng)用程序運(yùn)行環(huán)境要求</p><p>　　Microsoft Visual C++6.0</p><p>　　5.5輸入數(shù)據(jù)類(lèi)型、格式和內(nèi)容限制</p><p>　　輸入的數(shù)據(jù)都是整型（int），輸入

21、迷宮的數(shù)據(jù)間要用空格或回車(chē)隔開(kāi)</p><p><b>　　6 總結(jié)提高</b></p><p><b>　　6.1課程設(shè)計(jì)總結(jié)</b></p><p>　　要能很好的掌握編程,僅僅通過(guò)簡(jiǎn)單的程序的編寫(xiě)是無(wú)法達(dá)成的,需要大量積累和深入研究才有可能。就從這個(gè)迷宮問(wèn)題求解來(lái)說(shuō),在迷宮求路徑就需要使用鏈表的棧,靠出棧和進(jìn)棧來(lái)存取

22、路徑數(shù)據(jù).在程序的編寫(xiě)中也不能一味的向已有的程序進(jìn)行模仿,而要自己摸索,去尋找最好的解決方法,只有帶著問(wèn)題去反復(fù)進(jìn)行實(shí)踐,才能更熟練的掌握和運(yùn)用,當(dāng)然,對(duì)現(xiàn)有的程序也要多去接觸,因?yàn)橛行┏绦蚴俏覀儫o(wú)法在短時(shí)間內(nèi)想出來(lái)的.最重要的一點(diǎn)是持之以恒,要經(jīng)常性的復(fù)習(xí)原來(lái)接觸的程序,這樣才能保證我們有足夠的經(jīng)驗(yàn)去面對(duì)程序問(wèn)題.</p><p>　　6.2開(kāi)發(fā)中遇到的問(wèn)題和解決方法</p><p>　

23、　問(wèn)題： 在開(kāi)始時(shí)迷宮求解的 路徑無(wú)法顯示尋找路徑所走的方向等問(wèn)題。</p><p>　　解決方法：在棧中增加一個(gè)變量d來(lái)表示方向，在尋找路徑的時(shí)候判斷下一個(gè)坐標(biāo)點(diǎn)和本坐標(biāo)點(diǎn)的關(guān)系。在（x）行不變的情況下：（y+1）列加一則表示坐標(biāo)往右走了一步記為1、（y-1）列減一則表示坐標(biāo)往左走了一步記為3；在（y）不變的情況下：（x+1）行加一則表示坐標(biāo)往下走了一步記為2、（x-1）行減一則表示坐標(biāo)往上走了一步記為4；&l

24、t;/p><p>　　6.3 對(duì)自己完成課設(shè)完成情況的評(píng)價(jià)</p><p>　　經(jīng)過(guò)本次課程設(shè)計(jì)，我深刻地明白了理論與實(shí)踐應(yīng)用相結(jié)合的重要性，并努力克服自己在分析復(fù)雜問(wèn)題的弱點(diǎn)。這次課程設(shè)計(jì)同時(shí)也考驗(yàn)我的綜合運(yùn)用所學(xué)知識(shí)的能力和操作能力。</p><p><b>　　參考用書(shū)：</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)

25、言）》，嚴(yán)蔚敏、吳偉民等，清華大學(xué)出版社，2010 年</p><p>　　《數(shù)據(jù)結(jié)構(gòu)與算法分析（c++語(yǔ)言描述）》第2 版，黃達(dá)民編著，清華大學(xué)出版社2006.11</p><p>　　6.4《C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程的意見(jiàn)與建議</p><p>　　希望老師能指導(dǎo)我們把所有的課程設(shè)計(jì)題目都做一遍，因?yàn)槊恳坏李}目所能體現(xiàn)的知識(shí)點(diǎn)是有限的，而且要想提高我們的編

26、程能力還需要大量的練習(xí)。</p><p><b>　　附錄：程序源代碼</b></p><p>　　#include <stdio.h> </p><p>　　#include <malloc.h> </p><p>　　#include<stdlib.h></p>&l

27、t;p>　　#include<conio.h></p><p>　　#define length 50</p><p>　　#define d direction //用d代表所走路徑的方向</p><p><b>　　int n=-1;</b></p><p>　　int step=0; //記

28、錄步驟數(shù) </p><p>　　typedef struct{ </p><p>　　int pos_x[length];//進(jìn)棧坐標(biāo)</p><p>　　int pos_y[length];</p><p><b>　　int top; </b></p><p>　　int base; <

29、/p><p>　　}Stack; //新建結(jié)構(gòu)體</p><p>　　void initStack(Stack *p) </p><p><b>　　{ </b></p><p>　　p->top=p->base=0; </p><p><b>　　}//初始化棧. </b

30、></p><p>　　Push(Stack *p,int x,int y,int d) //入棧具體操作</p><p><b>　　{ </b></p><p><b>　　step++;</b></p><p><b>　　d=0;</b></p>&

31、lt;p><b>　　n=n+1; </b></p><p>　　p->top=p->top+1; </p><p>　　p->pos_x[n]=x; </p><p>　　p->pos_y[n]=y;</p><p><b>　　}</b></p>&l

32、t;p>　　Pop(Stack *p,int read[2],int d) //出棧并讀出前一步的坐標(biāo)</p><p><b>　　{ </b></p><p><b>　　step++;</b></p><p><b>　　d=0;</b></p><p><b&

33、gt;　　n=n-1; </b></p><p>　　p->top=p->top-1; </p><p>　　read[0]=p->pos_x[n]; </p><p>　　read[1]=p->pos_y[n];</p><p><b>　　}</b></p><

34、p>　　initMaze(int Maze[10][9])//建立迷宮函數(shù). </p><p><b>　　{ </b></p><p><b>　　int i; </b></p><p>　　for (i=0;i<=9;i++) {Maze[0][i]=1;} </p><p>　

35、　for (i=0;i<=10;i++) {Maze[i][0]=1;} </p><p>　　for (i=0;i<=9;i++) {Maze[10][i]=1;} </p><p>　　for (i=0;i<=10;i++) {Maze[i][9]=1;} </p><p>　　Maze[1][1]=0;Maze[1][2]=0;Maz

36、e[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]=1;Maze[1][8]=0; </p><p>　　Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=1;Maze[2][8]=0; </p><

37、p>　　Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=0;Maze[3][8]=1; </p><p>　　Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4][6]=0;Maze[4]

38、[7]=1;Maze[4][8]=0; </p><p>　　Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;Maze[5][8]=0;</p><p>　　Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=

39、0;Maze[6][5]=0;Maze[6][6]=1;Maze[6][7]=0;Maze[6][8]=1;</p><p>　　Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;Maze[7][5]=1;Maze[7][6]=0;Maze[7][7]=0;Maze[7][8]=1;</p><p>　　Maze[8][1]=1;Maz

40、e[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0;Maze[8][8]=1;</p><p>　　Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;Maze[9][5]=0;Maze[9][6]=0;Maze[9][7]=0;Maze[9][8]=0;</

41、p><p><b>　　} </b></p><p>　　Print( )//打印出迷宮界面</p><p><b>　?。?lt;/b></p><p>　　int m,n，j,sum；</p><p>　　int Maze[10][9];</p><p&g

42、t;　　printf("迷宮(1代表墻即不通,0代表可通過(guò))\n"); </p><p>　　printf(" ");</p><p>　　for(j=1;j<=8;j++) { printf("%4d",j);}</p><p>　　printf("\n");</p&

43、gt;<p>　　for(m=0;m<=10;m++) </p><p><b>　　{ </b></p><p>　　for(n=0;n<=9;n++) </p><p><b>　　{ </b></p><p>　　printf("%4d",Maze

44、[m][n]);</p><p><b>　　sum++; </b></p><p>　　if(sum%10==0) printf("\n"); </p><p><b>　　} </b></p><p><b>　　} </b></p>&l

45、t;p><b>　?。?lt;/b></p><p>　　Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具體路徑的求解函數(shù)</p><p><b>　　{ </b></p><p><b

46、>　　int x,y; </b></p><p>　　int read[2]; </p><p>　　x=rukou_x; </p><p>　　y=rukou_y; </p><p>　　printf("第%d步:",step);</p><p>　　printf("(

47、%d,%d,%d)\n",x,y,d);</p><p>　　if(x==chukou_x&&y==chukou_y)</p><p><b>　　{</b></p><p>　　printf("到達(dá)出口坐標(biāo)共走了%d步\n",step);return 0;</p><p>

48、<b>　　}</b></p><p>　　else if(Maze[x][y+1]==0) {y=y+1;d=1;Push(p,x,y,d);Maze[x][y-1]=1;Maze[x][y]=1;} </p><p>　　else if(Maze[x+1][y]==0) {x=x+1;d=2;Push(p,x,y,d);Maze[x-1][y]=1;Maze[x]

49、[y]=1;} </p><p>　　else if(Maze[x][y-1]==0) {y=y-1;d=3;Push(p,x,y,d);Maze[x][y+1]=1;Maze[x][y]=1;} </p><p>　　else if(Maze[x-1][y]==0) {x=x-1;d=4;Push(p,x,y,d);Maze[x+1][y]=1;Maze[x][y]=1;} </p

50、><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　Pop(p,read,d); </p><p>　　x=read[0]; </p><p>　　y=read[1];</p><p>　　if(p-&

51、gt;top==p->base) {printf("找不到出口\n");return 0;} </p><p><b>　　} </b></p><p>　　Ways(p,Maze,x,y,chukou_x,chukou_y,d);</p><p><b>　　return 1;</b></

52、p><p><b>　　} </b></p><p><b>　　menu()</b></p><p><b>　　{</b></p><p>　　printf("\t\t************************************\n");

53、 </p><p>　　printf("\t\t* 歡迎進(jìn)入課程設(shè)計(jì) *\n");</p><p>　　printf("\t\t* 迷宮求解程序 *\n");</p><p>　　printf("\t\t* 菜單:

54、 *\n");</p><p>　　printf("\t\t***進(jìn)入迷宮***請(qǐng)輸入1 *\n");</p><p>　　printf("\t\t***退出迷宮***請(qǐng)輸入2 *\n");</p><p>　　print

55、f("\t\t************************************\n");</p><p><b>　　}</b></p><p>　　int main() </p><p><b>　　{ </b></p><p>　　Stack *p; </p&g

56、t;<p><b>　　Stack S; </b></p><p>　　int Maze[10][9]; //定義迷宮</p><p>　　int elem_1[1],elem_2[1],a,j; </p><p>　　int rukou_x,rukou_y,d=0;</p><p>　　int chuko

57、u_x,chukou_y; </p><p>　　int sum=0; </p><p><b>　　p=&S; </b></p><p>　　initMaze(Maze); </p><p>　　system("color 5f");//dos窗口背景顏色函數(shù)</p><

58、p>　　menu();//調(diào)用菜單函數(shù)</p><p>　　printf("請(qǐng)輸入您的選擇:");</p><p>　　scanf("%d",&a);</p><p><b>　　if(a==1){</b></p><p>　　Print( ) //打印迷宮圖.；&l

59、t;/p><p>　　printf("請(qǐng)輸入入口坐標(biāo):"); </p><p>　　scanf("%d",&elem_1[0]); </p><p>　　scanf("%d",&elem_1[1]);</p><p>　　rukou_x=elem_1[0];rukou_y

60、=elem_1[1]; </p><p>　　printf("請(qǐng)輸入出口坐標(biāo):"); //迷宮入口坐標(biāo). </p><p>　　scanf("%d",&elem_2[0]); </p><p>　　scanf("%d",&elem_2[1]);</p><p>　　c

61、hukou_x=elem_2[0];chukou_y=elem_2[1];//迷宮出口坐標(biāo). </p><p>　　if(elem_1[0]>10||elem_1[1]>9||elem_2[0]>10||elem_2[1]>9|| </p><p>　　elem_1[0]<0||elem_1[1]<0||elem_2[0]<0||elem_2[1]

62、<0) </p><p><b>　　{</b></p><p>　　printf("輸入的入口或出口坐標(biāo)錯(cuò)誤\n");} //首先判斷輸入坐標(biāo)是否正確</p><p><b>　　else </b></p><p>　　{ printf("\n")

63、;</p><p>　　printf("說(shuō)明(x,y,z)x,y代表坐標(biāo)點(diǎn);\n");</p><p>　　printf("z代表上個(gè)坐標(biāo)到達(dá)這個(gè)坐標(biāo)所走的方向,0為初始值,1234分別代表向右、下、左、上方向\n");</p><p>　　printf("查找路徑的具體步驟:\n"); </p>

64、;<p>　　initStack(p); </p><p>　　Push(p,rukou_x,rukou_y,d); </p><p>　　Ways(p,Maze,rukou_x,rukou_y,chukou_x,chukou_y,d); </p><p><b>　　} </b></p><p>　　sy

65、stem("pause");</p><p>　　system("cls");</p><p>　　return main();</p><p><b>　　}</b></p><p><b>　　else{</b></p><p>