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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：迷宮問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 班 級(jí)：計(jì)科 152學(xué) 號(hào)：19215225姓 名：徐昌港南京農(nóng)業(yè)大學(xué)計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告內(nèi)容一課程設(shè)計(jì)題目迷宮問題以一個(gè) m*n的長方陣表示迷宮， 0和 1分別表示迷宮中的通路和障 礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮， 求出一條從入口到出口的通路， 或得出沒有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類 型，然后編寫一個(gè)求解迷宮的非遞歸程序。 求得的通路以三元組 （i ，j ， d）的形式輸出。其中：（i，j ）指示迷宮中的一個(gè)坐標(biāo)， d 表示走到下 一坐標(biāo)的方向。二算法設(shè)計(jì)思想1. 需求分析（ 1）迷宮數(shù)據(jù)用一個(gè)二維數(shù)

2、組 int mazerowcol 來存儲(chǔ)，在定 義了迷宮的行列數(shù)后，用兩個(gè) for 循環(huán)來錄入迷宮數(shù)據(jù)，并在迷宮周圍 加墻壁。（2）迷宮的入口位置和出口位置可以由用戶自己決定。2. 概要設(shè)計(jì)（ 1）主程序模塊：void main（）int mazerowcol;struct mark start,end; /出入口的坐標(biāo)int dir42=0,1,1,0,0,-1,-1,0;/ 方向，依次是東西南北built_maze（maze）;printf（ 請(qǐng)輸入入口的橫縱坐標(biāo)： ）; scanf（%d,%d,&start.a,&start.b）;printf（ 請(qǐng)輸入出口的橫縱坐標(biāo)： ）;scanf（

3、%d,%d,&end.a,&end.b）;printf（0 為東， 1為南， 2為西， 3為北， -1為出路 n）; maze_path（maze,dir,start,end）;getchar（）;（ 2）棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型 （3）迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型，建立迷宮，找出迷宮 的一條通路3. 詳細(xì)設(shè)計(jì)（ 1）坐標(biāo)位置類型struct markint a,b; /迷宮 a行b列為位置;（2）迷宮類型void built_maze（int mazerowcol）/ 按照用戶輸入的 row行和 col 列的二維數(shù)組（元素值為 0和1）/ 設(shè)置迷宮 maze的初值，包括邊上邊緣一圈的值voi

4、d maze_path（int mazerowcol,int dir42,structmark start,struct mark end）/ 求解迷宮 maze中，從入口 start 到出口 end的一條路徑，/ 若存在，則返回 TRUE；否則返回 FALSE（3）棧類型struct elementint i,j,d; /坐標(biāo)與方向;typedef struct Linkstack element elem;struct Linkstack *next;*SLinkstack;4. 求迷宮路徑為偽碼算法void maze_path(int mazerowcol,int dir42,struc

5、t mark start,struct mark end)int i,j,d;int x,y;element elem,E;SLinkstack L1,L2;initstack(L1);initstack(L2); mazestart.astart.b=2; elem.i=start.a;elem.j=start.b;elem.d=-1; /d=-1 表示無方向 push_stack(L1,elem);while(!stack_empty(L1)pop(L1,elem);i=elem.i;j=elem.j;d=elem.d+1; / 下一個(gè)方向 while(d4) / 探索東西南北各個(gè)方向 x

6、=i+dird0;y=j+dird1;if(x=end.a&y=end.b&mazexy=0) / 這 里 表示已經(jīng)到了出口elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem); elem.i=x; elem.j=y;elem.d=-1;push_stack(L1,elem);while(L1) / 逆置序列，輸出迷宮路徑pop(L1,E);push_stack(L2,E);while(L2)pop(L2,E); printf(%3d%3d%3dn,E.i,E.j,E.d);return;if(mazexy=0) mazexy=2; / 標(biāo)記走過這個(gè)點(diǎn)

