迷宮問題課程設(shè)計報告

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

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

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

文檔簡介

1、　　課程設(shè)計說明書　　課程設(shè)計任務(wù)書　　課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法　　設(shè)計題目：迷宮問題　　已知技術(shù)參數(shù)和設(shè)計要求：&

2、lt;p>　　問題描述：　　以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1，1）到出口（m,n）的一條通路，或得出沒有通路的結(jié)論。　　基本要求：　　首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然

3、后編寫一個求迷宮問題的非遞歸程序，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)， d表示走到下一坐標(biāo)的方向。　　測試數(shù)據(jù)：　　迷宮用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生。　　左上角（1，1）為入口，右下角（m,n）為出口。<p

4、>　　選作內(nèi)容：　　1以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路　　設(shè)計工作量：　　40課時　　工作計劃：

5、　　課表如下：　?。ň唧w時間地點老師先申請，機(jī)動安排）　　指導(dǎo)教師簽名：　　　　　　　　　日期：　　　　教研室主任簽名：　　　　　　　日期：　　　　　　　　　　系主

6、任簽名：　　　　　　　　　日期：　　　　　　　　　　摘要　　設(shè)計一個迷宮程序，熟練運用所學(xué)的《C程序設(shè)計》及《數(shù)據(jù)結(jié)構(gòu)-C語言版》知識，按要求編寫，實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求迷宮問題的非遞歸程序，求得通路。迷宮需隨機(jī)產(chǎn)生，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮

7、中的一個坐標(biāo)， d表示走到下一坐標(biāo)的方向，此次程序設(shè)計。　　關(guān)鍵字：鏈?zhǔn)酱鎯Γ瑮?，非遞歸　　目錄　　1 設(shè)計內(nèi)容與要求6　　2 實驗設(shè)計7　　2.1

8、鏈表結(jié)構(gòu)7　　2.2 鏈?zhǔn)綏?　　2.3棧的基本操作8　　3實現(xiàn)9　　main函數(shù)10　　**Init

9、Maze()10　　PrintWay( )10　　FindMaze()11　　3.1產(chǎn)生迷宮方式13　　4 測試16　　5總結(jié)18<

10、/p>　　參考文獻(xiàn)19　　1 設(shè)計內(nèi)容與要求　　課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法　　設(shè)計題目：迷宮問題　　已知技術(shù)參數(shù)和設(shè)計要求：<

11、;/p>　　問題描述：　　以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1，1）到出口（m,n）的一條通路，或得出沒有通路的結(jié)論。　　基本要求：　　首先實現(xiàn)一個以鏈表作

12、存儲結(jié)構(gòu)的棧類型，然后編寫一個求迷宮問題的非遞歸程序，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)， d表示走到下一坐標(biāo)的方向。　　測試數(shù)據(jù)：　　迷宮用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生。　　左上角（1，1）為入口，右下角（m,n）為出口。</p&

13、gt;　　選作內(nèi)容：　　1以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路　　2 實驗設(shè)計　　本程序要求實現(xiàn)迷宮問題的相關(guān)操作，包括迷宮的組織和存儲，并實現(xiàn)迷宮路由算法（即查找迷宮路徑）。程序所能達(dá)到的：具體包括迷

14、宮的建立，迷宮的存儲（迷宮由自動生成或文件生成），迷宮中路徑的查找。　　迷宮是一個矩形區(qū)域，迷宮存在一個入口和一個出口，其內(nèi)部包含了不能穿越的障礙，迷宮的建立即是建立這樣一個迷宮矩陣，用于存儲迷宮信息，包括可以穿越的路和不可穿越的障礙物，分別用0表示通路，1表示障礙。對于迷宮矩陣，用m×n的矩陣來描述，m和n分別代表迷宮的行數(shù)和列數(shù)。這樣，則迷宮中的每個位置都可以用其行號和列號來指定。

