C++霍夫曼編碼

暫時(shí)只實(shí)現(xiàn)了顯示編碼結(jié)果，求平均碼長(zhǎng)沒有完成。

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),鐵力企業(yè)網(wǎng)站建設(shè),鐵力品牌網(wǎng)站建設(shè),網(wǎng)站定制,鐵力網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,鐵力網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

#include?iostream

using?namespace?std;

/*

*?霍夫曼樹結(jié)構(gòu)

*/

class?HuffmanTree

{

public:

unsigned?int?Weight,?Parent,?lChild,?rChild;

};

typedef?char?**HuffmanCode;

/*

*?從結(jié)點(diǎn)集合中選出權(quán)值最小的兩個(gè)結(jié)點(diǎn)

*?將值分別賦給s1和s2

*/

void?Select(HuffmanTree*?HT,int?Count,int?*s2,int?*s1)

{

unsigned?int?temp1=0;

unsigned?int?temp2=0;

unsigned?int?temp3;

for(int?i=1;i=Count;i++)

{

? if(HT[i].Parent==0)

? {

? ? ? if(temp1==0)

? ? ? {

? ? ? ? ? temp1=HT[i].Weight;

? ? ? ? ? (*s1)=i;

? ? ? }

? ? ? else

? ? ? {

? ? ? ? ? if(temp2==0)

? ? ? ? ? {

? ? ? ? ? ? ? temp2=HT[i].Weight;

? ? ? ? ? ? ? (*s2)=i;

? ? ? ? ? ? ? if(temp2temp1)

? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? temp3=temp2;

? ? ? ? ? ? ? ? ? temp2=temp1;

? ? ? ? ? ? ? ? ? temp1=temp3;

? ? ? ? ? ? ? ? ? temp3=(*s2);

? ? ? ? ? ? ? ? ? (*s2)=(*s1);

? ? ? ? ? ? ? ? ? (*s1)=temp3;

? ? ? ? ? ? ? }

? ? ? ? ? }

? ? ? ? ? else

? ? ? ? ? {

? ? ? ? ? ? ? if(HT[i].Weighttemp1)

? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? temp2=temp1;

? ? ? ? ? ? ? ? ? temp1=HT[i].Weight;

? ? ? ? ? ? ? ? ? (*s2)=(*s1);

? ? ? ? ? ? ? ? ? (*s1)=i;

? ? ? ? ? ? ? }

? ? ? ? ? ? ? if(HT[i].Weighttemp1HT[i].Weighttemp2)

? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? temp2=HT[i].Weight;

? ? ? ? ? ? ? ? ? (*s2)=i;

? ? ? ? ? ? ? }

? ? ? ? ? }

? ? ? }

? }

}

}

/*

*?霍夫曼編碼函數(shù)

*/

void?HuffmanCoding(HuffmanTree?*?HT,

? ? ? ? ? ? ?HuffmanCode?*?HC,

? ? ? ? ? ? ?int?*Weight,

? ? ? ? ? ? ?int?Count)

{

int?i;

int?s1,s2;

int?TotalLength;

char*?cd;

unsigned?int?c;

unsigned?int?f;

int?start;

if(Count=1)?return;

TotalLength=Count*2-1;

HT?=?new?HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];

for(i=1;i=Count;i++)

{

? HT[i].Parent=0;

? HT[i].rChild=0;

? HT[i].lChild=0;

? HT[i].Weight=(*Weight);

? Weight++;

}

for(i=Count+1;i=TotalLength;i++)

{

? HT[i].Weight=0;

? HT[i].Parent=0;

? HT[i].lChild=0;

? HT[i].rChild=0;

}

//建造霍夫曼樹

for(i=Count+1;i=TotalLength;++i)

{

Select(HT,?i-1,?s1,?s2);

HT[s1].Parent?=?i;

HT[s2].Parent?=?i;

HT[i].lChild?=?s1;

HT[i].rChild?=?s2;

HT[i].Weight?=?HT[s1].Weight?+?HT[s2].Weight;

}

//輸出霍夫曼編碼

(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));

cd?=?new?char[Count*sizeof(char)];

cd[Count-1]='\0';

for(i=1;i=Count;++i)

{

? start=Count-1;

? for(c?=?i,f?=?HT[i].Parent;?f?!=?0;?c?=?f,?f?=?HT[f].Parent)

? {

? ? ? if(HT[f].lChild?==?c)

? ? ? ? ? cd[--start]='0';

? ? ? else

? ? ? ? ? cd[--start]='1';

? ? ? (*HC)[i]?=?new?char?[(Count-start)*sizeof(char)];

? ? ? strcpy((*HC)[i],?cd);

? }

}

