迷宮數(shù)據(jù)結(jié)構(gòu)

1、實(shí)驗(yàn)報(bào)告題目：設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。一、需求分析1 .以二維數(shù)組mazeNN表示迷宮，數(shù)組中以元素值0表示通路，1表示障礙，限定迷宮大小N<100o2 .第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第2行到第m+1為迷宮值，同一行兩個(gè)數(shù)字之間用空格表示。3 .實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型。4 .編寫一個(gè)求解迷宮的非遞歸程序。5 .迷宮的入口位置和出口位置可由用戶自己設(shè)定6 .本程序只求出一條成功的通路求得的通路以三元組(i,j,d)的形式輸出，其中：(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。7 .測(cè)試數(shù)據(jù)：迷宮的測(cè)

2、試數(shù)據(jù)如下：左上角(1,1)為入口，右下角(9,8)為出口0010001000100010000011010111001000010000010001010111100111000101110000008.程序執(zhí)行的命令為：1)創(chuàng)建迷宮；2)求解迷宮；3)輸出迷宮的解。二、概要設(shè)計(jì)擬采用棧來保存從入口到當(dāng)前位置的路徑，并采用“窮舉求解”的方法進(jìn)行求解。程序中將涉及到以下抽象數(shù)據(jù)類型：1 .設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack數(shù)據(jù)對(duì)象：D=ai|aCharSet,i=1,2,n,n-0數(shù)據(jù)關(guān)系：R1=：二2二,2歸，日D,i=2,，n基本操作：InitStack(StackSq*S)操作結(jié)

