任務(wù)書1(迷宮問題)(共20頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課題名稱 迷宮問題 專 業(yè) 信息與計(jì)算科學(xué) 班 級(jí) 1002班 學(xué) 號(hào) 08 姓 名 田雯 指導(dǎo)教師 劉洞波 ××× 2012年 6月 9日課程設(shè)計(jì)任務(wù)書課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課 題 迷宮問題 專業(yè)班級(jí) 信科1002班 學(xué)生姓名 田雯 學(xué) 號(hào) 08 指導(dǎo)老師 劉洞波 審 批 任務(wù)書下達(dá)日期： 2012年 6月 9日任務(wù)完成日期： 2012年 6月 16日專心-專注-專業(yè)目 錄3. 3 各模塊的調(diào)用關(guān)系.2一、設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1設(shè)計(jì)內(nèi)容：1）問題描述以一個(gè)M*N的長(zhǎng)方陣表示迷宮，0和

2、1分別表示迷宮中的通路和墻壁。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出米有通路的結(jié)論。2）基本要求a.實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一個(gè)坐標(biāo)的方向。b.編寫遞歸形式的算法，求得迷宮中所有可能的通路。3）測(cè)試數(shù)據(jù)迷宮的測(cè)試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。0010001000100010000011010111001000010000010001010111100111000101110000004）實(shí)現(xiàn)提示計(jì)算機(jī)解

3、迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則，沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則設(shè)定的迷宮沒有通路?？梢远S數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。2設(shè)計(jì)要求：l 課程設(shè)計(jì)報(bào)告規(guī)范1)需求分析（1）首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷

4、宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。否則報(bào)告一個(gè)無(wú)法通過(guò)的信息。（2）建立InitStack函數(shù)，用于構(gòu)造一個(gè)空棧。（3）建立DestroyStack函數(shù)，用于銷毀棧。（4）建立Pop函數(shù)，用于刪除棧頂元素，返回棧頂元素的值。（5）建立Push函數(shù)，用于插入新的棧頂元素。（6）建立NextPos函數(shù)，用于定位下一個(gè)位置。2)概要設(shè)計(jì) 31抽象數(shù)據(jù)類型定義（1）棧的抽象數(shù)據(jù)類型定義InitStack( LStack *S )操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack( LStack *S )操作結(jié)果：棧S被銷毀。Pop( LStack *S，ElemType *e )操作結(jié)果：刪除

5、S的棧頂元素。用e返回棧頂元素的值。若棧為空則返回0。Push( LStack *S，ElemType e )操作結(jié)果：在棧頂之上插入元素e為新的棧頂元素。若棧S為空棧，則返回0。（2）迷宮的抽象數(shù)據(jù)類型定義 NextPos(unsigned *x，unsigned *y，short di)操作結(jié)果：找到下一個(gè)位置。32模塊劃分本程序包括三個(gè)模塊：（1）主程序模塊void main()初始化；構(gòu)造迷宮；迷宮求解；迷宮輸出；（2）棧模塊實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型（3）迷宮模塊實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型各模塊的調(diào)用關(guān)系如下：4）求解迷宮的通路的偽碼算法：設(shè)定當(dāng)前位置的處值為入口位置；DO若當(dāng)前的位置可通。則

6、將當(dāng)前的位置插入棧頂；若該位置為出口位置，則結(jié)束；否則切換當(dāng)前位置的東鄰的為新的當(dāng)前位置；否則若棧不為空且棧的頂位置尚有其他的方向沒有被探索，則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到棧頂?shù)奈恢玫南乱粋€(gè)相鄰塊；若棧不空但棧頂?shù)乃闹芫豢赏ㄟ^(guò)，則刪去棧頂位置；若棧不為空，則重新測(cè)試新的棧頂位置；只至找到一個(gè)可通過(guò)的塊至?？?；1 坐標(biāo)的位置的類型typedef structint line;int row;PosType;2 迷宮類型void CreatMaze(int r,int l)/定義迷宮的墻為*，通路為_，障礙為#int i,j;for(i=0;i<r;i+)mazei0='

