(完整word版)實驗報告——迷宮問題_第1頁
(完整word版)實驗報告——迷宮問題_第2頁
(完整word版)實驗報告——迷宮問題_第3頁
(完整word版)實驗報告——迷宮問題_第4頁
已閱讀5頁,還剩2頁未讀, 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、實習 2棧的應用本次實習的主要目的在于幫助學生深入了解棧的特性,以便在實際問題背景下靈活運用他們;同時還將鞏固對棧這種結構的構造方法的理解。實驗課時6 課時程序 1:迷宮問題問題描述以一個 m×n 的長方陣表示迷宮, 0和 1分別表示迷宮中的通路和障礙。設計一個程序,對任意設定的迷宮,求出一條從入口到出口的通路,或得出沒有通路的結論。基本要求首先實現一個以順序表或鏈表做存儲結構的棧類型,然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出,其中:( i,j)指示迷宮中的一個坐標,d表示走到下一坐標的方向。如:對下列數據的迷宮,輸出的一條通路為: ( 1,1,1

2、),(1,2,2),( 2, 2, 2),測試數據迷宮的測試數據如下:左上角(1, 1)為入口,右下角(3, 4)為出口。0123451111111001111001111000!1111111 實現提示 計算機解迷宮通常用的是 “窮舉求解” 方法,即從入口出發, 順著某一個方向進行探索,若能走通, 則繼續往前進;否則沿原路退回, 換一個方向再繼續探索, 直至所有可能的通路都探索到為止 ,如果所有可能的通路都試探過,還是不能走到終點,那就說明該迷宮不存在從起點到終點的通道,可以二維數組存儲迷宮數據。程序實現 #include <stdio.h>#include <stdlib

3、.h>/1.迷宮位置坐標類型typedef structint x;/ 行int y;/ 列PosType;#define MAXENGTH 25 /迷宮最大行列數位25typedef int MazeTypeMAXENGTHMAXENGTH;/迷宮數列typedef struct/ 定義棧int ord;/ 通道塊在路徑上的序號PosType seat;/通道塊在迷宮中的位置int di;/走向下一塊的方向(03 表示東、南、西、北)SElemType;/2.全局變量MazeType m;/ 迷宮數組int curstep=1;/ 當前位置,初值為1#define STACK_INIT

4、_SIZE 10/存儲空間初始分配量#define STACKINCREMENT 2/存儲空間分配增量/3.棧的順序存儲表示typedef struct SqStackSElemType *base;/ 尾指針SElemType *top;/ 頭指針int stacksize;/ 棧大小SqStack;/ 順序表/4.構造空棧int InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(S.base)exit(0);S.top=S.base;S.stacksize=

5、STACK_INIT_SIZE;return 1;/5.判斷棧是否為空(用來判斷迷宮是否不可達到出口)int StackEmpty(SqStack S)if(S.top=S.base)/ 棧底與棧頂相等為空棧return 1;elsereturn 0;/6.插入元素int Push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)/ 棧頂 -棧底 >=棧長,說明空間已滿S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemT

6、ype);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)+=e;return 1;/7.棧不為空時,刪除棧頂元素,用 e 返回(用于當棧頂元素各方向均不通時,將其從路徑中刪除)int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return 0;e=*-S.top;/ 先將 S.top 的值賦給 e,再將 S.top 向下移一位 return 1;/8.判斷迷宮 m 中 b 點是否可通過(是 1,否 0),其中墻為 0,可

7、通過路徑為 1,不可通過路徑為 -1int Pass(PosType b)if(mb.xb.y=1)return 1;elsereturn 0;/9.是迷宮 m 中 a 的序號變為足跡(即該位置目前可通過)void FootPrint(PosType a)ma.xa.y=curstep;/10.根據當前位置方向,返回下一位置PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0;c.x+=direcdi.x;c.y+=direcdi.y;return c;/11.道路不能通過時(即為死路),將其標記為-1void Ma

8、rkPrint(PosType b)mb.xb.y=-1;/12.求迷宮出口int MazePath(PosType start,PosType end)SqStack S;PosType curpos;/當前位置SElemType e;InitStack(S);curpos=start;doif(Pass(curpos)FootPrint(curpos);e.ord=curstep;e.di=0;Push(S,e);curstep+;if(curpos.x=end.x&&curpos.y=end.y)return 1;curpos=NextPos(curpos,e.di);e

9、lseif(!StackEmpty(S)Pop(S,e);curstep-;while(e.di=3&&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);curstep-;if(e.di<3)e.di+;Push(S,e);curstep+;curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/13.輸出迷宮結構void Print(int x,int y)int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)printf("%3d&

10、quot;,mij);printf("n");/14.主函數int main()PosType begin,end;int i,j,x,y,x1,y1;printf(" 請輸入迷宮行列數(包括外墻):(空格隔開) n");scanf("%d %d",&x,&y);for(i=0;i<x;i+)/定義外墻m0i=0;mx-1i=0;for(j=0;j<y-1;j+)mj0=0;mjy-1=0;for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=1;/墻內初始值均為1/輸入迷

11、宮中墻的個數printf(" 輸入墻的個數:");scanf("%d",&j);/安排墻的位置printf(" 請輸入墻的位置(坐標),用空格隔開 :n");for(i=1;i<=j;i+)scanf("%d %d",&x1,&y1);mx1y1=0;printf(" 迷宮結構如下n");Print(x,y);printf(" 請輸入起點坐標:n");scanf("%d %d",&begin.x,&begin.y);printf(" 請輸入終點坐標

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論