对一串字符进行huffman编码并解码

答案:2 悬赏:40 手机版

解决时间 2021-11-10 08:24

提问者网友：椧運幽默
2021-11-09 18:21

对一串字符进行huffman编码并解码

最佳答案

五星知识达人网友：走死在岁月里
2021-11-09 19:09

#include
#include
#include
#include

#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)
{

int j, k;
for(k = 1; k < i; k++)
{
if(HT[k].parent != NULL)
continue;
s1 = k;
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));
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< for(i=0;i<=7;i++)
{
cout<<"please input the weight for "< cin>>w[i];
z++;
}
HuffmanCoding(HT,HC,zi,w,8);
cout< cout<<"char weight huffmancode "< for(i=1;i<=8;i++)
cout< cout<<"please input the text:";
cin>>c;
cout<<"The code is:";

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

cout<
cout< 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')
{

yu = HT[yu].lchild;
i++;
continue;
}
if(c[i-1]== '1')
{
yu=HT[yu].rchild;
i++;
continue;
}
}

cout< yu = 15;
}
cout<}

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！