[料][作] 霍夫曼＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-01-02 19:42:49| 人13,169| 回1 | 上一篇 | 下一篇

[料][作] 霍夫曼

推 0 收藏 0 0 站台

作容:

建一Huffman tree

依照入的元素以及其率(率小模式且其和1)

透Huffman coding其

出

※注意率低的一其0

(例如:a 0.25 b 0.35 c 0.4 第一次a0 b1

第二次 (a & b) 0.6 c 0.4 (a & b)1 c0

也就是最後的 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交/之日期)

coderar/zip/7z後上

名格式101522054_hw5_ver1.rar

(期限如果想再重新上命名ver2 ver3依此推

助教改作以最後一版，名格式者不被改到)

次作有任何的同寄信或到lab找助教

小光的疑
a 0.10 b 0.15 c 0.30 d 0.16 e 0.29
a 0.8 b 0.12 c 0.42
a 0.2 c 0.2 d 0.2 b 0.2 e 0.2
a 0.49999999999 b 0.50000000001
a -1 b 2
ab 1 c 0
a 1 a 0

助教解析

不出有率相同的
以免造成建出的huffman tree不同

些分回答

1
a 0.49999999999 b 0.50000000001
的超float的
因此都被0.500000

2
的率是不被允的
不初在作sample未加入
感提醒

3
sample的可以理多字元
(基本上字或其他符也行)
不作需求要求小英文字母

4
重的部分的是把它作不同的符理
不在次作的也不有

如果有任何可以再信，感

以下是小光代，不要直接照抄上作， ... 我想也不有我班的同看。

#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;
}