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

1、揚(yáng)州大學(xué)信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)-課程設(shè)計報告題目： 迷宮問題 班級： 計科1301 學(xué)號： 131404126 姓名： 張艷 指導(dǎo)教師： 王麗愛 目 錄1 課程題目2 需求分析 2.1 功能與數(shù)據(jù)需求 2.1.1 題目要求的功能 2.1.2 擴(kuò)展功能 2.2 界面需求 2.3 開發(fā)環(huán)境與運(yùn)行需求 3 概要設(shè)計 3.1主要數(shù)據(jù)結(jié)構(gòu)3.2程序總體結(jié)構(gòu)3.3各模塊函數(shù)說明4 詳細(xì)設(shè)計4.1算法分析與設(shè)計4.2主要程序段設(shè)計5 測試6 附程序源代碼一、設(shè)計題目迷宮問題二、需求分析2.1 功能與數(shù)據(jù)需求 迷宮求解問題描述：以一個m×n的長方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程

2、序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。2.1.1 題目要求的功能 基本要求：首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1）, （1,2,2）, （2,2,2）（3,2,3）, （3,1,2）,。測試數(shù)據(jù)：迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（9,8）為出口。0010001000100010000011010111001000010000010001010111

3、10011100010111000000 1 2 3 4 5 6 7 82.1.2 擴(kuò)展功能（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路2.2 界面需求請求輸入進(jìn)入程序請求輸入起始位置請求輸入終點位置輸出方陣迷宮輸出路徑輸出方陣路徑2.3 開發(fā)環(huán)境與運(yùn)行需求Visual C+6.0三、概要設(shè)計3.1主要數(shù)據(jù)結(jié)構(gòu)定義模塊函數(shù)模塊主函數(shù) 輸入起始位置，終點位置 判斷首節(jié)點是否為通路判斷路徑能否走通對坐標(biāo)標(biāo)記 是否到達(dá)迷宮出口處左邊是否存在通路下邊是否存在通路右邊是否存在通路上邊是否存在通路存儲路徑，將路徑入棧 有解迷宮 無解迷宮 YNYNY輸出迷宮 選擇路徑

4、 3.3各模塊函數(shù)說明typedef struct int pos_xlength;/進(jìn)棧坐標(biāo)int pos_ylength;int top; int base; Stack; /新建結(jié)構(gòu)體void initStack(Stack *p) /初始化棧Push(Stack *p,int x,int y,int d) /入棧具體操作 Pop(Stack *p,int read2,int d) /出棧并讀出前一步的坐標(biāo) initMaze(int Maze109)/建立迷宮Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,in

5、t chukou_y,int d) /具體路徑的求解 menu();/調(diào)用菜單函數(shù) main();/實現(xiàn)迷宮求解的主函數(shù)帶頭結(jié)點的單循環(huán)鏈表抽象數(shù)據(jù)類型SCLinList，其中包括基本操作的函數(shù)有：初始化操作函數(shù)、插入一個結(jié)點操作函數(shù)、刪除一個結(jié)點操作函數(shù)、取一個結(jié)點數(shù)據(jù)操作函數(shù)和判表是否非空操作函數(shù)。該抽象數(shù)據(jù)類型文件名為SCLinList.h。JesephRing()函數(shù)是實現(xiàn)問題要求的主要函數(shù)。void SCLLDeleteAfter(SCLNode *p)，其功能是刪除帶頭結(jié)點的單循環(huán)鏈表中指針p所指結(jié)點的下一個結(jié)點。void JesephRing(SCLNode *head, int

6、 m)，其功能是對帶頭結(jié)點的單循環(huán)鏈表head,以m為初始報數(shù)上限值實現(xiàn)問題要求。void main(void)，主函數(shù)，功能是給出測試數(shù)據(jù)值，建立測試數(shù)據(jù)值的帶頭結(jié)點單循環(huán)鏈表，調(diào)用JesephRing()函數(shù)實現(xiàn)問題要求。四、詳細(xì)設(shè)計迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按左、右、上、下4個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果4方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明找到了一條合適的通路；若退回到了入口處，則說明不存在合法的通路到

7、達(dá)出口。用一個二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（1，1）處，出口點在位置（m,n）處。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的外墻；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；假設(shè)當(dāng)前所在位置是（x,y）。沿某個方向前進(jìn)一步，它可能到達(dá)的位置最多有4。JesephRing()函數(shù)作為主要函數(shù)，其算法思想是：從1至m對帶頭結(jié)點的單循環(huán)鏈表循環(huán)計數(shù)，到m時，輸出該結(jié)點的編號值，將該結(jié)點的密碼作為新的m值，

8、再從該結(jié)點的下一個結(jié)點起重新自1起循環(huán)計數(shù)；如此下去，直到單循環(huán)鏈表空時循環(huán)過程結(jié)束。（1）數(shù)據(jù)類型DataType定義如下：typedef structint number;int cipher; DataType; （2）帶頭結(jié)點單循環(huán)鏈表抽象數(shù)據(jù)類型SCLinList。（3）帶頭結(jié)點單循環(huán)鏈表抽象數(shù)據(jù)類型的結(jié)點結(jié)構(gòu)定義如下： typedef struct nodeDataType data;struct node *next; SCLNode; 五、測試數(shù)據(jù)及運(yùn)行結(jié)果 使用說明1應(yīng)用程序功能的詳細(xì)說明按提示輸入數(shù)字1進(jìn)入迷宮，輸入迷宮入口，迷宮出口2應(yīng)用程序運(yùn)行環(huán)境要求Microsoft

