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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 迷宮問(wèn)題數(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)容1 課程設(shè)計(jì)題目迷宮問(wèn)題以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。二算法設(shè)計(jì)思想1.需求分析（1）迷宮數(shù)據(jù)用一個(gè)二維數(shù)組int maze

2、rowcol來(lái)存儲(chǔ)，在定義了迷宮的行列數(shù)后，用兩個(gè)for循環(huán)來(lái)錄入迷宮數(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(%d,%d,&end.a,&end.b);

3、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的初值，包括邊上邊緣一圈的值void maze_path(int mazerowcol,int dir42,s

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

5、;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表示無(wú)方向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) /這里表示已

6、經(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)記走過(guò)這個(gè)點(diǎn)elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=x;j=y;d=-1;d+;p

7、rintf(此迷宮無(wú)出路);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,&end.a,&end.b);printf(0為東，1為南，2為西，3為北，-1為出路n);maze_path(maze,dir,start,en

8、d);getchar();3 程序結(jié)構(gòu) main() 定義方向二維數(shù)組初始化鏈棧，并將入口，出口信息入棧是棧是否為空否當(dāng)前坐標(biāo)周圍是否有方向可以探索否是刪除棧中此步信息換個(gè)方向搜索坐標(biāo)移動(dòng)是此坐標(biāo)周圍有無(wú)障礙否迷宮無(wú)出路此坐標(biāo)信息入棧此坐標(biāo)是否為出口是棧逆置并輸出路線 結(jié)束 主程序 maze_path built_maze push_stack stack_empty pop initstack四 實(shí)驗(yàn)結(jié)果與分析1.用戶使用說(shuō)明（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)以下窗口后輸入迷宮的行列

9、數(shù)，回車；再繼續(xù)輸入迷宮的數(shù)據(jù)，1表示障礙，0表示通路；再輸入入口坐標(biāo)和出口坐標(biāo)，回車。就可以顯示出迷宮路徑。2. 測(cè)試結(jié)果（1） 輸入行列數(shù)：5,5 輸入迷宮數(shù)據(jù)為：0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 出口位置：1,1 出口位置：5,5 （2）輸入行列數(shù)：4,9 輸入迷宮數(shù)據(jù)為：0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 輸入入口坐標(biāo)：1,1 輸入出口坐標(biāo)：4,9 （3）輸入行列數(shù)：9,8 輸入迷宮數(shù)據(jù)為：0 0 1 0 0 0

10、1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 輸入入口坐標(biāo)：1,1 輸入出口坐標(biāo)：9,83. 調(diào)試分析 （1） 在剛開(kāi)始寫(xiě)完代碼后，運(yùn)行發(fā)現(xiàn)程序只能運(yùn)行簡(jiǎn)單的一條直線的迷宮，在運(yùn)行復(fù)雜的迷宮時(shí)，不會(huì)碰到死路（周圍沒(méi)有可探索的道路）就刪除坐標(biāo)往回到前坐標(biāo)換方向探索。最后我和同寢室同學(xué)一起探討才發(fā)現(xiàn)程序中探索過(guò)的坐標(biāo)沒(méi)有標(biāo)記，后來(lái)我將mazexy=2將它作為標(biāo)記才解決問(wèn)題。（2） 程

11、序中主要的兩個(gè)算法：initmaze和maze_path的時(shí)間復(fù)雜度為O(m*n)，空間復(fù)雜度也為O(m*n)。 五 總結(jié)（收獲與體會(huì)）通過(guò)這段時(shí)間的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)和C語(yǔ)言的理解更加深刻了。在實(shí)踐過(guò)程中我遇到了不少問(wèn)題，但通過(guò)閱讀相關(guān)書(shū)籍、求問(wèn)老師同學(xué)，最終也解決了不少問(wèn)題。這些問(wèn)題也給了我相當(dāng)多的收獲。但通過(guò)這段時(shí)間的學(xué)習(xí)和解決的這么多問(wèn)題，我覺(jué)得我對(duì)這些知識(shí)的掌握比以前好了許多。求解迷宮問(wèn)題用的是“窮舉求解”的方法。從入口出發(fā)，沿著某一方向探索（這里我選擇優(yōu)先探索的是東面），若無(wú)障礙，繼續(xù)往前走，否則眼原路返回，換個(gè)方向繼續(xù)探索，直到將所有可能的通道都探索完為止。所以需要用棧來(lái)保存

12、從入口到當(dāng)前位置的路徑。但因?yàn)橹霸趯W(xué)習(xí)棧這一節(jié)的時(shí)候沒(méi)學(xué)扎實(shí)，現(xiàn)在有很多知識(shí)都忘了。所以在編寫(xiě)求解迷宮路徑的算法的時(shí)候我覺(jué)得有些困難，后來(lái)經(jīng)過(guò)一步步分析和借鑒書(shū)上的窮舉法才把算法寫(xiě)出來(lái)。但我還是除了許多錯(cuò)誤，其中大部分是語(yǔ)法錯(cuò)誤，這些最后都還是一一解決了。而且除了加深了棧的學(xué)習(xí)，我還復(fù)習(xí)了以前大一學(xué)的C語(yǔ)言中的二維數(shù)組和for，while循環(huán)。這次課程設(shè)計(jì)不僅是讓我們加深了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的是培養(yǎng)我們解決實(shí)際問(wèn)題的能力，能在不斷地遇到問(wèn)題，不斷地解決問(wèn)題的過(guò)程中培養(yǎng)自己的專業(yè)思維。所以我相信通過(guò)這次課程設(shè)計(jì)我們能夠提升自己的分析、設(shè)計(jì)程序和編寫(xiě)程序的能力。六 源程序#includ

13、e#include#define row 100#define col 100struct 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,elem

14、ent E)SLinkstack P;P=(SLinkstack)malloc(sizeof(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)隔開(kāi)）：);scanf(%d,%d,&m,&n

15、);printf(請(qǐng)輸入迷宮各行各列的數(shù)據(jù)（用空格隔開(kāi)）：n);for(x=0;xm+2;x+)for(y=0;yn+2;y+)if(x=0|x=m+1|y=0|y=n+1)/迷宮周圍加墻壁mazexy=1;elsescanf(%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,

16、d;int x,y;element elem,E;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表示無(wú)方向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

17、&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(%d,%d,%d)n,E.i,E.j,E.d);return;if(mazexy=0)mazexy=2; /標(biāo)記走過(guò)這個(gè)點(diǎn)elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=x;j=y;d=-1;d+;printf(此迷宮無(wú)出路);void main()int mazerowcol;struct mark start,end; /出入口的坐標(biāo)int dir42=0,1,1