Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

作業內容:

建構一個Huffman tree

並將依照輸入的元素以及其頻率(頻率為小數模式且其總和為1)

透過Huffman coding將其編碼

並輸出編碼

※請注意編碼時頻率較低的一邊應將其編為0

(例如:a 0.25 b 0.35 c 0.4 第一次編碼時a為0 b為1

第二次編碼時 (a & b) 0.6   c 0.4       則(a & b)為1 c為0

也就是最後的編碼為 a:10 b:11 c:0 

輸入及輸出說明:

輸入為一個字元且其後面為該字元之出現頻率依此格式直到所有字元皆輸入

字元內容皆為小寫英文字母(a~z)

輸出為列出所有字元(以其字母順序排列)以及其Huffman code(以0、1表示)

sample input 1:

a 0.10 b 0.15 c 0.30 d 0.16 e 0.29

sample output 1:

a : 010
b : 011
c : 11
d : 00
e : 10

sample input 2:

a 0.8 b 0.12 c 0.42

sample output 2:

The sum of frequency is not equal to 1

繳交方式及期限:

deadline : 1/11 22:00

遲交一天扣成績10%

1/15 22:00後交不予計分

繳交一樣上傳到FTP的hw5資料夾下

補交也一樣上傳到FTP的補交資料夾內hw5補交資料夾中的對應日期資料夾下  (即為:補交/hw5補交/對應之日期)

以下是小光代碼，請不要直接照抄上傳作業， ... 我想也不會有我們班的同學來看。

---

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#define eps 1e-6
using namespace std;
struct ND {
    int l, r, ptr;
    string token;
    double p;
    void set(int a, int b, int c, string d, double e) {
        l = a, r = b, ptr = c;
        token = d;
        p = e;
    }
};
struct cmp {
    bool operator() (ND a, ND b) {
        return a.p > b.p;
    }
};
ND nd[1024];
char buf[128];
map<string, string> hufcode;
void dfs(int idx, int dep) {
    if(!idx)    return;
    buf[dep] = '0';
    dfs(nd[idx].l, dep+1);
    buf[dep] = '1';
    dfs(nd[idx].r, dep+1);
    if(!nd[idx].l) {
        buf[dep] = '\0';
        hufcode[nd[idx].token] = buf;
    }
}
int main() {
    puts("Input data (seperate by space):");
    string line, token;
    getline(cin, line);
    stringstream sin(line);
    int size = 0, i;
    double p, sump = 0;
    priority_queue<ND, vector<ND>, cmp> pQ;
    ND L, R;
    while(sin >> token >> p) {
        ++size;
        nd[size].set(0, 0, size, token, p);
        sump += p;
        pQ.push(nd[size]);
    }
    if(fabs(sump-1) > eps) {
        puts("The sum of frequency is not equal to 1");
        system("pause");
        return 0;
    }
    while(pQ.size() >= 2) {
        L = pQ.top(), pQ.pop();
        R = pQ.top(), pQ.pop();
        ++size;
        nd[size].set(L.ptr, R.ptr, size, "", L.p+R.p);
        pQ.push(nd[size]);
    }
    dfs(size, 0);
    for(map<string, string>::iterator it = hufcode.begin();
        it != hufcode.end(); it++) {
        cout << it->first << " : " << it->second << endl;
    }
    system("pause");
    return 0;
}