delete?[]?HT;

delete?[]?cd;

}

/*

*?在字符串中查找某個(gè)字符

*?如果找到，則返回其位置

*/

int?LookFor(char?*str,?char?letter,?int?count)

{

int?i;

for(i=0;icount;i++)

{

? if(str[i]==letter)?return?i;

}

return?-1;

}

void?OutputWeight(char?*Data,int?Length,

? ? ? ? ? ? char?**WhatLetter,

? ? ? ? ? ? int?**Weight,int?*Count)

{

int?i;

char*?Letter?=?new?char[Length];

int*?LetterCount?=?new?int[Length];

int?AllCount=0;

int?Index;

int?Sum=0;

float?Persent=0;

for(i=0;iLength;i++)

{

? if(i==0)

? {

? ? ? Letter[0]=Data[i];

? ? ? LetterCount[0]=1;

? ? ? AllCount++;

? }

? else

? {

? ? ? Index=LookFor(Letter,Data[i],AllCount);

? ? ? if(Index==-1)

? ? ? {

? ? ? ? ? Letter[AllCount]=Data[i];

? ? ? ? ? LetterCount[AllCount]=1;

? ? ? ? ? AllCount++;

? ? ? }

? ? ? else

? ? ? {

? ? ? ? ? LetterCount[Index]++;

? ? ? }

? }

}

for(i=0;iAllCount;i++)

{

? Sum=Sum+LetterCount[i];

}

(*Weight)?=?new?int[AllCount];

(*WhatLetter)?=?new?char[AllCount];

for(i=0;iAllCount;i++)

{

? Persent=(float)LetterCount[i]/(float)Sum;

? (*Weight)[i]=(int)(100*Persent);

? (*WhatLetter)[i]=Letter[i];

}

(*Count)=AllCount;

delete?[]?Letter;

delete?[]?LetterCount;

}

int?main()

{

HuffmanTree?*?HT?=?NULL;

HuffmanCode?HC;

char?Data[100];

char?*WhatLetter;

int?*Weight;

int?Count;

cout"請(qǐng)輸入一行文本數(shù)據(jù):"endl;

cinData;

coutendl;

OutputWeight(Data,strlen(Data),

? ? ? ? ? ?WhatLetter,

? ? ? ? ? ?Weight,

? ? ? ? ? ?Count);

HuffmanCoding(HT,?HC,?Weight,?Count);

cout"字符出現(xiàn)頻率編碼結(jié)果"endl;

for(int?i?=?0;?iCount;?i++)

{

coutWhatLetter[i]"? ? ?";

coutWeight[i]"%\t";

coutHC[i+1]endl;

}

coutendl;

system("pause");

return?0;

}

霍夫曼編碼 用c語言實(shí)現(xiàn)

以前寫的，證明最優(yōu)子結(jié)構(gòu)，隨便一本算法書上就有. #includestdio.h

#includestdlib.h

#define NIL -2

#define Size_Max_bm 30

#define left(i) (2*(i)+1)

#define right(i) (2*(i)+2)

#define swap(a,b) {cjys t;t=(a);(a)=(b);(b)=t;}

#define parent(i) ((i)%2?((i)-1)/2:((i)-2)/2)typedef struct cjys

{

char sj;

int pl;

struct cjys *left;

struct cjys *right;

}cjys;typedef struct cjdl

{

int size;

int leapsize;

cjys *p;

}cjdl;

cjys *fpnn(void);

void input(cjdl *p);

cjys *fpnn(void);

void zxdwh(cjys *p, int i, int leapsize);

void rd(cjdl *p, cjys tp);

cjys cd(cjdl *p);

void hbs(cjdl *p);

cjys *cjs(cjdl *p);

void bls(cjys *p,int *jl, int i);

void disp(char *tp, cjys *p);int main()

{

cjdl p;

char x[255];

cjys *re=NULL;

int jl[Size_Max_bm];

input(p);

re=cjs(p);

printf("對(duì)照編碼圖為:\n");

bls(re,jl,0);

freopen("CON","r",stdin);

printf("輸入Huffman碼(VLC):");

scanf("%s",x);

disp(x,re);

system("pause");

}

void input(cjdl *p)

