1、哈爾濱工業(yè)大學(xué)課程設(shè)計(jì)報(bào)告Harbin Institute of Technology數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告(2014年度秋季學(xué)期)設(shè)計(jì)題目： 應(yīng)用不相交集合 生成隨機(jī)迷宮 小組成員： 院 系： 軟件學(xué)院 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 2014.11.142015.1.6 哈爾濱工業(yè)大學(xué)項(xiàng)目任務(wù)分工及進(jìn)度計(jì)劃表任務(wù)編號(hào)具體內(nèi)容執(zhí)行人預(yù)計(jì)開(kāi)始時(shí)間預(yù)計(jì)完成時(shí)間實(shí)際完成情況1確定題目周方恬2014.11.142014.11.14已完成2撰寫(xiě)文檔系統(tǒng)目的部分周方恬2014.11.142014.11.14已完成3撰寫(xiě)文檔系統(tǒng)功能需求部分周方恬2014.11.142014.11.14已完成4查閱不相交集合數(shù)

2、據(jù)結(jié)構(gòu)資料趙杰2014.11.142014.11.17已完成5查閱先深度搜索資料張丹丹2014.11.142014.11.17已完成6撰寫(xiě)文檔系統(tǒng)關(guān)鍵技術(shù)部分李曉璇2014.11.142014.11.17已完成里程碑1：完成選題，完成文檔中“需求分析”部分的撰寫(xiě)，具有一定的設(shè)計(jì)/開(kāi)發(fā)思路。時(shí)間節(jié)點(diǎn)：第10周 周五7不相交集合數(shù)據(jù)結(jié)構(gòu)算法構(gòu)思趙杰2014.11.172014.11.21已完成8構(gòu)造隨機(jī)迷宮算法構(gòu)思周方恬2014.11.172014.11.21已完成9先深度搜索尋找路徑算法構(gòu)思李曉璇2014.11.172014.11.21已完成10畫(huà)出迷宮和路徑算法構(gòu)思張丹丹2014.11.172

3、014.11.21已完成11繪制構(gòu)造隨機(jī)迷宮算法流程圖周方恬2014.11.172014.11.21已完成12繪制尋找路徑算法流程圖李曉璇2014.11.172014.11.21已完成13繪制畫(huà)出迷宮和路徑算法流程圖趙杰2014.11.172014.11.21已完成里程碑2：確定項(xiàng)目整體設(shè)計(jì)思路，完成文檔中“算法設(shè)計(jì)”部分的撰寫(xiě)。時(shí)間節(jié)點(diǎn)：第11周 周五14構(gòu)造隨機(jī)迷宮部分代碼開(kāi)發(fā)周方恬2014.11.222014.12.25已完成15尋找路徑部分代碼開(kāi)發(fā)李曉璇2014.11.222014.12.25已完成16畫(huà)出迷宮部分代碼開(kāi)發(fā)張丹丹2014.11.222014.12.25已完成17畫(huà)出路徑

4、部分代碼開(kāi)發(fā)趙杰2014.11.222014.12.25已完成里程碑3：項(xiàng)目開(kāi)發(fā)完成90%以上，文檔中“算法實(shí)現(xiàn)”部分完成80%以上。時(shí)間節(jié)點(diǎn)：第16周 周四18程序調(diào)試周方恬2014.12.262015.1.5已完成19分析程序復(fù)雜度及優(yōu)缺點(diǎn)李曉璇2014.12.262015.1.5未完成20完善文檔張丹丹2014.12.262015.1.5未完成21制作答辯PPT趙杰2014.12.262015.1.5未完成里程碑4：開(kāi)發(fā)任務(wù)全部完成，完成系統(tǒng)測(cè)試，文檔撰寫(xiě)全部完成，答辯PPT全部完成。時(shí)間節(jié)點(diǎn)：第18周 周一22打印文檔張丹丹2015.1.62015.1.6未完成23上傳文檔及PPT電子

5、版趙杰2015.1.62015.1.6未完成24協(xié)助準(zhǔn)備答辯李曉璇2015.1.62015.1.6未完成25答辯周方恬2015.1.62015.1.6未完成里程碑5：項(xiàng)目結(jié)題驗(yàn)收時(shí)間節(jié)點(diǎn)：第18周 周二 2015-1-6每條任務(wù)的執(zhí)行人只能是一個(gè)；如果多個(gè)人一起完成，請(qǐng)拆分任務(wù)，具體到人目 錄任務(wù)分工及進(jìn)度計(jì)劃表2目 錄31 需求分析41.1 系統(tǒng)目標(biāo)41.2 系統(tǒng)功能需求41.3 系統(tǒng)關(guān)鍵技術(shù)42 算法設(shè)計(jì)62.1 系統(tǒng)整體思路62.2 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)62.3 構(gòu)建隨機(jī)迷宮功能相關(guān)算法62.3.1算法基本思想62.3.2算法流程圖62.4 尋找迷宮路徑功能相關(guān)算法72.4.1算法基本思想7

