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

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

2、nt mazerowcol 來存儲，在定義了迷宮的行列數(shù)后，用兩個 for 循環(huán)來錄入迷宮數(shù)據(jù)，并在迷宮周圍加墻壁。（ 2）迷宮的入口位置和出口位置可以由用戶自己決定。2. 概要設(shè)計（ 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);prin

3、tf("請輸入出口的橫縱坐標：");scanf("%d,%d",&end.a,&end.b);printf("0為東， 1為南， 2為西， 3為北， -1 為出路 n");maze_path(maze,dir,start,end);getchar();（ 2）棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型（ 3）迷宮模塊實現(xiàn)迷宮抽象數(shù)據(jù)類型，建立迷宮，找出迷宮的一條通路3. 詳細設(shè)計（ 1）坐標位置類型 struct markint a,b; /迷宮 a行b列為位置;（ 2）迷宮類型void built_maze(int mazerowco

4、l)/ 按照用戶輸入的 row行和 col 列的二維數(shù)組（元素值為 0和1）/ 設(shè)置迷宮 maze的初值，包括邊上邊緣一圈的值voidmaze_path(intmazerowcol,intdir42,structmark start,struct mark end)/ 求解迷宮 maze中，從入口 start 到出口 end的一條路徑，/ 若存在，則返回 TRUE；否則返回 FALSE（3）棧類型struct elementint i,j,d;/坐標與方向;typedef struct Linkstackelement elem;struct Linkstack *next;*SLinksta