9、 Visual C+6.03輸入數(shù)據(jù)類型、格式和內(nèi)容限制4輸入的數(shù)據(jù)都是整型（int），輸入迷宮的數(shù)據(jù)間要用空格或回車隔開六、附程序源代碼#include <stdio.h> #include <malloc.h> #include<stdlib.h>#include<conio.h>#define length 50#define d direction /用d代表所走路徑的方向int n=-1;int step=0; /記錄步驟數(shù) typedef struct int pos_xlength;/進(jìn)棧坐標(biāo)int pos_ylength;int

10、top; int base; Stack; /新建結(jié)構(gòu)體void initStack(Stack *p) p->top=p->base=0; /初始化棧. Push(Stack *p,int x,int y,int d) /入棧具體操作 step+;d=0;n=n+1; p->top=p->top+1; p->pos_xn=x; p->pos_yn=y;Pop(Stack *p,int read2,int d) /出棧并讀出前一步的坐標(biāo) step+;d=0;n=n-1; p->top=p->top-1; read0=p->pos_xn; r

11、ead1=p->pos_yn;initMaze(int Maze109)/建立迷宮函數(shù). int i; for (i=0;i<=9;i+) Maze0i=1; for (i=0;i<=10;i+) Mazei0=1; for (i=0;i<=9;i+) Maze10i=1; for (i=0;i<=10;i+) Mazei9=1; Maze11=0;Maze12=0;Maze13=1;Maze14=0;Maze15=0;Maze16=0;Maze17=1;Maze18=0; Maze21=0;Maze22=0;Maze23=1;Maze24=0;Maze25=0;

12、Maze26=0;Maze27=1;Maze28=0; Maze31=0;Maze32=0;Maze33=0;Maze34=0;Maze35=1;Maze36=1;Maze37=0;Maze38=1; Maze41=0;Maze42=1;Maze43=1;Maze44=1;Maze45=0;Maze46=0;Maze47=1;Maze48=0; Maze51=0;Maze52=0;Maze53=0;Maze54=1;Maze55=0;Maze56=0;Maze57=0;Maze58=0;Maze61=0;Maze62=1;Maze63=0;Maze64=0;Maze65=0;Maze66=1;

13、Maze67=0;Maze68=1;Maze71=0;Maze72=1;Maze73=1;Maze74=1;Maze75=1;Maze76=0;Maze77=0;Maze78=1;Maze81=1;Maze82=1;Maze83=0;Maze84=0;Maze85=0;Maze86=1;Maze87=0;Maze88=1;Maze91=1;Maze92=1;Maze93=0;Maze94=0;Maze95=0;Maze96=0;Maze97=0;Maze98=0; Print( )/打印出迷宮界面int m,n，j,sum；int Maze109;printf("迷宮(1代表墻即不通

14、,0代表可通過)n"); printf(" ");for(j=1;j<=8;j+) printf("%4d",j);printf("n");for(m=0;m<=10;m+) for(n=0;n<=9;n+) printf("%4d",Mazemn);sum+; if(sum%10=0) printf("n"); Ways(Stack *p,int Maze109,int rukou_x,int rukou_y,int chukou_x,int chukou_y,in

15、t d) /具體路徑的求解函數(shù) int x,y; int read2; x=rukou_x; y=rukou_y; printf("第%d步:",step);printf("(%d,%d,%d)n",x,y,d);if(x=chukou_x&&y=chukou_y)printf("到達(dá)出口坐標(biāo)共走了%d步n",step);return 0;else if(Mazexy+1=0) y=y+1;d=1;Push(p,x,y,d);Mazexy-1=1;Mazexy=1; else if(Mazex+1y=0) x=x+1;

16、d=2;Push(p,x,y,d);Mazex-1y=1;Mazexy=1; else if(Mazexy-1=0) y=y-1;d=3;Push(p,x,y,d);Mazexy+1=1;Mazexy=1; else if(Mazex-1y=0) x=x-1;d=4;Push(p,x,y,d);Mazex+1y=1;Mazexy=1; else Pop(p,read,d); x=read0; y=read1;if(p->top=p->base) printf("找不到出口n");return 0; Ways(p,Maze,x,y,chukou_x,chukou_

17、y,d);return 1; menu()printf("tt*n"); printf("tt* 歡迎進(jìn)入課程設(shè)計 *n"); printf("tt* 迷宮求解程序 *n"); printf("tt* 菜單: *n");printf("tt*進(jìn)入迷宮*請輸入1 *n");printf("tt*退出迷宮*請輸入2 *n");printf("tt*n");int main() Stack *p; Stack S; int Maze109; /定義迷宮int e

18、lem_11,elem_21,a,j; int rukou_x,rukou_y,d=0;int chukou_x,chukou_y; int sum=0; p=&S; initMaze(Maze); system("color 5f");/dos窗口背景顏色函數(shù) menu();/調(diào)用菜單函數(shù)printf("請輸入您的選擇:");scanf("%d",&a);if(a=1)Print( ) /打印迷宮圖.；printf("請輸入入口坐標(biāo):"); scanf("%d",&elem_10); scanf("%d",&elem_11);rukou_x=elem_10;rukou_y=elem_11; printf("請輸入出口坐標(biāo):"); /迷宮入口坐標(biāo). scanf("%d",&elem_20); scanf(&