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

1、WORD格式數(shù)據(jù)構(gòu)造課程設(shè)計(jì)報(bào)告- 迷宮問題求解學(xué)號： 1315925375*：X曉龍班級：13移動 1班指導(dǎo)教師：錢鴿專業(yè)資料整理WORD格式目錄一、需求分析3二、數(shù)據(jù)構(gòu)造31. 數(shù)據(jù)構(gòu)造設(shè)計(jì)考慮32. 邏輯構(gòu)造存儲構(gòu)造3三、算法設(shè)計(jì)4四、調(diào)試分析7五、程序?qū)崿F(xiàn)及測試8六、體會及缺乏之處9七、參考文獻(xiàn)10八、源代碼10專業(yè)資料整理WORD格式一、需求分析本課程設(shè)計(jì)是解決迷宮求解的問題， 從入口出發(fā)， 順某一方向向前探索，假設(shè)能走通，那么繼續(xù)往前走；否那么沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的構(gòu)造來保存從入

2、口到當(dāng)前位置的路徑。 因此，在求迷宮通路的算法中要應(yīng)用“棧 的思想假設(shè) “當(dāng)前位置 指的是 “在搜索過程中的某一時(shí)刻所在圖中某個(gè)方塊位置，那么求迷宮中一條路徑的算法的根本思想是：假設(shè)當(dāng)前位置 “可通，那么納入“當(dāng)前路徑 ，并繼續(xù)朝 “下一位置探索，即切換“下一位置為“當(dāng)前位置 ，如此重復(fù)直至到達(dá)出口；假設(shè)當(dāng)前位置“不可通，那么應(yīng)順著“來向退回到“前一通道塊，然后朝著除“來向之外的其他方向繼續(xù)探索；假設(shè)該通道塊的四周4 個(gè)方塊均“不可通 ，那么應(yīng)從“當(dāng)前路徑上刪除該通道塊。所謂“下一位置指的是當(dāng)前位置四周 4 個(gè)方向上、下、左、右上相鄰的方塊。假設(shè)以棧記錄“當(dāng)前路徑，那么棧頂中存放的是“當(dāng)前路徑

3、上最后一個(gè)通道塊。由此，“納入路徑的操作即為“當(dāng)前位置入棧；“從當(dāng)前路徑上刪除前一通道塊的操作即為“出棧。二、數(shù)據(jù)構(gòu)造1. 數(shù)據(jù)構(gòu)造設(shè)計(jì)考慮1) 建立一個(gè)二維數(shù)組表示迷宮的路徑0 表示通道， 1 表示墻壁；2) 創(chuàng)立一個(gè)棧， 用來存儲“當(dāng)前路徑 ，即“在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置。2. 邏輯構(gòu)造存儲構(gòu)造1) 創(chuàng)立一個(gè) Int 類型的二維數(shù)組 int mazen1n2, 用來存放 0 和 1 0 表示通道，1 表示墻壁；2) 創(chuàng)立一個(gè)構(gòu)造體用來儲存數(shù)組信息構(gòu)造體：typedef struct/ 迷宮內(nèi)部設(shè)置int shu1616;int row;int col;Maze;創(chuàng)造一個(gè)鏈棧

4、struct nodeint row;int col;struct node *next;專業(yè)資料整理WORD格式三、算法設(shè)計(jì)首先，創(chuàng)立數(shù)組的大小，此數(shù)組大小要求用戶自己輸入。具體算法：printf(" 輸入迷宮的形狀!n");scanf("%d%d",&x,&y);Maze m;CreatInit(&m,x,y);函數(shù)：void CreatInit(Maze *m,int x,int y)/創(chuàng)立迷宮printf("please input number:n");int i,j;for(i=0;i<=x;

5、i+)for(j=0;j<=y;j+)m->shuij = 2;for(i=1;i<=x;i+)for(j=1;j<=y;j+)scanf("%d",&m->shuij);m->row = x;m->col = y;其中的 0 和 1 分別是表示通路和障礙，定義的數(shù)組其實(shí)就是迷宮的設(shè)計(jì)圖其次，產(chǎn)生迷宮，算法：for(i=1;i<=x;i+)for(j=1;j<=y;j+)printf("%dt",m.shuij);printf("n");最后， 迷宮尋路，在尋路的時(shí)候，我們