3、果：構(gòu)造一個(gè)空棧SoStackEmpty(StackSq*S)初始條件：棧S已存在。操作結(jié)果:若S為空棧，則返回TRUE,否則返回FALSE。Push(StackSq*S,SElemTypee)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(StackSq*S,SElemType&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。ADTStack2 .設(shè)定迷宮的抽象數(shù)據(jù)類型為：ADTmaze數(shù)據(jù)對(duì)象：D=aij|aiw0,1,2,3,0wiwm1,0<j<n-1R=ROW,COL數(shù)據(jù)關(guān)系：ROL=；a,j,ai,j|ai,j,ai

4、,jD,i=1,.,m,j=0,.,nCOL=二ai,j,ai,j|©D,i=1,.,m,j=0,.,n基本操作：InitMaze(&Maze,row,col)初始條件：用數(shù)組MazeMN表示迷宮，迷宮的數(shù)據(jù)由用戶自己定義，其中自第1行至第M行、每行中自第1列至第1列的元素已有值，并且以值0表示通路，以值1表不'障礙。操作結(jié)果：構(gòu)成迷宮的數(shù)字型數(shù)組，以0表示通路，以1表示障礙。MatePath(&S)初始條件：迷宮S已被賦值。操作結(jié)果：若迷宮S中存在一條通路，則按如下規(guī)定改變迷宮S的狀態(tài)：以2表示路徑上的位置，以3表示死胡同；否則迷宮的狀態(tài)不變。PrintMa

5、ze(Maze)初始條件：迷宮M已經(jīng)存在操作結(jié)果：以數(shù)字形式輸出迷宮。ADTmaze;3 .本程序包括三個(gè)模塊1)主程序模塊：voidmain()初始化；do接受命令；處理命令；while(命令!="退出");2)棧模塊-實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型3)迷宮模塊-實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型各個(gè)模塊之間的調(diào)用關(guān)系如下：主程序模塊->迷宮模塊->棧模塊三.詳細(xì)設(shè)計(jì)1.坐標(biāo)位置類型typedefstructPosType定義坐標(biāo)(intx;/當(dāng)前橫坐標(biāo)inty;當(dāng)前縱坐標(biāo)PosType;2.迷宮類型intMaze;/迷宮存放在一個(gè)數(shù)字型數(shù)組中intMazePath(intmazeN

6、N,PosTypestart,PosTypeend,LinkStack&stack,intn1,intn2)求解迷宮maze中，從入口Start到出口end的一條路徑(stack=NULL;SElemTypee;PosTypecurpos;InitStack(stack);/初始化stackcurpos.x=start.x;設(shè)定當(dāng)前位置為入口位置curpos.y=start.y;intcurstep=1;/探索第一步doif(Pass(curpos,maze,n1,n2)=1)當(dāng)前位置可通FootPrint(curpos,maze);留下足跡e.ord=curstep;e.seat.x

7、=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e);/加入路徑，入棧if(curpos.x=end.x&&curpos.y=end.y)至U達(dá)出口位置return1;elseNextPos(curpos,1);/探索下一步curstep+;/ifelse當(dāng)前位置不能通過if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&&!StackEmpty(stack)(MarkPrint(e.seat,maze);/留下不能通過的標(biāo)記，并退回一步Pop(stack,e);/whilei

8、f(e.di<4)/換下一個(gè)方向探索(e.di+;Push(stack,e);NextPos(e.seat,e.di);設(shè)當(dāng)前位置是該新方向上的相鄰塊，1代表向右,2代表向下，3代表向左，4代表向上。curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return0;voidInitMaze(intMazeNN,intr,intc)初始化迷宮(printf("請(qǐng)輸入迷宮(以0表示可走,1表示有障礙)：n");按照用戶要求輸入一二維數(shù)組來表示迷宮for(inti=0;i<r;i+)for(int

9、j=0;j<c;j+)(scanf("%d",&Mazeij);if(Mazeij!=0&&Mazeij!=1)exit(0);intMarkPrint(PosTypecurpos,intmazeNN)標(biāo)記此處不能走(mazecurpos.xcurpos.y+;return1;2 .棧類型typedefstructmigong(intord;通道塊在路徑上的序號(hào)PosTypeseat;/通道塊在迷宮中坐標(biāo)位置intdi;/從此通道塊走向下一通道塊的方向SElemType;棧數(shù)據(jù)元素的類型typedefstructSNode(SElemTypeS

10、Item;structSNode*next;SNode,*LinkStack;棧的基本操作設(shè)置如下：intInitStack(LinkStack&S)(S=(LinkStack)malloc(sizeof(SNode);/通過malloc函數(shù)分配空間if(!S)return0;/如果分配失敗，則返回0S->next=NULL;return1;voidDestroyStack(LinkStack&S)(LinkStackq;if(S!=NULL)(while(S->next!=NULL)如果棧非空，則釋放空間(q=S->next;if(S->next-&g

11、t;next!=NULL)S->next=S->next->next;elseS->next=NULL;free(q);free(S);S=NULL;voidClearStack(LinkStack&S)(LinkStackq;if(S!=NULL)(while(S->next!=NULL)如果棧非空，則釋放空間(q=S->next;if(S->next->next!=NULL)S->next=S->next->next;elseS->next=NULL;free(q);intStackEmpty(LinkStac

12、kS)(if(S!=NULL)判斷棧是否存在(if(S->next=NULL)(return1;return0;intStackLength(LinkStackS)(intm=0;LinkStackq=S;if(S!=NULL)/判斷棧是否存在(if(q->next!=NULL)/判斷棧是否為空(while(q->next!=NULL)(+m;q=q->next;returnm;return0;)intGetTop(LinkStackS,SElemType&e)(LinkStackq=S;if(S!=NULL)/判斷棧是否存在(if(q->next!=NU

13、LL)判斷棧是否為空(while(q->next!=NULL)(q=q->next;)e=q->SItem;return1;)return0;如果不能得到數(shù)據(jù)元素，則返回0(false)intPush(LinkStack&S,SElemTypee)(LinkStackq=S;LinkStackm=(LinkStack)malloc(sizeof(SNode);通過malloc函數(shù)分配空間if(S!=NULL)(while(q->next!=NULL)(q=q->next;)m->SItem=e;m->next=NULL;q->next=m

14、;)return0;)intPop(LinkStack&S,SElemType&e)(LinkStackq=S;if(S!=NULL)if(q->next!=NULL)/若棧不是空的(while(q->next->next!=NULL)(q=q->next;)e=q->next->SItem;q->next=NULL;return1;)return0;)intStackTraverse(LinkStackS)/依次輸出從棧底到棧頂?shù)拿總€(gè)元素(if(S!=NULL)(LinkStackq=S;if(q->next!=NULL)/若棧

15、不是空的(printf("n依次輸出從棧底到棧頂?shù)拿總€(gè)元素為：n");while(q->next!=NULL)(q=q->next;printf("%d",q->SItem);)printf("n");return1;)return0;)3 .求解迷宮路徑的代碼intMazePath(intmazeNN,PosTypestart,PosTypeend,LinkStack&stack,intn1,intn2)求解迷宮maze中，從入口Start到出口end的一條路徑(stack=NULL;SElemTypee;

16、PosTypecurpos;InitStack(stack);/初始化stackcurpos.x=start.x;設(shè)定當(dāng)前位置為入口位置curpos.y=start.y;intcurstep=1;/探索第一步if(Pass(curpos,maze,n1,n2)!=1)判斷初始方塊是否是障礙物return0;elsedoif(Pass(curpos,maze,n1,n2)=1)當(dāng)前位置可通FootPrint(curpos,maze);留下足跡e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e);加入路徑，入棧

17、if(curpos.x=end.x&&curpos.y=end.y)至U達(dá)出口位置return1;elseNextPos(curpos,1);/探索下一步curstep+;/ifif(!StackEmpty(stack)else當(dāng)前位置不能通過Pop(stack,e);while(e.di=4&&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通過的標(biāo)記，并退回一步Pop(stack,e);/whileif(e.di<4)/換下一個(gè)方向探索e.di+;Push(stack,e);NextPos(e.seat,e.

18、di);/設(shè)當(dāng)前位置是該新方向上的相鄰塊curpos.x=e.seat.x;curpos.y=e.seat.y;)while(!StackEmpty(stack);return0;4 .主函數(shù)和其他函數(shù)的代碼voidmain()intm,n;intmazeNN=0;LinkStackS;PosTypestart,end;intcmd;for(inti;i+)printf("nn");printf("1.創(chuàng)建迷宮：n");printf("2.退出n");printf("n");printf("請(qǐng)輸入選擇：n

19、");scanf("%d",&cmd);switch(cmd)case1:printf("請(qǐng)輸入迷宮的行數(shù)和列數(shù)：n");scanf("%d%d",&m,&n);InitMaze(maze,m,n);迷宮初始化printf("請(qǐng)輸入起點(diǎn)坐標(biāo)：n");scanf("%d%d",&start.x,&start.y);start.x-;start.y-;printf("請(qǐng)輸入出口坐標(biāo)：n");scanf("%d%d&quo

20、t;,&end.x,&end.y);end.x-;end.y-;printf("迷宮為n");PrintMaze(maze,m,n);/輸出初始迷宮if(MazePath(maze,start,end,S,m,n)printf("走出迷宮的路徑為：n");StackTraverse(S);else(printf("此迷宮無通路！n");)printf("此時(shí)路徑在迷宮中(用2標(biāo)記表示可通路徑，用3表示死胡同)顯示為：n");PrintMaze(maze,m,n);/輸出改變狀態(tài)的迷宮break;ca

21、se2:exit(0);break;default:exit(0);break;)DestroyStack(S);)intPass(PosTypeseat,intmazeNN,intn1,intn2)/檢查當(dāng)前通道塊是否可通(if(mazeseat.xseat.y=0&&seat.x<n1&&seat.x>=0&&seat.y<n2&&seat.y>=0)return1;elsereturn0;intFootPrint(PosTypecurpos,intmazeNN)(mazecurpos.xcurpos.

22、y=2;return1;voidNextPos(PosType&curpos,inti)/轉(zhuǎn)換至下一個(gè)位置(if(i=1)curpos.y+;elseif(i=2)curpos.x+;elseif(i=3)curpos.y-;elseif(i=4)curpos.x-;intMarkPrint(PosTypecurpos,intmazeNN)/標(biāo)記此處不能走(mazecurpos.xcurpos.y+;return1;5.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)主程序IlaxepathKInitStackPushPopStackE*ptyNewtPos2、 調(diào)試分析1 .此次作業(yè)有一個(gè)核

23、心算法，就是求迷宮的路徑，在調(diào)試過程中一開始沒有及時(shí)更新當(dāng)前位置導(dǎo)致死循環(huán)，后來在判斷該方塊是否在當(dāng)前路徑上出錯(cuò)，在調(diào)試起點(diǎn)位置為障礙物時(shí)出現(xiàn)了錯(cuò)誤，因此還要再加入判斷初始方塊是否為障礙物才能進(jìn)行下面的操作，另外就是一些語法小錯(cuò)誤。2 .StackTravers在調(diào)試過程中可以插入在MazeParh中，以察看求解迷宮過程走的路徑是否正確。3 .本題中三個(gè)主要算法：InitMaze,MazePath和PrintMaze時(shí)間復(fù)雜度均為O(mMn),本題的空間復(fù)雜度亦為O(mn)4 .經(jīng)驗(yàn)體會(huì)：借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，可以加快找好到程序中的錯(cuò)誤和瑕疵。3、 用戶手冊(cè)1 .本程序的運(yùn)行環(huán)境Windows操作系統(tǒng)，執(zhí)彳T文件為：Maze.cpp2 .進(jìn)入演示程序后，顯示用戶界面為：3.鍵入“1創(chuàng)建迷宮”的命令后，就可以按提示創(chuàng)建迷宮如圖:創(chuàng)建迷宮二2”退出請(qǐng)輸A選擇:量輸入迷宮的行數(shù)和列數(shù)：3 3請(qǐng)輸入迷宮以目表示可走.工表示有障礙）:S011M1諳輸入起點(diǎn)坐標(biāo)：11情輸入出口坐標(biāo)：33迷宮為0011011005.程序收到迷宮后開始求解路徑，如圖:走出迷宮的路徑為:第1步第2步:122第