數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、院 系： 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 班 級(jí)： 軟件 11-1 班 姓 名： 李慧玲李慧玲 學(xué) 號(hào)： 20111702010114 指導(dǎo)教師： 薛京麗 2012 年 12 月 24 日程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)任務(wù)書(shū)程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)任務(wù)書(shū)一、 題目：迷宮 二、 設(shè)計(jì)要求1 自己制定工作計(jì)劃。2 分時(shí)間按規(guī)定工作量敲好代碼，認(rèn)真理解，熟練運(yùn)用。 3 數(shù)據(jù)必須存盤(pán)，數(shù)據(jù)量必須足夠多，并采用真是數(shù)據(jù)。三、 課程設(shè)計(jì)工作計(jì)劃2012 年 12 月 19 上午由薛京麗指導(dǎo)教師講課，學(xué)生準(zhǔn)備文獻(xiàn)資料；2012 年 12 月 19 下午日各設(shè)計(jì)小組進(jìn)行總體方案設(shè)計(jì)和任務(wù)分工；2012 年 12 月 20 日下午201

2、2 年 12 月 28 日 完成自己承擔(dān)的程序模塊并通過(guò)獨(dú)立編譯。2012 年 12 月 26 日，驗(yàn)收，學(xué)生撰寫(xiě)課程設(shè)計(jì)報(bào)告。指導(dǎo)教師簽字： 程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)指導(dǎo)教師評(píng)語(yǔ)指導(dǎo)教師評(píng)語(yǔ)：表現(xiàn)成績(jī)： 驗(yàn)收成績(jī)： 報(bào)告成績(jī)： 總成績(jī)： 指導(dǎo)教師簽字： 2013 年 1 月 日 1目目 錄錄目目 錄錄.11 程序的功能設(shè)計(jì)程序的功能設(shè)計(jì).12 程序的數(shù)據(jù)設(shè)計(jì)程序的數(shù)據(jù)設(shè)計(jì).22.1 概要設(shè)計(jì).22.1.1 節(jié)點(diǎn)類型和指針類型.23 程序的函數(shù)設(shè)計(jì)程序的函數(shù)設(shè)計(jì).33.1 迷宮操作.43.2 菜單選擇.64 4 函數(shù)編程及調(diào)試函數(shù)編程及調(diào)試.85 5 整體調(diào)試整體調(diào)試.126 總結(jié)總結(jié).19參考文

3、獻(xiàn)參考文獻(xiàn).20 21 需求分析需求分析1.1 設(shè)計(jì)任務(wù)設(shè)計(jì)任務(wù)以一個(gè) mn 的長(zhǎng)方陣表示迷宮，0 和 1 分別表示迷宮中的道路和障礙，設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。1.2 任務(wù)分析任務(wù)分析1.建立迷宮迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用 0 表示通路，用 1 表示障礙，這樣迷宮就可以用 0、1 矩陣來(lái)描述。2.存儲(chǔ)迷宮迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組 mazem+2n+2（注：其中 m，n 分別表示迷宮

4、最大行、列數(shù)，本程序 m、n 的缺省值為 39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大?。?，然后用它的前 m 行 n 列來(lái)存放元素，即可得到一個(gè) mn 的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。3搜索路徑首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為 2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一

5、個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。0 0 1 0 1 1 0 0 1 0以矩陣 1 0 0 0 1 為例，來(lái)示范一下： 3 0 0 1 0 0首先，將位置（0,0） （序號(hào) 0）放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開(kāi)始搜索，其標(biāo)記變?yōu)?2，由于其只有一個(gè)非障礙位置，所以接下來(lái)移動(dòng)到(0,1)（序號(hào) 1） ，其前節(jié)點(diǎn)序號(hào)為 0，標(biāo)記變?yōu)?2，然后從(0,1)移動(dòng)到(1,1)（序號(hào) 2） ，放入隊(duì)列中，其前節(jié)點(diǎn)序號(hào)為 1，(1,1)存在(1，2)（序號(hào) 3） 、(2，1)（序號(hào)4

6、）兩個(gè)可移動(dòng)位置，其前節(jié)點(diǎn)序號(hào)均為 2.對(duì)于每一個(gè)非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。如下表所示： 0 1234 5678910(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)-10122345679由此可以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 11 程序的功能設(shè)計(jì)程序的功能設(shè)計(jì)1.手動(dòng)2.自動(dòng)3.退出switch1,2,3是否為通路123退出結(jié)束輸入m，

