




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、精選優質文檔-傾情為你奉上武漢紡織大學數學與計算機學院數據結構課程設計報告迷宮問題求解學生姓名:學 號:班 級:指導老師:報告日期:一、 問題描述以一個m x n的長方矩陣表示迷宮,1和0分別表示迷宮中的通路和障礙。設計一個程序,對任意設定的迷宮,求出從入口到出口的通路,或者沒有通路的結論。二、 需求分析1、 以二維數組maze1010表示迷宮,數組中以元素1表示通路,0表示障礙,迷宮的大小理論上可以不限制,但現在只提供10*10大小迷宮。2、 迷宮的入口和出口需由用戶自行設置。
2、3、 以長方形矩陣的形式將迷宮及其通路輸出,輸出中“#”表示迷宮通路,“1”表示障礙。4、 本程序只求出一條成功的通路。但是只要對函數進行小量的修改,就可以求出其他全部的路徑。5、 程序執行命令為:(1)輸入迷宮;(2)、求解迷宮;(3)、輸出迷宮。三、 概要設計1、 設定棧的抽象數據類型定義:ADT zhan基本操作:InitStack(SqStack &S)操作結果:構造一個空棧push(*s,*e)初始條
3、件:棧已經存在操作結果:將e所指向的數據加入到棧s中pop(*s,*e)初始條件:棧已經存在操作結果:若棧不為空,用e返回棧頂元素,并刪除棧頂元素getpop(*s,*e)初始條件:棧已經存在操作結果:若棧不為空,用e返回棧頂元素stackempty(*s)初始條件:棧已經存在操作結果:判斷棧是否為空。若棧為空,返回1,否則返回0ADT zhan2、 設定迷宮的抽象數據類型定義ADT migong基本操作: Status print(MazeType maze); /顯示迷宮
4、Status Pass(MazeType maze,PosType curpos); /判斷當前位置是否可通Status FootPrint(MazeType &maze,PosType curpos);/標記當前位置已經走過Status MarkPrint(MazeType &maze,PosType curpos); /標記當前位置不可通PosType NextPos(PosType curpos,DirectiveTypedi); / 進入下一位置ADT yanshu3、 本程序包括三個模塊a
5、、 主程序模塊void main()初始化;迷宮求解;迷宮輸出;b、 棧模塊實現棧的抽象數據類型c、 迷宮模塊實現迷宮的抽象數據類型四、流程圖將入口、出口位置傳入方法里判斷當前位置是否可通將元素入棧是否到達迷宮出口右邊是否存在通路上邊是否存在通路左邊是否存在通路下邊是否存在通路存儲結點入棧循環結束,無解迷宮有解迷宮五、 數據結構 typedef struct /位置結構 int row; /行位置 int col; /列位置 PosType;typedef struct /迷宮類型 int arr1010; MazeType; typedef structint step
6、; /當前位置在路徑上的"序號" PosType seat; /當前的坐標位置 DirectiveType di; /往下一個坐標位置的方向 SElemType;typedef struct / 棧類型SElemType *base; /棧的尾指針 SElemType *top; /棧的頭指針 int stacksize; /棧的大小 SqStack;六、調試結果和分析a) 測試結果實際程序執行過程如下圖所示: 參考文獻1 嚴蔚敏、吳偉民:數據結構(C語言版)M,清華大學出版社 2007年版2 譚浩強:C語言設計(第三版)M,清華大學出版社 2005年版心得體會通過這段時間
7、的課程設計,本人對計算機的應用,數據結構的作用以及C語言的使用都有了更深的了解。尤其是C語言的進步讓我深刻的感受到任何所學的知識都需要實踐,沒有實踐就無法真正理解這些知識以及掌握它們,使其成為自己的財富。在設計此程序時,剛開始感到比較迷茫,然后一步步分析,試著寫出基本的算法,思路漸漸清晰,最后完成程序。當然也遇到不少的問題,也正是因為這些問題引發的思考給我帶了收獲。在遇到描寫迷宮路徑的算法時,我感到有些困難,后來經過一步步分析和借鑒書本上的窮舉求解的算法,最后把算法寫出來。這次課程設計讓我更加深入了解很多方面的知識,如數組的運用等等。在程序的編寫中不要一味的模仿,要自己去摸索,只有帶著問題反復
8、實踐,才能熟練地掌握和運用。附錄、 源代碼 #include <stdio.h> /頭文件 #include <malloc.h> #include <stdlib.h> #include <string.h> #define OK 1 /宏定義 #define ERROR 0 #define OVERFLOW -2 typedef int Status; /函數的返回值 typedef int DirectiveType; /下一個通道方向 #define STACK_INIT_SIZE 500 /棧的最大值 #defi
9、ne STACKINCREMENT 10 /增量/-存儲結構 typedef struct int row; int col; PosType; typedef structint step; /當前位置在路徑上的"序號" PosType seat; /當前的坐標位置 DirectiveType di; /往下一個坐標位置的方向 SElemType;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;/棧的存儲typedef structint arr1010; MazeType;/迷
10、宮類型/-函數聲明Status InitStack(SqStack &S);Status Pop(SqStack &S,SElemType &e);Status Push(SqStack &S,SElemType e);Status StackEmpty(SqStack S);Status MazePath(MazeType &maze,PosType start,PosType end);Status Pass(MazeType maze,PosType curpos);Status FootPrint(MazeType &maze,PosTy
11、pe curpos);PosType NextPos(PosType curpos,DirectiveType di);Status MarkPrint(MazeType &maze,PosType curpos);Status print(MazeType maze);void main()PosType start,end; MazeType a;printf("請輸入迷宮數據n");for(int i=0;i<10;i+) /接受輸入的迷宮數據for(int j=0; j<10;j+)scanf("%d",&a.arri
12、j); printf("請輸入起始位置:行列 "); / 用戶自定義起始點與終點scanf("%d%d",&start.row,&start.col);printf("請輸入結束位置:行列 ");scanf("%d%d",&end.row,&end.col);if(MazePath(a,start,end) /尋找路徑print(a);elseprintf("沒有找到路徑n");Status InitStack(SqStack &S)S.base=(SEl
13、emType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); / 為棧申請存儲地址if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/end InitStackStatus Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR; e=*(S.top-1);/如果沒有這句話就會在原地打轉,導致在死胡同堵死S.top-;return OK;/end PopStatus Push(
14、SqStack &S,SElemType e)*S.top=e;S.top+;return OK;/end PushStatus StackEmpty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;/end StackEmptyStatus MazePath(MazeType &maze,PosType start,PosType end)PosType curpos;curpos=start; int curstep=1;SElemType e;SqStack S;InitStack(S);doif(Pass(maz
15、e,curpos) /當前位置可以通過,即未曾走過的模塊 e.step=curstep; e.seat=curpos; e.di=1;FootPrint(maze,curpos);/留下足跡Push(S,e); /加入到路徑棧中if(curpos.col=end.col&&curpos.row=end.row)/達到終點(出口)return OK;curpos=NextPos(curpos,1);/下一位置是當前位置的東鄰curstep+;/探索下一步/end ifelse /當前位置不能通過if(!StackEmpty(S)Pop(S,e);while(e.di=4&
16、&!StackEmpty(S)MarkPrint(maze,e.seat);Pop(S,e);/ 留下不能通過的標記,并回退一步/end whileif(e.di<4)e.di+;/ 換一個方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/設定當前位置是該新方向的相鄰快/end if/end if/end elsewhile(!StackEmpty(S);/end ifprintf("nn");for(int i=0;i<10;i+)for(int j=0; j<10;j+)printf("%d &qu
17、ot;,maze.arrij); printf("n"); return ERROR;/end MazePathStatus Pass(MazeType maze,PosType curpos)if(maze.arrcurpos.rowcurpos.col=0) /判斷當前路徑對應數組值是否等于0,即當前路徑是否可通return OK;elsereturn ERROR;Status FootPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rowcurpos.col=2;/為當前路徑留下可以通過的標志return
18、OK;/end PassPosType NextPos(PosType curpos,DirectiveType di)PosType pos = curpos;switch(di)case 1:pos.col+; /向東尋找break;case 2:pos.row+; /向西尋找break;case 3:pos.col-; /向南尋找break;case 4:pos.row-; /向北尋找break;return pos;/end NextPosStatus MarkPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rowcurpos.col=3;/為當前路徑留下不可通過的標志return OK;/end MarkPrintStatus print(MazeType maze) /迷宮的輸出顯示int i,j;printf("nn"
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 寵物醫生助理崗位面試問題及答案
- UI 設計師崗位面試問題及答案
- 山東省東營市利津一中2025屆化學高一下期末監測模擬試題含解析
- 2025屆云南省麗江市玉龍縣第一中學高一化學第二學期期末檢測試題含解析
- 江西省贛州市寧師中學2025年高二化學第二學期期末綜合測試模擬試題含解析
- 民事審判團隊管理辦法
- 醫療安全事件管理辦法
- 保安公司公章管理辦法
- 桐鄉疫情出入管理辦法
- 江蘇公司商旅管理辦法
- 2025年武漢市漢陽區社區干事崗位招聘考試筆試試題(含答案)
- 2025屆山東煙臺中考歷史真題試卷【含答案】
- 志愿者心理調適培訓(改)
- 個人信息保護與安全培訓
- 基于響應面法的工藝參數優化研究
- 黨課課件含講稿:《關于加強黨的作風建設論述摘編》輔導報告
- 國家開放大學行管專科《監督學》期末紙質考試總題庫2025春期版
- GB/T 3280-2015不銹鋼冷軋鋼板和鋼帶
- T∕CQAP 2002-2022 基于水泡性口炎病毒載體的新型冠狀病毒核酸檢測用陽性假病毒質控品
- 1#球磨機襯板更換及方案
- 常用塑料改性加工工藝
評論
0/150
提交評論