《c語言迷宮問題的求解(棧和遞歸)(共15頁).docx》由會員分享，可在線閱讀，更多相關(guān)《c語言迷宮問題的求解(棧和遞歸)(共15頁).docx（15頁珍藏版）》請在匯文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)報告【實(shí)驗(yàn)名稱】項(xiàng)目一 迷宮問題的求解 【實(shí)驗(yàn)?zāi)康摹?1. 了解棧的基本操作以及充分理解棧的特點(diǎn)。熟悉掌握棧的基本操作和結(jié)構(gòu)體的運(yùn)用。2. 學(xué)會用?；蛘哌f歸方法解決迷宮問題?！緦?shí)驗(yàn)原理】1.本次實(shí)驗(yàn)中，以二維數(shù)組mazerowcol表示迷宮，0表示通路，1表示墻，在構(gòu)建迷宮時，為了清晰顯示，在最外層添加一圈墻。2.算法的核心思想是利用棧后進(jìn)先出的特點(diǎn)，對迷宮進(jìn)行探索，如果此路可行，則將此坐標(biāo)的信息入棧，如果此路不通，則將此坐標(biāo)的信息出棧。3.輸入形式：根據(jù)控制臺的提示，依次輸入迷宮的行數(shù)、列數(shù)，然后輸入迷宮，再輸入入口和出口坐標(biāo)。4.輸出形式：由用戶選擇，由遞歸、

2、非遞歸兩種求解方式輸出一條迷宮通路。以非遞歸方式會顯示一種求解方案，并給出相應(yīng)的三元組序列和迷宮方陣；以遞歸方式則會顯示出所有的路線?！緦?shí)驗(yàn)內(nèi)容】1. 需求分析（1） 問題描述以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。要求以遞歸和非遞歸兩種方式分別輸出一條迷宮的通路，以帶方向坐標(biāo)和迷宮圖像表示。（2） 基本要求（1）首先實(shí)現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向

3、。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。（2）編寫遞歸形式的算法，求得迷宮中所有可能的通路。（3）以方陣形式輸出迷宮及其通路。2. 概要設(shè)計（1） 棧的抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2, ,n, n0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD, i=1,2, ,n 約定an端為棧頂，a1端為棧底?；静僮鳎?InitStack( &S ) 操作結(jié)果：構(gòu)造一個空棧S。 DestroyStack ( &S ) 初始條件：棧S已存

4、在。 操作結(jié)果：銷毀棧S。 ClearStack( &S ) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackEmpty( S ) 初始條件：棧S已存在。 操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。 StackLength( S ) 初始條件：棧S已存在。 操作結(jié)果：返回S的數(shù)據(jù)元素個數(shù)，即棧的長度。 GetTop( S, &e ) 初始條件：棧S已存在且非空。 操作結(jié)果：用e返回S的棧頂元素。 Push( &S, e ) 初始條件：棧S已存在。 操作結(jié)果：插入元素e為新的棧頂元素。 Pop( &S, &e ) 初始條件：棧S

5、已存在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。ADT Stack（2） 程序模塊A. 主程序模塊：int main()B. 棧模塊：實(shí)現(xiàn)棧抽象數(shù)據(jù)類型C. 迷宮模塊：實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型3. 詳細(xì)設(shè)計（1） 類型定義typedef struct int x; int y;coordinate; /迷宮中坐標(biāo)類型typedef struct int x; /x行 int y; /y列 int d; /下一步的位置SElemType;/數(shù)據(jù)類型typedef struct Stack SElemType elem; struct Stack *next;Stack,*LinkStac

6、k; /鏈棧定義（2） 遞歸求解算法void MazePath2(int mazeMN,int a,int b,coordinate end,int m,int n) /采用遞歸的方式進(jìn)行四個方向的探索 mazeab=-1; /起點(diǎn)標(biāo)記為-1，即一定正確的通路，每次遞歸便將遞歸的坐標(biāo)標(biāo)記為正確的通路 if(a=end.x&&b=end.y) printf("find a access:n"); PrintMaze2(maze,m,n); /找到了路徑，繪制地圖 if(mazeab+1=0) MazePath2(maze,a,b+1,end,m,n); /向右

7、探索 if(mazea+1b=0) MazePath2(maze,a+1,b,end,m,n); /向下探索 if(mazea-1b=0) MazePath2(maze,a-1,b,end,m,n); /向上探索 if(mazeab-1=0) MazePath2(maze,a,b-1,end,m,n); /向左探索 mazeab=0;/如果當(dāng)前道路不通，則回溯重新探索（3） 非遞歸求解算法Status MazePath(coordinate start,coordinate end,int mazeMN) /迷宮求解函數(shù) int row,col,k,a,b,trg=1;/行、寬、新行、新寬、判

8、斷標(biāo)志int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量數(shù)組 方向依次為東西南北 SElemType elem,elem2;/elem用于存儲當(dāng)前的地址信息，elem2用于最后將棧逆置輸出 LinkStack S1, S2; /S1用于存放迷宮路徑，S2用于逆置 InitStack(S1); InitStack(S2); /棧的初始化 mazestart.xstart.y=2; /標(biāo)記初始位置 elem.x=start.x; elem.y=start.y; elem.d=-1; Push(S1,elem); /進(jìn)行第一次入棧，代表從起點(diǎn)出發(fā) while(!StackEmp

9、ty(S1) /棧不為空 有可行路徑 Pop(S1,elem); /出棧，獲取當(dāng)前坐標(biāo)及方向信息 row=elem.x; col=elem.y; k=elem.d+1; /下一個方向 while(k<4) /試探東南西北各個方向（0-東，1-南，2-西，3北） a=row+addk0; /新的行坐標(biāo) b=col+addk1; /新的列坐標(biāo) if(a=end.x && b=end.y && mazeab=0) /找到出口 elem.x=row; elem.y=col; elem.d=k; /4代表找到了出口 Push(S1,elem); elem.x=a;

10、elem.y=b; elem.d=4; Push(S1,elem);/終點(diǎn)入棧 printf("nFind a access,the access is(row,col,direct):n"); while(S1) /逆置鏈棧 Pop(S1,elem2); mazeelem2.xelem2.y=3;/區(qū)分可行的路徑，用于最后的輸出 Push(S2,elem2); while(S2) /以三元組形式輸出迷宮路徑序列 Pop(S2,elem2); if(trg=1) printf("(%d,%d,%d)",elem2.x,elem2.y,elem2.d); trg+; else printf(",(%d,%d,%d)",elem2.x,elem2.y,elem2.d); trg+; if(trg%5=0) printf("n"); printf("n"); return OK; /跳出循環(huán)