7、*'/左面墻mazeil-1='*'/右面墻for(j=1;j<l-1;j+)maze0j='*'/上面墻mazer-1j='*'/下面墻for(i=1;i<r-1;i+)for(j=1;j<l-1;j+)mazeij='_'cout<<"請(qǐng)輸入迷宮內(nèi)障礙物的個(gè)數(shù)："int num;cin>>num;cout<<"請(qǐng)依次輸入障礙物的坐標(biāo)："<<endl;int x,y;for(i=1;i<=num;i+)cin&

8、gt;>x>>y;mazexy='#'cout<<endl<<"創(chuàng)建的迷宮的如下："<<endl<<endl;PrintMaze(r,l);cout<<endl;4 迷宮的路徑的算法int MazePath(PosType start,PosType end)InitStack(S);curpos=start;/ 設(shè)定當(dāng)前位置為入口位置curstep=1;/第一步doif(Pass(curpos)/當(dāng)前位置可以通過(guò)（未曾走過(guò)）FootPrint(curpos);/留下足跡e.ord

9、=curstep;e.seat=curpos;e.di=1;Push(S,e);/加入路徑if(curpos.row=end.row&&curpos.line=end.line)/到達(dá)終點(diǎn)return TRUE;curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰curstep+;/探索下一步/ifelse/當(dāng)前位置不能通過(guò)if(!StackEmpty(S)Pop(S,e);while(e.di=4&&!StackEmpty(S)MarkPrint(e.seat);/留下不能通過(guò)的標(biāo)志Pop(S,e);/退回一步/curstep-;/wh

10、ileif(e.di<4)e.di+;/換下一個(gè)方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/設(shè)定當(dāng)前位置是該新方向上的相鄰塊/if/if/elsewhile(!StackEmpty(S);return FALSE;3)詳細(xì)設(shè)計(jì) 41數(shù)據(jù)類型的定義（1）迷宮類型typedef struct unsigned ord, x, y；short di； ElemType；unsigned x, y, curstep,i=0；char maze1010；（2）棧類型typedef struct Node ElemType data；struct Node*

11、 next； Node, *LinkList；typedef struct LinkList top；unsigned length； LStack；LinkList q；LStack S,T；ElemType e；42主要模塊的算法描述4.1函數(shù)尋找下一個(gè)位置流程圖此函數(shù)的功能是尋找下一個(gè)位置。首先判斷di的值，如果di=1，指針x+，退出。如果di=2，指針y+，退出。如果di=3，指針x-，退出。如果di=4，指針y-，退出。如果di為其它值，則直接退出。見圖4.1。YNYNYYNNdi=1di=2di=3di=4Break；指針x自增；Break；指針y自增；Break；指針x自減；B

12、reak；指針y自減；Break；開始結(jié)束圖4.1 函數(shù)尋找下一個(gè)位置流程圖4.2 函數(shù)銷毀棧流程圖此函數(shù)的功能是銷毀棧，首先建立單鏈表q，判斷top指針是否為空，若為空則釋放s的空間，否則出棧，直到top指針為空，釋放s的空間。見圖4.2。YNLinkList q；判斷棧的top釋放棧s的空間；出棧；開 始結(jié) 束圖4.2 函數(shù)銷毀棧流程圖4.3 函數(shù)出棧流程圖此函數(shù)的功能是出棧。首先建立單鏈表q，如果棧s為空則返回0，若棧s不為空，則出棧，修改指針。返回1。見圖4.3。YNLinkList q；棧s為空出棧；Return 1；Return 0；開 始結(jié) 束圖4.3 函數(shù)出棧流程圖4.4 函數(shù)

13、入棧流程圖此函數(shù)的功能是入棧。首先在鏈表中生成結(jié)點(diǎn)p，判斷p是否為空。若為空則返回0，若非空，則入棧，修改指針，返回0。見圖4.4。YN生成結(jié)點(diǎn)p；!p入棧；Return 1；Return 0；開 始結(jié) 束圖4.4 函數(shù)入棧流程圖4.5 主函數(shù)流程圖主函數(shù)實(shí)現(xiàn)了求解迷宮，首先建立棧s和t，輸出迷宮圖形，然后探索路徑，實(shí)現(xiàn)迷宮求解，最后輸出出迷宮順序。如果有完整路徑則輸出完整路徑，如果沒有完整路徑則輸出無(wú)法通過(guò)信息。見圖4.5。 建立棧S和T； 輸出迷宮圖形； 迷宮求解； 輸出出迷宮順序；結(jié) 束 開 始圖4.5 主函數(shù)流程4)調(diào)試分析（1）有一條完整路徑通過(guò)迷宮的測(cè)試數(shù)據(jù)及結(jié)果。見圖5.1。圖5

14、.1 有一條完整路徑通過(guò)迷宮的測(cè)試數(shù)據(jù)及結(jié)果從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。輸出通路的坐標(biāo)，即出迷宮的順序。（2）沒有路徑能通過(guò)迷宮的測(cè)試數(shù)據(jù)及結(jié)果。見圖5.2。圖5.2 沒有路徑能通過(guò)迷宮的測(cè)試數(shù)據(jù)及結(jié)果從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至前面沒有路徑。輸出此時(shí)無(wú)法通過(guò)，沒有能夠通過(guò)迷宮的路徑的信息！ 5)課程設(shè)計(jì)總結(jié)通過(guò)這次課程設(shè)計(jì)使我充分的理解了用棧實(shí)現(xiàn)迷宮問題的基本原理，知道了棧存儲(chǔ)結(jié)構(gòu)的定義和算法描述，同時(shí)也學(xué)會(huì)了編寫簡(jiǎn)單的迷

15、宮問題的程序。雖然此次的程序不是很完備，但是總體還是一個(gè)比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)能力的程序了，當(dāng)然只是相對(duì)于我這個(gè)初學(xué)者來(lái)說(shuō)。在剛開始編程的時(shí)候，錯(cuò)誤百出，不知道怎么樣改正，但是通過(guò)自己的仔細(xì)的分析和老師的細(xì)心的指導(dǎo)，在認(rèn)真分析了原程序后，終于認(rèn)識(shí)并理解了自己錯(cuò)誤的地方，使自己加以改正，汲取教訓(xùn)。為以后知識(shí)水平的提高，做了最好的準(zhǔn)備。在此我非常要感謝的是我們的指導(dǎo)老師申壽云老師，同時(shí)也要感謝我們的成婭輝老師平時(shí)上課的教導(dǎo)，和編程時(shí)細(xì)心認(rèn)真的輔導(dǎo)，教給我許多知識(shí)。這次課程設(shè)計(jì)能夠順利的完成，當(dāng)然有我個(gè)人的努力，但同時(shí)更離不開指導(dǎo)老師的答疑解惑。6)使用說(shuō)明 先初始化棧，然后增加棧頂，撤銷棧頂，再

