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