7、elem.i=i;elem.j=j;elem.d=d; push_stack(L1,elem); i=x;j=y;d=-1;d+;printf( 此迷宮無出路 );5. 主函數(shù)和其他函數(shù)的偽碼算法void main()int mazerowcol;struct mark start,end; /出入口的坐標(biāo)int dir42=0,1,1,0,0,-1,-1,0;built_maze(maze); / 方向，依次是東西南北 printf( 請(qǐng)輸入入口的橫縱坐標(biāo)： ); scanf(%d,%d,&start.a,&start.b);printf( 請(qǐng)輸入出口的橫縱坐標(biāo)： );scanf(%d,%d

8、,&end.a,&end.b);printf(0 為東， 1為南， 2為西， 3為北， -1為出路 n); maze_path(maze,dir,start,end);getchar();三 程序結(jié)構(gòu)主程序四 實(shí)驗(yàn)結(jié)果與分析1. 用戶使用說明（ 1） 本 程 序的 運(yùn) 行 環(huán)境 為 debug運(yùn) 行 環(huán) 境 ， 執(zhí) 行 文件 為 ： 19215225.cpp ；（2）用VC+運(yùn)行文件后出現(xiàn)以下窗口：點(diǎn)擊 運(yùn)行程序（3）出現(xiàn)以下窗口后輸入迷宮的行列數(shù)，回車；再繼續(xù)輸入迷宮的數(shù)據(jù)， 1表示障礙， 0 表示通路； 再輸入入口坐標(biāo)和出口坐標(biāo)， 回車。就可以顯示出迷宮路徑。2. 測(cè)試結(jié)果1）輸入行列數(shù)：

9、 5,5輸入迷宮數(shù)據(jù)為： 0 0 0 1 11 1 0 1 10 0 0 1 0 0 1 1 0 0 0 0 0 0 0出口位置： 1,1出口位置： 5,52）輸入行列數(shù)： 4,9輸入迷宮數(shù)據(jù)為： 0 0 0 0 0 0 1 0 00 1 0 0 0 1 0 0 00 0 1 1 1 0 0 1 10 0 1 1 1 0 1 0 0 輸入入口坐標(biāo)： 1,1 輸入出口坐標(biāo)： 4,93）輸入行列數(shù)： 9,8輸入迷宮數(shù)據(jù)為： 0 0 1 0 0 0 1 00 0 1 0 0 0 1 0 0 0 0 0 1 1 0 10 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0

10、1 0 10 1 1 1 1 0 0 11 1 0 0 0 1 0 11 1 0 0 0 0 0 0輸入入口坐標(biāo)： 1,1輸入出口坐標(biāo)： 9,83. 調(diào)試分析（1）在剛開始寫完代碼后，運(yùn)行發(fā)現(xiàn)程序只能運(yùn)行簡單的一條 直線的迷宮，在運(yùn)行復(fù)雜的迷宮時(shí)，不會(huì)碰到死路（周圍沒有可探 索的道路）就刪除坐標(biāo)往回到前坐標(biāo)換方向探索。最后我和同寢室 同學(xué)一起探討才發(fā)現(xiàn)程序中探索過的坐標(biāo)沒有標(biāo)記，后來我將 mazexy=2 將它作為標(biāo)記才解決問題。（2）程序中主要的兩個(gè)算法： initmaze 和 maze_path的時(shí)間復(fù)雜 度為 O（m*n），空間復(fù)雜度也為 O（m*n）。五 總結(jié)（收獲與體會(huì)）通過這段時(shí)間

11、的課程設(shè)計(jì)， 我對(duì)數(shù)據(jù)結(jié)構(gòu)和 C語言的理解更加深刻 了。在實(shí)踐過程中我遇到了不少問題，但通過閱讀相關(guān)書籍、求問老師 同學(xué)，最終也解決了不少問題。這些問題也給了我相當(dāng)多的收獲。但通 過這段時(shí)間的學(xué)習(xí)和解決的這么多問題， 我覺得我對(duì)這些知識(shí)的掌握比 以前好了許多。求解迷宮問題用的是“窮舉求解”的方法。從入口出發(fā)，沿著某一 方向探索(這里我選擇優(yōu)先探索的是東面)，若無障礙，繼續(xù)往前走， 否則眼原路返回，換個(gè)方向繼續(xù)探索，直到將所有可能的通道都探索完 為止。所以需要用棧來保存從入口到當(dāng)前位置的路徑。但因?yàn)橹霸趯W(xué) 習(xí)棧這一節(jié)的時(shí)候沒學(xué)扎實(shí)，現(xiàn)在有很多知識(shí)都忘了。所以在編寫求解 迷宮路徑的算法的時(shí)候我覺

