哈夫曼算法構(gòu)造代碼
1.定義
哈夫曼編碼主要用于數(shù)據(jù)壓縮。
哈夫曼編碼是一種可變長編碼。該編碼將出現(xiàn)頻率高的字符，使用短編碼；將出現(xiàn)頻率低的字符，使用長編碼。
變長編碼的主要問題是，必須實(shí)現(xiàn)非前綴編碼，即在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。如：0、10就是非前綴編碼，而0、01不是非前綴編碼。
2.哈夫曼樹的構(gòu)造
按照字符出現(xiàn)的頻率，總是選擇當(dāng)前具有較小頻率的兩個(gè)節(jié)點(diǎn)，組合為一個(gè)新的節(jié)點(diǎn)，循環(huán)此過程知道只剩下一個(gè)節(jié)點(diǎn)為止。
對(duì)于5個(gè)字符A、B、C、D、E，頻率分別用1、5、7、9、6表示，則構(gòu)造樹的過程如下：
上面過程對(duì)應(yīng)的哈夫曼樹為：
假設(shè)規(guī)定左邊為0，右邊為1，則變長編碼為：
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)用過
Node(){
par=-1;
isUsed=false;
}
};
int input(Node*,int); //輸入節(jié)點(diǎn)信息
int buildedTree(Node*,int); //建哈夫曼樹
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++深入探究類與對(duì)象之友元與運(yùn)算符重載
友元就是讓一個(gè)函數(shù)或者類，訪問另一個(gè)類中的私有成員；打個(gè)比方，這相當(dāng)于是說：朋友是值得信任的，所以可以對(duì)他們公開一些自己的隱私，運(yùn)算符重載的實(shí)質(zhì)就是函數(shù)重載或函數(shù)多態(tài)，運(yùn)算符重載是一種形式的C++多態(tài)，目的在于讓人能夠用同名的函數(shù)來完成不同的基本操作2022-04-04
Base64是一種很常用的編碼方式，利用它可以將任何二進(jìn)制的字符編碼到可打印的64個(gè)字符之中， 這樣，不管是圖片，中文文本等都可以編碼成只有ASCII的純文本。2015-11-11
關(guān)于VS2019 C++項(xiàng)目同時(shí)出現(xiàn)LNK2005 和LNK1169 error 的解決辦法
這篇文章主要介紹了關(guān)于VS2019 C++項(xiàng)目同時(shí)出現(xiàn)LNK2005 和LNK1169 error 的解決辦法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
使用C語言順序表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧的代碼示例
這篇文章主要給大家介紹了如何使用C語言順序表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧,文章通過代碼示例介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的參考價(jià)值,需要的朋友可以參考下2023-09-09
這篇文章主要給大家分享的是C++構(gòu)造函數(shù)一些常見的坑，文章圍繞C++構(gòu)造函數(shù)的相關(guān)資料展開關(guān)于C++構(gòu)造函數(shù)坑的內(nèi)容，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-01-01
通過c語言調(diào)用系統(tǒng)curl動(dòng)態(tài)庫的示例詳解
這篇文章中我們將通過一個(gè)簡單的示例來講解如何在Ubuntu系統(tǒng)中通過C語言調(diào)用動(dòng)態(tài)庫（共享庫）的方法,我們將使用libcurl庫,這是一個(gè)基于客戶端的URL傳輸庫,廣泛用于各種程序和應(yīng)用中以訪問網(wǎng)頁和服務(wù)器數(shù)據(jù),需要的朋友可以參考下2024-03-03
使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形，其中著重的講解了OpenCV使用過程中需要注意的一些小細(xì)節(jié)，避免浪費(fèi)大家在開發(fā)過程中浪費(fèi)多余的時(shí)間2021-08-08
這篇文章主要介紹了C語言編程中函數(shù)的基本學(xué)習(xí)教程,其中著重講到了傳值調(diào)用與參數(shù),需要的朋友可以參考下2015-12-12
詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)
這篇文章主要介紹了詳解C++ 編寫String 的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)的相關(guān)資料,這里提供實(shí)例幫助大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-08-08
C語言詳細(xì)圖解浮點(diǎn)型數(shù)據(jù)的存儲(chǔ)實(shí)現(xiàn)
使用編程語言進(jìn)行編程時(shí)，需要用到各種變量來存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個(gè)變量時(shí)，就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類型的信息，操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2022-05-05