6、應(yīng)從輸入的入口位置進(jìn)入迷宮， 當(dāng)迷宮的入口處有障礙或者出口被堵， 再或者沒有通路時(shí)整個(gè)程序完畢， 并輸出迷宮無解的提示。 如果迷宮求解過程中沒有出現(xiàn)無解情況， 那么在求解的過程中， 會輸出迷宮的通路路徑， 并且輸出坐標(biāo)值，讓使用者更清楚路徑的走法。 在尋路的過程中， 每走過一個(gè)格， 那個(gè)格得知就會被賦值為 -1，用來標(biāo)記此處已走過， 免去了來來回回的重走， 以免出現(xiàn)死循環(huán)， 這樣程序就能從入口進(jìn)入到迷宮當(dāng)中。如果在迷宮當(dāng)中沒有通路的話， 可以完畢循環(huán)輸出“迷宮無解！ ，那么當(dāng)迷宮如果出現(xiàn)有解時(shí)， 就會輸出路徑。 這樣就簡單的實(shí)現(xiàn)了，有解無解的輸出。從而實(shí)現(xiàn)了要求的程序！代碼如下：專業(yè)資料整理W

7、ORD格式while(x1 >= 1 && x1 <= x) | (y1 >= 1 && y1<= y)專業(yè)資料整理WORD格式if(x1 = x2 && y1 = y2)break;if(m.shux1y1+1 = 0 )y1=y1+1;push(x1,y1);m.shux1y1 = -1;continue;if(m.shux1-1y1=0 )x1=x1-1;push(x1,y1);m.shux1y1 = -1;continue;if(m.shux1y1-1=0 )y1=y1-1;push(x1,y1);m.shux1y

8、1= -1;continue;if(m.shux1+1y1=0 )x1=x1+1;push(x1,y1);m.shux1y1= -1;continue;pop();if(p->next=NULL)break;x1=p->row;y1=p->col;if(x1 = x2 && y1 = y2)專業(yè)資料整理WORD格式while(p->next != NULL)專業(yè)資料整理WORD格式printf("%d %dn",p->row,p->col);pop();elseprintf("No Answer !")

9、;其中要尋求所有的通路，在這里那么使用了一個(gè)while 循環(huán)，這樣可以找到所有的通路。圖解分析：整體流程圖：開場輸入數(shù)據(jù)是否操作判定開場專業(yè)資料整理WORD格式迷宮內(nèi)部操作流程圖：專業(yè)資料整理WORD格式開場數(shù)據(jù)否方向是數(shù)據(jù)入棧完畢四、調(diào)試分析第一個(gè)問題，在剛開場的調(diào)試過程中，我們遇到了，無法判斷走過的路程，從而出現(xiàn)了死循環(huán)，導(dǎo)致程序不能正常進(jìn)展，但是經(jīng)過我們的討論，我們想出用標(biāo)記的方法來解決，也就是讓走過的路程全給標(biāo)示了，這樣就不會再走重復(fù)的路。第二個(gè)問題， 就是性用菜單來實(shí)現(xiàn)操作，那樣程序的操作性就會更強(qiáng)，所以我們就要把所有的方法， 給寫成一個(gè)個(gè)的函數(shù)來調(diào)用，這樣就遇到了參量傳遞的問題，但