6、2.4.2算法流程圖72.5 畫(huà)出迷宮和路徑功能相關(guān)算法72.5.1算法基本思想72.5.2算法流程圖83 算法實(shí)現(xiàn)93.1 開(kāi)發(fā)語(yǔ)言及工具93.2 算法關(guān)鍵代碼93.2.1 構(gòu)造隨機(jī)迷宮算法關(guān)鍵代碼93.2.2 尋找迷宮路徑算法關(guān)鍵代碼9 3.2.3 圖形界面算法關(guān)鍵代碼.93.3 主要功能界面93.3.1 XXX功能運(yùn)行結(jié)果93.3.2 XXX功能運(yùn)行結(jié)果93.3.3 XXX功能運(yùn)行結(jié)果94 算法分析104.1算法復(fù)雜性分析104.2算法優(yōu)缺點(diǎn)分析105 項(xiàng)目總結(jié)111 需求分析1.1 系統(tǒng)目標(biāo)使用不相交集合數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)造一個(gè)N×N的從左上角到右下角只有一條路徑的隨機(jī)迷宮，然后在

7、這一迷宮上執(zhí)行深度優(yōu)先搜索。利用不相交集合應(yīng)用數(shù)組進(jìn)行物理存儲(chǔ)，用先深度搜索找到最短路徑，記錄下最短路徑，最后將隨機(jī)生成的迷宮和相應(yīng)的路徑顯示出來(lái)。1.2 系統(tǒng)功能需求（1）構(gòu)建隨機(jī)迷宮功能 提示用戶輸入迷宮大小N，隨機(jī)生成一個(gè)N×N的迷宮。（2）尋找迷宮路徑功能 每次生成迷宮后，自動(dòng)開(kāi)始尋找迷宮路徑，將此次隨機(jī)生成的迷宮的最短路徑記錄下來(lái)。（3）畫(huà)出迷宮和路徑功能當(dāng)用戶選擇生成迷宮時(shí)，將生成的隨機(jī)迷宮用圖形方式畫(huà)出，用線段來(lái)表示迷宮中的墻。當(dāng)用戶選擇顯示路徑時(shí)，將所計(jì)算出的最短路徑畫(huà)出，用每個(gè)方格的中心點(diǎn)連成的線段來(lái)表示路徑。1.3 系統(tǒng)關(guān)鍵技術(shù)（1）不相交集合數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)

8、 不相交即對(duì)于任意兩個(gè)集合A和B，AB=¢。不相交集合?？梢员硎緸闃?shù)，此時(shí)兩個(gè)不相交的集合的并很容易實(shí)現(xiàn)，如圖1-1所示。不相交集合?？捎脕?lái)根據(jù)等價(jià)關(guān)系對(duì)集合進(jìn)行等價(jià)劃分。圖1-1 不相交集合的樹(shù)的表示（2）構(gòu)建隨機(jī)迷宮算法給定一個(gè)N×N的方格，初始時(shí)每個(gè)方格的四面都是墻，如圖1-2所示，期中的S是迷宮的開(kāi)始處，F(xiàn)是迷宮的結(jié)束處。N×N迷宮的N2個(gè)方格0，1，N2-1初始時(shí)每個(gè)方格自己成為一個(gè)等價(jià)類，即0，1，N2-1。生成隨機(jī)迷宮的方法是隨機(jī)選擇一個(gè)內(nèi)部墻（連接兩個(gè)相鄰方格的墻），如果該內(nèi)部墻關(guān)聯(lián)的兩個(gè)相鄰的方格屬于不同的等價(jià)類就將該墻除去，在除去該墻的同時(shí)將這

