云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)4
《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)4》由會(huì)員分享，可在線閱讀，更多相關(guān)《云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)4（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
實(shí)驗(yàn)難度： A □ B □ C □序號(hào) 學(xué)號(hào) 姓名 成績(jī)指導(dǎo)教師 （簽名）學(xué) 期： 2017 秋季學(xué)期 任課教師: 實(shí)驗(yàn)題目: 組員及組長(zhǎng): 承擔(dān)工作： 聯(lián)系電話: 電子郵件: 完成提交時(shí)間： 年 月 日云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告一、 【實(shí)驗(yàn)構(gòu)思（Conceive ） 】(10%)（本部分應(yīng)包括：描述實(shí)驗(yàn)實(shí)現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程序設(shè)計(jì)等相關(guān)知識(shí)，對(duì)問(wèn)題進(jìn)行概要性地分析）首先輸入迷宮數(shù)據(jù)，在計(jì)算機(jī)的屏幕上顯示一個(gè) 8 行 8 列的矩陣表示迷宮。矩陣中的每個(gè)數(shù)據(jù)或?yàn)橥罚ㄒ?0 表示），或?yàn)閴Γㄒ?1 表示），所求路徑必須是簡(jiǎn)單路徑，即在求得的路徑上不能重復(fù)出現(xiàn)同一道塊。假設(shè)以棧 S 記錄“當(dāng)前路徑” ，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊” 。由此， “納入路徑”的操作為“當(dāng)前位置入?！?；從當(dāng)前路徑刪除前一通道塊的操作為“出棧” 。若找到出口，則從棧中彈出數(shù)據(jù)，在屏幕上顯示從入口到出口的路徑坐標(biāo)。二、 【實(shí)驗(yàn)設(shè)計(jì)(Design)】(20%)（本部分應(yīng)包括：抽象數(shù)據(jù)類(lèi)型的定義和基本操作說(shuō)明，程序包含的模塊以及各模塊間的調(diào)用關(guān)系，關(guān)鍵算法偽碼描述及程序流程圖等，如有界面則需包括界面設(shè)計(jì)，功能說(shuō)明等）1、定義坐標(biāo)（X， Y）:struct Coor {int row; int column; int direction; }; 2、定義方向：struct Move {int row;int column;};3、定義/鏈表結(jié)點(diǎn)：struct LinkNode {Coor data;LinkNode *next;};4、定義棧：class stack{private:LinkNode *top; public:stack(); ~stack(); void Push(Coor data); Coor Pop(); Coor GetPop(); void Clear(); bool IsEmpty(); };5.流程圖：三、 【實(shí)現(xiàn)（Implement） 】(30%)（本部分應(yīng)包括：抽象數(shù)據(jù)類(lèi)型各操作的具體實(shí)現(xiàn)代碼、 關(guān)鍵操作的具體算法實(shí)現(xiàn)、 函數(shù)實(shí)現(xiàn)，主程序?qū)崿F(xiàn)等，并給出關(guān)鍵算法的時(shí)間復(fù)雜度分析。如有界面則需包括界面的關(guān)鍵實(shí)現(xiàn)方法等。 ）1.定義迷宮定義移動(dòng)的 4 個(gè)方向：Move move[4]={{0,1},{1,0},{0,-1},{-1,0}};2.幾個(gè)函數(shù)功能的描述:stack(); //構(gòu)造函數(shù)，置空棧~stack(); //析構(gòu)函數(shù)void Push(Coor data); //把元素 data 壓入棧中Coor Pop(); //使棧頂元素出棧Coor GetPop(); //取出棧頂元素void Clear(); //把棧清空bool IsEmpty(); //判斷棧是否為空bool Mazepath(int **maze,int m,int n); //尋找迷宮 maze 中從（0 ， 0）到（m,n ）的路徑//到則返回 true,否則返回 falsevoid PrintPath(stack p); //輸出迷宮的路徑void PrintPath2(int m,int n,stack p,int **maze); //輸出路徑void Restore(int **maze,int m,int n); //恢復(fù)迷宮3.主函數(shù)實(shí)現(xiàn)：int main(){system("color f5");int m=0,n=0;int **maze; //定義二維指針存取迷宮cout ='0'&&ch=1) cout#include#include#define true 1#define false 0using namespace std;struct Coor //定義描當(dāng)前位置的結(jié)構(gòu)類(lèi)型{int row;int column;int direction;};struct Move //定義下一個(gè)位置的方向{int row;int column;};struct LinkNode //鏈表結(jié)點(diǎn){Coor data;LinkNode *next;};class stack //定義棧{private:LinkNode *top;public:stack(); //構(gòu)造函數(shù)，置空棧~stack(); //析構(gòu)函數(shù)void Push(Coor data); //把元素 data 壓入棧中Coor Pop(); //使棧頂元素出棧Coor GetPop(); //取出棧頂元素void Clear(); //把棧清空int IsEmpty(); //判斷棧是否為空};stack::stack() //構(gòu)造函數(shù)，置空棧{top=NULL;}stack::~stack() //析構(gòu)函數(shù){}void stack::Push(Coor x)//把元素 data 壓入棧中{LinkNode *TempNode;TempNode=new LinkNode;TempNode->data=x;TempNode->next=top;top=TempNode;}Coor stack::Pop() //使棧頂元素出棧{Coor Temp;LinkNode *TempNode;TempNode=top;top=top->next;Temp=TempNode->data;delete TempNode;return Temp;}Coor stack::GetPop() //取出棧頂元素{return top->data;}void stack::Clear() //清空棧{top=NULL;}int stack::IsEmpty() //判斷是否空棧{if(top==NULL)return true;elsereturn false;}Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定義移動(dòng)的 4 個(gè)方向int Mazepath(int **maze,int m,int n); //尋找迷宮 maze 中從（ 0，0）到（m,n ）的路徑，找到則返回 true,否則返回 falsevoid PrintPath(stack p); //輸出迷宮的路徑void PrintPath2(int m,int n,stack p,int **maze); //輸出路徑void Restore(int **maze,int m,int n); //恢復(fù)迷宮int** GetMaze(int //獲取迷宮//返回存取迷宮的二維指針int main(){system("color f5");int m=0,n=0;int **maze; //定義二維指針存取迷宮cout >a>>b;cout>maze[i][j];//給迷宮的四周加一堵墻，即把迷宮四周定義為 1for(i=0;i=1)cout>choose;if(choose=='1'){PrintPath(p); //坐標(biāo)顯示輸出Restore(maze,m,n);}else{PrintPath2(m,n,p,maze); //矩陣顯示輸出Restore(maze,m,n);}return 1; //表示成功找到路徑}}if(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().column)//如果沒(méi)有新位置入棧，則返回到上一個(gè)位置{p.Pop();q.Pop();}}return 0; //表示查找失敗，即迷宮無(wú)路經(jīng)}void PrintPath(stack p) //輸出路徑{coutdata=p.Pop(); //取棧 p 的頂點(diǎn)元素，即第一個(gè)位置t.Push(temp->data); //第一個(gè)位置入棧 tdelete temp; //釋放空間while(!p.IsEmpty()) //棧 p 非空，則反復(fù)轉(zhuǎn)移{temp=new LinkNode;temp->data=p.Pop(); //獲取下一個(gè)位置//得到行走方向a=t.GetPop().row-temp->data.row; //行坐標(biāo)方向b=t.GetPop().column-temp->data.column;//列坐標(biāo)方向if(a==1) temp->data.direction=1; //方向向下，用 1 表示else if(b==1) temp->data.direction=2; //方向向右，用 2 表示else if(a==-1) temp->data.direction=3;//方向向上，用 3 表示else if(b==-1) temp->data.direction=4;//方向向左，用 4 表示t.Push(temp->data); //把新位置入棧delete temp;}cout<<"坐標(biāo)（row,column,direction）中 x 在指向當(dāng)前位置所在的行數(shù)，y 指向當(dāng)前位置所在的列數(shù)，";cout<<"direction 表示下一位置走向。"<下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
10 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 云南大學(xué) 軟件 學(xué)院 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)
裝配圖網(wǎng)所有資源均是用戶(hù)自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶(hù)書(shū)面授權(quán)，請(qǐng)勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://www.820124.com/p-359757.html