10、是經(jīng)過我們的參考以及從書本上的實(shí)例， 我們慢慢地更深的了解到了參量傳遞的應(yīng)用，那么這個(gè)問題也就迎刃而解了。從此我們實(shí)現(xiàn)了菜單操作！專業(yè)資料整理WORD格式五、程序?qū)崿F(xiàn)及測試運(yùn)行界面：開場界面專業(yè)資料整理WORD格式六、體會及缺乏之處通過此次課程設(shè)計(jì)，是我對于數(shù)據(jù)構(gòu)造有了更深的了解，更新的認(rèn)識。數(shù)據(jù)構(gòu)造是一門重要的課程， 只有數(shù)據(jù)構(gòu)造學(xué)得扎實(shí)了，才能對于計(jì)算機(jī)有更深的應(yīng)用，所以學(xué)好數(shù)據(jù)構(gòu)造是很重要的。 經(jīng)過兩周的上機(jī)設(shè)計(jì)，我實(shí)現(xiàn)了簡單的迷宮求解， 能夠簡單的實(shí)現(xiàn)求解過程。但是還存在著缺乏之處，本程序不能循環(huán)執(zhí)行，只能執(zhí)行一次。有待改進(jìn)！專業(yè)資料整理WORD格式七、參考文獻(xiàn)1、" 數(shù)據(jù)構(gòu)

11、造 (c 語言版 ) "嚴(yán)蔚敏清華大學(xué)2、" 數(shù)據(jù)構(gòu)造實(shí)驗(yàn)教程"李業(yè)麗、X良斌" 數(shù)據(jù)構(gòu)造"高教3、" 數(shù)據(jù)構(gòu)造習(xí)題"李春保清華大學(xué)4、" 數(shù)據(jù)構(gòu)造習(xí)題"嚴(yán)蔚敏清華大學(xué)5、" C 語言與數(shù)據(jù)構(gòu)造"王立柱清華大學(xué)6、" 數(shù)據(jù)構(gòu)造 (C 語言篇 )習(xí)題與解析"李春保 清華大學(xué)。八、源代碼#include <stdio.h>#include <stdlib.h>typedef struct/ 迷宮內(nèi)部設(shè)置int shu1616;int row;in

12、t col;Maze;struct nodeint row;int col;struct node *next;struct node *p;void push(int x1,int y1)struct node *a;a=(struct node *)malloc(sizeof(struct node);a->row=x1;a->col=y1;a->next=p;p=a;專業(yè)資料整理WORD格式void pop(void)專業(yè)資料整理WORD格式struct node *q;q=p;p=p->next;free(q);void CreatInit(Maze *m,in

13、t x,int y)/創(chuàng)立迷宮printf("please input number:n");int i,j;for(i=0;i<=x;i+)for(j=0;j<=y;j+)m->shuij = 2;for(i=1;i<=x;i+)for(j=1;j<=y;j+)scanf("%d",&m->shuij);m->row = x;m->col = y;void menu()printf("n*n");專業(yè)資料整理WORD格式printf("printf("歡迎進(jìn)

14、入迷宮1、進(jìn)入迷宮n");n");專業(yè)資料整理WORD格式printf("2、退出n");專業(yè)資料整理WORD格式int main(void)int t;int x,y;int x1,y1;int x2,y2;int i,j;while(1)menu();printf(" 請選擇 :");專業(yè)資料整理WORD格式scanf("%d",&t);if(t = 2)break;printf(" 輸入迷宮的形狀!n");scanf("%d%d",&x,&y);

15、Maze m;CreatInit(&m,x,y);for(i=1;i<=x;i+)for(j=1;j<=y;j+)printf("%dt",m.shuij);printf("n");printf(" 輸入入口位置:");scanf("%d%d",&x1,&y1);printf(" 輸入出口的位置:");scanf("%d%d",&x2,&y2);p=(struct node *)malloc(sizeof(struct no

16、de);p->row=0;p->col=0;p->next=NULL;push(x1,y1);while(x1 >= 1 && x1 <= x) | (y1 >= 1 && y1<= y)if(x1 = x2 && y1 = y2)break;if(m.shux1y1+1 = 0 )y1=y1+1;push(x1,y1);m.shux1y1 = -1;continue;if(m.shux1-1y1=0 )x1=x1-1;push(x1,y1);m.shux1y1 = -1;continue;if(m.shux1y1-1=0 )專業(yè)資料整理WORD格式y(tǒng)1=y1-1;push(x1,y1);m.shux1y1= -1;continue;if(m.shux1+1y1=0 )x1