Download presentation
Presentation is loading. Please wait.
1
106二專班第二次作業 2017/11/27
2
霍夫曼樹 1.(60%，對照表20%，每個traversal為10%)題目給出代碼A~E共5個節點，和相對應的機率(權種值)，建立霍夫曼樹，並產生個點的對照表，再用level order traversal、postorder traversal、preorder traversal、inorder traversal排列出來(用A~E來排列) 2.(40%，隨機產生權重10%，對照表10%，輸入輸出20%)隨機產生節點數量(5<=x<=10)，產出節點後給出相對應的代碼，(如:產生5個點，則所給出的節點為A~E，產生10個節點則為A~J)，並隨機決定各節點的權重(0%<x<100%)，建立霍夫曼樹，且可以輸入字串並給出解碼之後的結果(如:A=0，B=1，則輸入AB，需產生:01，須提醒使用者輸入的範圍)
3
霍夫曼樹----題目一舉例 100 E D 20 C 45 1 B A 55 中間過程 (不須印出) 節點 機率 A 27% B 28% C
1 B A 55 中間過程 (不須印出) 節點 機率 A 27% B 28% C 25% D 15% E 5% 題目預設 節點 轉換 A 10 B 11 C 01 D 001 E 000 自己求出(需印出) 1 1 追蹤 結果 inorder traversal E、20、D、45、C、100、A、55、B postorder traversal E、D、20、C、45、A、B、55、100 preorder traversal 100、45、20、E、D、C、55、A、B level order traversal 100、45、55、20、C、A、B、E、D 追蹤結果(需印出)
4
霍夫曼樹----建樹過程 1 2 20 E D C 45 3 20 E D 55 A B 最小的2(E、D)個相加 最小的2個(A、B)相加
100
5
霍夫曼樹----題目二舉例 節點 機率 A 28% B 27% C 25% D 15% E 5% 自己求出(需印出) 中間過程 (不須印出)
自己假設(可能更多) 節點 轉換 A 10 B 11 C 01 D 001 E 000 100 E D 20 C 45 1 B A 55 輸入 輸出 AB 1011 自己求出
6
霍夫曼樹 寄程式碼和結果圖 日期: 2017/12/18 12:00 (HW1) 學號 系級 名字 請打上註解不然不計分
日期: 2017/12/18 12:00 (HW1) 學號 系級 名字 請打上註解不然不計分 請盡量使用Dev C++
Similar presentations
