106 Data Structure Homework 4 2017/12/26

建立迷宮&Min-Max heap 本此的作業希望同學運用minimum spanning tree的概念建立一個 迷宮 上述的方法必定可以建立一個從起點到終點的迷宮 以建立迷宮的路徑建立Min-Max heap 包含三個功能

建立迷宮&Min-Max heap 1 A B C D E F G H I 以3*3的圖為例子

隨機選取兩個點中的一個邊,如果它們不是同一個集合的話就將某一邊取走 建立迷宮&Min-Max heap 2 A B C D E F G I 隨機選取兩個點中的一個邊,如果它們不是同一個集合的話就將某一邊取走

建立迷宮&Min-Max heap 3 A C D E F G I A C D E G I 4 A C D E G A C D E 6 5

建立迷宮&Min-Max heap 7 8 C D A A

建立迷宮&Min-Max heap 首先要建立6*6的迷宮要先做13*13的格子 包含柱子@,橫邊-,直邊| @ - @ - @ - @ - @ - @ - @ | | | | | | | | | | | | | | 首先要建立6*6的迷宮要先做13*13的格子 包含柱子@,橫邊-,直邊|

建立迷宮&Min-Max heap @ - @ - @ - @ - @ - @ - @ | 1 2 3 | # | 4 5 | @ - @ @ - @ - @ - @ - @ | # | 6 | # | 7 8 9 | @ - @ @ - @ @ - @ - @ | 10 11 | # | 12 | # | # | @ @ - @ - @ @ - @ - @ | 13 | # | # | 14 15 16 | @ @ - @ - @ @ @ - @ | 17 | # | 18 19 20 | # | @ @ - @ @ - @ @ - @ | 21 22 23 | # | 24 25 | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # 1 2 3 # 4 5 # # # 6 # 7 8 9 # # 10 11 # 12 # # # # 13 # # 14 15 16 # # 17 # 18 19 20 # # # 21 22 23 # 24 25 # 在完成迷宮之後依序將數字依照左邊的格式填入迷宮之中 紅字為起點以及終點 #字號為牆壁 最後將最短迷宮路徑印出 1-2-6-11-10-13-17-21-22-23-18-19-20-24-25

建立迷宮&Min-Max heap @ - @ - @ - @ - @ - @ - @ | 1 2 3 | # | 4 5 | @ - @ @ - @ - @ - @ - @ | # | 6 | # | 7 8 9 | @ - @ @ - @ @ - @ - @ | 10 11 | # | 12 | # | # | @ @ - @ - @ @ - @ - @ | 13 | # | # | 14 15 16 | @ @ - @ - @ @ @ - @ | 17 | # | 18 19 20 | # | @ @ - @ @ - @ @ - @ | 21 22 23 | # | 24 25 | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # 1 2 3 # 4 5 # # # 6 # 7 8 9 # # 10 11 # 12 # # # # 13 # # 14 15 16 # # 17 # 18 19 20 # # # 21 22 23 # 24 25 # 請確保起終點連通,若是有點集合沒有和起終點路線相連通,請一樣填入數字。 完全沒有被選到過的點請填#字號 若有路徑可以連接起終點,則迷宮停止建立。

建立迷宮&Min-Max heap 接下來使用迷宮得出的路徑編號建立Min-Max heap 舉例 是一個Complete binary tree 此樹的level是以min-level與MAX-level交替出現 Root位於min-level 以40為例,40為以40為root的子樹最大的值 以7為例,7為以7為root的子樹最小的值

建立迷宮&Min-Max heap Min-Max heap要包含3個功能 以右邊的表示法來呈現你的Min-Max heap (7) Insert X Delete-min Delete-Max 以右邊的表示法來呈現你的Min-Max heap (7) (70,40) (30,9)(10,15) (45,50)(30,20)(12)

建立迷宮&Min-Max heap # # # # # # # # # 1 2 3 # 4 5 # # # 6 # 7 8 9 # 需求 能夠用手動輸入的方式來選擇建立迷宮的大小(50%) E.g. 6*6 需要以右圖的方式呈現隨機生成的迷宮 以下圖的方式呈現迷宮的最短路徑(10%) @ - @ - @ - @ - @ - @ - @ | 1 2 3 | # | 4 5 | @ - @ @ - @ - @ @ - @ | # | 6 | # | 7 8 9 | @ - @ @ - @ @ - @ - @ | 10 11 | # | 12 | # | # | @ @ - @ - @ @ - @ - @ | 13 | # | # | 14 15 16 | @ @ - @ - @ @ @ - @ | 17 | # | 18 19 20 | # | @ @ - @ @ - @ @ - @ | 21 22 23 | # | 24 25 | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # 1 2 3 # 4 5 # # # 6 # 7 8 9 # # 10 11 # 12 # # # # 13 # # 14 15 16 # # 17 # 19 20 21 # # # 23 24 25 # 27 28 # 1-2-6-11-10-13-17-21-22-23-18-19-20-24-25 1-2-6-11-10-13-17-23-24-25-19-20-21-27-28

建立迷宮&Min-Max heap 1-2-6-11-10-13-17-21-22-23-18-19-20-24-25 需求 使用迷宮得出的路徑編號建立Min-Max heap (20%) 請依照路徑的順序插入建立 heap 建立功能表可以使用三種功能 Insert X (10%) 輸入數字插入heap Delete-min (10%) Delete-MAX (10%) 三個功能都要用右圖的格式呈現 (1) (23,25) (2,10)(6,13) (11,21)(22,18)(17,19)(20,24) 1-2-6-11-10-13-17-21-22-23-18-19-20-24-25 1-2-6-11-10-13-17-23-24-25-19-20-21-27-28

建立迷宮&Min-Max heap 請寫word檔說明你的作業步驟，如果你的程式不符合規定，你的 word檔請寫出你做到什麼地步斟酌給分 寄信主旨請打以下格式 HW4_學號_姓名(不合規定斟酌扣分) 用ZIP壓縮word及程式碼(檔名請打你的學號) 請寄到 nchuwccclab@gmail.com Deadline 2018/01/15 用Yahoo信箱我好像收不到 不管你要用什麼寫，請你確定可以在Dev-C++上執行再寄給我 Code請不要貼在txt或word檔，我一定扣分 抄襲嚴懲 , 請打上註解不然不計分