106 Data Structure Homework 4

Presentation on theme: "106 Data Structure Homework 4"— Presentation transcript:

1 106 Data Structure Homework 4
2017/12/26

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

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

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

5 建立迷宮&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

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

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

8 建立迷宮&Min-Max heap @ - @ - @ - @ - @ - @ - @ | | # | | @ - @ @ - @ - @ - @ - @ | # | | # | | @ - @ @ - @ @ - @ - @ | | # | | # | # | @ @ - @ - @ @ - @ - @ | | # | # | | @ @ - @ - @ @ @ - @ | | # | | # | @ @ - @ @ - @ @ - @ | | # | | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # # 4 5 # # # 6 # # # # 12 # # # # 13 # # # # 17 # # # # # # 在完成迷宮之後依序將數字依照左邊的格式填入迷宮之中 紅字為起點以及終點 #字號為牆壁 最後將最短迷宮路徑印出

9 建立迷宮&Min-Max heap @ - @ - @ - @ - @ - @ - @ | | # | | @ - @ @ - @ - @ - @ - @ | # | | # | | @ - @ @ - @ @ - @ - @ | | # | | # | # | @ @ - @ - @ @ - @ - @ | | # | # | | @ @ - @ - @ @ @ - @ | | # | | # | @ @ - @ @ - @ @ - @ | | # | | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # # 4 5 # # # 6 # # # # 12 # # # # 13 # # # # 17 # # # # # # 請確保起終點連通,若是有點集合沒有和起終點路線相連通,請一樣填入數字。 完全沒有被選到過的點請填#字號 若有路徑可以連接起終點,則迷宮停止建立。

10 建立迷宮&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的子樹最小的值

11 建立迷宮&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)

12 建立迷宮&Min-Max heap # # # # # # # # # 1 2 3 # 4 5 # # # 6 # 7 8 9 #
需求 能夠用手動輸入的方式來選擇建立迷宮的大小(50%) E.g. 6*6 需要以右圖的方式呈現隨機生成的迷宮 以下圖的方式呈現迷宮的最短路徑(10%) @ - @ - @ - @ - @ - @ - @ | | # | | @ - @ @ - @ - @ @ - @ | # | | # | | @ - @ @ - @ @ - @ - @ | | # | | # | # | @ @ - @ - @ @ - @ - @ | | # | # | | @ @ - @ - @ @ @ - @ | | # | | # | @ @ - @ @ - @ @ - @ | | # | | @ - @ - @ - @ - @ - @ - @ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

13 建立迷宮&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)

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