16、輸出棧，想出迷宮路徑，最后撤出棧s，制造迷宮7)書寫格式見附帶說(shuō)明。8)附錄a.參考書目1 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）M. 北京：清華大學(xué)出版社，20022 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國(guó)鐵道出版社，2003b.源程序清單（帶注釋）#include <stdio.h>#include <stdlib.h>typedef struct unsigned ord,x,y;/*通道塊在路徑上的序號(hào)和在迷宮中的坐標(biāo)位置*/short di;/* 從此通道塊走向下一通道塊的"方向" */ElemType;typedef struct No

17、de /* 定義單鏈表 */ElemType data;struct Node* next;Node,*LinkList;typedef struct /* 定義鏈棧結(jié)構(gòu) */LinkList top; /* 棧頂指針 */unsigned length; /* 棧中元素個(gè)數(shù) */LStack;void DestroyStack( LStack *S ) /* 銷毀棧 */LinkList q;while ( S->top ) q = S->top;S->top = S->top->next; /* 修改棧頂指針 */free( q );/* 釋放被刪除的結(jié)點(diǎn)空間

18、 */S->length = 0; void InitStack( LStack *S ) /* 構(gòu)造空棧 */S->top = NULL; /* 棧頂指針初值為空 */S->length = 0; /* 空棧中元素個(gè)數(shù)為 0 */ int Pop( LStack *S,ElemType *e ) /* 若棧不空,則刪除 S 的棧頂元素,用 e 返回棧頂元素的值。*/LinkList q;if (!S->top ) return 0;*e=S->top->data; /* 返回棧頂元素 */q=S->top;S->top=S->top-&g

