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

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

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

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

4、 mark end)/求解迷宮maze中，從入口start到出口end的一條路徑，/假設存在，則返回TRUE；否則返回FALSE3棧類型struct elementint i,j,d; /坐標與方向;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; /下一個方向while(d4) /探索東西南北各個方向*=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; /標記走過這個點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; /出入口的坐標int dir42=0,1,1,0,0,-1,-1,0; built_maze(maze); /方向，依次是東西南北printf(請輸入入口的橫縱坐標：);scanf(%d,%d,&start.a,&start.b);printf(請輸入出口的橫縱坐標：);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ù)組初始化鏈棧，并將入口，出口信息入棧是棧是否為空否當前坐標周圍是否有方向可以探索否是刪除棧中此步信息換個方向搜索坐標移動是此坐標周圍有無障礙否迷宮無出路此坐標信息入棧此坐標是否為出口是棧逆置并輸出路線 完畢 主程序 maze_path built_maze push_stack stack_empty pop initstack四 實驗結(jié)果與分析1.用戶使用說明1本程序的運行環(huán)境為debug運行環(huán)境，執(zhí)行文件為：19215225.cpp；2用VC+運行文件后出現(xiàn)以下窗口：點擊運行程序出現(xiàn)以下窗口后輸入迷宮的行列數(shù)，回車；再繼續(xù)輸入迷宮的數(shù)據(jù)，1表示障礙，0表示通路；再輸入入口坐標和出口坐標

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

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

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

13、int i,j,d; /坐標與方向;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ù)用逗號隔開：);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; /標記起點坐標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; /下一個方向while(d4) /探索東西南北各個方向*=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; /標記走過這個點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; /出入口的坐標int dir42=0,1,1,0,0