哈夫曼算法構(gòu)造代碼

更新時(shí)間：2013年12月23日 16:12:18 作者：

這篇文章主要介紹了哈夫曼算法構(gòu)造代碼，有需要的朋友可以參考一下

1.定義

　　哈夫曼編碼主要用于數(shù)據(jù)壓縮。

　　哈夫曼編碼是一種可變長(zhǎng)編碼。該編碼將出現(xiàn)頻率高的字符，使用短編碼；將出現(xiàn)頻率低的字符，使用長(zhǎng)編碼。

　　變長(zhǎng)編碼的主要問(wèn)題是，必須實(shí)現(xiàn)非前綴編碼，即在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。如：0、10就是非前綴編碼，而0、01不是非前綴編碼。

2.哈夫曼樹(shù)的構(gòu)造

　　按照字符出現(xiàn)的頻率，總是選擇當(dāng)前具有較小頻率的兩個(gè)節(jié)點(diǎn)，組合為一個(gè)新的節(jié)點(diǎn)，循環(huán)此過(guò)程知道只剩下一個(gè)節(jié)點(diǎn)為止。

　　對(duì)于5個(gè)字符A、B、C、D、E，頻率分別用1、5、7、9、6表示，則構(gòu)造樹(shù)的過(guò)程如下：

上面過(guò)程對(duì)應(yīng)的哈夫曼樹(shù)為：

假設(shè)規(guī)定左邊為0，右邊為1，則變長(zhǎng)編碼為：

　　A 1:010

　　B 5:011

　　C 7:10

　　D 9:11

　　E 6: 00

3.哈夫曼構(gòu)造代碼

復(fù)制代碼代碼如下:

#include <iostream>
#include <string.h>
using namespace std;
struct Node{
    char c;
    int value;
    int par;
    char tag;    //tag='0',表示左邊；tag='1'，表示右邊
    bool isUsed;    //判斷這個(gè)點(diǎn)是否已經(jīng)用過(guò)
    Node(){
        par=-1;
        isUsed=false;
    }
};

int input(Node*,int); //輸入節(jié)點(diǎn)信息
int buildedTree(Node*,int); //建哈夫曼樹(shù)
int getMin(Node*,int); //尋找未使用的，具有最小頻率值的節(jié)點(diǎn)
int outCoding(Node*,int); //輸出哈夫曼編碼

int main ()
{
    int n;
    cin>>n;
    Node *nodes=new Node[2*n-1];
    input(nodes,n);
    buildedTree(nodes,n);
    outCoding(nodes,n);
    delete(nodes);
    return 0;
}

int input(Node* nodes,int n){
    for(int i=0;i<n;i++){
        cin>>(nodes+i)->c;
        cin>>(nodes+i)->value;
    }
    return 0;
}

int buildedTree(Node* nodes,int n){
    int last=2*n-1;
    int t1,t2;
    for(int i=n;i<last;i++){
        t1=getMin(nodes,i);
        t2=getMin(nodes,i);
        (nodes+t1)->par=i; (nodes+t1)->tag='0';
        (nodes+t2)->par=i; (nodes+t2)->tag='1';
        (nodes+i)->value=(nodes+t1)->value+(nodes+t2)->value;
    }
    return 0;
}

int getMin(Node* nodes,int n){
    int minValue=10000000;
    int pos=0;
    for(int i=0;i<n;i++)
    {
        if((nodes+i)->isUsed == false && (nodes+i)->value<minValue){
            minValue=(nodes+i)->value;
            pos=i;
        }
    }
    (nodes+pos)->isUsed=true;
    return pos;
}

int outCoding(Node* nodes,int n){
    char a[100];
    int pos,k,j;
    char tmp;
    for(int i=0;i<n;i++){
        k=0;
        pos=i;
        memset(a,'\0',sizeof(a));
        while((nodes+pos)->par!=-1){
            a[k++]=(nodes+pos)->tag;
            pos=(nodes+pos)->par;
        }
        strrev(a);    //翻轉(zhuǎn)字符串
        cout<<(nodes+i)->c<<" "<<(nodes+i)->value<<":"<<a<<endl;
    }
    return 0;
}