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

哈夫曼算法構造代碼

 更新時間:2013年12月23日 16:12:18   作者:  
這篇文章主要介紹了哈夫曼算法構造代碼,有需要的朋友可以參考一下

1.定義

  哈夫曼編碼主要用于數據壓縮。

  哈夫曼編碼是一種可變長編碼。該編碼將出現頻率高的字符,使用短編碼;將出現頻率低的字符,使用長編碼。

  變長編碼的主要問題是,必須實現非前綴編碼,即在一個字符集中,任何一個字符的編碼都不是另一個字符編碼的前綴。如:0、10就是非前綴編碼,而0、01不是非前綴編碼。

2.哈夫曼樹的構造

  按照字符出現的頻率,總是選擇當前具有較小頻率的兩個節(jié)點,組合為一個新的節(jié)點,循環(huán)此過程知道只剩下一個節(jié)點為止。

  對于5個字符A、B、C、D、E,頻率分別用1、5、7、9、6表示,則構造樹的過程如下:

上面過程對應的哈夫曼樹為:

假設規(guī)定左邊為0,右邊為1,則變長編碼為:

  A 1:010

  B 5:011

  C 7:10

  D 9:11

  E 6: 00

3.哈夫曼構造代碼

復制代碼 代碼如下:

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

int input(Node*,int);   //輸入節(jié)點信息
int buildedTree(Node*,int); //建哈夫曼樹
int getMin(Node*,int);  //尋找未使用的,具有最小頻率值的節(jié)點
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);    //翻轉字符串
        cout<<(nodes+i)->c<<" "<<(nodes+i)->value<<":"<<a<<endl;
    }
    return 0;
}

執(zhí)行示例:

相關文章

  • 解決C++ 無法從void 轉換為LRESULT的方法詳解

    解決C++ 無法從void 轉換為LRESULT的方法詳解

    本篇文章是對C++中無法從void轉換為LRESULT的解決方法進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • 深入分析C++中兩個大數相乘結果不正確的問題

    深入分析C++中兩個大數相乘結果不正確的問題

    本篇文章是對C++中兩個大數相乘結果不正確的問題進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • C語言多媒體框架GStreamer入門和概述

    C語言多媒體框架GStreamer入門和概述

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

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

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

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

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

    C語言實現斗地主的核心算法

    本文給大家分享的是使用C語言實現的斗地主游戲的核心算法,主要實現了面向對象設計,洗牌、發(fā)牌、判斷牌型、比較牌的大小、游戲規(guī)則等算法。通過這個斗地主小項目的練習,提高了我的面向對象設計能力,加深了對算法的理解。最近把這些設計和算法分享給大家。
    2015-03-03
  • DLL加載設置相對路徑的方法

    DLL加載設置相對路徑的方法

    這篇文章給大家介紹了DLL加載設置相對路徑的方法,非常不錯,具有一定的參考借鑒加載,需要的朋友參考下吧
    2018-08-08
  • C++獲得本機所有網卡的IP和MAC地址信息的實現方法

    C++獲得本機所有網卡的IP和MAC地址信息的實現方法

    下面小編就為大家?guī)硪黄狢++獲得本機所有網卡的IP和MAC地址信息的實現方法。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-10-10
  • C++ 詳細講解stack與queue的模擬實現

    C++ 詳細講解stack與queue的模擬實現

    C++ Stack(堆棧) 是一個容器類的改編,為程序員提供了堆棧的全部功能,也就是說實現了一個先進后出(FILO)的數據結構,許多程序都使用了 queue 容器。queue 容器可以用來表示超市的結賬隊列或服務器上等待執(zhí)行的數據庫事務隊列
    2022-04-04
  • C++實現趣味掃雷游戲

    C++實現趣味掃雷游戲

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

最新評論