第1个回答 推荐于2016-01-25
#include <stdio.h>
#include <malloc.h>
#include <string.h>
struct huffmantree
{
char zifu;
int weight;
int parent,lchild,rchild;
};
struct huffmancode
{
char cd[50];
int start;
};
int *select(struct huffmantree HT[],int n,int s[])
{
int i,min1,min2;
min1 = 32767;
min2 = 32767;
for (i = 1; i <= n; ++ i)
{
if (HT[i].weight<min1&&HT[i].parent==0)
{
min1 = HT[i].weight;
s[0] = i;
}
}
for (i = 1; i <= n; ++ i)
{
if (HT[i].weight< min2 &&HT[i].parent == 0&&HT[i].weight >= min1&&i != s[0])
{
min2 = HT[i].weight;
s[1] = i;
}
}
return s;
}
void createhuffmantree(struct huffmantree HT[],struct huffmancode HC[],char zi[],int w[],int n)
{
FILE *fp;
int m,i,s[2],c,f,end=0,j,k;
char linshi[50];
if (n<=1) return;
m=2*n-1;
fp = fopen ("hfmtree.txt","w+");
for (i=1;i<=n;++i)
{
HT[i].zifu=zi[i];
HT[i].weight=w[i];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (;i<=m;++i)
{
HT[i].weight=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
}
for (i=n+1;i<=m;++i)
{
select(HT,i-1,s);
HT[s[0]].parent = i;
HT[s[1]].parent = i;
HT[i].lchild = s[0];
HT[i].rchild = s[1];
HT[i].weight = HT[s[0]].weight + HT[s[1]].weight;
}
for (i = 1;i <= m; ++ i)
{
fprintf(fp,"[%d] %d %d %d\n",i,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
for (i = 1;i <= n; ++ i)
{
for (c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent)
{
if (HT[f].lchild == c)
{
linshi[end] = '0';
}
else linshi[end] = '1';
end ++;
}
linshi[end] = '\0';
HC[i].start = end;
for (j = end-1,k = 0;j >= 0;j --,k ++)
{
HC[i].cd[k] = linshi[j];
}
HC[i].cd[k] = '\0';
end = 0;
}
}
void print(struct huffmantree HT[],struct huffmancode HC[],int n)
{
int i,j;
printf("输出哈夫曼编码:\n");
for (i = 1;i <= n; i ++)
{
printf("%c:",HT[i].zifu);
for (j = 0;j < HC[i].start;j ++)
{
printf("%c",HC[i].cd[j]);
}
printf("\n");
}
}
void printhuffmantree(struct huffmantree HT[],int n)
{
int m,i;
m = 2 * n - 1;
printf("char----parent----lchild----rchild\n");
for (i = 1;i <= m; ++ i)
{
printf("[%d] %d %d %d\n",i,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
}
int main()
{
FILE *fp;
int n,i,w[100],xuanze,j,k=0,x,y=0,p=0,q;
char zi[100],a[1000],huffman[1000],yiwen[1000];
struct huffmancode HC[100];
struct huffmantree HT[100];
printf("***************\n 1.建立哈夫曼树\n 2.哈夫曼编码\n 3.哈夫曼译码\n 4.打印哈夫曼树 \n 0.退出\n***************\n");
printf("输入你想要的操作\n");
scanf("%d",&xuanze);
while (xuanze)
{
switch (xuanze)
{
case 1:
printf("输入需要字符的个数\n");
scanf("%d",&n);
printf("输入需要字符的字符和权数\n");
for (i = 1;i <= n;++ i)
{
getchar();
scanf ("%c %d",&zi[i],&w[i]);
}
createhuffmantree(HT,HC,zi,w,n);
break;
case 2:
fp = fopen("ToBeTran.txt","w+");
printf("输入你想编码的电文\n");
getchar();
gets(a);
fprintf(fp,"%s",a);
for (i = 0;a[i] != '\0'; ++i)
{
for (j = 1;j <= n; ++j)
{
if (a[i] == HT[j].zifu)
{
for (x = 0;HC[j].cd[x] != '\0'; ++ k,++ x)
{
huffman[k] = HC[j].cd[x];
}
}
}
}
huffman[k] = '\0';
printf("打印哈夫曼编码\n");
for (i = 0;i < 50; ++i)
{
for (j = 0;j < 50; ++j)
{
printf("%c",huffman[p]);
p++;
if (p >= k)
{
break;
}
}
printf("\n");
if (p >= k)
{
break;
}
}
fp = fopen("CodeFile.txt","w+");
fprintf(fp,"%s",huffman);
break;
case 3:
for (i = 0;huffman[i] != '\0';)
{
for (j = 1;j <= n; ++j)
{
q = 0;
for (p = 0;p < HC[j].start; ++p)
{
if (huffman[i] == HC[j].cd[p])
{
q ++;
i ++;
if(p == (HC[j].start - 1))
{
yiwen[y] = HT[j].zifu;
y ++;
break;
}
}
else
{
i = i - q;
break;
}
}
}
}
yiwen[y] = '\0';
puts(yiwen);
printf("\n");
break;
case 4:
printhuffmantree(HT,n);
print(HT,HC,n);
break;
case 0:break;
}
printf("***************\n 1.建立哈夫曼树\n 2.哈夫曼编码\n 3.哈夫曼译码\n 4.打印哈夫曼树 \n 0.退出\n***************\n");
printf("输入你想要的操作\n");
scanf("%d",&xuanze);
}
return 0;
}
这个只是哈夫曼树的一个例子。本回答被提问者采纳