數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言課程設(shè)計(jì)報(bào)告

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：迷宮求解專(zhuān) 業(yè) 機(jī)電一體化 班 級(jí) 08專(zhuān)接本 學(xué) 生 學(xué) 號(hào) 1 指導(dǎo)教師 高在村 完成時(shí)間 2011. 5 目錄 一.實(shí)驗(yàn)內(nèi)容3二.需求分析3三總體設(shè)計(jì)3四詳細(xì)設(shè)計(jì)5五代碼9六.測(cè)試14七. 總結(jié)16參考文獻(xiàn)17一.實(shí)驗(yàn)內(nèi)容任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：界面友好，函數(shù)功能要?jiǎng)澐趾?；總體設(shè)計(jì)應(yīng)畫(huà)一流程圖；程序要加必要的注釋?zhuān)灰峁┏绦蛟O(shè)計(jì)方案；程序一定要經(jīng)得起測(cè)試；寧可功能少一點(diǎn)，也要能運(yùn)行起來(lái)，不能運(yùn)行的程序是沒(méi)有價(jià)值的。二.需求分析1.可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走

2、出迷宮的路徑，并將路徑輸出；要求：使用非遞歸算法。2.用戶(hù)可以根據(jù)自己的需求進(jìn)行輸入所需的迷宮，其中1表示迷宮的墻壁，0表示迷宮的通路，從而建立自己的迷宮；3.用戶(hù)還可以自己設(shè)計(jì)迷宮的入口坐標(biāo)，當(dāng)然也可以設(shè)計(jì)出口了；4.程序執(zhí)行的命令包括：（1）構(gòu)造棧Stack, T 描述迷宮中當(dāng)前位置的結(jié)構(gòu)類(lèi)型, LinkNode鏈表結(jié)點(diǎn)三個(gè)類(lèi),其中Stack是Linknode的友元類(lèi). （2）構(gòu)造存取迷宮的二維指針GetMaze(int &m,int &n) （3）恢復(fù)迷宮Restore(int *maze,int m,int n) （4）在迷宮中尋找一條通路Mazepath(int *m

3、aze,int m,int n) （5）輸出所找到的通路PrintPath() (6) 定義當(dāng)前位置移動(dòng)的4個(gè)方向move數(shù)組.三總體設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)：首先用二維指針存儲(chǔ)迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶(hù)輸入。一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向（東、南、西、北四個(gè)方向所用代表數(shù)字，自行定義）。1從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的

4、迷宮沒(méi)有通路。迷宮的入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m，n）。為處理方便起見(jiàn)，可在迷宮的四周加一圈障礙。對(duì)于迷宮的任一位置，均可約定有東、南、西、北四個(gè)方向可通。經(jīng)過(guò)的位置把0變?yōu)?1，帶輸出迷宮路徑后在恢復(fù)迷宮院士為止2. 本程序有三個(gè)模塊： 主程序模塊 三個(gè)類(lèi)模塊即其對(duì)象：實(shí)現(xiàn)棧鏈表抽象數(shù)據(jù)類(lèi)型； 迷宮二維指針單元模塊：存儲(chǔ)迷宮,尋路徑,輸出迷宮,恢復(fù)迷宮。(二)流程圖存取迷宮GetMaze(int &m,int &n)求取一條路徑MazePath（）if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetP

5、op().y)輸入迷宮的長(zhǎng)和寬內(nèi)容顯示結(jié)果Printpath（）迷宮無(wú)路經(jīng) END數(shù)組move用于更改方向,函數(shù)Push, PrintPath, Restore調(diào)用函數(shù)GetPop, Push,Pop恢復(fù)迷宮Restore()調(diào)用四詳細(xì)設(shè)計(jì)(一).基本算法：首先用二維指針存儲(chǔ)迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶(hù)輸入。一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向（東、南、西、北四個(gè)方向所用代表數(shù)字，自行定義）。迷宮的過(guò)程可以模擬為一個(gè)搜索的過(guò)程：每到一處，總讓它按東、南、西、北4

6、個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過(guò)，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果4方向都走不通或曾經(jīng)到達(dá)過(guò)，則退回一步，在原來(lái)的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說(shuō)明找到了一條通路；若退回到了入口處，則說(shuō)明不存在通路。用一個(gè)二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點(diǎn)在位置（1，1）處，出口點(diǎn)在位置（m,n）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的外墻；第1行第1列元素和第m行第

7、m列元素置成“0”， 表示迷宮的入口和出口；其余元素值用GetMaze函數(shù)獲取.假設(shè)當(dāng)前所在位置是（x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有4。如果用二維數(shù)組move記錄4方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move數(shù)組確定： x=x+moveloop0 y=y+moveloop1從迷宮的入口位置開(kāi)始，沿圖示方向順序依次進(jìn)行搜索。定義一個(gè)棧，按從入口到出口存取路徑.在搜索過(guò)程中，每前進(jìn)一步，如果有新位置入棧，則把上一個(gè)探索的位置存入棧中,當(dāng)前位置”-1”（表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。如果沒(méi)有新位置入棧，則返回到上一個(gè)