{

int i;

cjys *tp;

tp=fpnn();

printf("輸入字母?jìng)€(gè)數(shù):");

scanf("%d", p-size);

p-p=malloc(sizeof(cjys)*p-size);

p-leapsize=0;

for(i = 0; i p-size;i++)

{

printf("輸入第%d字母:",i+1),scanf(" %c",tp-sj);

printf("輸入出現(xiàn)次數(shù)(頻率整數(shù)):"),scanf("%d",tp-pl);

rd(p,*tp);

}

free(tp);

}

cjys *fpnn(void)

{

cjys *p=NULL;

p=malloc(sizeof(cjys));

p-left=NULL;

p-right=NULL;

return p;

} void zxdwh(cjys *p, int i, int leapsize)

{

int l=left(i), r=right(i), mini=i;

if(lleapsize p[l].plp[mini].pl)

mini=l;

if(rleapsize p[r].plp[mini].pl)

mini=r;

if(mini != i)

{

swap(p[i],p[mini]);

zxdwh(p,mini,leapsize);

}

}

void rd(cjdl *p, cjys tp)

{

if(p-leapsize == p-size)

{

printf("隊(duì)列已滿!");

exit(0);

}

p-p[p-leapsize]=tp;

int j=p-leapsize,k=parent(j);

while(k=0 p-p[j].pl p-p[k].pl)

{

swap(p-p[j],p-p[k]);

j=k;

k=parent(j);

}

p-leapsize++;

}

cjys cd(cjdl *p)

{

if(p-leapsize == 0)

{

printf("隊(duì)列已空!");

exit(0);

}

cjys tp=p-p[0];

p-leapsize--;

p-p[0]=p-p[p-leapsize];

zxdwh(p-p,0,p-leapsize);

return tp;

}

void hbs(cjdl *p)

{

cjys *p1=NULL, *p2=NULL;

cjys tp;

p1=fpnn();

p2=fpnn();

*p1=cd(p);

*p2=cd(p);

tp.left=p1;

tp.right=p2;

tp.pl=p1-pl+p2-pl;

tp.sj=NIL;

rd(p,tp);

}cjys *cjs(cjdl *p)

{

int i, n=p-leapsize;

cjys *tp=NULL;

tp=fpnn();

for(i = 0; i n-1; i++)

hbs(p);

*tp=p-p[0];

return tp;

}

void bls(cjys *p, int *jl, int i)

{

if(p == NULL)

return;

if(p-sj!=NIL)

{

int i2;

printf("%c:",p-sj);

for(i2 = 0; i2 i; i2++)

printf("%d",jl[i2]);

printf("\n");

}

jl[i]=0;

bls(p-left,jl,i+1);

jl[i]=1;

bls(p-right,jl,i+1);

}

void disp(char *tp, cjys *p)

{

cjys *ttp=NULL;

int pd=0;

while(1)

{

ttp=p;

while(1)

{

if(ttp-sj != NIL)

{

printf("%c",ttp-sj);

break;

}

if(*tp == '\0')

{

pd=1;

break;

}

if(*tp++ == '0' )

ttp=ttp-left;

else

ttp=ttp-right;

}

if(pd)

break;

}

}

哈夫曼編碼 c++，輸入字符和出現(xiàn)的概率，求輸入的數(shù)據(jù)的Huffman樹路徑？要求代碼?。?！，急急急

這是我們大三做的一個(gè)上機(jī)題：

上機(jī)題：設(shè)電文字符集D及各字符出現(xiàn)的概率F如下：

D={a，b，c，d，e，f，g，h}（字符數(shù)n=8）

F={5，29，7，8，14，23，3，11}(%)

編寫完成下列功能的程序：

①構(gòu)造關(guān)于F的Huffman樹；

②求出并打印D總各字符的Huffman編碼。

程序結(jié)構(gòu)： 類型說明；

構(gòu)造Huffman樹的函數(shù)：Huffman_tree(H[m+1])；

求Huffman編碼的函數(shù)：Huffman_code(code[n+1])；

main()

{ 變量說明；

輸入字符集D及頻率F；

調(diào)用Huffman_tree(H)；

調(diào)用Huffman_code(code)；

打印編碼；Y繼續(xù)，N退出}

運(yùn)行后，輸入8個(gè)字符（中間不能有空格，否則將空格視為字符處理），然后輸入概率（整數(shù)，空格或回車分隔。如果要支持浮點(diǎn)數(shù)，要改程序）然后Enter，出現(xiàn)構(gòu)造的霍夫曼節(jié)點(diǎn)和編碼，程序如下

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#define N 8