7、n輸入m，n手動(dòng)輸入數(shù)字迷宮字符迷宮自動(dòng)生成下下左左上上右右迷宮無(wú)解迷宮有解輸出路徑打印通路歡迎界面 22 程序的數(shù)據(jù)設(shè)計(jì)程序的數(shù)據(jù)設(shè)計(jì)2.1 概要設(shè)計(jì)構(gòu)建一個(gè)二維數(shù)組 mazem+2n+2用于存儲(chǔ)迷宮矩陣自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組 mazem+2n+2賦值構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑建立迷宮節(jié)點(diǎn) struct point,用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問(wèn)情況實(shí)現(xiàn)搜索算法屏幕上顯示操作菜單2.1.1 節(jié)點(diǎn)類型和指針類型迷宮矩陣類型：int mazem+2n+2;為方便操作使其為全局變量迷宮中節(jié)點(diǎn)類型及隊(duì)列類型：struct pointint row,col,predecessor que51

8、2 33 程序的函數(shù)設(shè)計(jì)程序的函數(shù)設(shè)計(jì)主函數(shù) main()手動(dòng)生成迷宮函數(shù) shoudong_maze()自動(dòng)生成迷宮函數(shù) zidong_maze()將迷宮打印成圖形 print_maze()打印迷宮路徑 (若存在路徑) result_maze()入隊(duì) enqueue()出隊(duì) dequeue()判斷隊(duì)列是否為空 is_empty()訪問(wèn)節(jié)點(diǎn) visit()搜索迷宮路徑 mgpath() 43.1 迷宮操作(1)手動(dòng)生成迷宮void shoudong_maze(int m,int n)定義 i,j 為循環(huán)變量for(i=m)for(j=n)輸入 mazeij的值(2)自動(dòng)生成迷宮void zid

9、ong_maze(int m,int n)定義 i,j 為循環(huán)變量for(i=m)for(j=n) mazeij=rand()%2 /由于 rand()產(chǎn)生的隨機(jī)數(shù)是從 0 到rand_max,rand_max 是定義在 stdlib.h 中的,其值至少為 32767),要產(chǎn)生從 x 到 y 的數(shù),只需要這樣寫(xiě)：k=rand()%(y-x+1)+x(3)打印迷宮圖形void print_maze(int m,int n) 用 i,j 循環(huán)變量，將 mazeij輸出 、 (4)打印迷宮路徑void result_maze(int m,int n) 用 i,j 循環(huán)變量，將 mazeij輸出 、

10、5(5)搜索迷宮路徑 宮中隊(duì)列入隊(duì)操作void enqueue(struct point p)將 p 放入隊(duì)尾，tail+ 宮中隊(duì)列出隊(duì)操作struct point dequeue(struct point p)head+,返回 quehead-1 斷隊(duì)列是否為空int is_empty()返回 head=tail 的值，當(dāng)隊(duì)列為空時(shí)，返回 0 問(wèn)迷宮矩陣中節(jié)點(diǎn)void visit(int row,int col,int maze4141)建立新的隊(duì)列節(jié)點(diǎn) visit_point,將其值分別賦為 row,col,head-1,mazerowcol=2,表示該節(jié)點(diǎn)以被訪問(wèn)過(guò);調(diào)用 enqueue

11、(visit_point),將該節(jié)點(diǎn)入隊(duì) 徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點(diǎn)為 struct point p=0,0,-1，從 maze00開(kāi)始訪問(wèn)。如果入口處即為障礙，則此迷宮無(wú)解，返回 0 ，程序結(jié)束。否則訪問(wèn)入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)標(biāo)記為訪問(wèn)過(guò) mazep.rowp.col=2,調(diào)用函數(shù) enqueue(p)將該節(jié)點(diǎn)入隊(duì)。判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，則運(yùn)行以下操作：調(diào)用 dequeue()函數(shù)，將隊(duì)頭元素返回給 p，如果 p.row=m-1 且 p.col=n-1,即到達(dá)出口節(jié)點(diǎn)，即找到了路徑，結(jié)束如果 p.col+1n 且

12、mazep.rowp.col+1=0,說(shuō)明未到迷宮右邊界，且其右 6方有通路,則 visit(p.row,p.col+1,maze),將右邊節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)如果 p.row+10 且 mazep.rowp.col-1=0,說(shuō)明未到迷宮左邊界，且其左方有通路,則 visit(p.row,p.col-1,maze),將左方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)如果 p.row-10 且 mazep.row-1p.col=0,說(shuō)明未到迷宮上邊界，且其上方有通路,則 visit(p.row,p.col+1,maze),將上方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)訪問(wèn)到出口(找到路徑)即 p.row=m-1 且 p.col=n-1,則逆序?qū)?/p>