5、ck;4. 求迷宮路徑為偽碼算法voidmaze_path(intmazerowcol,intdir42,structmark 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

6、=elem.j;d=elem.d+1; /下一個方向while(d<4)/探索東西南北各個方向x=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(&quo

7、t;%3d%3d%3dn",E.i,E.j,E.d);return;if(mazexy=0)mazexy=2; /標記走過這個點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;/出入口的坐標int dir42=0,1,1,0,0,-1,-1,0;built_maze(maze);/方向，依次是東西南北printf("

8、請輸入入口的橫縱坐標：");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();三 程序結(jié)構(gòu)換個方向搜索是main()定義方向二維數(shù)組初始化鏈棧，并將入口，出口信息入棧棧是否為空否當(dāng)前坐標周圍是否有方向可

9、以探索是坐標移動此坐標周圍有無障礙否此坐標信息入棧此坐標是否為出口是棧逆置并輸出路線是否刪除棧中此步信息迷宮無出路結(jié)束主程序built_mazemaze_pathinitstackpush_stackpopstack_empty四 實驗結(jié)果與分析1. 用戶使用說明（ 1 ） 本程 序的運 行 環(huán)境為 debug運 行環(huán)境， 執(zhí)行 文件 為：19215225.cpp ；（ 2）用 VC+運行文件后出現(xiàn)以下窗口：點擊運行程序（ 3）出現(xiàn)以下窗口后輸入迷宮的行列數(shù)，回車；再繼續(xù)輸入迷宮的數(shù)據(jù)， 1表示障礙， 0 表示通路；再輸入入口坐標和出口坐標， 回車。就可以顯示出迷宮路徑。2. 測試結(jié)果（1）輸

10、入行列數(shù)： 5,5輸入迷宮數(shù)據(jù)為： 0 0 0 1 111011000100110000000出口位置： 1,1出口位置： 5,5（2）輸入行列數(shù)： 4,9輸入迷宮數(shù)據(jù)為： 000000100010001000001110011001110100輸入入口坐標： 1,1輸入出口坐標： 4,9（3）輸入行列數(shù)： 9,8輸入迷宮數(shù)據(jù)為： 001000100010001000001101011100100001000001000101011110011100010111000000輸入入口坐標： 1,1輸入出口坐標： 9,83. 調(diào)試分析（1）在剛開始寫完代碼后，運行發(fā)現(xiàn)程序只能運行簡單的一條直線的迷

11、宮，在運行復(fù)雜的迷宮時，不會碰到死路（周圍沒有可探索的道路）就刪除坐標往回到前坐標換方向探索。最后我和同寢室同學(xué)一起探討才發(fā)現(xiàn)程序中探索過的坐標沒有標記，后來我將mazexy=2 將它作為標記才解決問題。（2）程序中主要的兩個算法： initmaze 和maze_path的時間復(fù)雜度為 O(m*n)，空間復(fù)雜度也為 O(m*n)。五 總結(jié)（收獲與體會）通過這段時間的課程設(shè)計， 我對數(shù)據(jù)結(jié)構(gòu)和 C語言的理解更加深刻了。在實踐過程中我遇到了不少問題，但通過閱讀相關(guān)書籍、求問老師同學(xué)，最終也解決了不少問題。這些問題也給了我相當(dāng)多的收獲。但通過這段時間的學(xué)習(xí)和解決的這么多問題， 我覺得我對這些知識的掌

12、握比以前好了許多。求解迷宮問題用的是“窮舉求解”的方法。從入口出發(fā)，沿著某一方向探索（這里我選擇優(yōu)先探索的是東面），若無障礙，繼續(xù)往前走，否則眼原路返回，換個方向繼續(xù)探索，直到將所有可能的通道都探索完為止。所以需要用棧來保存從入口到當(dāng)前位置的路徑。但因為之前在學(xué)習(xí)棧這一節(jié)的時候沒學(xué)扎實，現(xiàn)在有很多知識都忘了。所以在編寫求解迷宮路徑的算法的時候我覺得有些困難， 后來經(jīng)過一步步分析和借鑒書上的窮舉法才把算法寫出來。但我還是除了許多錯誤，其中大部分是語法錯誤，這些最后都還是一一解決了。而且除了加深了棧的學(xué)習(xí)，我還復(fù)習(xí)了以前大一學(xué)的 C語言中的二維數(shù)組和 for ，while 循環(huán)。這次課程設(shè)計不僅是

13、讓我們加深了解數(shù)據(jù)結(jié)構(gòu)的理論知識， 更重要的是培養(yǎng)我們解決實際問題的能力，能在不斷地遇到問題，不斷地解決問題的過程中培養(yǎng)自己的專業(yè)思維。 所以我相信通過這次課程設(shè)計我們能夠提升自己的分析、設(shè)計程序和編寫程序的能力。六 源程序#include<stdio.h>#include<stdlib.h>#define row 100#define col 100struct markint a,b;struct elementint i,j,d;/坐標與方向;typedef struct Linkstackelement elem;struct Linkstack *next;*

14、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->next=L;L=P;return 1;int pop(SLinkstack &L,element &E)SLink

15、stack 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(" 請輸入迷宮的行列數(shù)（用逗號隔開）： "); scanf("%d,%d",&m,&n);printf(" 請輸入迷宮各行各列的數(shù)據(jù)（用空格隔開）： n"); for(x=0;x<m+2;x+)for(y=0;y<n+2;

16、y+)if(x=0|x=m+1|y=0|y=n+1)/ 迷宮周圍加墻壁 mazexy=1;elsescanf("%d",&mazexy);printf("迷宮生成中 n");printf("迷宮顯示為： n");for(x=0;x<m+2;x+)for(y=0;y<n+2;y+)printf("%3d",mazexy);printf("n");void maze_path(int mazerowcol,int dir42,struct mark start,struct ma

17、rk 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; /下一個方向while(d<4)/探索東西南北各個方向x=i+dird0;y=j+dird1

18、;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("(%d,%d,%d)n",E.i,E.j,E.d);return;if(mazexy=0)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;/出入口的坐標intdir42=0,1,1,0,0,-1,-1,0;/方向，依次是東西南北printf("* *n");printf("t*歡迎使用迷宮模擬程序*n");printf("*n");b