#define M 2*N-1

#define MAX 32767

typedef char datatype;

typedef struct

{

int wi;

char data;

int Parent,Lchild,Rchild;

}huffm;

typedef struct

{

char bits[N+1];

int start;

char ch;

}ctype;

void Huffman_tree(huffm H[M+1])

{

int i,j,p1,p2;

int w,s1,s2;

for(i=1;i=M;i++)

{

H[i].wi=MAX;

H[i].Parent=0;

H[i].Lchild=H[i].Rchild=0;

}

printf("please enter the weight:\n");

for(i=1;i=N;i++)

{

scanf("%d",H[i].wi);

}

for(i=N+1;i=M;i++)

{

p1=p2=0;

s1=s2=MAX;

for(j=1;j=M;j++)

if(H[j].Parent==0)

if(H[j].wis1)

{

s2=s1;

s1=H[j].wi;

p2=p1; p1=j;

}

else if(H[j].wis2) {s2=H[j].wi; p2=j;}

H[p1].Parent=H[p2].Parent=i;

H[i].Lchild=p1;

H[i].Rchild=p2;

H[i].wi=H[p1].wi+H[p2].wi;

}

printf("Number\tParent\tLchild\tRchild\n");

for(i=1;i=M;i++)

printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);

}

void Huffman_code(ctype code[N+1])

{

int i,j,p,s;

char c[N];

huffm H[M+1];

ctype md;

printf("please enter char:\n");

/* for(i=1;i=N;i++)

{

scanf("%c",c);

H[i].data=code[i].ch=c;

}

*/

scanf("%s",c);

for(i=1;i=N;i++)H[i].data=code[i].ch=c[i-1];

Huffman_tree(H);

for(i=1;i=N;i++)

{

md.ch=code[i].ch;

md.start=N+1;

s=i;

p=H[i].Parent;

while(p!=0)

{

md.start--;

if(H[p].Lchild==s)

md.bits[md.start]='1';

else

md.bits[md.start]='0';

s=p;

p=H[p].Parent;

}

code[i]=md;

}

printf("print the code:\n");

for(i=1;i=N;i++)

printf("%c\t",code[i].ch);

printf("\n");

for(i=1;i=N;i++)

{

for(j=code[i].start;j=N;j++)

printf("%c",code[i].bits[j]);

printf("\t");

}

printf("\n");

}

int Continue()

{ char c;

getchar();

printf("continue? y/n\n");

c=getchar();

if(c=='y') return 1;

else return 0;

}

main()

{

do{

/* huffm H[M+1]; */

ctype code[N+1];

Huffman_code(code);

}while(Continue());

}

Huffman編碼C語言實(shí)現(xiàn)

說明：本程序是依據(jù)嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語言版）上的代碼實(shí)現(xiàn)的。

#pragmaonce

#includestdio.h

#includetchar.h

#includestdlib.h

#define MAX 100

typedefstruct{ //節(jié)點(diǎn)

int weight;

int parent, lchild, rchild;

}HTNode, *HuffmanTree;

typedefchar **HuffmanCode; //字符串?dāng)?shù)組，用于存儲(chǔ)葉子節(jié)點(diǎn)的編碼

void SelectMinNode(HuffmanTree HT, int m, int i1, int i2) //找出權(quán)值最小的兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)

{

HuffmanTree p = HT;

int s1, s2;

s1 = s2 = MAX;

i1 = i2 = 1;

for(int i=1; i=m; i++)

{

if(!(p+i)-parent)

{

if((p+i)-weight s1)

{

i2 = i;

s1 = (p+i)-weight ;

}

}

}

for(int i=1; i=m; i++)

{

if(!(p+i)-parent i!=i2)

{

if((p+i)-weight s2)

{

i1 = i;

s2 = (p+i)-weight ;

}

}

}

}

void StrCopy(char *p, char *q, int start) //從字符數(shù)組中第start個(gè)字符開始復(fù)制

{

char *c1, *c2;

c1 = p;

while(q != '\0')

{

*c1 = q;

c1++;

start++;

}

*c1 = q;//別忘了將‘\n’復(fù)制過來

}

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n)

