huffman树和huffman编码

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

//huffman树和huffman编码

#include <stdlib.h>

#include <iostream.h>

#include <stdio.h>

#include <string.h>

#define OVERFLOW -1

typedef struct

{

char letter;

int weight;

int parent;

int lchild;

int rchild;

}HTNode,*HuffmanTree;

typedef char * *HuffmanCode;

void Select(HuffmanTree &HT,int i,int &s1,int &s2)

{

/*选择森林中,根结点的权值最小和次小的两个树,

*将其根结点的下标号记入s1和s2中

*/

int j, k;

for(k = 1; k < i; k++)

{

if(HT[k].parent != NULL)

continue;

s1 = k;/*init the number*/

break;

}

for(j = 1; j < i; j++)

{

if(HT[j].parent != NULL)

continue;

if(HT[j].weight < HT[s1].weight)

s1 = j;

}

for(k = 1; k <= i; k++)

{

if(HT[k].parent != NULL || k == s1)

continue;

s2 = k;

break;

}

for(j = 1; j < i; j++)

{

if(HT[j].parent != NULL)

continue;

if(HT[j].weight <= HT[s2].weight && j != s1)

s2 = j;

}

}

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

{

HuffmanTree p;

int m,i,s1,s2,f,c;

int Istart = 1;

char *cd;

if(n <= 1)

return;

m = 2*n-1;

if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))

exit(OVERFLOW);

for(p=HT+1,i=1;i<=n;++i,++zi,++p,++w)

{

/*生成独立的森林*/

p->parent = NULL;

p->letter = *zi;

p->lchild = NULL;

p->rchild = NULL;

p->weight = *w;

}

for(;i<=m;++i,++p)

{

(*p).weight=0;

(*p).parent=0;

(*p).lchild=0;

(*p).rchild=0;

}

for(i=n+1;i<=m;++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((n+1)*sizeof(char *));

cd=(char*)malloc(n*sizeof(char));/*临时的code存储*/

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

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

{

Istart = n - 1;

/*按已生成的哈夫曼树,得到各个字符的哈夫曼编码

*/

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

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

cd[--Istart] = '0';

else

cd[--Istart] = '1';

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

strcpy(HC[i], &cd[Istart]);

}

free(cd);

}

void main()

{

HuffmanTree HT;

HuffmanCode HC;

int i,j,yu;

char zi[9]={'A','B','C','D','E','F','G','H'};

int w[100];

char z;

char c[100];

z='A';

cout<<endl;

for(i=0;i<=7;i++)

{

cout<<"please input the weight for "<<z<<":";

cin>>w[i];

z++;

}

HuffmanCoding(HT,HC,zi,w,8);

cout<<endl;

cout<<"char weight huffmancode "<<endl;

for(i=1;i<=8;i++)

cout<<HT[i].letter<<" "<<HT[i].weight<<" "<<HC[i]<<endl;

cout<<"please input the text:";

cin>>c;

cout<<"The code is:";

for(i=0; i < strlen(c); i++)

/*根据字符的哈夫曼编码,将输入的文本(变量c表示的)翻译成电码。

*/

cout<<HC[(c[i] - 'A' + 1)];

cout<<endl;

cout<<"Enter the code:";

cin>>c;

j=strlen(c);

yu=15;

i=1;

cout<<"The text is:";

while(i <= j)

{

while(HT[yu].lchild != 0)/*因为是完全二叉树*/

{

if(c[i-1] == '0')

{

/*用哈夫曼树,将输入的电码(变量c表示的)翻译成文本,

说明:变量名c在程序中

*/

yu = HT[yu].lchild;

i++;

continue;

}

if(c[i-1]== '1')

{

yu=HT[yu].rchild;

i++;

continue;

}

}

/*显示由部分电码译码得到的字符,并准备对后面的电码进行译码*/

cout<<HT[yu].letter;

yu = 15;

}

cout<<endl;

}

//没有出错处理

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航