欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

哈夫曼算法構(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;
}

執(zhí)行示例:

相關(guān)文章

  • 解決C++ 無(wú)法從void 轉(zhuǎn)換為L(zhǎng)RESULT的方法詳解

    解決C++ 無(wú)法從void 轉(zhuǎn)換為L(zhǎng)RESULT的方法詳解

    本篇文章是對(duì)C++中無(wú)法從void轉(zhuǎn)換為L(zhǎng)RESULT的解決方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • 深入分析C++中兩個(gè)大數(shù)相乘結(jié)果不正確的問(wèn)題

    深入分析C++中兩個(gè)大數(shù)相乘結(jié)果不正確的問(wèn)題

    本篇文章是對(duì)C++中兩個(gè)大數(shù)相乘結(jié)果不正確的問(wèn)題進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C語(yǔ)言多媒體框架GStreamer入門(mén)和概述

    C語(yǔ)言多媒體框架GStreamer入門(mén)和概述

    這篇文章主要介紹了C語(yǔ)言多媒體開(kāi)源框架GStreamer,本文總結(jié)了多媒體框架GStreamer一些基本概念及流程,希望能給使用GStreamer開(kāi)源庫(kù)的朋友提供一個(gè)借鑒或參考,需要的朋友可以參考下
    2022-07-07
  • C++ cin.get用法案例詳解

    C++ cin.get用法案例詳解

    這篇文章主要介紹了C++ cin.get用法案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • c++中for雙循環(huán)的那些事

    c++中for雙循環(huán)的那些事

    本人很菜,今天看《C++編程思想》中的一道課后題中說(shuō)到這樣一個(gè)問(wèn)題。修改兩層嵌套的for循環(huán)的標(biāo)識(shí)符,觀察結(jié)果變化
    2013-05-05
  • C語(yǔ)言實(shí)現(xiàn)斗地主的核心算法

    C語(yǔ)言實(shí)現(xiàn)斗地主的核心算法

    本文給大家分享的是使用C語(yǔ)言實(shí)現(xiàn)的斗地主游戲的核心算法,主要實(shí)現(xiàn)了面向?qū)ο笤O(shè)計(jì),洗牌、發(fā)牌、判斷牌型、比較牌的大小、游戲規(guī)則等算法。通過(guò)這個(gè)斗地主小項(xiàng)目的練習(xí),提高了我的面向?qū)ο笤O(shè)計(jì)能力,加深了對(duì)算法的理解。最近把這些設(shè)計(jì)和算法分享給大家。
    2015-03-03
  • DLL加載設(shè)置相對(duì)路徑的方法

    DLL加載設(shè)置相對(duì)路徑的方法

    這篇文章給大家介紹了DLL加載設(shè)置相對(duì)路徑的方法,非常不錯(cuò),具有一定的參考借鑒加載,需要的朋友參考下吧
    2018-08-08
  • C++獲得本機(jī)所有網(wǎng)卡的IP和MAC地址信息的實(shí)現(xiàn)方法

    C++獲得本機(jī)所有網(wǎng)卡的IP和MAC地址信息的實(shí)現(xiàn)方法

    下面小編就為大家?guī)?lái)一篇C++獲得本機(jī)所有網(wǎng)卡的IP和MAC地址信息的實(shí)現(xiàn)方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2016-10-10
  • C++ 詳細(xì)講解stack與queue的模擬實(shí)現(xiàn)

    C++ 詳細(xì)講解stack與queue的模擬實(shí)現(xiàn)

    C++ Stack(堆棧) 是一個(gè)容器類(lèi)的改編,為程序員提供了堆棧的全部功能,也就是說(shuō)實(shí)現(xiàn)了一個(gè)先進(jìn)后出(FILO)的數(shù)據(jù)結(jié)構(gòu),許多程序都使用了 queue 容器。queue 容器可以用來(lái)表示超市的結(jié)賬隊(duì)列或服務(wù)器上等待執(zhí)行的數(shù)據(jù)庫(kù)事務(wù)隊(duì)列
    2022-04-04
  • C++實(shí)現(xiàn)趣味掃雷游戲

    C++實(shí)現(xiàn)趣味掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)趣味掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06

最新評(píng)論