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