12、得有些困難， 后來經(jīng)過一步步分析和借鑒書 上的窮舉法才把算法寫出來。但我還是除了許多錯(cuò)誤，其中大部分是語 法錯(cuò)誤，這些最后都還是一一解決了。而且除了加深了棧的學(xué)習(xí)，我還 復(fù)習(xí)了以前大一學(xué)的 C語言中的二維數(shù)組和 for ，while 循環(huán)。這次課程設(shè)計(jì)不僅是讓我們加深了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)， 更重要 的是培養(yǎng)我們解決實(shí)際問題的能力，能在不斷地遇到問題，不斷地解決 問題的過程中培養(yǎng)自己的專業(yè)思維。 所以我相信通過這次課程設(shè)計(jì)我們 能夠提升自己的分析、設(shè)計(jì)程序和編寫程序的能力。六 源程序 #include #include #define row 100 #define col 100 struc

13、t markint a,b;struct elementint i,j,d; / 坐標(biāo)與方向;typedef struct Linkstackelement elem;struct Linkstack *next;*SLinkstack;int initstack(SLinkstack &L)L=NULL;return 1;int stack_empty(SLinkstack L)if(L=NULL)return 1;elsereturn 0;int push_stack(SLinkstack &L,element E)SLinkstack P;P=(SLinkstack)malloc(siz

14、eof(Linkstack);P-elem=E;P-next=L;L=P;return 1;int pop(SLinkstack &L,element &E)SLinkstack P;if(!stack_empty(L)E=L-elem;P=L;L=L-next;free(P);return 1;elsereturn 0;建立迷宮void built_maze(int mazerowcol)/int x,y; int m,n; printf( 請(qǐng)輸入迷宮的行列數(shù)(用逗號(hào)隔開)： ); scanf(%d,%d,&m,&n);printf( 請(qǐng)輸入迷宮各行各列的數(shù)據(jù)(用空格隔開)： n); for

15、(x=0;xm+2;x+)for(y=0;yn+2;y+) if(x=0|x=m+1|y=0|y=n+1)/ 迷宮周圍加墻壁 mazexy=1;else scanf(%d,&mazexy);printf( 迷宮生成中 , n);printf( 迷宮顯示為： n);for(x=0;xm+2;x+)for(y=0;yn+2;y+) printf(%3d,mazexy);printf(n);void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int x,y;element elem,E

16、;SLinkstack L1,L2;initstack(L1);initstack(L2);mazestart.astart.b=2; / 標(biāo)記起點(diǎn)坐標(biāo) elem.i=start.a;elem.j=start.b;elem.d=-1; /d=-1 表示無方向 push_stack(L1,elem);while(!stack_empty(L1)pop(L1,elem);i=elem.i;j=elem.j;d=elem.d+1; / 下一個(gè)方向while(d4) / 探索東西南北各個(gè)方向x=i+dird0;y=j+dird1;if(x=end.a&y=end.b&mazexy=0) / 這里表示已

17、經(jīng)到了出口 elem.i=i; elem.j=j; elem.d=d;push_stack(L1,elem);elem.i=x;elem.j=y;elem.d=-1;push_stack(L1,elem);while(L1) / 逆置序列，輸出迷宮路徑 pop(L1,E); push_stack(L2,E); while(L2) pop(L2,E); printf(%d,%d,%d)n,E.i,E.j,E.d); return;if(mazexy=0)標(biāo)記走過這個(gè)點(diǎn)mazexy=2; / elem.i=i; elem.j=j; elem.d=d;push_stack(L1,elem);i=x;j=y; d=-1;d+;printf( 此迷宮無出路 );void main()int mazerowcol;struct mark start,end; / 出入口的坐標(biāo)方向，依次是int dir42=0,1,1,0,0,-1,-1,0; /