{ //HT赫夫曼樹節(jié)點(diǎn)數(shù)組，HC存儲(chǔ)赫夫曼編碼，*w 節(jié)點(diǎn)權(quán)值數(shù)組的首地址，n節(jié)點(diǎn)個(gè)數(shù)

int i, i1, i2, m;

HuffmanTree p;

if(n=1) return;

m = 2 * n -1; //n個(gè)葉子節(jié)點(diǎn)的赫夫曼樹的節(jié)點(diǎn)總數(shù)為2n-1，可以結(jié)合樹的度為n-1自己證明。

HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //數(shù)組首元素不使用，故多分配一個(gè)空間

p = HT + 1;

for(i=1;i=n;++i,++p,++w) //n個(gè)葉子節(jié)點(diǎn)初始化

{

p-weight = *w;

p-lchild = 0;

p-rchild = 0;

p-parent = 0;

}

for(;i=m;++i,++p) //非葉子節(jié)點(diǎn)初始化

{

p-weight = 0;

p-lchild = 0;

p-rchild = 0;

p-parent = 0;

}

for(i=n+1;i=m;++i) //對(duì)非葉子節(jié)點(diǎn)重新計(jì)算

{

SelectMinNode(HT, i-1, i1, i2);

HT[i1].parent = i;

HT[i2].parent = i;

HT[i].lchild = i1;

HT[i].rchild = i2;

HT[i].weight = HT[i1].weight + HT[i2].weight ;

}

///從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)求赫夫曼編碼

char* cd;

int start, c, f;

HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指針數(shù)組，同樣多分配一個(gè)

cd = (char*)malloc(n*sizeof(char)); //零時(shí)變量，用于存儲(chǔ)當(dāng)前葉子節(jié)點(diǎn)的赫夫曼編碼

cd[n-1] = '\0';

for(int i=1; i=n; i++)

{

start = n-1;

for(c=i,f=HT[i].parent; f!=0;c=f,f=HT[f].parent)

{

if(HT[f].lchild == c)

cd[--start] = '0';

else

cd[--start] = '1';

}

HC[i] = (char*)malloc((n-start)*sizeof(char));

StrCopy(HC[i], cd, start); //將存儲(chǔ)的編碼copy給HC的第i個(gè)數(shù)組

}

free(cd);

}

void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各節(jié)點(diǎn)的赫夫曼編碼

{

HuffmanCode p;

for(int i=1; i=n; i++)

{

p = HC;

printf("The weight %d HuffmanCode is: ", HT[i]);

while(*p[i]!='\0')

{

printf("%c",*p[i]);

p[i]++;

}

printf("\n");

}

}

void main()

{

int n = 8;

HuffmanTree HT;

HuffmanCode HC;

int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信號(hào)源的概率分布，即P={p0, p1,…, pK-1}

HuffmanCoding(HT, HC, a, n);

PrintHuffmanCode(HT, HC, n);

system("pause");}

霍夫曼（Huffman）編碼學(xué)習(xí)的重點(diǎn)和難點(diǎn)是什么

哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。 在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。這種方法是由David.A.Huffman發(fā)展起來的。 例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來表示，而z則可能花去25個(gè)位（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)位。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。

本文描述在網(wǎng)上能夠找到的最簡(jiǎn)單，最快速的哈夫曼編碼。本方法不使用任何擴(kuò)展動(dòng)態(tài)庫(kù)，比如STL或者組件。只使用簡(jiǎn)單的C函數(shù)，比如：memset，memmove，qsort，malloc，realloc和memcpy。

因此，大家都會(huì)發(fā)現(xiàn)，理解甚至修改這個(gè)編碼都是很容易的。

背景

哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。

編碼使用

我用簡(jiǎn)單的C函數(shù)寫這個(gè)編碼是為了讓它在任何地方使用都會(huì)比較方便。你可以將他們放到類中，或者直接使用這個(gè)函數(shù)。并且我使用了簡(jiǎn)單的格式，僅僅輸入輸出緩沖區(qū)，而不象其它文章中那樣，輸入輸出文件。

bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *pDes, int nDesLen);

bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *pDes, int nDesLen);

要點(diǎn)說明

速度

為了讓它(huffman.cpp)快速運(yùn)行，我花了很長(zhǎng)時(shí)間。同時(shí)，我沒有使用任何動(dòng)態(tài)庫(kù)，比如STL或者M(jìn)FC。它壓縮1M數(shù)據(jù)少于100ms（P3處理器，主頻1G）。

壓縮

壓縮代碼非常簡(jiǎn)單，首先用ASCII值初始化511個(gè)哈夫曼節(jié)點(diǎn)：