15、從入口到出口的路徑是由一組位置構(gòu)成的，每個位置都沒有障礙，且每個位置（第一個除外）都是前一個位置的上、下、左、右的鄰居。　　為了描述迷宮中位置（i,j）處有無障礙，規(guī)定當(dāng)位置（i,j）處有一個障礙時，其值為1，否則為0，這樣迷宮就可以用0、1矩陣來描述，在構(gòu)造矩陣時，為了操作方便會將矩陣四周置為1（不通）。　　用來描述迷宮位置和方向的結(jié)構(gòu)體定義：<

16、/p>　　typedef struct pos /*描述迷宮當(dāng)前位置和方向*/　　{　　int x;//橫坐標(biāo)　　int y;//豎坐標(biāo)　　int way;/*0:無效,1:左,2:下,3:右,4:上*

17、/　　}P;　　2.1 鏈表結(jié)構(gòu)　　單鏈表的結(jié)構(gòu)體定義：　　typedef struct LinkNode /*鏈表結(jié)構(gòu),用于棧的元素類型*/<

18、b>　　{　　P pos;　　struct LinkNode *next;　　}LinkNode;　　2.2 鏈?zhǔn)綏?lt;/b>　　棧的鏈?zhǔn)?/p>

19、存儲結(jié)構(gòu)，鏈棧是沒有附加頭結(jié)點的運算受限的單鏈表，棧頂指針就是鏈表的頭指針，棧的結(jié)點定義為：　　typedef struct stack /*鏈?zhǔn)綏?用于存儲迷宮路徑信息*/　　{　　LinkNode *head; /*頭指針*/

20、;　　}Stack;　　2.3棧的基本操作　　棧是一種后進(jìn)先出的線性表（LIFO），它上面的插入和刪除運算只能在線性表的同一端進(jìn)行，插入和刪除的這一端稱為棧頂（變化端），另一端稱為棧底（固定端）。　　棧的基本運算有：初始化棧、進(jìn)棧（入棧、

21、插入）、退棧（出棧、刪除）、判棧空、取棧頂元素。　　void InitStack(Stack *s) /*棧置空*/　　{　　s->head=NULL;　　}<

22、p>　　void Push(Stack *s,P p) /*數(shù)據(jù)入棧*/　　{　　LinkNode *LN=(LinkNode *)malloc(sizeof(LinkNode));//申請內(nèi)存空間　　LN->pos=p;

23、;　　LN->next=s->head;　　s->head=LN;　　}　　P Pop(Stack *s) /*棧頂元素出棧*/　　{<p&g

24、t;　　P pos;　　LinkNode *LN;　　LN=s->head;　　s->head=s->head->next;　　pos=LN->pos;　　del

25、ete LN;　　return pos;　　}　　int Empty(Stack s) /*判空*/　　{　　if(s.head==NULL)<

26、/p>　　return 1;　　else 　　return 0;　　}　　P GetPop(

27、Stack s) /*讀取棧頂元素*/　　{　　return s.head->pos;　　}　　3實現(xiàn)

28、按課程設(shè)計要求編寫代碼，實現(xiàn)了以鏈表作存儲結(jié)構(gòu)的棧類型，迷宮用偽隨機(jī)數(shù)產(chǎn)生　　程序產(chǎn)生，對于查找迷宮路由問題：首先，從迷宮的坐標(biāo)為（1,1）進(jìn)入，考察其上、下、左、右位置上的鄰居是否是障礙，若不是就移動到這個相鄰位置上，然后對于這個位置開始搜索通往出口的路徑，如果不成功，就選擇另一個相鄰的位置，并從它開始搜索路徑，為防止搜索出現(xiàn)重復(fù)，將已經(jīng)搜索過的位置記為-1，同時為保留過搜索的痕跡，在考察相鄰

