霍夫曼编码之一.docx

霍夫曼编码之一.docx

《霍夫曼编码之一.docx》由会员分享，可在线阅读，更多相关《霍夫曼编码之一.docx（8页珍藏版）》请在冰点文库上搜索。

霍夫曼编码之一

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

/*#include"stdcon.h"*/

#include"malloc.h"

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBBLE-1

#defineOVERFLOW-2

typedefintStatus;

typedefstruct{

unsignedintweight;

unsignedintparent,lchild,rchild;

}HTNode,*HuffmanTree;/*动态分配数组存储霍夫曼树*/

typedefchar**HuffmanCode;/*动态分配数组存储霍夫曼编码表*/

voidSelect（HuffmanTreeHT,intn,int*s1,int*s2）{

intm1,m2;

inti,weight;

weight=30000;

for（i=1;i<=n;i++）{

if（HT[i].parent==0&&HT[i].weight

m1=i;

weight=HT[i].weight;

}

}

weight=30000;

for（i=1;i<=n;i++）{

if（i!

=m1&&HT[i].parent==0&&HT[i].weight

m2=i;

weight=HT[i].weight;

}

}

*s1=m1;

*s2=m2;

}

voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*w,intn）{

/*w存放n个字符的权值（均>0），构造霍夫曼树HT，并求出n个字符的霍夫曼编码HC.*/

intm,i;

ints1,s2;

HuffmanTreep;

char*cd;

intstart;

intc,f;

if（n<=1）

return;

m=2*n-1;/*霍夫曼树的大小*/

*HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/

for（p=*HT+1,i=1;i<=n;++i,++p,++w）{

p->weight=*w;

p->lchild=0;

p->rchild=0;

p->parent=0;

}

for（;i<=m;++i,++p）{

p->weight=0;

p->lchild=0;

p->rchild=0;

p->parent=0;

}

for（i=n+1;i<=m;++i）{/*建立霍夫曼树*/

/*在HT[1-i-1]选择parent为零且weight为最小的两个结点，其序号分别为s1和s2*/

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（（n+1）*sizeof（char*））;

cd=（char*）malloc（n*sizeof（char））;

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

for（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））;

strcpy（（*HC）[i],&cd[start]）;

}

free（cd）;

}

StatusoutputCode（HuffmanCodeHC,intn）{

inti;

for（i=1;i<=n;i++）

printf（"->%s\n",HC[i]）;

returnOK;

}

voidoutputHuffmanTree（HuffmanTreeHT,intm）{

inti;

printf（"\n"）;

printf（""）;

for（i=1;i<=m;i++）

printf（"%4d",i）;

printf（"\n"）;

printf（"weight:

"）;

for（i=1;i<=m;i++）

printf（"%4d",HT[i].weight）;

printf（"\n"）;

printf（"parent:

"）;

for（i=1;i<=m;i++）

printf（"%4d",HT[i].parent）;

printf（"\n"）;

printf（"lchild:

"）;

for（i=1;i<=m;i++）

printf（"%4d",HT[i].lchild）;

printf（"\n"）;

printf（"rchild:

"）;

for（i=1;i<=m;i++）

printf（"%4d",HT[i].rchild）;

printf（"\n"）;

}

char*codeing（char*str,HuffmanCodeHC）{

inti;

char*cd;

cd=（char*）malloc（50*sizeof（char））;

cd[0]='\0'

;

i=0;

while（str[i]!

='\0'）{

switch（str[i]）{

case'a':

strcat（cd,HC[1]）;

break;

case'b':

strcat（cd,HC[2]）;

break;

case'c':

strcat（cd,HC[3]）;

break;

case'd':

strcat（cd,HC[4]）;

break;

case'e':

strcat（cd,HC[5]）;

break;

}

i++;

}

returncd;

}

char*decodeing（char*str,HuffmanTreeHT）{

inti,j,k,c;

char*cd;

cd=（char*）malloc（30*sizeof（char））;

i=0;

j=0;

while（str[i]!

='\0'）{

c=9;

while（str[i]!

='\0'&&HT[c].lchild!

=0）{

if（str[i]=='0'）

c=HT[c].lchild;

else

c=HT[c].rchild;

i++;

}

switch（c）{

case1:

cd[j]='a';

break;

case2:

cd[j]='b';

break;

case3:

cd[j]='c';

break;

case4:

cd[j]='d';

break;

case5:

cd[j]='e';

break;

}

j++;

}

cd[j]='\0';

returncd;

}

voidmain（）{

intw[5]={20,10,5,3,1};

HuffmanTreeHT;

HuffmanCodeHC;

charstr[10],*code,*decode;

inti;

HuffmanCoding（&HT,&HC,w,5）;

outputHuffmanTree（HT,9）;

printf（"\n"）;

outputCode（HC,5）;

printf（"\n"）;

printf（"sourse:

"）;

scanf（"%s",str）;

code=codeing（str,HC）;

printf（"code:

%s\n",code）;

decode=decodeing（code,HT）;

printf（"decode:

%s\n",decode）;

getch（）;

}