8、位置.到達(dá)出口后,最后一個(gè)位置入棧,輸出路徑,并回復(fù)路徑.把-1變?yōu)?.總之,入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。迷宮的入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m，n）。為處理方便起見(jiàn)，可在迷宮的四周加一圈障礙。對(duì)于迷宮的任一位置，均可約定有東、南、西、北四個(gè)方向可通。(二). 為實(shí)現(xiàn)算法，需要類(lèi)的象數(shù)據(jù)類(lèi)型：類(lèi)及其對(duì)象:類(lèi) Stack 對(duì)象成員如下:Stack(); 構(gòu)造函數(shù)，置空棧操作結(jié)果：構(gòu)造一個(gè)空的棧S。Stack(); 析構(gòu)函數(shù)

9、void Push(T e); 把元素data壓入棧中T Pop(); 使棧頂元素出棧 T GetPop(); 取出棧頂元素 void Clear(); 把棧清空 bool empty(); 判斷棧是否為空，如果為空則返回1，否則返回0T類(lèi) 迷宮中當(dāng)前位置的結(jié)構(gòu)類(lèi)型: T對(duì)象成員如下:x; x代表當(dāng)前位置的行坐標(biāo)y; y代表當(dāng)前位置的列坐標(biāo)dir; 0:無(wú)效,1:東,2:南,3:西,4:北LinkNode類(lèi) 鏈表結(jié)點(diǎn): 對(duì)象成員如下:友元類(lèi) StackT dataLinkNode *next(三).函數(shù)調(diào)用關(guān)系main GetMaze Mazepath Empy() GetPop() Push

10、() PrintPath() Restore() Pop() GetPop() Push()(四) 算法的時(shí)間、空間復(fù)雜度1）本算法在空間上主要開(kāi)辟了一個(gè)二維指針，規(guī)模都是迷宮(m+2)*(n+2)，一個(gè)是棧，一個(gè)是迷宮路徑記錄，輸出時(shí)候調(diào)用棧，在恢復(fù)迷宮。2）在時(shí)間上為簡(jiǎn)單的鏈表?xiàng)５拇鎯?chǔ)結(jié)構(gòu)，二維指針GetMaze, Restore兩函數(shù)算法時(shí)間復(fù)雜度為O（(m+2)*(n+2)）, Mazepath,PrintPath為O(1),（m為行數(shù)，n為列數(shù)）。(五) UML圖T+X:int+y:int+dir:int LinkNode+T dataStack+push(T e):void+T G

11、etpop ( ):void+T pop ( )+empty ( ):bool+Stack ( )+Stack ( )+Clear ( ):void+nextLinkNodeLinkNode-top<<friend>>五代碼/*以一個(gè)m×n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。 首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對(duì)于下

12、列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），。*/#include<iostream>using namespace std;class T /定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類(lèi)型public: int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int dir; /0:無(wú)效,1:東,2:南,3:西,4:北;class LinkNode /鏈表結(jié)點(diǎn) friend class Stack;public: T data; LinkNode *next;class Stackprivate: Li

13、nkNode *top; /指向第一個(gè)結(jié)點(diǎn)的棧頂指針public: Stack(); /構(gòu)造函數(shù)，置空棧 Stack(); /析構(gòu)函數(shù) void Push(T e); /把元素data壓入棧中 T Pop(); /使棧頂元素出棧 T GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool empty(); /判斷棧是否為空，如果為空則返回1，否則返回0;Stack:Stack() /構(gòu)造函數(shù)，置空棧 top=NULL;Stack:Stack() /析構(gòu)函數(shù)void Stack:Push(T e) /把元素x壓入棧中 LinkNode *P; P=new LinkN

14、ode; P->data=e; P->next=top; top=P;T Stack:Pop() /使棧頂元素出棧 T Temp; LinkNode *P; P=top; top=top->next; Temp=P->data; delete P; return Temp;T Stack:GetPop() /取出棧頂元素 return top->data;void Stack:Clear() /把棧清空 top=NULL;bool Stack:empty() /判斷棧是否為空，如果為空則返回1，否則返回0 if(top=NULL) return 1; else r

15、eturn 0;int move42=0,1,1,0,0,-1,-1,0; /定義當(dāng)前位置移動(dòng)的4個(gè)方向bool Mazepath(int *maze,int m,int n); /尋找迷宮maze中從（0，0）到（m,n）的路徑 /到則返回true,否則返回falsevoid PrintPath(Stack p); /輸出迷宮的路徑void Restore(int *maze,int m,int n); /恢復(fù)迷宮int* GetMaze(int &m,int &n); /獲取迷宮 /返回存取迷宮的二維指針int main() int m=0,n=0; /定義迷宮的長(zhǎng)和寬 i

