云南大學(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ì)問題進(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ù)類型的定義和基本操作說明,程序包含的模塊以及各模塊間的調(diào)用關(guān)系,關(guān)鍵算法偽碼描述及程序流程圖等,如有界面則需包括界面設(shè)計(jì),功能說明等)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 stackprivate: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ù)類型各操作的具體實(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 move4=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)類型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 move4=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 ab;coutmazeij;/給迷宮的四周加一堵墻,即把迷宮四周定義為 1for(i=0;i=1)coutchoose;if(choose=1)PrintPath(p); /坐標(biāo)顯示輸出Restore(maze,m,n);elsePrintPath2(m,n,p,maze); /矩陣顯示輸出Restore(maze,m,n);return 1; /表示成功找到路徑if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column)/如果沒有新位置入棧,則返回到上一個(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ù),;coutdirection 表示下一位置走向。endl;/輸出路徑,包括行坐標(biāo),列坐標(biāo),下一個(gè)位置方向while(!t.IsEmpty() /棧非空,繼續(xù)輸出data=t.Pop();cout(data.row,data.column,data.direction,; /輸出行坐標(biāo),列坐標(biāo)switch(data.direction) /輸出相應(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 PrintPath2(int m,int n,stack p,int *maze)/輸出路徑cout迷宮的路徑為n;for (int i = 0; i m+2; +i )for (int j = 0; j n+2; +j)cout mazeij ;cout endl;void Restore(int *maze,int m,int n)/恢復(fù)迷宮int i,j;for(i=0;im+2;i+) /遍歷指針for(j=0;jn+2;j+)if(mazeij=8) /恢復(fù)探索過位置,即把-1 恢復(fù)為 0mazeij=0;- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 云南大學(xué) 軟件 學(xué)院 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)
鏈接地址:http://ioszen.com/p-359757.html