19、t;next; /* 修改棧頂指針 */-S->length;/* 棧的長(zhǎng)度減1 */free(q);/* 釋放被刪除的結(jié)點(diǎn)空間 */return 1; int Push( LStack *S,ElemType e ) /* 在棧頂之上插入元素 e 為新的棧頂元素 */LinkList p=malloc(sizeof *p); /* 建新的結(jié)點(diǎn) */if(!p) return 0; /* 存儲(chǔ)分配失敗 */p->data=e;p->next = S->top; /* 鏈接到原來(lái)的棧頂 */S->top = p; /* 移動(dòng)棧頂指針 */+S->length;

20、 /* 棧的長(zhǎng)度增1 */return 1; void NextPos(unsigned *,unsigned *,short); /* 定位下一個(gè)位置 */int main(void)LStack S,T;unsigned x,y,curstep,i=0;/* 迷宮坐標(biāo),探索步數(shù) */ElemType e;char maze1010 = '#',' ','#','#','#','#','#','#','#','#','#

21、9;,' ',' ','#',' ',' ',' ','#',' ','#','#',' ',' ','#',' ',' ',' ','#',' ','#','#',' ',' ',' ',' ','#

22、9;,'#',' ',' ','#','#',' ','#','#','#',' ',' ',' ',' ','#','#',' ',' ',' ','#',' ',' ',' ',' ','#','#

23、9;,' ','#',' ',' ',' ','#',' ',' ','#','#',' ','#','#','#','#','#','#',' ','#','#','#',' ',' ',' ',' 

24、9;,' ',' ',' ','#','#','#','#','#','#','#','#','#',' ','#',;InitStack(&S);InitStack(&T);printf("迷宮圖形,#號(hào)代表墻壁,空格代表通路:n");for(x=0;x<10;x+) for(y=0;y<10;y+) printf(&quo

25、t;%c",mazexy);printf("n");x=1; /*迷宮起點(diǎn)*/y=0;curstep=1; /* 探索第一步 */do /* 進(jìn)入迷宮 */if(mazeyx=' ') /* 如果當(dāng)前位置可以通過(guò) */mazeyx='1'/* 留下足跡 */e.x=x;e.y=y;e.di=1;e.ord = curstep;if(!Push(&S,e) /* 加入路徑,即壓棧 */fprintf( stderr,"內(nèi)存不足。n" );if(x=8&&y=9) /* 到達(dá)終點(diǎn) */brea

26、k;NextPos(&x, &y, 1); /* 下一位置是當(dāng)前位置的東鄰 */curstep+; else /* 如果當(dāng)前位置不能通過(guò) */if (S.length!=0) Pop(&S,&e);while(e.di = 4 && S.length!=0) mazee.ye.x='0' /* 留下不能通過(guò)足跡 */Pop(&S, &e); /* 退回一步,即出棧 */if(e.di<4)e.di+;if(!Push(&S,e) /* 加入路徑,即壓棧 */fprintf(stderr,"內(nèi)

27、存不足。n");x=e.x; /* 重置坐標(biāo) */y=e.y;NextPos(&x,&y,e.di); /* 尋找下一位置 */while(S.length!=0);printf("走出迷宮路線,1代表走過(guò)的路,0代表試探過(guò)的路徑n");for(x=0;x<10;x+) for(y=0;y<10;y+) printf("%c",mazexy);if(mazexy='1')i+;printf("n");for(x=0;x<i;x+)Pop(&S,&e);Push(&T,e);printf("出迷宮順序,（X坐標(biāo),Y坐標(biāo),前進(jìn)方向）:n");while(T.length!=0)printf("(%d,%d,%d)t",T.top->