16、nt *maze; /定義二維指針存取迷宮 maze=GetMaze(m,n); /調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮 if(Mazepath(maze,m,n) /調(diào)用Mazepath(int *maze,int m,int n)函數(shù)獲取路徑 cout<<"迷宮路徑探索成功!n" else cout<<"路徑不存在!n" return 0;int* GetMaze(int &m,int &n)/返回存取迷宮的二維指針 int *maze; /定義二維指針存取迷宮 int

17、 i=0,j=0; cout<<"請(qǐng)輸入迷宮的長(zhǎng)和寬:" int a,b;cin>>a>>b; /輸入迷宮的長(zhǎng)和寬 cout<<"請(qǐng)輸入迷宮內(nèi)容:n" m=a; n=b; /m,n分別代表迷宮的行數(shù)和列數(shù) maze=new int *m+2; /申請(qǐng)長(zhǎng)度等于行數(shù)加2的二級(jí)指針 for(i= 0;i<m+2;i+) /申請(qǐng)每個(gè)二維指針的空間 mazei=new intn+2; for(i=1;i<=m;i+) /輸入迷宮的內(nèi)容，0代表可通，1代表不通 for(j=1;j<=n;j+) cin

18、>>mazeij; for(i=0;i<m+2;i+) mazei0=mazein+1=1; for(i=0;i<n+2;i+) maze0i=mazem+1i=1; return maze; /返回存貯迷宮的二維指針maze;bool Mazepath(int *maze,int m,int n)/尋找迷宮maze中從（0，0）到（m,n）的路徑 /到則返回true,否則返回false Stack q,p; /定義棧p、q,分別存探索迷宮的過(guò)程和存儲(chǔ)路徑 T Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push

19、(Temp1); /將入口位置入棧 p.Push(Temp1); maze11=-1; /標(biāo)志入口位置已到達(dá)過(guò) while(!q.empty() /棧q非空，則反復(fù)探索 Temp2=q.GetPop(); /獲取棧頂元素 if(!(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個(gè)探索的位置存入棧p for(loop=0;loop<4;loop+) /探索當(dāng)前位置的4個(gè)相鄰位置 x=Temp2.x+moveloop0; /計(jì)算出新位置x位置值 y=Temp

20、2.y+moveloop1; /計(jì)算出新位置y位置值 if(mazexy=0) /判斷新位置是否可達(dá) Temp1.x=x; Temp1.y=y; mazexy=-1; /標(biāo)志新位置已到達(dá)過(guò) q.Push(Temp1); /新位置入棧 if(x=(m)&&(y=(n) /成功到達(dá)出口 Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); /把最后一個(gè)位置入棧 PrintPath(p); /輸出路徑 Restore(maze,m,n); /恢復(fù)路徑 return 1; /表示成功找到路徑 if(p.GetPop().x=q.GetPop

21、().x&&p.GetPop().y=q.GetPop().y) /如果沒(méi)有新位置入棧，則返回到上一個(gè)位置 p.Pop(); q.Pop(); return 0; /表示查找失敗，即迷宮無(wú)路經(jīng)void PrintPath(Stack p) /輸出路徑 cout<<"迷宮的路徑為n" cout<<"括號(hào)內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)n" Stack t; /定義一個(gè)棧，按從入口到出口存取路徑 int a,b; T data; LinkNode *temp; temp=new LinkNode;

22、 /申請(qǐng)空間 temp->data=p.Pop(); /取棧p的頂點(diǎn)元素，即第一個(gè)位置 t.Push(temp->data); /第一個(gè)位置入棧t delete temp; /釋放空間 while(!p.empty() /棧p非空，則反復(fù)轉(zhuǎn)移 temp=new LinkNode; temp->data=p.Pop(); /獲取下一個(gè)位置 /得到行走方向 a=t.GetPop().x-temp->data.x; /行坐標(biāo)方向 b=t.GetPop().y-temp->data.y; /列坐標(biāo)方向 if(a=1) temp->data.dir=1; /方向向下，

23、用1表示 else if(b=1) temp->data.dir=2; /方向向右，用2表示 else if(a=-1) temp->data.dir=3; /方向向上，用3表示 else if(b=-1) temp->data.dir=4; /方向向左，用4表示 t.Push(temp->data); /把新位置入棧 delete temp; /輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個(gè)位置方向 while(!t.empty() /棧非空，繼續(xù)輸出 data=t.Pop(); cout<<'('<<data.x<<'

24、;,'<<data.y<<','<<data.dir<<"," /輸出行坐標(biāo)，列坐標(biāo) switch(data.dir) /輸出相應(yīng)的方向 case 1:cout<<")n"break; case 2:cout<<")n"break; case 3:cout<<")n"break; case 4:cout<<")n"break; case 0:cout<<")n"break; void Restore(int *maze,int m,int n