CHuffmanNode nodes[511];

for(int nCount = 0; nCount 256; nCount++)

nodes[nCount].byAscii = nCount;

然后，計(jì)算在輸入緩沖區(qū)數(shù)據(jù)中，每個(gè)ASCII碼出現(xiàn)的頻率：

for(nCount = 0; nCount nSrcLen; nCount++)

nodes[pSrc[nCount]].nFrequency++;

然后，根據(jù)頻率進(jìn)行排序：

qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);

現(xiàn)在，構(gòu)造哈夫曼樹，獲取每個(gè)ASCII碼對(duì)應(yīng)的位序列：

int nNodeCount = GetHuffmanTree(nodes);

構(gòu)造哈夫曼樹非常簡(jiǎn)單，將所有的節(jié)點(diǎn)放到一個(gè)隊(duì)列中，用一個(gè)節(jié)點(diǎn)替換兩個(gè)頻率最低的節(jié)點(diǎn)，新節(jié)點(diǎn)的頻率就是這兩個(gè)節(jié)點(diǎn)的頻率之和。這樣，新節(jié)點(diǎn)就是兩個(gè)被替換節(jié)點(diǎn)的父節(jié)點(diǎn)了。如此循環(huán)，直到隊(duì)列中只剩一個(gè)節(jié)點(diǎn)（樹根）。

// parent node

pNode = nodes[nParentNode++];

// pop first child

pNode-pLeft = PopNode(pNodes, nBackNode--, false);

// pop second child

pNode-pRight = PopNode(pNodes, nBackNode--, true);

// adjust parent of the two poped nodes

pNode-pLeft-pParent = pNode-pRight-pParent = pNode;

// adjust parent frequency

pNode-nFrequency = pNode-pLeft-nFrequency + pNode-pRight-nFrequency;

這里我用了一個(gè)好的訣竅來避免使用任何隊(duì)列組件。我先前就直到ASCII碼只有256個(gè)，但我分配了511個(gè)(CHuffmanNode nodes[511])，前255個(gè)記錄ASCII碼，而用后255個(gè)記錄哈夫曼樹中的父節(jié)點(diǎn)。并且在構(gòu)造樹的時(shí)候只使用一個(gè)指針數(shù)組(ChuffmanNode *pNodes[256])來指向這些節(jié)點(diǎn)。同樣使用兩個(gè)變量來操作隊(duì)列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。

接著，壓縮的最后一步是將每個(gè)ASCII編碼寫入輸出緩沖區(qū)中：

int nDesIndex = 0;

// loop to write codes

for(nCount = 0; nCount nSrcLen; nCount++)

{

*(DWORD*)(pDesPtr+(nDesIndex3)) |=

nodes[pSrc[nCount]].dwCode (nDesIndex7);

nDesIndex += nodes[pSrc[nCount]].nCodeLength;

}

(nDesIndex3): 3 以8位為界限右移后到達(dá)右邊字節(jié)的前面

(nDesIndex7): 7 得到最高位.

注意：在壓縮緩沖區(qū)中，我們必須保存哈夫曼樹的節(jié)點(diǎn)以及位序列，這樣我們才能在解壓縮時(shí)重新構(gòu)造哈夫曼樹（只需保存ASCII值和對(duì)應(yīng)的位序列）。

解壓縮

解壓縮比構(gòu)造哈夫曼樹要簡(jiǎn)單的多，將輸入緩沖區(qū)中的每個(gè)編碼用對(duì)應(yīng)的ASCII碼逐個(gè)替換就可以了。只要記住，這里的輸入緩沖區(qū)是一個(gè)包含每個(gè)ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發(fā)現(xiàn)一個(gè)葉節(jié)點(diǎn)，然后將它的ASCII值添加到輸出緩沖區(qū)中：

int nDesIndex = 0;

DWORD nCode;

while(nDesIndex nDesLen)

{

nCode = (*(DWORD*)(pSrc+(nSrcIndex3)))(nSrcIndex7);

pNode = pRoot;

while(pNode-pLeft)

{

pNode = (nCode1) ? pNode-pRight : pNode-pLeft;

nCode = 1;

nSrcIndex++;

}

pDes[nDesIndex++] = pNode-byAscii;

}

當(dāng)前名稱：c語言霍夫曼函數(shù) c語言阿克曼函數(shù)
文章出自：http://jinyejixie.com/article2/dodhsoc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)