9、兩個(gè)等價(jià)類合并。直到所有的方格都在一個(gè)等價(jià)類中，就完成了隨機(jī)迷宮的生成。圖1-2 N×N的迷宮（3）尋找迷宮路徑算法迷宮一旦建立后，將迷宮表示為一個(gè)無(wú)向圖：方格作為圖中的頂點(diǎn)，如果兩個(gè)相鄰的方格之間沒(méi)有墻則兩個(gè)頂點(diǎn)之間有邊。為找到從S到F的唯一的路徑，在該圖上從S處開(kāi)始出發(fā)先深搜索，如果搜索到達(dá)了F，則搜索停止。（4）畫(huà)出迷宮和路徑算法用圖形方式將上述算法獲得的隨機(jī)迷宮及其上的最短路徑畫(huà)出。用線段來(lái)表示迷宮中的墻，用在每個(gè)方格的中心的點(diǎn)來(lái)表示路徑。2 算法設(shè)計(jì)2.1 系統(tǒng)整體思路使用不相交集合數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)造一個(gè)N×N的從左上角到右下角只有一條路徑的隨機(jī)迷宮，然后在這一迷宮上

10、執(zhí)行深度優(yōu)先搜索。利用不相交集合應(yīng)用數(shù)組進(jìn)行物理存儲(chǔ)，用先深度搜索找到最短路徑，記錄下最短路徑，最后將隨機(jī)生成的迷宮和相應(yīng)的路徑顯示出來(lái)。2.2 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 用一個(gè)二維數(shù)組存儲(chǔ)迷宮，用不同的數(shù)字表示不同的狀態(tài)，9表示不可到達(dá)的點(diǎn)，1表示墻，0表示通路，5表示頂點(diǎn)。按此方式存儲(chǔ)生成的隨機(jī)迷宮，并根據(jù)這樣的結(jié)構(gòu)來(lái)搜尋最短路徑。最后根據(jù)這樣的迷宮結(jié)構(gòu)畫(huà)出相應(yīng)的圖形界面。2.3 構(gòu)建隨機(jī)迷宮功能相關(guān)算法2.3.1算法基本思想 隨機(jī)選擇一條邊，判斷邊連接的頂點(diǎn)，是否在同一子樹(shù)中，如果是則執(zhí)行，如果不是則執(zhí)行。 連通這兩個(gè)頂點(diǎn)，并把他們?nèi)我庖粋€(gè)添加到另一個(gè)所在的子樹(shù)中。判斷起點(diǎn)和終點(diǎn)是否在同一子樹(shù)中

11、，如果不是則執(zhí)行，如果是則退出。按這個(gè)步驟執(zhí)行程序直至程序退出。2.3.2算法流程圖開(kāi)始隨機(jī)選擇一條邊 是 判斷邊連接的頂點(diǎn)是否在同一子樹(shù)中 否連通這兩個(gè)頂點(diǎn)并合并兩個(gè)子樹(shù) 判斷所有頂點(diǎn) 否是否在同一子樹(shù)中 是結(jié)束圖2-1 構(gòu)建隨機(jī)迷宮算法流程圖2.4 尋找迷宮路徑功能相關(guān)算法2.4.1算法基本思想 迷宮表示為一個(gè)無(wú)向圖：格子作為圖中的頂點(diǎn)，如果兩個(gè)相鄰的方格之間沒(méi)有墻則兩個(gè)頂點(diǎn)之間有邊（在二維數(shù)組中用不同數(shù)字作為標(biāo)記）。找到從S到F的唯一的路徑，在該圖上從S處開(kāi)始出發(fā)先深搜索，利用棧存儲(chǔ)每一次回退前由起始點(diǎn)“S”到某點(diǎn)v的路徑（鏈表實(shí)現(xiàn)，只需要存儲(chǔ)對(duì)應(yīng)二維數(shù)組的下標(biāo)），回退前判斷終止點(diǎn)v是否

12、為迷宮重點(diǎn)“F”，如果是，停止搜索，棧中路徑即為要求的最短路徑，如果不是，棧頂元素出棧，并且依次回退，繼續(xù)搜索下一條路徑，以此類推，直到找最短路徑。如果沒(méi)有找到，則代表迷宮建立出錯(cuò)。 另：這里面迷宮生成時(shí)即生成只有一條有效路徑到達(dá)終點(diǎn)（不重復(fù)訪問(wèn)格子的路徑），所以尋找路徑時(shí)找到的第一條即是唯一的一條路徑。2.4.2算法流程圖開(kāi)始令v=S（迷宮起點(diǎn)）標(biāo)記頂點(diǎn)v，壓入棧 令v=n 是判斷v是否有未訪問(wèn)過(guò)的鄰接頂點(diǎn)n 否 是判斷v是否為迷宮重點(diǎn)F 否v出棧，回退至上一個(gè)頂點(diǎn)輸出棧中內(nèi)容即為最短路徑結(jié)束圖2-2 尋找迷宮路徑算法流程圖2.5 畫(huà)出迷宮和路徑功能相關(guān)算法2.5.1算法基本思想用圖形方式將

