任務書1(迷宮問題)

任務書1(迷宮問題)任務書1(迷宮問題)任務書1(迷宮問題)任務書1(迷宮問題)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:課程設計報告課程名稱數據結構課程設計課題名稱迷宮問題專業(yè)信息與計算科學班級1002班學號08姓名田雯指導教師劉洞波×××201

課程設計任務書課程名稱數據結構課程設計課題迷宮問題專業(yè)班級信科1002班學生姓名田雯學號08指導老師劉洞波審批任務書下達日期：2012年任務完成日期：2012年6月16日 目錄 TOC\o"1-2"\h\z\u1問題描述 12需求分析 13概要設計 13．1抽象數據類型定義 13．2模塊劃分 23.3各模塊的調用關系….24詳細設計 24．1數據類型的定義 24．2主要模塊的算法描述 35測試分析 66課程設計總結 7參考文獻 8附錄（源程序清單） 9一、設計內容與設計要求1．設計內容：1）問題描述以一個M*N的長方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出米有通路的結論。2）基本要求a.實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一個坐標的方向。b.編寫遞歸形式的算法，求得迷宮中所有可能的通路。3）測試數據迷宮的測試數據如下：左上角（1,1）為入口，右下角（8,9）為出口。0010001000100010000011010111001000010000010001010111100111000101110000004）實現提示計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則，沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則設定的迷宮沒有通路?？梢远S數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的下標為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。2．設計要求：課程設計報告規(guī)范1)需求分析（1）首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向。否則報告一個無法通過的信息。（2）建立InitStack函數，用于構造一個空棧。（3）建立DestroyStack函數，用于銷毀棧。（4）建立Pop函數，用于刪除棧頂元素，返回棧頂元素的值。（5）建立Push函數，用于插入新的棧頂元素。（6）建立NextPos函數，用于定位下一個位置。2)概要設計3．1抽象數據類型定義（1）棧的抽象數據類型定義InitStack(LStack*S)操作結果：構造一個空棧S。DestroyStack(LStack*S)操作結果：棧S被銷毀。Pop(LStack*S，ElemType*e)操作結果：刪除S的棧頂元素。用e返回棧頂元素的值。若棧為空則返回0。Push(LStack*S，ElemTypee)操作結果：在棧頂之上插入元素e為新的棧頂元素。若棧S為空棧，則返回0。（2）迷宮的抽象數據類型定義NextPos(unsigned*x，unsigned*y，shortdi)操作結果：找到下一個位置。3．2模塊劃分本程序包括三個模塊：（1）主程序模塊voidmain(){初始化；構造迷宮；迷宮求解；迷宮輸出；}（2）棧模塊——實現棧的抽象數據類型（3）迷宮模塊——實現迷宮的抽象數據類型各模塊的調用關系如下：4）求解迷宮的通路的偽碼算法：設定當前位置的處值為入口位置；DO{若當前的位置可通。則{將當前的位置插入棧頂；若該位置為出口位置，則結束；否則切換當前位置的東鄰的為新的當前位置；}否則{若棧不為空且棧的頂位置尚有其他的方向沒有被探索，則設定新的當前位置為沿順時針方向旋轉找到棧頂的位置的下一個相鄰塊；若棧不空但棧頂的四周均不可通過，則{刪去棧頂位置；若棧不為空，則重新測試新的棧頂位置；只至找到一個可通過的塊至?？?；}1坐標的位置的類型typedefstruct{ intline; introw;}PosType;2迷宮類型voidCreatMaze(intr,intl)YNYNYYNNdi=1di=2di=3di=4Break；指針x自增；Break；指針y自增；BreakYNYNYYNNdi=1di=2di=3di=4Break；指針x自增；Break；指針y自增；Break；指針x自減；Break；指針y自減；Break；開始結束YNLinkListq；判斷棧的top釋放棧s的空間；出棧；開始結束YNLinkListq；棧s為空出棧；Return1；Return0；開始結束YN生成結點p；!p入棧；Return1；Return0；開始結束建立棧S和T；輸出迷宮圖形；迷宮求解；輸出出迷宮順序；結束開始[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2002[2]劉振鵬，張曉莉，郝杰．數據結構[M]．北京：中國鐵道出版社，2003b.源程序清單（帶注釋）#include<>#include<>typedefstruct{ unsignedord,x,y;/*通道塊在路徑上的序號和在迷宮中的坐標位置*/ shortdi;/*從此通道塊走向下一通道塊的"方向"*/}ElemType;typedefstructNode{/*定義單鏈表*/ ElemTypedata; structNode*next;}Node,*LinkList;typedefstruct{/*定義鏈棧結構*/ LinkListtop;/*棧頂指針*/ unsignedlength;/*棧中元素個數*/}LStack;voidDestroyStack(LStack*S)/*銷毀棧*/{ LinkListq; while(S->top) { q=S->top; S->top=S->top->next;/*修改棧頂指針*/ free(q);/*釋放被刪除的結點空間*/ } S->length=0;}voidInitStack(LStack*S)/*構造空棧*/{ S->top=NULL;/*棧頂指針初值為空*/ S->length=0;/*空棧中元素個數為0*/}intPop(LStack*S,ElemType*e){/*若棧不空,則刪除S的棧頂元素,用e返回棧頂元素的值。*/ LinkListq; if(!S->top) { return0; } *e=S->top->data;/*返回棧頂元素*/ q=S->top; S->top=S->top->next;/*修改棧頂指針*/ --S->length;/*棧的長度減1*/ free(q);/*釋放被刪除的結點空間*/ return1;}intPush(LStack*S,ElemTypee){/*在棧頂之上插入元素e為新的棧頂元素*/ LinkListp=malloc(sizeof*p);/*建新的結點*/ if(!p) { return0;/*存儲分配失敗*/ } p->data=e; p->next=S->top;/*鏈接到原來的棧頂*/ S->top=p;/*移動棧頂指針*/ ++S->length;/*棧的長度增1*/ return1;}voidNextPos(unsigned*,unsigned*,short);/*定位下一個位置*/intmain(void){ LStackS,T; unsignedx,y,curstep,i=0;/*迷宮坐標,探索步數*/ ElemTypee; charmaze[10][10]= { {'#','','#','#','#','#','#','#','#','#'}, {'#','','','#','','','','#','','#'}, {'#','','','#','','','','#','','#'}, {'#','','','','','#','#','','','#'}, {'#','','#','#','#','','','','','#'}, {'#','','','','#','','','','','#'}, {'#','','#','','','','#','','','#'}, {'#','','#','#','#','#','#','#','','#'}, {'#','#','','','','','','','','#'}, {'#','#','#','#','#','#','#','#','','#'}, }; InitStack(&S); InitStack(&T); printf("迷宮圖形,#號代表墻壁,空格代表通路:\n"); for(x=0;x<10;x++) { for(y=0;y<10;y++) printf("%c",maze[x][y]); printf("\n"); } x=1;/*迷宮起點*/ y=0; curstep=1;/*探索第一步*/ do{/*進入迷宮*/ if(maze[y][x]=='') {/*如果當前位置可以通過*/ maze[y][x]='1';/*留下足跡*/ =x; =y; =1; =curstep; if(!Push(&S,e)) {/*加入路徑,即壓棧*/ fprintf(stderr,"內存不足。\n"); } if(x==8&&y==9) {/*到達終點*/ break; } NextPos(&x,&y,1);/*下一位置是當前位置的東鄰*/ curstep++; } else{/*如果當前位置不能通過*/ if!=0) { Pop(&S,&e); while==4&&!=0) { maze[][]='0';/*留下不能通過足跡*/ Pop(&S,&e);/*退回一步,即出棧*/ } if<4) { ++; if(!Push(&S,e)) {/*加入路徑,即壓棧*/ fprintf(stderr,"內存不足。\n"); } x=;/*重置坐標*/ y=; NextPos(&x,&y,;/*尋找下一位置*/ } } } } while!=0); printf("走出迷宮路線,1代表走過的路,0代表試探過的路徑\n"); for(x=0;x<10;x++) { for(y=0;y<10;y++) { printf("%c",maze[x][y]); if(maze[x][y]=='1') i++; } printf("\n"); } for(x=0;x<i;x++) { Pop(&S,&e); Push(&T,e); } printf("出迷宮順序,（X坐標,Y坐標,前進方向）:\n"); while!=0) { printf("(%d,%d,%d)\t",>,>,>; Pop(&T,&e); } DestroyStack(&S); getchar(); return0;}voidNextPos(unsigned*x,unsigned*y,shortdi)/*定位下一個位置*/{ switch(di) { case1:++(*x); break; case2:++(*y); break; case3:--(*x); break; case4:--(*y); break; default: break; }}考核方式指導老師負責驗收程序的運行結果，并結合學生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學的課程設計成績。具體考核標準包含以下幾