13、路徑標(biāo)記為 3即 mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3;最后將路徑圖形打印出來(lái)。3.2 菜單選擇 while(cycle!=(-1) 手動(dòng)生成迷宮 請(qǐng)按：1 自動(dòng)生成迷宮 請(qǐng)按：2 退出 請(qǐng)按：3 scanf(%d,&i); switch(i) case 1：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); 7 if(x!=0) result_maze(m,n);ca

14、se 2 ：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入 zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(x!=0) result_maze(m,n);case 3：cycle=(-1); break;（注：具體源代碼見(jiàn)附錄。 ） 84 4 函數(shù)編程及調(diào)試函數(shù)編程及調(diào)試在調(diào)試過(guò)程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過(guò)算法比較，改用此算法。1. 本程序的運(yùn)行環(huán)境為 dos 操作系統(tǒng)，執(zhí)行文件為：migong_1.exe。2. 進(jìn)入演示程序后即顯示文本方式的用戶界面：3. 選擇相應(yīng)的菜單，按提示執(zhí)行程

15、序。程序相關(guān)信息程序操作菜單操作提示信息 9測(cè)試結(jié)果測(cè)試結(jié)果手動(dòng)輸入迷宮 106.2 自動(dòng)生成迷宮 11 125 5 整體調(diào)試整體調(diào)試#includestdlib.h#includestdio.h#define n 39#define m 39int x;int mazen+2m+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf(nn);printf(請(qǐng)按行輸入迷宮，0 表示通路，1 表示障礙:nn);for(i=0;im;

16、i+)for(j=0;jn;j+)scanf(%d,&mazeij);void zidong_maze(int m,int n)int i,j;printf(n 迷宮生成中nn);system(pause);for(i=0;im;i+)for(j=0;jn;j+) 13mazeij=rand()%2;/由于 rand()產(chǎn)生的隨機(jī)數(shù)是從 0 到 rand_max/rand_max 是定義在 stdlib.h 中的,其值至少為 32767)/要產(chǎn)生從 x 到 y 的數(shù),只需要這樣寫(xiě)：k=rand()%(y-x+1)+x; void print_maze(int m,int n)int i,j;p

17、rintf(n 迷宮生成結(jié)果如下:nn);printf(迷宮入口n);printf();for(i=0;im;i+)printf(n);for(j=0;jn;j+) if(mazeij=0) printf();if(mazeij=1) printf();printf(迷宮出口n);void result_maze(int m,int n)int i,j;printf(迷宮通路(用表示)如下所示：nt);for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0|mazeij=2) printf(); 14if(mazeij=1) printf();if(

18、mazeij=3) printf();void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)x=1;str

19、uct point p=0,0,-1;if(mazep.rowp.col=1)printf(n=n); 15printf(此迷宮無(wú)解nn);x=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze);if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);if(p.ro

20、w-1=0)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&p.col=n-1)printf(n=n);printf(迷宮路徑為：n);printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3; 16else printf(n=n);printf(此迷宮無(wú)解！nn);x=0;return 0;void main(

21、)int i,m,n,cycle=0;while(cycle!=(-1)printf(*n);printf( 歡迎進(jìn)入迷宮求解系統(tǒng)n);printf( 設(shè)計(jì)者:李慧玲 n);printf(*n);printf( 手動(dòng)生成迷宮 請(qǐng)按：1n);printf( 自動(dòng)生成迷宮 請(qǐng)按：2n);printf( 退出 請(qǐng)按：3nn);printf(*n);printf(n);printf(請(qǐng)選擇你的操作：n);scanf(%d,&i);switch(i)case 1:printf(n 請(qǐng)輸入行數(shù)：);scanf(%d,&m); 17printf(n);printf(請(qǐng)輸入列數(shù)：);scanf(%d,&n);

22、while(m39)|(n39)printf(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請(qǐng)重新輸入：nn);printf(請(qǐng)輸入行數(shù)：);scanf(%d,&m);printf(n);printf(請(qǐng)輸入列數(shù)：);scanf(%d,&n);shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(x!=0) result_maze(m,n);printf(nnpress enter contiue!n); getchar();while(getchar()!=n);break;case 2:printf(n 請(qǐng)輸入行數(shù)：);

23、scanf(%d,&m);printf(n);printf(請(qǐng)輸入列數(shù)：);scanf(%d,&n);while(m39)|(n39)printf(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請(qǐng)重新輸入：nn);printf(請(qǐng)輸入行數(shù)：);scanf(%d,&m);printf(n);printf(請(qǐng)輸入列數(shù)：);scanf(%d,&n); 18zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(x!=0) result_maze(m,n);printf(nnpress enter contiue!n);getchar();while(getchar()!=n);break;case 3:cycle=(-1);break;default:printf(n);printf(你的輸入有誤!n);printf(npress enter contiue!n);getchar();wh