13、上述算法獲得的隨機(jī)迷宮及其上的最短路徑畫(huà)出。第一部分是畫(huà)出隨機(jī)迷宮，給定二維數(shù)組，其中有標(biāo)記格子以及墻的有無(wú)，根據(jù)二位數(shù)組的下標(biāo)計(jì)算出每個(gè)位置在顯示器中的坐標(biāo)X，Y，判斷數(shù)組中內(nèi)容所對(duì)應(yīng)的是墻還是頂點(diǎn)還是通路，利用java中swing類組件畫(huà)出相應(yīng)圖形。第二部分畫(huà)出最短路徑，給定棧中存儲(chǔ)路徑在二維數(shù)組中格子的下標(biāo)，計(jì)算出在顯示器中的坐標(biāo)X，Y，由兩個(gè)頂點(diǎn)中心點(diǎn)的連線表示兩點(diǎn)之間的路徑，利用java中swing類組件畫(huà)出路徑。2.5.2算法流程圖開(kāi)始i=1，j=1計(jì)算相應(yīng)頂點(diǎn)（i,j）坐標(biāo)（X,Y）根據(jù)數(shù)組內(nèi)容在（X,Y）畫(huà)出相應(yīng)圖形 j+ 是判斷j<N 否 i+，j=1 是判斷i<

14、N 否結(jié)束圖2-3 畫(huà)出迷宮算法流程圖開(kāi)始出棧計(jì)算路徑相應(yīng)坐標(biāo)在相應(yīng)位置畫(huà)出路徑 否判斷棧是否為空 是結(jié)束圖2-4 畫(huà)出迷宮路徑算法流程圖3 算法實(shí)現(xiàn)3.1 開(kāi)發(fā)語(yǔ)言及工具開(kāi)發(fā)語(yǔ)言：JAVA開(kāi)發(fā)工具：eclipse3.2 算法關(guān)鍵代碼3.2.1 構(gòu)建隨機(jī)迷宮算法關(guān)鍵代碼public void CreateMaze(int Maze) /生成隨機(jī)迷宮，存在二維數(shù)組Maze中int x,y,i,j,d,xt1,yt1,xt2,yt2,count = n*n;Init();/初始化等價(jià)類for(i = 0;i < wid;i+) /初始化二維數(shù)組for(j = 0;j < wid;j+)

15、 Mazeij = 9;/9為不可到達(dá)的點(diǎn)for(i = 1;i < wid;i+) /初始化二維數(shù)組if(i%2 = 1) for(j = 1;j < wid;j += 2) Mazeij = 5;/5為格子for(j = 2;j < wid;j += 2) Mazeij = 1;/1為墻else for(j = 1;j < wid;j += 2) Mazeij = 1;/1為墻while(count > 1) /循環(huán)至只有一個(gè)等價(jià)類結(jié)束do x = (int)(Math.random()*wid);y = (int)(Math.random()*wid);wh

