C++哈夫曼樹和哈夫曼編碼詳解-創(chuàng)新互聯(lián)

? 理論部分

成都創(chuàng)新互聯(lián)成立以來不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點，以客戶需求中心、市場為導(dǎo)向”的快速反應(yīng)體系。對公司的主營項目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計、行業(yè) / 企業(yè)門戶設(shè)計推廣、行業(yè)門戶平臺運營、重慶APP開發(fā)公司、手機網(wǎng)站制作設(shè)計、微信網(wǎng)站制作、軟件開發(fā)、成都服務(wù)器托管等實行標(biāo)準(zhǔn)化操作，讓客戶可以直觀的預(yù)知到從成都創(chuàng)新互聯(lián)可以獲得的服務(wù)效果。

先補充一個概念，什么是路徑長度？

從樹中一個節(jié)點到另一個節(jié)點之間的分支構(gòu)成這兩個節(jié)點之間的路徑，路徑上的分支數(shù)目稱作路徑長度。而一般不帶權(quán)的單個路徑長度默認(rèn)為1，所以可以認(rèn)為節(jié)點數(shù)為n的樹的路徑長度為n-1。

哈夫曼樹的定義是帶權(quán)路徑長度最短的樹，也叫最優(yōu)二叉樹。換種更好的理解方式，就是一棵特殊的二叉樹，而這棵樹的葉子節(jié)點到根節(jié)點的帶權(quán)路徑都是盡可能最短的

如下圖：

樹a的路徑長度就是7*2+5*2+2*2+4*2=36。

樹b的路徑長度就是7*3+5*3+2*1+4*2=46

樹c的路徑長度就是7*1+5*2+2*3+4*3=35

明顯，樹c的路徑長度最小，但它是最優(yōu)二叉樹嗎？

想要驗證樹c是不是哈夫曼樹，就得從定義出發(fā)。帶權(quán)路徑長度最小，那么很容易想到，權(quán)重大的路徑所在的層數(shù)一定偏小，而權(quán)重小的路徑層數(shù)就偏小。那么很容易聯(lián)想到，把權(quán)重小的路徑先找出來并放在下面。經(jīng)過總結(jié)可得出以下結(jié)論：

(1)根據(jù)給定的n個權(quán)值?{w1,w2,?,wn}?構(gòu)成n棵二叉樹的集合?F={T1,T2,?,T?},?其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。
(2)在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。
(3)在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。
(4)重復(fù)(2)和(3)，直到F只含一棵樹為止。這棵樹便是赫夫曼樹。

哈夫曼編碼與前綴編碼：
前綴編碼:如果在一個編碼方案中， 任一個編碼都不是其他任何編碼的前綴(最左子串)，如稱編碼是前綴編碼。前綴編碼可以保證對壓縮文件進(jìn)行解碼時不產(chǎn)生二義性，確保正確解碼。

哈夫曼編碼:對一棵具有n個葉子的哈夫曼樹，若對樹中的每個左分支賦予0，右分支賦予1,則從根到每個葉子的路徑上，各分支的賦值分別構(gòu)成一一個二進(jìn)制串，該二進(jìn)制串就稱為哈夫曼編碼。
哈夫曼編碼是前綴編碼：哈夫曼編碼是根到葉子路徑上的編碼序列，由樹的特點知，若路徑A是另一條路徑B的最左部分，則B經(jīng)過了A.則A的終點一定不是葉子，而哈夫曼編碼對應(yīng)路徑的終點一定為葉子，因此，任一哈夫曼碼都不會與任意其他哈夫曼編碼的前綴部分完全重疊，因此哈夫曼編碼是前綴編碼。

哈夫曼編碼是最優(yōu)前綴編碼：對于包括n個字符的數(shù)據(jù)文件，分別以它們的出現(xiàn)次數(shù)為權(quán)值構(gòu)造哈夫曼樹，則利用該樹對應(yīng)的哈夫曼編碼對文件進(jìn)行編碼，能使該文件壓縮后對應(yīng)的二進(jìn)制文件的長度最短。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

實踐部分

以數(shù)據(jù)結(jié)構(gòu)哈夫曼樹和哈夫曼編碼基礎(chǔ)題為例

請構(gòu)建夫曼樹和哈夫曼編碼的實現(xiàn)，對于輸入的（n=8）個字符和對應(yīng)的概率，生成其對應(yīng)的哈夫曼編碼。

參考輸入如下：

"a","b","c","d","e","f","g","h"

0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1

參考輸出如下：

a:? ? ? ? 1010

b:? ? ? ? 00

c:? ? ? ? 10000

d:? ? ? ? 1001

e:? ? ? ? 11

f:? ? ? ? 10001

g:? ? ? ? 01

h:? ? ? ? 1011

首先是哈夫曼樹的定義，一般要求記錄節(jié)點的權(quán)重，雙親節(jié)點，左、右子女節(jié)點。

typedef struct{
    int weight;//權(quán)重
    int parents, Lchild, Rchlid;
}thnode,HuffmanTree[1000];

