哈夫曼算法構(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)造代碼
#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的方法詳解
本篇文章是對(duì)C++中無(wú)法從void轉(zhuǎn)換為L(zhǎng)RESULT的解決方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05深入分析C++中兩個(gè)大數(shù)相乘結(jié)果不正確的問(wèn)題
本篇文章是對(duì)C++中兩個(gè)大數(shù)相乘結(jié)果不正確的問(wèn)題進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05C語(yǔ)言多媒體框架GStreamer入門(mén)和概述
這篇文章主要介紹了C語(yǔ)言多媒體開(kāi)源框架GStreamer,本文總結(jié)了多媒體框架GStreamer一些基本概念及流程,希望能給使用GStreamer開(kāi)源庫(kù)的朋友提供一個(gè)借鑒或參考,需要的朋友可以參考下2022-07-07C++獲得本機(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-10C++ 詳細(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