29、位置之前，將當(dāng)前位置保存在一個棧中，如果所有相鄰的非障礙位置均被搜索過，且未能找到通往出口的路徑，則表明不存在從入口到出口的路徑。　　本程序函數(shù)關(guān)系圖如下：　　路徑查找流程圖　　main函數(shù)如下：void main()　　{ syst

30、em("color 4F");　　int **maze=InitMaze(); /*初始化迷宮*/　　if(FindMaze(maze,row,line)) /*探索路徑*/　　printf("路徑探索成功!\n");&l

31、t;b>　　else　　printf("路徑探索失敗!\n");　　}　　**InitMaze() 函數(shù)創(chuàng)建一個迷宮圖并返回迷宮的二維指針　　int **InitMaze() {</

32、p>　　int **maze=NULL;　　int i;　　int j,choice;　　printf("請選擇產(chǎn)生迷宮類型【1.隨機(jī)產(chǎn)生 2.規(guī)定數(shù)組產(chǎn)生】\n");　　scanf(&

33、quot;%d",&choice);　　printf("請輸入迷宮的行跟列(x,y):");　　加上【3.1產(chǎn)生迷宮方式】代碼　　return maze;　　}<p&

34、gt;　　PrintWay()輸出迷宮路徑函數(shù)　　void PrintWay(Stack p) /*輸出路徑*/　　{int i=0;　　P pos;　　Stack t; /*

35、臨時棧,用于存儲從入口到出口的路徑*/　　LinkNode *temp;　　int a,b;　　InitStack(&t);　　temp=(LinkNode *)malloc(sizeof(LinkNode));</p&

36、gt;　　temp->pos=Pop(&p); /*取棧頂元素,即出口*/　　Push(&t,temp->pos); /*入棧*/　　free(temp);　　while(!Empty(p))<b&g

37、t;　　{　　temp=(LinkNode *)malloc(sizeof(LinkNode));　　temp->pos=Pop(&p); /*獲取下一個元素*/　　a=GetPop(t).x-temp->pos.x; /*左:a=0,b=1; 下:a=1,b=

38、0*/　　b=GetPop(t).y-temp->pos.y; /*右:a=0,b=-1 上:a=-1,b=0;*/　　if(b==1)　　temp->pos.way=1;　　else if(a==1)</p&

39、gt;　　temp->pos.way=2;　　else if(b==-1)　　temp->pos.way=3;　　else if(a==-1)　　temp->pos.way=4;　　Push

40、(&t,temp->pos); /*新位置入棧*/　　free(temp);　　}　　printf("迷宮的路徑為:\n");　　printf("前兩個數(shù)字表示位置,最后一個數(shù)字表示方

41、向\n");　　printf("1表示向左\n2表示向下\n3表示向右\n4表示向上\n0表示無方向\n");　　while(!Empty(t)) /*輸出路徑*/　　{　　pos=Pop(&am

42、p;t);　　printf("\t<%d,%d,%d>\n",pos.x,pos.y,pos.way);　　}　　}　　FindMaze()尋找路徑函數(shù)，接受**I

43、nitMaze()返回的迷宮二維指針，接受參數(shù)r和參數(shù)l，尋找路徑,找到返回1,沒找到返回0。　　其函數(shù)代碼如下：　　int FindMaze(int **maze,int r,int l) 　　{

44、;　　Stack p,q; /*棧p,q分別表示探索迷宮的路徑和過程*/　　P temp1,temp2;　　int a,b;　　InitStack(&p);　　InitStack(&q);

45、;　　temp1.x=1;　　temp1.y=1; //　　maze[1][1]=-1; /*標(biāo)記已經(jīng)走過*/　　Push(&p,temp1);　　Push(&q,temp1);<p

46、>　　while(!Empty(q))　　{　　temp2=GetPop(q);　　if(!(GetPop(p).x==GetPop(q).x　　&&GetPop(p).y==GetPop(q).y)) <

47、;/p>　　Push(&p,temp2); /*若有新元素入棧,就把q的棧頂元素存入p中*/ 　　a=temp2.x;　　b=temp2.y+1; /*當(dāng)前位置左方向相鄰的方塊*/　　if(maze[a][b]==0)&l

48、t;b>　　{　　temp1.x=a;　　temp1.y=b;　　maze[a][b]=-1; /*標(biāo)記已走過*/　　Push(&q,temp1);　　}

49、;　　if(a==r&&b==l) /*到達(dá)出口*/　　{ 　　temp1.way=0;　　Push(&p,temp1);　　PrintWay(p);</

50、p>　　return 1;　　}　　a=temp2.x+1;　　b=temp2.y; /*當(dāng)前位置下方向相鄰的方塊*/　　if(maze[a][b]==0)&l

51、t;/p>　　{　　temp1.x=a;　　temp1.y=b;　　maze[a][b]=-1; /*標(biāo)記已走過*/　　Push(&q,temp1);

52、　　}　　if(a==r&&b==l) /*到達(dá)出口*/　　{　　temp1.way=0;　　Push(&p,temp1);

53、;　　PrintWay(p);　　return 1;　　}　　a=temp2.x;　　b=temp2.y-1; /*當(dāng)前位置右方向相鄰的方塊*/

54、　if(maze[a][b]==0)　　{　　temp1.x=a;　　temp1.y=b;　　maze[a][b]=-1; /*標(biāo)記已走過*/　　Push(&q,temp1);&

55、lt;/p>　　}　　if(a==r&&b==l) /*到達(dá)出口*/　　{　　temp1.way=0;　　Push(&p,temp1);

56、　　PrintWay(p);　　return 1;　　}　　a=temp2.x-1;　　b=temp2.y; /*當(dāng)前位置上方向相鄰的方塊*/&l

57、t;/p>　　if(maze[a][b]==0)　　{　　temp1.x=a;　　temp1.y=b;　　maze[a][b]=-1; /*標(biāo)記已走過*/

58、Push(&q,temp1);　　}　　if(a==r&&b==l) /*到達(dá)出口*/　　{　　temp1.way=0;

59、　Push(&p,temp1);　　PrintWay(p);　　return 1;　　}　　if(GetPop(p).x==GetPop(q).x

60、　　&&GetPop(p).y==GetPop(q).y) /*若四個方向都走不通,則數(shù)據(jù)出棧,退回一格*/　　{ 　　Pop(&p);　　Pop(&q);<

61、/p>　　}　　}　　return 0; }/*探索迷宮失敗*/　　3.1產(chǎn)生迷宮方式　　程序運行中會要求選擇產(chǎn)生迷宮類型（1

62、.隨機(jī)產(chǎn)生 2.規(guī)定數(shù)組產(chǎn)生）　　隨機(jī)產(chǎn)生: 迷宮用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生,其產(chǎn)生程序如下　　->首先要向計算機(jī)系統(tǒng)申請一定長度的內(nèi)存空間用來存放隨機(jī)產(chǎn)生的數(shù)據(jù)　　printf("請選擇產(chǎn)生迷宮類型【1.隨機(jī)產(chǎn)生 2.規(guī)定數(shù)組產(chǎn)生】\n");　　s

63、canf("%d",&choice);　　printf("請輸入迷宮的行跟列(x,y):"); 　　scanf("%d,%d",&row,&line); /*輸入迷宮的行和列*/　　maze=(int **)malloc((r

64、ow+2)*sizeof(int *)); 　　for(i=0;i<row+2;i++) 　　{　　maze[i]=(int *)malloc(sizeof(int)*(line+2)); 　　}</

65、b>　　輸入1選擇隨機(jī)產(chǎn)生迷宮，rand()產(chǎn)生偽隨機(jī)數(shù)，把其產(chǎn)生的偽隨機(jī)數(shù)賦給maze[i][j]　　if(choice==1)　　{　　printf("自動生成迷宮如下:\n"); /*迷宮,1代表

66、路障,0代表通行*/　　for(i=1;i<=row;i++)　　for(j=1;j<=line;j++)　　maze[i][j]=rand()%2; 　　for(i=0;i<line+2;i++) /*將迷宮的四周都變?yōu)?*/

67、　　maze[0][i]=1;　　for(i=0;i<line+2;i++)　　maze[row+1][i]=1;　　for(i=0;i<row+2;i++)　　maze[i][0]=1;　　fo

68、r(i=0;i<row+2;i++)　　maze[i][line+1]=1;　　for(i=0;i<row+2;i++) /*輸出迷宮*/　　{　　for(j=0;j<line+2;j++)

69、　　printf("% d ",maze[i][j]);　　printf("\n");　　} }　　規(guī)定數(shù)組產(chǎn)生：　　讀取文件中已經(jīng)設(shè)

70、定好的迷宮數(shù)組，文件為open.txt,　　其代碼如下：　　printf("規(guī)定數(shù)組產(chǎn)生的迷宮如下:\n");　　fp=fopen("open.txt","r");　　if(

71、fp==NULL)　　printf("error!\n");　　else　　{for(i=1;i<=row;i++)　　{　　f

72、or(j=1;j<=line;j++)　　{fscanf(fp,"%d",&maze[i][j]);　　}　　}fclose(fp); }　　求解迷宮中一條通路的算法：<

73、p>　　while（棧不空）{　　設(shè)定當(dāng)前位置的初值為入口位置；　　若當(dāng)前位置可通；　　則{ 將當(dāng)前位置插入棧頂；　　若該位置是出口位置，則結(jié)束；　　否則換當(dāng)前位置的東鄰方塊為新的當(dāng)前位

74、置；　　}　　否則{　　若棧不空且棧頂位置尚有其他方向未被探索，　　則設(shè)定新的當(dāng)前位置為沿恩順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；　　若棧不空但棧頂位

75、置的四周均不可通，　　則{刪去棧頂位置；　　若棧不空，則重新測試新的棧頂位置，　　直至找一個可通的相鄰塊或出棧至?？?；　　}　　}<

76、;/b>　　}　　4 測試　　測試是否將產(chǎn)生的偽隨機(jī)數(shù)賦值給maze[i][j]，自動生成一個迷宮，并查找出路徑。　　測試結(jié)果如表4.1所示：<p&

77、gt;　　表4.1 　　用debug的方法測試迷宮路徑查找的全過程　　表4.2 　　測試結(jié)果如圖4.1-1　　圖4.1-1<

78、p>　　5總結(jié)　　之前很多的知識都顯得很模糊，處于似懂非懂的邊緣，但是通過兩周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，至少能讓我更多的接觸這門課程，更為清晰地了解它，也學(xué)會了全面分析問題。當(dāng)然實際過程中存在的問題相當(dāng)多,比如在迷宮路徑查找上，一開始就沒想到這些問題而走了不少彎路，不過幸好有查閱資料意識到錯誤。同時也認(rèn)識到編程的過程是相當(dāng)嚴(yán)謹(jǐn)?shù)?，只要有一個小小的符號疏忽都是

79、錯誤的根源。而且還得使程序的運行結(jié)果不那么機(jī)器化更貼近我們的生活就需要更細(xì)致的分析，因此在編程的過程中只有想得深才能跟好的滿足我們的需求。在整個設(shè)計過程中，我認(rèn)識到自己有很大的不足，甚至包括一些概念性的東西都還沒弄懂，值得反思。但又通過實際操作讓我有了更多的興趣在其中，還有因為是用C語言編寫的,所以使自己對C語言又溫習(xí)了。總之，課程設(shè)計讓我學(xué)到了很多，使得自己的思維都更系統(tǒng)，更謹(jǐn)慎，提高了自己的分析能力，反正對自己有很大的幫助。<

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

迷宮問題課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

迷宮問題課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載