再是哈夫曼樹的構(gòu)建，先對前n個（葉子）節(jié)點進(jìn)行處理，記錄它們的權(quán)重，其他信息記為0。再對后面構(gòu)建哈夫曼樹形成的過程節(jié)點（容易得知哈夫曼樹的節(jié)點個數(shù)為2*n-1個，所以過程節(jié)點有n-1個）的所有信息記為0。在根據(jù)理論部分的規(guī)律，進(jìn)行哈夫曼樹的構(gòu)建。

void Huffman_Creat(HuffmanTree ht,int w[],int n)//n為葉子結(jié)點個數(shù)
{
    //先處理前n個節(jié)點
    int m = 2 * n - 1;//樹的總結(jié)點數(shù)
    int i,s1,s2;
    for (i = 1; i<= n;i++)
    {
        ht[i].weight = w[i];
        ht[i].Lchild = 0;
        ht[i].Rchlid = 0;
        ht[i].parents = 0;
    }
    //再處理后面的過程節(jié)點
    for (i = n+1; i<= m;i++)
    {
        ht[i].weight = 0;
        ht[i].Lchild = 0;
        ht[i].Rchlid = 0;
        ht[i].parents = 0;
    }
    //最后再按規(guī)律構(gòu)建哈夫曼樹
    for (i = n + 1; i<= m;i++)
    {
        select(ht, i - 1, &s1, &s2);//尋找雙親節(jié)點不為0的權(quán)重最小的2個節(jié)點
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[i].Lchild = s1;
        ht[i].Rchlid = s2;
        ht[s1].parents = i;
        ht[s2].parents = i;
    }
}

select函數(shù)就是尋找雙親節(jié)點不為0的權(quán)重最小的2個節(jié)點。

void select(HuffmanTree ht,int end,int*s1,int*s2)
{
    int min1, min2;//最小和第二小
    int i = 1;
    while(ht[i].parents!=0 && i<=end)
        i++;
    min1 = ht[i].weight;
    *s1 = i;

    i++;
    while(ht[i].parents!=0 && i<=end)
        i++;
    if(ht[i].weight=min1 && ht[j].weight

哈夫曼樹構(gòu)建完成后，就是哈夫曼編碼的建立。利用定義中的parent，可以從葉子節(jié)點尋找回根節(jié)點，跟從根節(jié)點遍歷到葉子節(jié)點的方法相比，不但減少代碼量，還方便記錄過程編碼。

typedef char* HuffmanCode[1000];
void HuffmanCode_Creat(HuffmanTree ht, HuffmanCode hc,int n)
{
    char *s;
    int start;
    int i, c, p;
    s = (char *)malloc(n * sizeof(char));//創(chuàng)建臨時數(shù)組
    s[n - 1] = '\0';//反向存入s數(shù)組中，方便后續(xù)輸出
    for (i = 1; i<= n;i++)
    {
        start = n - 1;
        c = i;//存儲當(dāng)前節(jié)點
        p = ht[i].parents;//存雙親
        while(p!=0)//只有根節(jié)點的雙親節(jié)點為0
        {
            --start;
            if(ht[p].Lchild==c)
                s[start] = '0';
            else
                s[start] = '1';
            c = p;
            p = ht[p].parents;//向上尋找雙親，直到為根節(jié)點
        }
        hc[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy(hc[i], &s[start]);//將每次的結(jié)果存入hc數(shù)組
    }
    free(s);
}

結(jié)合本題要求，可得完整代碼為：

請代入個人思考，本代碼故意改了部分，輸出一定是錯誤的！??！

請代入個人思考，本代碼故意改了部分，輸出一定是錯誤的！?。?/p>

請代入個人思考，本代碼故意改了部分，輸出一定是錯誤的?。?！

#includeusing namespace std;
typedef struct{
	char id;
    double weight;//權(quán)
    int parents, Lchild, Rchlid;
}thnode,HuffmanTree[1000];
void select(HuffmanTree ht,int end,int*s1,int*s2)
{
    double min1, min2;
    int i = 1;
    while(ht[i].parents!=0 && i<=end)
        i++;
    min1 = ht[i].weight;
    *s1 = i;

    i++;
    while(ht[i].parents!=0 && i<=end)
        i++;
    if(ht[i].weight=min1 && ht[j].weight>n;
    for (int i=1;i<=n;i++)
    	cin>>ppp[i];
    for (int i=1;i<=n;i++)
    	cin>>w[i];
    HuffmanTree ht;
    Huffman_Creat(ht, w, n);
	for (int i=1;i<=n;i++)
    	ht[i].id=ppp[i];
    HuffmanCode hc;
    HuffmanCode_Creat(ht,hc, n);
    for (i = 1; i<=n; i++)
      {
          printf("%c: %s\n", ht[i].id,hc[i]);
      }
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：C++哈夫曼樹和哈夫曼編碼詳解-創(chuàng)新互聯(lián)
本文來源：http://bm7419.com/article36/ggspg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、網(wǎng)站制作、靜態(tài)網(wǎng)站、定制網(wǎng)站、App設(shè)計、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)