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

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

2、col來存儲(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(請輸入入口的橫縱坐標(biāo)：);scanf(%d,%d,&start.a,&start.b);printf(請輸入出口的橫縱坐標(biāo)：);scanf(%d,%d,&end.a,&end.b);printf(

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

4、 mark end)/求解迷宮maze中，從入口start到出口end的一條路徑，/假設(shè)存在，則返回TRUE；否則返回FALSE3棧類型struct elementint i,j,d; /坐標(biāo)與方向;typedef struct Linkstackelement elem;struct Linkstack *ne*t;*SLinkstack;求迷宮路徑為偽碼算法void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int *,y;element elem,E;SLinkstack

5、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è)方向*=i+dird0;y=j+dird1;if(*=end.a&y=end.b&maze*y=0) /這里表示已經(jīng)到了出口elem.i=i;elem.j=j;elem

6、.d=d;push_stack(L1,elem);elem.i=*;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(maze*y=0)maze*y=2; /標(biāo)記走過這個(gè)點(diǎn)elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);i=*;j=y;d=-1;d+;printf(此迷宮無出路);主函數(shù)和其他函數(shù)的偽碼算法

7、void main()int mazerowcol;struct mark start,end; /出入口的坐標(biāo)int dir42=0,1,1,0,0,-1,-1,0; built_maze(maze); /方向，依次是東西南北printf(請輸入入口的橫縱坐標(biāo)：);scanf(%d,%d,&start.a,&start.b);printf(請輸入出口的橫縱坐標(biāo)：);scanf(%d,%d,&end.a,&end.b);printf(0為東，1為南，2為西，3為北，-1為出路n);maze_path(maze,dir,start,end);getchar();程序構(gòu)造 main() 定義方向二

8、維數(shù)組初始化鏈棧，并將入口，出口信息入棧是棧是否為空否當(dāng)前坐標(biāo)周圍是否有方向可以探索否是刪除棧中此步信息換個(gè)方向搜索坐標(biāo)移動(dòng)是此坐標(biāo)周圍有無障礙否迷宮無出路此坐標(biāo)信息入棧此坐標(biāo)是否為出口是棧逆置并輸出路線 完畢 主程序 maze_path built_maze push_stack stack_empty pop initstack四 實(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)行程序出現(xiàn)以下窗口后輸入迷宮的行列數(shù)，回車；再繼續(xù)輸入迷宮的數(shù)據(jù)，1表示障礙，0表示通路；再輸入入口坐標(biāo)和出口坐標(biāo)

9、，回車。就可以顯示出迷宮路徑。測試結(jié)果輸入行列數(shù)：5,5 輸入迷宮數(shù)據(jù)為：0 0 0 1 1 1 1 0 1 10 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 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

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

11、通過這段時(shí)間的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)構(gòu)造和C語言的理解更加深刻了。在實(shí)踐過程中我遇到了不少問題，但通過閱讀相關(guān)書籍、求問教師同學(xué)，最終也解決了不少問題。這些問題也給了我相當(dāng)多的收獲。但通過這段時(shí)間的學(xué)習(xí)和解決的這么多問題，我覺得我對(duì)這些知識(shí)的掌握比以前好了許多。求解迷宮問題用的是“窮舉求解的方法。從入口出發(fā)，沿著*一方向探索這里我選擇優(yōu)先探索的是東面，假設(shè)無障礙，繼續(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ù)構(gòu)造的理論知識(shí)，更重要的是培養(yǎng)我們解決實(shí)際問題的能力，能在不斷地遇到問題，不斷地解決問題的過程中培養(yǎng)自己的專業(yè)思維。所以我相信通過這次課程設(shè)計(jì)我們能夠提升自己的分析、設(shè)計(jì)程序和編寫程序的能力。六 源程序*include*include*define row 100*define col 100struct markint a,b;struct element

13、int i,j,d; /坐標(biāo)與方向;typedef struct Linkstackelement elem;struct Linkstack *ne*t;*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(sizeof(Linkstack);P-elem=E;P-ne*

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

15、|y=0|y=n+1)/迷宮周圍加墻壁maze*y=1;elsescanf(%d,&maze*y);printf(迷宮生成中n);printf(迷宮顯示為：n);for(*=0;*m+2;*+)for(y=0;yn+2;y+)printf(%3d,maze*y);printf(n);void maze_path(int mazerowcol,int dir42,struct mark start,struct mark end)int i,j,d;int *,y;element elem,E;SLinkstack L1,L2;initstack(L1);initstack(L2);mazest

16、art.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è)方向*=i+dird0;y=j+dird1;if(*=end.a&y=end.b&maze*y=0) /這里表示已經(jīng)到了出口elem.i=i;elem.j=j;elem.d=d;push_stack(L1,elem);elem.i=

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