C语言 编写哈弗曼树
问题描述：对输入的一串电文实现哈弗曼编码，在对哈弗曼编码编译并输出电文字符串。
基本要求：
1.输入一串电文，分析电文的字符个数并输出字符的个数或者频率
2.将电文转换成哈弗曼树，并输出每个字符相应的哈弗曼编码
3.将电文转换成哈弗曼编码的文档
扩展要求：
1.对原电文或译码电文通过文件保存
2.可以将转换成编码的文档，转换成原字符串并输出
一定要是C语言编写的，要简单易懂，能运行，最好在DEV-c++上面测试一下
不要在网上抄袭别人的，否则不给分
发送到我的邮箱：15212213858@139.com
满意的可以再加分
答案：#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000
typedef struct {
unsigned int weight;
unsigned int lchild,rchild,parent;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
//找到权值最小的两个结点
void select(HuffmanTree HT,int k,int &s1,int &s2)
{
int j;
s1=s2=k;
for(j=0;j<k;j++)
if(HT[j].parent==0)
{
if(HT[j].weight<HT[s1].weight)
{
s2=s1;
s1=j;
}
else if(HT[j].weight<HT[s2].weight)
s2=j;
}
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n)
{
int m,i,s1,s2;
HuffmanTree p;
m=2*n-1;
HT=(HuffmanTree)malloc(m*sizeof(HTNode));
for(p=HT,i=0;i<n;i++,p++,w++)
{
p->lchild=p->parent=p->rchild=0;
p->weight=*w;
}
for(i=n;i<m;i++,p++)
p->lchild=p->parent=p->rchild=p->weight=0;
for(i=n;i<m;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void print(HuffmanTree HT,char *u,int n)
{
int i;
char a;
printf("No\\tchar\\tweight\\tlchild\\trchild\\tparent\
");
for(i=0;i<2*n-1;i++)
{
if(i<n)
a=u[i];
else a='-';
printf("%d\\t%c\\t%d\\t%d\\t%d\\t%d\
",i,a,HT[i].weight,HT[i].lchild,HT[i].rchild,HT[i].parent);
}
}
//编码哈夫曼树
void Huffmancoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
int i,c,start;
int f;
char *cd;
HC=(HuffmanCode)malloc(n*sizeof(char *));
cd=(char *)malloc((n-1)*sizeof(char));
cd[n-1]='\\0';
for(i=0;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]);
}
}
//编码
void code(HuffmanCode HC,char *u,char *v)
{
int i,j;
for(i=0;i<strlen(v);i++)
for(j=0;j<strlen(u);j++)
if(v[i]==u[j])
{
printf("%s",HC[j]);
break;
}
}
//译码
void recode(HuffmanCode HC,int n,char *u,char *v)
{
int i,j,k;
char *p;
i=0;
p=v;
while(i<strlen(v))
{
for(j=0;j<n;j++)
{
char temp[M]={0};
strncpy(temp,p,strlen(HC[j]));
if(strcmp(temp,HC[j])==0)
{
printf("%c",u[j]);
break;
}
}
p+=strlen(HC[j]);
i+=strlen(HC[j]);
}
}
main ()
{
HuffmanTree HT;
HuffmanCode HC;
int n,i;
int *w;
char *u,*v;
u=(char *)malloc(M*sizeof(char));
v=(char *)malloc(M*sizeof(char));
w=(int *)malloc(M*sizeof(int));
printf("请输入字符数:");
scanf("%d",&n);
printf("请输入字符:\
");
scanf("%s",u);
printf("请输入对应的权值:\
");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
CreateHuffmanTree(HT,w,n);
Huffmancoding(HT,HC,n);
printf("各字符对应的编码:\
");
for(i=0;i<n;i++)
printf("%c: %s ",u[i],HC[i]);
printf("\
");
printf("输出哈夫曼树:\
");
print(HT,u,n);
free(w);
//编码
printf("待发送信息:\
");
scanf("%s",v);
printf("编码:\
");
code(HC,u,v);
//译码
printf("\
接收到的编码:\
");
scanf("%s",v);
printf("原文:\
");
recode(HC,n,u,v);
printf("\
");
}
上一个：C语言学习方法
下一个：电脑编程C语言
