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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目： 迷宮求解 班 級(jí)： 學(xué) 號(hào)： 作者姓名： 指導(dǎo)教師： 2021年12月11日目 錄1需求分析.12概要設(shè)計(jì).12.1數(shù)據(jù)結(jié)構(gòu).12.1.1邏輯結(jié)構(gòu).12.1.1存儲(chǔ)結(jié)構(gòu).22.2.基本操作.3 2.2.1.迷宮中棧的基本操作.3 2.2.2.迷宮的抽象數(shù)據(jù)類型.32.2.3.本程序包含三個(gè)模塊.43詳細(xì)設(shè)計(jì). .54調(diào)試與分析. .95用戶手冊(cè)96. 測(cè)試結(jié)果.107. 附錄.128. 參考文獻(xiàn).129、心得體會(huì)1210、小組成員工作分配.13一、 需求分析(1) 以二維數(shù)組mazen+2m+2表示迷宮，其中：maze0j和mazen+1j(0<=j<=m

2、+1)及mazei0和mazeim+1(0<=i<=j+1)為添加的一圈障礙。數(shù)組中以元素值為0的表示通路，1表示障礙，限定迷宮的大小，m，n<=0。(2) 迷宮的入口位置和出口位置可由用戶自行設(shè)定。(3) 如設(shè)定的迷宮處在通路，則值輸出迷宮中的通路，即0，現(xiàn)實(shí)的0連起來就是一個(gè)迷宮通路路徑；如設(shè)定的迷宮中不出在通路，則輸出“該迷宮找不到通路!”；(4) 測(cè)試樣例：輸入迷宮的長(zhǎng)寬為5和6，輸入迷宮為：1 0 0 1 1 10 0 1 1 1 11 0 0 0 1 10 1 0 1 1 11 1 0 0 0 0當(dāng)入口位置為（1,2），出口位置為（5,6）時(shí)，則輸出數(shù)據(jù)為：# #

3、 # # # # # # 0 # 0 # 0 0 # 0 # 0 0 0 0 # # # # # # # #(5) 程序執(zhí)行的命令為：1、 輸入迷宮的尺寸；2、創(chuàng)建迷宮；3、輸入迷宮的的出入口位置；4、求解迷宮；輸出迷宮的解。二、 概要設(shè)計(jì)2.1.數(shù)據(jù)結(jié)構(gòu)2.1.1、邏輯結(jié)構(gòu)1）棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表；2）操作特性：后進(jìn)先出;3) ADT定義：ADT Stack數(shù)據(jù)對(duì)象：D=ai|aiCharSet,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空

4、棧S。DestroyStack（&S）初始條件：棧S 已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S 已存在。操作結(jié)果：將 S 清為空棧。StackLength(&S)初始條件：棧S 已存在。操作結(jié)果：返回棧 S 的長(zhǎng)度。StackEmpty(&S)初始條件：棧S 已存在。操作結(jié)果：若 S 為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S 已存在。操作結(jié)果：若棧 S 不空，則以e 返回棧頂元素。Push(&S,e)初始條件：棧S 已存在。操作結(jié)果：在棧 S 的棧頂插入新的棧頂元素e。Pop

5、(&S,&e)初始條件：棧S 已存在。操作結(jié)果：刪除 S 的棧頂元素，并以e 返回其值。StackTraverse(S,visit()初始條件：棧S 已存在。操作結(jié)果：從棧底到棧頂依次對(duì) S 中的每個(gè)元素調(diào)用函數(shù)visit( )。ADT Stack2.1.2、存儲(chǔ)結(jié)構(gòu)1）順序存儲(chǔ)結(jié)構(gòu)： 順序棧：是利用一塊地址連續(xù)的存儲(chǔ)單元來存放棧中的元素，同時(shí)要利用一個(gè)指針top 來指示棧頂元素的位置。注：在本迷宮求解程序設(shè)計(jì)中用到的就是棧的順序存儲(chǔ)結(jié)構(gòu)。/- 棧的順序存儲(chǔ)表示 -#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; t

6、ypedef struct SElemType *base; SElemType *top; int stacksize;SqStack; 2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 鏈?zhǔn)綏＃烘湕Ｊ侵覆捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧。 鏈棧是一種特殊的單鏈表，即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表，因此鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。2.2、基本操作2.2.1、迷宮中棧的基本操作：基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。StackEmpty(&S)初始條件：棧S 已存在。操作結(jié)果：若 S 為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S 已