16、ile(Mazexy != 1);d = x%2;if(d = 0) /墻為豎直方向的xt1 = x + 1;yt1 = y;xt2 = x - 1;yt2 = y;if(FindSet(postolist(xt1,yt1) != FindSet(postolist(xt2,yt2) Mazexy = 0;UnionSet(postolist(xt1,yt1),postolist(xt2,yt2);count-;else /墻為水平方向的xt1 = x;yt1 = y + 1;xt2 = x;yt2 = y - 1;if(FindSet(postolist(xt1,yt1) != FindSe

17、t(postolist(xt2,yt2) Mazexy = 0;UnionSet(postolist(xt1,yt1),postolist(xt2,yt2);count-;int rank = new intMAX;/存儲(chǔ)節(jié)點(diǎn)的層數(shù)int parent = new intMAX;/存儲(chǔ)相應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)public void Init() /初始化等價(jià)類，一個(gè)格子為一個(gè)等價(jià)類for(int i = 0;i < MAXSIZE;i+) ranki = 0;parenti = i;public int FindSet(int x) /找到二叉樹(shù)的根節(jié)點(diǎn)if(x != parentx)paren

18、tx = FindSet(parentx);return parentx;public void UnionSet(int root1,int root2) /合并等價(jià)類int x = FindSet(root1);int y = FindSet(root2);if(x = y) return;if(rankx > ranky) parenty = x;else parentx = y;if(rankx = ranky) +ranky;public int postolist(int x,int y) /將二維數(shù)組中（x，y）轉(zhuǎn)化為一維數(shù)組對(duì)應(yīng)的ireturn (x/2)*n + (y/

19、2);3.2.2 尋找迷宮路徑算法關(guān)鍵代碼public Stack getPath()/尋找迷宮路徑，存儲(chǔ)在棧中Stack stackP = new Stack();int x=1,y=1;/起點(diǎn)坐標(biāo)（1，1）stackP.Push(1,1);setBeen(x,y);/標(biāo)記為已到達(dá)doif(ableRight(x,y)/如果向右沒(méi)有墻，則將右邊格子壓入棧setBeen(x+2,y);x = x+2;stackP.Push(x,y);else if(ableLeft(x,y)/如果向左沒(méi)有墻，則將左邊格子壓入棧setBeen(x-2,y);x = x-2;stackP.Push(x,y);el

20、se if(ableUp(x,y)/如果向上沒(méi)有墻，則將上邊格子壓入棧setBeen(x,y-2);y = y-2;stackP.Push(x,y);else if(ableDown(x,y)/如果向下沒(méi)有墻，則將下邊格子壓入棧setBeen(x,y+2);y = y+2;stackP.Push(x,y);elseif(x = mazeSize - 1 && y = mazeSize -1)/到達(dá)終點(diǎn)break;else if(stackP.isEmpty()/未找到路徑System.out.println("No Path!");break;stackP.

21、Pop();x = stackP.End().getX();y = stackP.End().getY();while(true);return stackP;3.2.3 圖形界面算法關(guān)鍵代碼public void paintComponent(Graphics g) /畫(huà)出迷宮和路徑super.paintComponent(g);Graphics2D g2 = (Graphics2D) g;System.out.println("path為空？"+path.isEmpty();Rectangle2D rect = new Rectangle2D.Double(Rectle

22、ftX, RecttopY, RectWidth, RectHeight);g2.draw(rect);/畫(huà)出迷宮邊界for(int i=1;i<=N-1;i=i+1)/根據(jù)二維數(shù)組Maze畫(huà)出迷宮for(int j=1;j<=N-1;j=j+1)if(isWall(Mazeij)if(i%2=0)g2.draw(new Line2D.Double(RectleftX + SIZE*(i),RecttopY +SIZE*(j-1),RectleftX + SIZE*(i),RecttopY + SIZE * (j+1);elseg2.draw(new Line2D.Double(R

23、ectleftX + SIZE*(i-1),RecttopY +SIZE*(j),RectleftX + SIZE*(i+1), RecttopY +SIZE*(j);while(!path.isEmpty()/根據(jù)棧中內(nèi)容畫(huà)出路徑g2.draw(new Ellipse2D.Double(RectleftX + (path.End().getX()-1)*SIZE + SIZE/3 , RecttopY + (path.End().getY()-1)*SIZE + SIZE/3,2*SIZE/3, 2*SIZE/3);path.Pop();3.3 主要功能界面按照主要功能分小節(jié)，自行增刪。每個(gè)

24、界面下需要有簡(jiǎn)短的文字說(shuō)明3.3.1 XXX功能運(yùn)行結(jié)果主要截圖及說(shuō)明3.3.2 XXX功能運(yùn)行結(jié)果主要截圖及說(shuō)明3.3.3 XXX功能運(yùn)行結(jié)果主要截圖及說(shuō)明4 算法分析4.1算法復(fù)雜性分析4.1.1 構(gòu)建隨機(jī)迷宮算法關(guān)鍵代碼時(shí)間復(fù)雜度若構(gòu)建N*N的迷宮，則時(shí)間復(fù)雜度 O(n) = n2。（與隨機(jī)情況有關(guān)） 空間復(fù)雜度 O(n) = n2。4.1.2 尋找迷宮路徑算法關(guān)鍵代碼若構(gòu)建N*N的迷宮，則時(shí)間復(fù)雜度 O(n) = n2。 空間復(fù)雜度 O(n) = n。4.1.3 圖形界面算法關(guān)鍵代碼若構(gòu)建N*N的迷宮，則時(shí)間復(fù)雜度 O(n) = n2。4.2算法優(yōu)缺點(diǎn)分析分析算法目前已發(fā)現(xiàn)的問(wèn)題或可能存在的問(wèn)題。4.2.1構(gòu)建隨機(jī)迷宮算法優(yōu)點(diǎn)：隨機(jī)性較大，基本不會(huì)出現(xiàn)迷宮過(guò)于簡(jiǎn)單、構(gòu)造特別奇特的情況。 存儲(chǔ)結(jié)構(gòu)二維數(shù)