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

2025-06-22 12:44:17

推荐回答（2个）

回答1：

#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)
{
/*选择森林中，根结点的权值最小和次小的两个树，
*将其根结点的下标号记入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< 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++)
/*根据字符的哈夫曼编码，将输入的文本（变量c表示的）翻译成电码。
*/
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')
{
/*用哈夫曼树，将输入的电码（变量c表示的）翻译成文本，
说明：变量名c在程序中
*/
yu = HT[yu].lchild;
i++;
continue;
}
if(c[i-1]== '1')
{
yu=HT[yu].rchild;
i++;
continue;
}
}
/*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/
cout< yu = 15;
}
cout<}

回答2：

#include
#include
#include
#include
using namespace std;
const MAXSIZE=100;
typedef struct Huffmantree
{
char cname;
int weight,mark;
struct Huffmantree *parent,*lchild,*rchild,*next;
}Hftree,*linktree;

linktree tidy_string(char ch[])
{
int i=0;
linktree tree,ptr,beforeptr,node;
tree=(linktree)malloc(sizeof(Hftree));
if(!tree)
return NULL;
tree->next=NULL;
for(i=0;ch[i]!='\0'&&ch[i]!='\n';i++)
{
ptr=tree;
beforeptr=tree;
node=(linktree)malloc(sizeof(Hftree));
if(!node)
return NULL;

node->parent=NULL;
node->lchild=NULL;
node->rchild=NULL;
node->next=NULL;
node->mark=0;
node->cname=ch[i];
node->weight=1;

if(tree->next==NULL)
tree->next=node;
else
{
ptr=tree->next;
while(ptr&&ptr->cname!=node->cname)
{
ptr=ptr->next;
beforeptr=beforeptr->next;
}
if(ptr&&ptr->cname==node->cname)
{
ptr->weight+=1;
free(node);
}
else
{
node->next=beforeptr->next;
beforeptr->next=node;
}

}

}
return tree;
}

linktree squent_node(linktree tree)
{
linktree head,ph,pt,beforeph;
head=(linktree)malloc(sizeof(Hftree));
if(!head)
return NULL;
head->next=NULL;

ph=head;
beforeph=head;
while(tree->next)
{
pt=tree->next;
tree->next=pt->next;
pt->next=NULL;
ph=head->next;
beforeph=head;
if(head->next==NULL)
head->next=pt;
else
{
while(ph&&ph->weightweight)
{
ph=ph->next;
beforeph=beforeph->next;
}
pt->next=beforeph->next;
beforeph->next=pt;
}
}
free(tree);
return head;
}

linktree createHtree(linktree tree)
{
linktree p,q,newnode,beforep;
for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)
{
tree->next=q->next;
q->next=NULL;
p->next=NULL;
newnode=(linktree)malloc(sizeof(Hftree));
if(!newnode)
return NULL;
newnode->next=NULL;
newnode->mark=0;
newnode->lchild=p;
newnode->rchild=q;
p->parent=newnode;
q->parent=newnode;
newnode->weight=p->weight+q->weight;
p=tree->next;
beforep=tree;
if(p!=NULL&&p->weight>=newnode->weight)
{
newnode->next=beforep->next;
beforep->next=newnode;
}
else
{
while(p!=NULL&&p->weightweight)
{
p=p->next;
beforep=beforep->next;
}
newnode->next=beforep->next;
beforep->next=newnode;
}
}
return (tree->next);
}

void Huffman_Coding(linktree tree)
{
int index=0;
char *code;
linktree ptr=tree;
code=(char*)malloc(10*sizeof(char));
printf("字符以及它的相应权数：哈夫曼编码：\n\n");
if(ptr==NULL)
{
printf("哈夫曼树是空的!\n");
exit(0);
}
else
{
while(ptr->lchild&&ptr->rchild&&ptr->mark==0)
{
while(ptr->lchild&&ptr->lchild->mark==0)
{
code[index++]='0';
ptr=ptr->lchild;
if(!ptr->lchild&&!ptr->rchild)
{
ptr->mark=1;
code[index]='\0';
printf("\tw[%c]=%d\t\t\t",ptr->cname,ptr->weight);
for(index=0;code[index]!='\0';index++)
printf("%c",code[index]);
printf("\n");
ptr=tree;
index=0;
}
}
if(ptr->rchild&&ptr->rchild->mark==0)
{
ptr=ptr->rchild;
code[index++]='1';
}
if(!ptr->lchild&&!ptr->rchild)
{
ptr->mark=1;
code[index++]='\0';
printf("\tw[%c]=%d\t\t\t",ptr->cname,ptr->weight);
for(index=0;code[index]!='\0';index++)
printf("%c",code[index]);
printf("\n");
ptr=tree;
index=0;
}
if(ptr->lchild->mark==1&&ptr->rchild->mark==1)
{
ptr->mark=1;
ptr=tree;
index=0;
}
}
}
printf("\n");
free(code);
}

void Huffamn_Decoding(linktree tree,char code[])
{
int i=0,j=0;
char *char0_1;
linktree ptr=tree;
char0_1=(char*)malloc(10*sizeof(char));
cout<<"哈夫曼编码相应的字符\n\n";
for(j=0,ptr=tree;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j=0,ptr=tree)
{
for(j=0;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j++,i++)
{
if(code[i]=='0')
{
ptr=ptr->lchild;
char0_1[j]='0';
}
if(code[i]=='1')
{
ptr=ptr->rchild;
char0_1[j]='1';
}

}
if(!ptr->lchild&&!ptr->rchild)
{
char0_1[j]='\0';
for(j=0;char0_1[j]!='\0';j++)
cout<printf("\t\t%c\n",ptr->cname);
}
if(code[i]=='\0'&&ptr->lchild&&ptr->rchild)
{
char0_1[j]='\0';
cout<<" 没有与最后几个字符的0，1序列："<return;
}
}
free(char0_1);

}

void deletenode(linktree tree)
{
linktree ptr=tree;
if(ptr)
{
deletenode(ptr->lchild);
deletenode(ptr->rchild);
free(ptr);
}
}

int main()
{
char string[MAXSIZE],code[MAXSIZE];
linktree temp,ht,htree,ptr=NULL;
cout<<"编码：请输入要当前字符串："<cin>>string;
cout<temp=tidy_string(string);
ht=squent_node(temp);
htree=createHtree(ht);
Huffman_Coding(htree);
cout<<"解码：请输入要解码的0，1序列："<cin>>code;
cout<Huffamn_Decoding(htree,code);
deletenode(htree);
return 0;

}