7、存在。操作結(jié)果：若棧 S 不空，則以e 返回棧頂元素。Push(&S,e)初始條件：棧S 已存在。操作結(jié)果：在棧 S 的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S 已存在。操作結(jié)果：刪除 S 的棧頂元素，并以e 返回其值。2.2.2、迷宮的抽象數(shù)據(jù)類型ADT MazeType數(shù)據(jù)對(duì)象 : D=ai,j|ai,j ,#、*，0<=i<=n+1, 0<=j<=m+1,m,n<=20 數(shù)據(jù)關(guān)系 :R=ROW,LINEROW=<ai-1,j,ai,j>|ai-1,j,ai,jD,i=1,m+1,j=0,n+1LINE=&

8、lt;ai-1,j,ai,j>|ai-1,j,ai,jD,i=1,m+1,j=0,n+1 基本操作 :Status Pass(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 如果可通,返回真,否則為假void FootPrint(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 將當(dāng)前坐標(biāo)curpos處的maze值記為 足跡PosType NextPos(PosType CurPos,int

9、di)初始條件: 各參數(shù)值已經(jīng)定義操作結(jié)果: 求得以當(dāng)前位置為棧頂?shù)南乱粋€(gè)方向的元素的坐標(biāo)Status MazePath(SqStack &S, PosType start, PosType end) 初始條件: maze 存在迷宮地圖操作結(jié)果: 為建立的迷宮找到一條路徑ADT maze;2.2.3、本程序包含三個(gè)模塊1）主函數(shù)模塊：int main（） 初始化迷宮； 求解迷宮； 輸出迷宮的解； return 0；2）棧實(shí)現(xiàn)模塊實(shí)現(xiàn)棧的抽象殊絕類型3）迷宮實(shí)現(xiàn)模塊實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型各模塊的調(diào)用關(guān)系如下：主函數(shù)模塊>迷宮模塊>棧模塊4）求解迷宮中一條通路的偽碼算法：設(shè)定當(dāng)

10、前位置的初值為入口位置；do 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； /納入路徑 若該位置是出口位置，則結(jié)束； /求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；否則 若棧不空且棧位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則刪去棧頂位置； /后退一步，從路徑中刪去該通道塊； 若棧不空，則重新測(cè)試新的棧頂位置； 直到找到一個(gè)可通的相鄰塊或出棧至?？?； while(棧不空)；?？照f明沒有路徑存在三、 詳細(xì)設(shè)計(jì)1、 坐標(biāo)位置類型typedef structint row;int line;PosT

11、ype;2、 迷宮類型Status Pass(PosType CurPos)/判定當(dāng)前位置是否可以通過，即是未曾走到過的通道塊void FootPrint(PosType CurPos)/給當(dāng)前可通過的位置標(biāo)記PosType NextPos(PosType CurPos,int di)/探尋下一個(gè)位置，并標(biāo)記方向Status MazePath(SqStack &S, PosType start, PosType end)/求解迷宮maze中，從入口start到出口end的一條路徑，/如存在，返回OK，否則返回ERROR3、 棧類型typedef structint ord; /通道塊在

12、路徑上的“序號(hào)”int di; /通道塊在迷宮中的“坐標(biāo)位置”PosType seat;/從此通道塊走向下一通道塊的“方向”SElemType; /棧的元素類型typedef structSElemType *base;/在構(gòu)造棧之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間，以元素為單位SqStack;/棧定義棧的基本操作如下：void InitStack(SqStack &S)/初始化棧，設(shè)棧S為空棧（S.top=NULL）void Push(SqStack &S,SElemType e)

13、/若分配空間成功，則在S 的棧頂插入新的棧頂元素e/否則增加棧棧的存儲(chǔ)空間，再插入新的元素int GetTop(SqStack &S,SElemType e)/若棧S不空，則以e帶回棧頂元素并返回TRUE，否則返回FALSEint Pop(SqStack &S,SElemType &e)/若棧不空，則刪除S 的棧頂元素并以e 帶回其值，且返回TRUE/否則返回FALSEint StackEmpty(SqStack S)/若S為空棧（S.top=NULL），則返回TRUE；否則返回FALSE具體部分操作的算法如下： void InitStack(SqStack &

14、S) /初始化棧S為空棧（S.top=NULL）S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;/Initstackvoid Push(SqStack &S,SElemType e) /若分配空間成功，則在S 的棧頂插入新的棧頂元素e/否則增加棧棧的存儲(chǔ)空間，再插入新的元素 if(S.top-S.base>=S.stacksize) S.base=(SElemTyp

15、e *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;/Push4、 求解迷宮的偽碼算法：Status MazePath(SqStack &S, PosType start, PosType end) /若迷宮maze中存在從入口start到出口end的通道，則/一條存放在棧中(從棧底到棧頂為從入口到出口的路徑)，并返/回O

16、K，否則返回ERRORPosType curpos;int curstep;SElemType e;InitStack(S);curpos = start;/設(shè)定“當(dāng)前位置”為“初始位置” curstep = 1; /探索第一步 do if (Pass(curpos) /當(dāng)前位置可以通過，即是未曾走到過的的通道塊/留下足跡FootPrint(curpos); e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); /加入路徑 if (curpos.row=end.row && curpos.line=end.line) return

17、OK; /到達(dá)出口位置 curpos = NextPos(curpos, 1); curstep+;/探索下一步 else /當(dāng)前位置不能通過 if (!StackEmpty(S) Pop(S,e);while (e.di=4 && !StackEmpty(S) FootPrint(e.seat); Pop(S,e); curstep-； if (e.di<4) e.di+; Push(S, e); curpos = NextPos(e.seat, e.di); /if /if while (!StackEmpty(S);return ERROR;/MazePath5、

18、主函數(shù)和其它函數(shù)的偽碼算法void printpath(SqStack S,int n,int m)/打印路徑printf("nn通路路徑為:n");/PosType start,end;SElemType * p=S.base;/定義一個(gè)指針p指向棧中的元素，設(shè)/定初值為p=S.basewhile(p!=S.top)mazep->seat.rowp->seat.line=2;p+;/將有效路徑的通道塊全部標(biāo)記為2或其他不為1或0的/值int i,flag=0;/打印出路徑，周圍用“#”圍成一圈作圍墻for(i=0;i<m+2;i+)printf(&quo

19、t;%c ",'#');printf("n");for(i=1;i<n+1;i+) printf("%c ",'#');for(int j=1;j<m+1;j+)if(mazeij=2) printf("%c ",'0');else printf(" ");printf("%c",'#');printf("n");for(i=0;i<m+2;i+)printf("%c &qu

20、ot;,'#');printf("nn");/printpathint main()/主函數(shù)SqStack S;int r,l;while(true)printf("創(chuàng)建一個(gè)迷宮，請(qǐng)輸入迷宮長(zhǎng)和寬(不得大于20):n");scanf("%d%d",&r,&l);if(r<1 | r>20|l<1|l>20)printf("輸入錯(cuò)誤!");int i;printf("按行輸入%d*%d數(shù)據(jù)(0代表可通,1代表不可通):n",r,l);for(

21、i=0;i<l+2;i+)maze0i=1;for(i=1;i<r+1;i+)mazei0=1;for(int j=1;j<l+1;j+)scanf("%d",&mazeij);mazeil+1=1;for(i=0;i<l+2;i+)mazer+1i=1;PosType start,end;printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line);printf("輸入出口行坐標(biāo)

22、和列坐標(biāo):");scanf("%d",&end.row);scanf("%d",&end.line);if(MazePath(S,start,end) printpath(S,r,l);else printf("該迷宮找不到通路!nn");return 0;/main四、 調(diào)試分析1、在本次的程序設(shè)計(jì)中，最核心的算法就是MazePath()函數(shù)，其他的算法并沒有出現(xiàn)什么問題。不過在最后輸出的時(shí)候本來想輸出路徑的先后順序，即maze12->maze22->maze32->maze33->

23、maze43->maze53->maze54->maze55->maze56，但是最后發(fā)現(xiàn)這樣只有在入口在左上角，出口在右下角時(shí)，才可以正確輸出。但是入口和出口是隨機(jī)的，若是入口在右下角，出口在左上角，則也同樣輸出maze12->maze22->maze32->maze33->maze43->maze53->maze54->maze55->maze56，雖然這兩個(gè)路徑是一樣的，但是有先后順序，故最后沒有輸出這種形式，將這段代碼注釋了（源程序中有注釋的代碼）；2、本來是想設(shè)計(jì)成既可以手動(dòng)輸入迷宮又可以自動(dòng)生成迷宮，但是感覺沒

24、有太大的用處，所以最后省略了，只保留了手動(dòng)輸入。3、在整個(gè)編寫的過程中，出現(xiàn)過很多錯(cuò)誤，包括一些標(biāo)點(diǎn)符號(hào)的小錯(cuò)誤，但是借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，很快找出來問題的所在。五、 用戶手冊(cè)1、 本程序的運(yùn)行環(huán)境為 DOS 操作系統(tǒng), 執(zhí)行文件為：迷宮求解.exe.2、 進(jìn)入演示程序后 , 即顯示文本方式的用戶界面:3、 根據(jù)提示輸入迷宮大小及迷宮后,輸入迷宮的行和列,回車后即可得到所 輸入迷宮的解或者是顯示“該迷宮找不到通路!”字樣。六、 測(cè)試結(jié)果1、 輸入長(zhǎng)寬為5，6，入口為（1,2），出口為（5,6）的迷宮1 0 0 1 1 10 0 1 1 1 11 0 0 0 1 10 1 0 1

25、1 11 1 0 0 0 0求解結(jié)果：2、 輸入長(zhǎng)寬為4，5，入口為（1,1），出口為（4,5）的迷宮0 1 0 1 10 0 1 1 01 0 1 1 11 0 0 0 0輸出結(jié)果為：3、 輸入長(zhǎng)寬為4，5，入口為（1,1），出口為（4,5）的迷宮1 1 0 1 1 10 1 0 1 0 11 0 0 0 1 10 1 0 1 1 11 1 0 0 0 0輸出結(jié)果為：七、 附錄源程序文件名清單：主函數(shù).cpp迷宮的實(shí)現(xiàn).h棧的實(shí)現(xiàn).h八、 參考文獻(xiàn)1、嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.北京：清華大學(xué)出版社，2021.2、嚴(yán)蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集(C語言版)M.北京：清華大學(xué)出

26、版社，2021.3、蘇仕華，魏韋巍，王敬生，劉燕君.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M.北京：機(jī)械工業(yè)出版社，2021.九、 心得體會(huì)做了這次程序設(shè)計(jì)，我們發(fā)現(xiàn)利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)并不像想像中的那么高深，像我們現(xiàn)在所做的，只是一些最基本的程序。經(jīng)過一個(gè)學(xué)期的學(xué)習(xí)，對(duì)數(shù)據(jù)結(jié)構(gòu)有了一個(gè)初步的認(rèn)識(shí)，但沒有進(jìn)行實(shí)際應(yīng)用。這次程序設(shè)計(jì)，就相當(dāng)于對(duì)一個(gè)學(xué)期的所學(xué)做一個(gè)總結(jié)，再進(jìn)行一次綜合運(yùn)用，更是學(xué)到了很多新的東西，無意中也提升了自己的程序設(shè)計(jì)水平；在程序設(shè)計(jì)過程中碰到了很多問題，通過上網(wǎng)查資料等各種手段，我們的解決實(shí)際問題的能力也得到了提高。這次的程序設(shè)計(jì)，讓我們對(duì)程序設(shè)計(jì)有了一個(gè)更全面的認(rèn)識(shí)，如果我們以后能在編程

27、領(lǐng)域深入發(fā)展，這一次也算是我們邁出的重要一步吧。十、 小組成員工作分配程序、文檔的編寫；程序校對(duì)及查找資料；文檔的勘誤及字體的調(diào)整。 教師見習(xí)報(bào)告總結(jié)期待已久的見習(xí)已經(jīng)結(jié)束了，在龍巖三中高中部見習(xí)聽課，雖然只是短短的兩個(gè)星期，但感觸還是蠻深的，以前作為一名學(xué)生坐在課室聽課，和現(xiàn)在作為一名準(zhǔn)教師坐在課室聽課是完全不同的感受，感覺自己學(xué)到了一些在平時(shí)課堂上學(xué)不到的東西。在這里，我獲得的不僅是經(jīng)驗(yàn)上的收獲，更多是教學(xué)管理，課堂教學(xué)等的理念，以及他們帶給我的種種思考。教育見習(xí)實(shí)踐過程：聽課。教育見習(xí)的主要目的是讓學(xué)生在指導(dǎo)教師的引導(dǎo)下，觀摩教師上課方法、技巧等。聽課是教育見習(xí)的主要內(nèi)容。我院規(guī)定在一周

28、的見習(xí)中需完成至少6課的見習(xí)任務(wù)。我在教師的安排指導(dǎo)下，分別對(duì)高一、高二物理專業(yè)課型為主，其他課型齊頭的方式，積極主動(dòng)的完成了聽課任務(wù)，收到良好的效果。我聽的第一節(jié)課是高二（8）班，這是一個(gè)平衡班，水平不如實(shí)驗(yàn)班高。在上課前?？迫卫蠋熞呀?jīng)跟我說了這個(gè)班的紀(jì)律是比較差的，而且成績(jī)也不是很好。在我聽課期間，確實(shí)有幾個(gè)學(xué)生在課堂上說話，但是我發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象，這個(gè)現(xiàn)象我在往后的幾個(gè)班都發(fā)現(xiàn)了，就是絕大部分的學(xué)生的學(xué)習(xí)熱情都好高漲，積極舉手發(fā)言，積極參與課堂活動(dòng)。我跟老師們提起這個(gè)現(xiàn)象的時(shí)候，科任老師就跟我說，一個(gè)班里不可能所有的學(xué)生都能全神貫注地聽完一節(jié)課，所以作為一名教師，應(yīng)該想辦法吸引學(xué)生的

29、注意力，調(diào)動(dòng)的積極性，比如可以以小組為單位，以搶答計(jì)分的形式調(diào)動(dòng)學(xué)生的積極性，這樣課堂氣氛就會(huì)活躍起來了。在為期兩周的見習(xí)工作中，我真的有很大的感觸，我第一次感受到自己已經(jīng)從一名學(xué)生向一名教師靠近，走在校園里，每當(dāng)有學(xué)生叫我一聲老師，我在感到無比自豪的同時(shí)，還感受到了自己的責(zé)任。見習(xí)工作結(jié)束了，我要回到學(xué)校繼續(xù)我的學(xué)習(xí)了，但是我會(huì)好好記住我從*中學(xué)學(xué)到的一切，并應(yīng)用于我的專業(yè)學(xué)習(xí)中去。一、教學(xué)管理理念 在龍巖三中，從領(lǐng)導(dǎo)階層到一位普通的科任老師，都秉承以學(xué)生為主體的宗旨進(jìn)行學(xué)校的管理，進(jìn)行教學(xué)工作的開展。作為一個(gè)課程改革的示范學(xué)校，一個(gè)教育實(shí)驗(yàn)基地。這所學(xué)校鼓勵(lì)著老師做各種研究，各種

30、改革。每個(gè)班主任都有著自己的管理經(jīng)驗(yàn)與管理宗旨。有了這種思想的自由，自然這里也就充滿著探索與嘗試，從而有所創(chuàng)造與進(jìn)步。在我見習(xí)的班集體中，班主任對(duì)他的學(xué)生說：“我要讓你們成為學(xué)習(xí)型的管理者，也是管理型的學(xué)習(xí)者?！边@樣一句簡(jiǎn)單的話，讓我感到這里老師進(jìn)行班級(jí)管理的良苦用心。他們關(guān)心的不只是學(xué)生的學(xué)習(xí)，更多的是從一個(gè)完整的人的概念出發(fā)，去培養(yǎng)學(xué)生多方面的素質(zhì)。二、教學(xué)理念 在見習(xí)期間，借著錄課的機(jī)會(huì)，我聽了很多的市級(jí)，校級(jí)的公開棵，還有理科實(shí)驗(yàn)班的課。在這些課堂上，讓我看到教學(xué)改革正在悄然進(jìn)行，有意識(shí)的老師正在努力體會(huì)“以學(xué)生為主體”的課堂模式。學(xué)生的創(chuàng)造也逐步成為教師追求的教學(xué)效果。其次，這里的老師也都在適應(yīng)著多媒體教學(xué)，信息化教學(xué)，使得課堂更加生動(dòng)，資源更加豐富，學(xué)生獲取學(xué)習(xí)資源的渠道也就更多。盡管，這種教學(xué)理念、教學(xué)模式的推廣仍然有很長(zhǎng)的路，但似乎也并不遙遠(yuǎn)，相信，這股改革的浪潮會(huì)給教育領(lǐng)域帶來很大的沖擊。 三、實(shí)際工作經(jīng)驗(yàn)&