數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書(shū)-不相交集輸出迷宮

PAGE課程設(shè)計(jì)說(shuō)明書(shū)課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)題目：不相交集輸出迷宮院系：計(jì)算機(jī)科學(xué)與信息工程學(xué)院課程設(shè)計(jì)任務(wù)書(shū)設(shè)計(jì)題目不相交集輸出迷宮學(xué)生姓名所在院系計(jì)算機(jī)科學(xué)與信息工程系專業(yè)、年級(jí)、班軟件工程<1>班設(shè)計(jì)要求：設(shè)計(jì)、實(shí)現(xiàn)一個(gè)用不相交集輸出的迷宮：(1)使用不相交集構(gòu)造；(2)使用C++編程；(3)運(yùn)行環(huán)境為VC++2012。學(xué)生應(yīng)完成的工作：(1)根據(jù)課程設(shè)計(jì)要求，分析思路并構(gòu)建模型，劃分子模塊、完善其功能；(2)根據(jù)各模塊的功能設(shè)計(jì)并編寫(xiě)程序段、連接各程序段使之形成一個(gè)有機(jī)的整體；(3)調(diào)試、運(yùn)行程序進(jìn)而得到正確的結(jié)果；(4)根據(jù)實(shí)驗(yàn)設(shè)計(jì)運(yùn)行過(guò)程，寫(xiě)出實(shí)驗(yàn)論文并總結(jié)實(shí)驗(yàn)教訓(xùn)。參考文獻(xiàn)閱讀：(1)C語(yǔ)言程序設(shè)計(jì)（潭浩強(qiáng)第二版，清華大學(xué)出版社）；(2)數(shù)據(jù)結(jié)構(gòu)（吳偉民等C語(yǔ)言版，清華大學(xué)出版社）；(3)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（高曉兵等，清華大學(xué)出版社）；(4)C++數(shù)據(jù)結(jié)構(gòu)與算法（徐丹、吳偉敏，清華大學(xué)出版社）。工作計(jì)劃：(1)第一周的第一天：布置設(shè)計(jì)題目；說(shuō)明進(jìn)度安排。(2)第一周的第二天：審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料準(zhǔn)備。(3)第一周的第三天、第四天、第五天：程序編寫(xiě)、上機(jī)調(diào)試(4)第二周的第一天至第三天：上機(jī)調(diào)試程序、結(jié)果分析。(5)第二周的第四天：撰寫(xiě)設(shè)計(jì)報(bào)告。(6)第二周的第五天：設(shè)計(jì)答辯。任務(wù)下達(dá)日期：2015年6月14日任務(wù)完成日期：2015年6月29日指導(dǎo)教師（簽名）：學(xué)生（簽名）：不相交集輸出迷宮摘要：當(dāng)今社會(huì)人們的生活越來(lái)越豐富，游戲也越來(lái)越受到人們的喜愛(ài)。不相交集生成的迷宮，不僅可以作為游戲的地圖。而且其產(chǎn)生的迷宮美觀，復(fù)雜，也可仿照建立實(shí)物；更直接的是有助于對(duì)不相交的深入學(xué)習(xí)。關(guān)鍵詞：不相交集；迷宮；目錄1設(shè)計(jì)背景………………11.1學(xué)習(xí)不相交集的重要性………12．設(shè)計(jì)方案 ……………12.1總體設(shè)計(jì)流程…………………13.方案實(shí)施……………13.1迷宮的建立·····································13.2不相交集算法………………14．結(jié)果與結(jié)論…………24.1關(guān)鍵程序代碼段詳細(xì)描述…………………24.2程序運(yùn)行結(jié)果…………………64.3課程設(shè)計(jì)總結(jié)……………75.收獲與致謝…………86.參考文獻(xiàn)……………8PAGE41.設(shè)計(jì)背景1.1學(xué)習(xí)不相交集的重要性不相交集是種用于合并的數(shù)據(jù)結(jié)合，在kruskal算法中有用到。它用到的兩個(gè)技術(shù)挺有意思的，一是按秩合并；二是路徑壓縮；這兩種技術(shù)都是用來(lái)控制樹(shù)的高度的。因?yàn)槿绻麡?shù)的高度過(guò)高，那么搜索一個(gè)元素所花費(fèi)的時(shí)間就會(huì)增加。對(duì)不相交集的掌握是很有必要的。2.設(shè)計(jì)方案2.1總體設(shè)計(jì)流程1.建立迷宮數(shù)組圖（1）建立迷宮數(shù)組；（2）對(duì)迷宮數(shù)組進(jìn)行初始化，并輸出。2.拆墻操作（1）按秩合并算法；（2）路徑壓縮算法。3.實(shí)現(xiàn)代碼文件的譯碼3.方案實(shí)施3.1迷宮的建立構(gòu)造迷宮的過(guò)程：（1）定義迷宮二維數(shù)組：數(shù)組元素為結(jié)構(gòu)的體，結(jié)構(gòu)體包含了一個(gè)字符串，和一個(gè)整形變量。（2）find操作：該操作返回包含給定元素的集合（即等價(jià)類）的名字。及判斷隨機(jī)找到的墻壁所隔開(kāi)的兩個(gè)路塊所在一個(gè)集合中，返回值為集合的名稱（3）union操作：Union操作是將兩個(gè)不相交的等價(jià)類合并為一個(gè)。只需要將某一個(gè)等價(jià)類集合代表的父指針修改為另一個(gè)集合的代表(根節(jié)點(diǎn))即可。3.2不相交集算法不相交集算法基本思想：把圖中節(jié)兩個(gè)等價(jià)類集合如果滿足：，則稱和構(gòu)成一個(gè)不相交集。對(duì)于不相交集中的任意兩個(gè)元素(x,y)我們有兩種操作：Find(x(ory))和Union(root(x),root(y))，其中root表示元素所在的等價(jià)類集合。4.結(jié)果與結(jié)論4.1關(guān)鍵程序代碼段詳細(xì)描述創(chuàng)建迷宮算法的代碼描述如下：迷宮數(shù)組元素的創(chuàng)建structsz{charp[5]; intq;};建立迷宮數(shù)組Maze::Maze(intm1,intn1):s(m1*n1),a(a1),b(b1),c(c1),d(d1)//不相交集的初始化{ m=m1; n=n1;for(inti=0;i<s.size();i++)//根數(shù)組初始化 s[i]=-1; for(inti=0;i<m;i++)////迷宮數(shù)組初始化 for(intj=0;j<n;j++) { t[i][j]=a; t[i][j].q=0; } t[m-1][n-1]=b; t[m-1][n-1].q=1;}不相交集類的建立：classMaze//不相交集類{public: explicitMaze(intm1,intn1);voidCreate();//拆墻賦值voidDisplay();//輸出迷宮private: intfind(intx);//路徑壓縮查找函數(shù)定義 voidunionSets(introot1,introot2);//按大小求并函數(shù)的定義 intm,n; vector<int>s; szt[50][50]; sza,b,c,d;};Find函數(shù)的實(shí)現(xiàn)：intMaze::find(intx)//路徑壓縮查找函數(shù)定義{if(s[x]<=0)returnx;else returns[x]=find(s[x]);//用遞歸找到其根}Union函數(shù)的實(shí)現(xiàn)：voidMaze::unionSets(introot1,introot2)//按大小求并{if(s[find(root1)]<s[find(root2)]){ s[find(root1)]=s[find(root1)]+s[find(root2)]; s[root2]=find(root1);}else{s[find(root2)]=s[find(root1)]+s[find(root2)]; s[root1]=find(root2);}}拆墻函數(shù)的代碼：voidMaze::Create()//創(chuàng)建迷宮{ intsm,sn,hz; ints1,s2;while(find(0)!=find(m*n-1)) { hz=rand()%2; if(hz==0)//拆橫墻 { sn=rand()%n;//隨機(jī)數(shù)找橫墻的坐標(biāo) sm=rand()%(m-1)+1; s1=(sm-1)*n+sn+1; s2=sm*n+sn+1; if(find(s1-1)!=find(s2-1)) { unionSets(s1-1,s2-1); if(t[sm-1][sn].q==0)//判斷其縱墻拆了沒(méi) { t[sm-1][sn]=b; t[sm-1][sn].q=1; } elseif(t[sm-1][sn].q==2) { t[sm-1][sn]=d; t[sm-1][sn].q=3; } } } else//拆縱墻 { sm=rand()%m; sn=rand()%(n-1)+1; s1=sm*n+sn+1; s2=s1-1; if(find(s1-1)!=find(s2-1)) { unionSets(s1-1,s2-1); if(t[sm][sn].q==0)//判斷其橫墻拆了沒(méi) { t[sm][sn]=c; t[sm][sn].q=2; } elseif(t[sm][sn].q==1) { t[sm][sn]=d; t[sm][sn].q=3; } } } }}輸出迷宮：voidMaze::Display()//迷宮的輸出{ cout<<"";for(inti=1;i<n;i++) cout<<"___";cout<<endl;for(inti=0;i<m;i++) for(intj=0;j<n;j++) { cout<<t[i][j].p; if(j==n-1) cout<<"|"<<endl; }}4.2程序運(yùn)行結(jié)果（1）系統(tǒng)初始化界面（2）輸出初始迷宮（3）拆墻后的迷宮4.3課程設(shè)計(jì)總結(jié)通過(guò)本次設(shè)計(jì)，使我明白了社么是不相交集，明白等價(jià)類的具體名字對(duì)于Find操作而言是無(wú)關(guān)緊要的，對(duì)于Find操作而言重要的是標(biāo)記；Union操作是將兩個(gè)不相交的等價(jià)類合并為一個(gè)。顯然只需要將某一個(gè)等價(jià)類集合代表的父指針修改為另一個(gè)集合的代表(根節(jié)點(diǎn))即可在設(shè)計(jì)中遇到的困難有：對(duì)數(shù)組、鏈表及結(jié)構(gòu)體掌握不牢,使得在編程時(shí)不能靈活運(yùn)用，以后需加強(qiáng);(2)程序調(diào)試方面不強(qiáng)。5.收獲與致謝總的來(lái)說(shuō),在整個(gè)設(shè)計(jì)的過(guò)程中,對(duì)文件的知識(shí)有了相當(dāng)程度的了解掌握,基本上學(xué)會(huì)了不相交集的操作等。在自學(xué)過(guò)程中也認(rèn)識(shí)，在學(xué)習(xí)的過(guò)程中要靈活的把所學(xué)的知識(shí)運(yùn)用到實(shí)踐當(dāng)中，并且還要鞏固練習(xí)和運(yùn)用，這樣才可以牢牢的記住。在對(duì)程序不斷的修改和逐步改進(jìn)提升的過(guò)程中，積累了不少經(jīng)驗(yàn)，為在以后的學(xué)習(xí)和實(shí)踐應(yīng)用奠定了一定的基礎(chǔ)。這次課程設(shè)計(jì)受益非淺，學(xué)到了不少知識(shí)，同時(shí)也認(rèn)識(shí)到自身的不足，需要加強(qiáng)自身訓(xùn)練，學(xué)以致用，學(xué)會(huì)自我總結(jié)，吸取教訓(xùn)，積累經(jīng)驗(yàn)，在學(xué)習(xí)和實(shí)踐中來(lái)不斷的提升自己。感謝老師的支持。6.參考文獻(xiàn)[1]C語(yǔ)言程序設(shè)計(jì)（潭浩強(qiáng)第二版，清華大學(xué)出版社）；[2]數(shù)據(jù)結(jié)構(gòu)（吳偉民等c語(yǔ)言版，清華大學(xué)出版社）；[3]數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（高曉兵等，清華大學(xué)出版社）；源代碼：*************************MG.h**********************#ifndefMG_H#defineMG_H#include<iostream>#include<vector>usingnamespacestd;structsz{charp[5]; intq;};classMaze//不相交集類{public: explicitMaze(intm1,intn1);voidCreate();//拆墻賦值voidDisplay();//輸出迷宮private: intfind(intx);//路徑壓縮查找函數(shù)定義 voidunionSets(introot1,introot2);//按大小求并函數(shù)的定義 intm,n; vector<int>s; szt[50][50]; sza,b,c,d;};#endif//!B_H**********************MG.cpp********************#include<iostream>#include<vector>#include<cstdlib>#include"MG.h"usingnamespacestd;//構(gòu)建方格的元素sza1={"|__"};//0szb1={"|"};//1szc1={"___"};//2szd1={""};//3Maze::Maze(intm1,intn1):s(m1*n1),a(a1),b(b1),c(c1),d(d1)//不相交集的初始化{ m=m1; n=n1;for(inti=0;i<s.size();i++)//根數(shù)組初始化 s[i]=-1; for(inti=0;i<m;i++)////迷宮數(shù)組初始化 for(intj=0;j<n;j++) { t[i][j]=a; t[i][j].q=0; } t[m-1][n-1]=b; t[m-1][n-1].q=1;}voidMaze::Create()//創(chuàng)建迷宮{ intsm,sn,hz; ints1,s2;while(find(0)!=find(m*n-1)) { hz=rand()%2; if(hz==0)//拆橫墻 { sn=rand()%n;//隨機(jī)數(shù)找橫墻的坐標(biāo) sm=rand()%(m-1)+1; s1=(sm-1)*n+sn+1; s2=sm*n+sn+1; if(find(s1-1)!=find(s2-1)) { unionSets(s1-1,s2-1); if(t[sm-1][sn].q==0)//判斷其縱墻拆了沒(méi) { t[sm-1][sn]=b; t[sm-1][sn].q=1; } elseif(t[sm-1][sn].q==2) { t[sm-1][sn]=d; t[sm-1][sn].q=3; } } } else//拆縱墻 { sm=rand()%m; sn=rand()%(n-1)+1; s1=sm*n+sn+1; s2=s1-1; if(find(s1-1)!=find(s2-1)) { unionSets(s1-1,s2-1); if(t[sm][sn].q==0)//判斷其橫墻拆了沒(méi) { t[sm][sn]=c; t[sm][sn].q=2; } elseif(t[sm][sn].q==1) { t[sm][sn]=d; t[sm][sn].q=3; } } } }}voidMaze::Display()//迷宮的輸出{ cout<<"";for(inti=1;i<n;i++) cout<<"___";cout<<endl;for(inti=0;i<m;i++) for(intj=0;j<n;j++) { cout<<t[i][j].p; if(j==n-1) cout<<"|"<<endl; }}voidMaze::unionSets(introot1,introot2)//按大小求并{if(s[find(root1)]<s[find(root2)]){ s[find(root1)]=s[find(root1)]+s[find(root2)]; s[root2]=find(root1);}else{s[find(root2)]=s[find(root1)]+s[find(root2)]; s[root1]=find(root2);}}intMaze::find(intx)//路徑壓縮查找函數(shù)定義{if(s[x]<=0)returnx;else returns[x]=find(s[x]);//用遞歸找到其根}**********************MainMG.cpp********************#include<iostream>#include<cstdlib>#include<vector>#include"MG.h"usingnamespacestd;intmain(){while(1){ cout<<endl<<endl; cout<<"**************主菜單**************"<<endl; cout<<"輸入迷宮的行、列m、n（m、n均小于25）："<<endl; intm,n; cin>>n>>m; if(m>50||n>50) return0; Mazesq(m,n);//定義不相交集對(duì)象 cout<<"初始化后的迷宮:\n"; sq.Display();//輸出初始化的迷宮 cout<<endl;