哈夫曼树实验报告
需求分析：
从终端读入一串字符， 利用建立好的哈夫曼树对其进行编码， 储存到文件当中去， 然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。
二、概要设计
程序分为以下几个模块：
1、从终端读入字符集大小， n 个字符和 n 个权值，建立哈夫曼树，写入文件
2、对 hfmTree 进行编码，建立 hfm 编码表。
hfmTree 中去。
3、从文件 ToTran 读入信息，根据 hfm 编码表对其进行 hfm 编码，将编码后的信息写入文件 Codefile 中去
4、对 Codefile 文件反向译码，结果储存在 Textfile
5、将建立的 hfmTree 打印在终端上，并储存于相应的
中去。
Treeprint
文件中去。
抽象的数据定义如下：
哈夫曼树结构
typedef struct
//
定义哈夫曼树的结构
{
int weight;
int parent;
int lchild;
int rchild;
//
//
//
//
权值
双亲
左孩子
右孩子
}htnode,huffmantree[M+1];
建立哈夫曼树
void crthuffmantree(huffmantree ht,int w[],int n) //
初始化哈夫曼树
{
int i,s1,s2,m;
for(i=1;i<=n;i++)
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
m=2*n-1;
for(i=n+1;i<=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2);
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
}
}
typedef char *huffmancode[N+1]; // 建立哈夫曼树编码表 void crthuffmancode(huffmantree ht,huffmancode hc,int n) {
char *cd;
//
新建立一个指针
int start,i,c,p;
cd=(char*)malloc(n*sizeof(char)) cd[n-1]='\0';
//
；//
分配求一个字符的哈夫曼编码的空间
编码结束符
for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht[i].parent;
while(p!=0)
{
--start;
if(ht[p].lchild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
p=ht[p].parent;
}
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
}
free(cd);
}
select(huffmantree ht,int pos,int *s1,int *s2) // 取最小和次小权值
{
int j,m1,m2;
m1=m2=maxint;
for(j=1;j<=pos;j++)
{
if(ht[j].weight<m1&&ht[j].parent==0) // 定义为双亲为零时才开始求，这样就做到
了防止筛选过的重新加入比较列表里
{
m2=m1;
*s2=*s1;
*s1=j;
m1=ht[j].weight;
}
else if(ht[j].weight<m2&&ht[j].parent==0)
{
m2=ht[j].weight;
*s2=j;
}
}
}
主程序模块
int main()
{
初始化参数
printf(" 请输入：初始化 I; 编码 E; 译码 D; 印代码文件 P; 印哈弗曼树 T\n"); printf(" 结束请输入 Q\n");
while(1)
{ // 这就是用户输入 scanf("%c",&q); if(q=='Q')
{
break;
}
if(q=='I')
{
fpw=fopen("hfmtree.txt","w");
ftest=fopen("date.txt","r");
printf(" 请输入密码表，第一位表示密码表大小，之后按空格键开始以紧凑的格式输入
编码字母和权值。
\n");
scanf("%d",&n);
getchar();
for(i=1;i<=n;i++)
//
//
//
字符集大小输入
吃空格用的这里本来是要在终端输入的， 我为了图个测试方
便就写文件里，可以自己改回来
{
fscanf(ftest,"%c",&a);
if(a!='\n')
{
str[i]=a;
fscanf(ftest,"%d",&weight[i]);
}
else i--;
//
减去回车键的计数， 应该是用于输入量过多
情况下需要隔行输入的设定
}
for(i=n+1;i<=2*n-1;i++)
//
补全剩余的{
str[i]='0';
}
crthuffmantree(ht1,weight,n); crthuffmancode(ht1,hc1,n); for(i=1;i<=2*n-1;i++)
//
//
//
建立哈夫曼树
建立哈夫曼编码表
打印到文件中去
{
fprintf(fpw,"%c %d %d %d %d\n",str[i],ht1[i].weight,ht1[i].parent,ht1[i].lchild,ht1 [i].rchild);
}
fclose(ftest); // 关闭文件，这点很重要，否则文件不会写入
fclose(fpw);
}
if(q=='E')
{
j=1;
i=1;
fpr=fopen("tobetran.txt","r");
fpr2=fopen("hfmtree.txt","r");
fpw2=fopen("codefile.txt","w");
while(fscanf(fpr2,"%c %d %d %d %d\n",&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j]. lchild,&ht1[j].rchild)!=EOF)
{
j++; // 计数，哈夫曼树
值大小
}
while(fscanf(fpr,"%c",&dst[i])!=EOF)
{
i++;
//
所输入文件字
符大小
}
count=j;
//count
代表就
是哈夫曼树大小， count1 代表输入文件大小
count1=i;
crthuffmancode(ht1,hc1,count-1); // 重新从文件
里建立哈夫曼编码表
for(i=1;i<=count1-1;i++)
{
for(j=1;j<=count/2;j++)
//count/2
就是
字符集大小了
{
if(dst[i]==str[j])
//
比较
{
fprintf(fpw2,"%s",hc1[j]);
//
找到后写入对
应的编码到文件中去，也就是
codefile
那个文件
}
}
}
fclose(fpr);
fclose(fpr2);
fclose(fpw2);
}
if(q=='D')
{
j=1;
i=1;
z=1;
fpr2=fopen("hfmtree.txt","r");
fpr3=fopen("codefile.txt","r");
fpw3=fopen("textfile.txt","w");
while(fscanf(fpr3,"%c",&dst[i])!=EOF)
{
i++;
}
count3=i;
while(fscanf(fpr2,"%c %d %d %d %d\n",&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchi ld,&ht1[j].rchild)!=EOF)
{
j++;
}
count2=j;
//count2
是哈夫曼树大小计数， count3 是读入的哈夫曼编码计数
crthuffmancode(ht1,hc1,count2-1); // 重新建
立哈夫曼编码表
for(i=1;i<count3;i++)
{
for(j=1;j<=count2/2;j++)
{
len=strlen(hc1[j]); // 对每个
字符哈夫曼编码长度统计
for(t=0;t<len;t++)
{
if(hc1[j][t]==dst[t+i]) // 这里就
相当字符匹配了
{
flag=1;
}
if(hc1[j][t]!=dst[t+i])
{
flag=0;
break;
}
}
if(flag==1&&t==len)
{
win[z]=str[j];
//
//
判断
写入字符
z++;
i=i+len-1;
break;
}
}
}
count4=z;
for(z=1;z<count4;z++) // 写入文件
中
{
fprintf(fpw3,"%c",win[z]);
}
fclose(fpr2);
fclose(fpr3);
fclose(fpw3);
}
if(q=='P') // 打印 codefile 文件
{
j=1;
fpr2=fopen("codefile.txt","r");
fpw3=fopen("codeprin.txt","w");
while(fscanf(fpr2,"%c",&dst[j])!=EOF)
{
j++;
}
count=j;
j=0;
for(i=1;i<count;i++)
{
j++;
if(j==50)
{
printf("\n");
j=0;
}
printf("%c",dst[i]);
fprintf(fpw3,"%c",dst[i]);
}
fclose(fpr2);
fclose(fpw3);
}
if(q=='T') // 打印哈夫曼树，完备的树结
构不好打印，这里就是通过本身结构大致打印出来
{
fpw=fopen("treeprin.txt","w");
fpr=fopen("hfmtree.txt","r");
i=1;
m=0;
while(fscanf(fpr,"%c %d %d %d %d\n",&str[i],&ht1[i].weight,&ht1[i].parent,&ht1[
i].lchild,&ht1[i].rchild)!=EOF)
{
m++;
i++;
}
n=(m+1)/2;
maxlen=0;
//
//
字符集大小
最大字符编码长度
crthuffmancode(ht1,hc1,n);
//
重新建立哈夫曼编码表
for(i=1;i<=n;i++)
{
len=strlen(hc1[i]);
if(maxlen<len)
maxlen=len;
}
count=maxlen;
//
求得最大字符编码长度，用来控制行数的for(i=1;i<=m;i++)
{
t=0;
if(ht1[i].parent==0)
//
先寻找根节点，打印出来
{
for(c=0;c<2*count;c++)
//
打印空格
{
printf(" ");
fprintf(fpw," ");
}
printf("%d\n",ht1[i].weight);
fprintf(fpw,"%d\n",ht1[i].weight);
count=count-1; // 跳入下一行
j=ht1[i].lchild;
low[t]=j; / 记录根节点右子树，用数组 low[]
t++;
k=ht1[i].rchild; // 记录根节点左子树
low[t]=k;
t++;
for(c=0;c<2*count;c++) // 打空格
{
printf(" ");
fprintf(fpw," ");
}
printf("%d ",ht1[j].weight);
//
打印根节点的右子树和左子树
fprintf(fpw,"%d ",ht1[j].weight);
printf(" ");
fprintf(fpw," ");
printf("%d\n",ht1[k].weight);
fprintf(fpw,"%d\n",ht1[k].weight);
count=count-1;
}
}
p=0;
while(p<maxlen-2)
//p
来控制打印的结束标志
{
for(j=0;j<2*count;j++)
{
printf(" ");
fprintf(fpw," ");
}
y=t;
//y
作为每一行节点数的记录用
t=0;
for(i=0;i<y;i++)
//
下面就是一个循环过程
{
if(ht1[low[i]].lchild!=0)
{
printf("%d ",ht1[ht1[low[i]].lchild].weight);
fprintf(fpw,"%d ",ht1[ht1[low[i]].lchild].weight);
}
else
{
printf("0 ");
fprintf(fpw," ");
}
if(ht1[low[i]].rchild!=0)
{
printf("%d ",ht1[ht1[low[i]].rchild].weight);
fprintf(fpw,"%d ",ht1[ht1[low[i]].rchild].weight);
}
else
{
printf("0 ");
fprintf(fpw," ");
}
if(ht1[low[i]].lchild!=0) // 记录本层的孩子数量和位置，用数组 d[]
{
d[t]=ht1[low[i]].lchild;
t++;
}
if(ht1[low[i]].rchild!=0)
{
d[t]=ht1[low[i]].rchild;
t++;
}
}
for(i=0;i<t;i++) // 转移
{
low[i]=d[i];
}
printf("\n");
p++;
count=count-1;
}
fclose(fpw);
//
记住关文件
fclose(fpr);
}
}
return 0;
}
函数的调用关系
Mian
Crthuffmancode crthuffmantree
select
设计和调试分析
、打印树本来是考虑用严格格式输出，但是需要空间太大，就用类似树的形式输出
、文件操作最后必须要关闭文件，否则会一直在缓冲区中
、注意关闭指针
用户手册
用户界面如下
用户需要预先准备好 totran 文件，然后根据提示输入字符集大小和每个字母和对应的权值，然后按 E 编译代码， D 印刷代码， P打印哈夫曼树到文件和终端上。
测试结果
测试数据为
字A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
符
权
64
13
22
32
103
21
15
47
57
1
5
32
20
57
63
值
字P
Q
R
S
T
U
V
W
X
Y
Z
符
权
15
1
48
51
80
23
8
18
1
16
1
值
测试语句为：
THIS PROGRAME IS MY FAVORITE
输出 hfmcode 文件
110100010110001111110001000101001100001001010101100100101110110001111111001010001111111
0011101011000001001001001101101010111
打印哈夫曼树
814
347
467
156
191
217
250
76
80
92
99 103
114
122
128
35 41
45
47
48
51
57
57 59
63
64
64
17
18
20 21
22
23
28
31
32
32
8
9
13
15 15
16
4
5
2 2
附录
程序源文件
(
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 100
#define M 2*N+1
#define maxint 32767
typedef struct
//
定义哈夫曼树的结构
{
int weight;
int parent;
int lchild;
int rchild;
}htnode,huffmantree[M+1];
select(huffmantree ht,int pos,int *s1,int *s2)
//
取最小和次小权值
{
int j,m1,m2;
m1=m2=maxint;
for(j=1;j<=pos;j++)
{
if(ht[j].weight<m1&&ht[j].parent==0) // 定义为双亲为零时才开始求，这样就做到
了防止筛选过的重新加入比较列表里
{
m2=m1;
*s2=*s1;
*s1=j;
m1=ht[j].weight;
}
else if(ht[j].weight<m2&&ht[j].parent==0)
{
m2=ht[j].weight;
*s2=j;
}
}
}
void crthuffmantree(huffmantree ht,int w[],int n) //
初始化哈夫曼树
{
int i,s1,s2,m;
for(i=1;i<=n;i++)
//
对字母建立哈夫曼树的结构
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
m=2*n-1;
//
剩下的结构初始化
for(i=n+1;i<=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
for(i=n+1;i<=m;i++)
//
开始通过子树并入方式刷新哈夫曼树
{
select(ht,i-1,&s1,&s2);
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
}
}
typedef char *huffmancode[N+1]; // 建立哈夫曼树编码表，这里采用
的是指针的形式
void crthuffmancode(huffmantree ht,huffmancode hc,int n)
{ // 变量说明一下， start 用于从根部开始逆向求哈夫曼编码的一个参数，每当录入一个值其结果减 1，类似短除法求二进制转换
参数 c 表示某个节点自身的位置，而 p 是其双亲的位置
char *cd;
//
新建立一个指针
int start,i,c,p;
cd=(char*)malloc(n*sizeof(char));
//
分配求一个字符的哈夫曼编码的空间
cd[n-1]='\0';
//
编码结束符
for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht[i].parent;
while(p!=0)
//
因为只有根的双亲为
0，所以相当于
逆向遍历到根
{
--start;
if(ht[p].lchild==c)
//
如果双亲的左孩子等于该值在则该值
就是左孩子，否则为右孩子，分别对应
0，1
cd[start]='0';
else
cd[start]='1';
c=p;
//
向上走
p=ht[p].parent;
}
hc[i]=(char
*)malloc((n-start)*sizeof(char)); //
这是我们实质储存的空间， 应该该叫
数组指针
strcpy(hc[i],&cd[start]);
//
字符串复制
}
free(cd);
}
int main()
{
FILE *fpw,*fpr,*fpw2,*fpr2,*fpr3,*fpw3,*ftest;
int
n=0,d[1000],m,low[1000],weight[10000]={0},i,j=0,count=0,count1=0,count3=0,z=1,count4=0, count2=0,len,t,flag=0,c,maxlen,k,p,y;
char str[10000]={0},q,dst[10000]={0},com[10000]={0},win[10000]={0},a;
huffmantree ht1;
huffmancode hc1;
printf(" 请输入：初始化 I; 编码 E; 译码 D; 印代码文件 P; 印哈弗曼树 T\n"); printf(" 结束请输入 Q\n");
while(1)
{ // 这就是用户输入 scanf("%c",&q);
if(q=='Q')
{
break;
}
if(q=='I')
{
fpw=fopen("hfmtree.txt","w");
ftest=fopen("date.txt","r");
printf(" 请输入密码表，第一位表示密码表大小，之后按空格键开始以紧凑的格式输入
编码字母和权值。
\n");
scanf("%d",&n);
getchar();
for(i=1;i<=n;i++)
//
//
//
字符集大小输入
吃空格用的这里本来是要在终端输入的， 我为了图个测试方
便就写文件里，可以自己改回来
{
fscanf(ftest,"%c",&a);
if(a!='\n')
{
str[i]=a;
fscanf(ftest,"%d",&weight[i]);
}
else i--;
//
减去回车键的计数， 应该是用于输入量过多
情况下需要隔行输入的设定
}
for(i=n+1;i<=2*n-1;i++)
//
补全剩余的{
str[i]='0';
}
crthuffmantree(ht1,weight,n); crthuffmancode(ht1,hc1,n); for(i=1;i<=2*n-1;i++)
//
//
//
建立哈夫曼树
建立哈夫曼编码表
打印到文件中去
{
fprintf(fpw,"%c %d %d %d %d\n",str[i],ht1[i].weight,ht1[i].parent,ht1[i].lchild,ht1 [i].rchild);
}
fclose(ftest); // 关闭文件，这点很重要，否则文件不会写入
fclose(fpw);
}
if(q=='E')
{
j=1;
i=1;
fpr=fopen("tobetran.txt","r");
fpr2=fopen("hfmtree.txt","r");
fpw2=fopen("codefile.txt","w");
while(fscanf(fpr2,"%c %d %d %d %d\n",&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j]. lchild,&ht1[j].rchild)!=EOF)
{
j++; // 计数，哈夫曼树
值大小
}
while(fscanf(fpr,"%c",&dst[i])!=EOF)
{
i++;
//
所输入文件字
符大小
}
count=j;
//count
代表就
是哈夫曼树大小， count1 代表输入文件大小
count1=i;
crthuffmancode(ht1,hc1,count-1); // 重新从文件
里建立哈夫曼编码表
for(i=1;i<=count1-1;i++)
{
for(j=1;j<=count/2;j++)
//count/2
就是
字符集大小了
{
if(dst[i]==str[j])
//
比较
{
fprintf(fpw2,"%s",hc1[j]);
//
找到后写入对
应的编码到文件中去，也就是
codefile
那个文件
}
}
}
fclose(fpr);
fclose(fpr2);
fclose(fpw2);
}
if(q=='D')
{
j=1;
i=1;
z=1;
fpr2=fopen("hfmtree.txt","r");
fpr3=fopen("codefile.txt","r");
fpw3=fopen("textfile.txt","w");
while(fscanf(fpr3,"%c",&dst[i])!=EOF)
{
i++;
}
count3=i;
while(fscanf(fpr2,"%c %d %d %d %d\n",&str[j],&ht1[j].weight,&ht1[j].parent,&ht1[j].lchi ld,&ht1[j].rchild)!=EOF)
{
j++;
}
count2=j; //count2
是哈夫曼树大小计数， count3 是读入的哈夫曼编码计数
crthuffmancode(ht1,hc1,count2-1); // 重新建
立哈夫曼编码表
for(i=1;i<count3;i++)
{
for(j=1;j<=count2/2;j++)
{
len=strlen(hc1[j]); // 对每个
字符哈夫曼编码长度统计
for(t=0;t<len;t++)
{
if(hc1[j][t]==dst[t+i]) // 这里就
相当字符匹配了
{
flag=1;
}
if(hc1[j][t]!=dst[t+i])
{
flag=0;
break;
}
}
if(flag==1&&t==len)
{
win[z]=str[j];
//
//
判断
写入字符
z++;
i=i+len-1;
break;
}
}
}
count4=z;
for(z=1;z<count4;z++)
//
写入文件
中
{
fprintf(fpw3,"%c",win[z]);
}
fclose(fpr2);
fclose(fpr3);
fclose(fpw3);
}
if(q=='P') // 打印 codefile 文件
{
j=1;
fpr2=fopen("codefile.txt","r");
fpw3=fopen("codeprin.txt","w");
while(fscanf(fpr2,"%c",&dst[j])!=EOF)
{
j++;
}
count=j;
j=0;
for(i=1;i<count;i++)
{
j++;
if(j==50)
{
printf("\n");
j=0;
}
printf("%c",dst[i]);
fprintf(fpw3,"%c",dst[i]);
}
fclose(fpr2);
fclose(fpw3);
}
if(q=='T') // 打印哈夫曼树，完备的树结
构不好打印，这里就是通过本身结构大致打印出来
{
fpw=fopen("treeprin.txt","w");
fpr=fopen("hfmtree.txt","r");
i=1;
m=0;
while(fscanf(fpr,"%c %d %d %d %d\n",&str[i],&ht1[i].weight,&ht1[i].parent,&ht1[ i].lchild,&ht1[i].rchild)!=EOF)
{
m++;
i++;
}
n=(m+1)/2;
maxlen=0;
crthuffmancode(ht1,hc1,n);
//
//
//
字符集大小
最大子符编码长度
重新建立哈夫曼编码表
for(i=1;i<=n;i++)
{
len=strlen(hc1[i]);
if(maxlen<len)
maxlen=len;
}
count=maxlen;
//
求得最大字符编码长度， 用
来控制行数的for(i=1;i<=m;i++)
{
t=0;
if(ht1[i].parent==0)
//
先寻找根节点，打印出来
{
for(c=0;c<2*count;c++)
//
打印空格
{
printf(" ");
fprintf(fpw," ");
}
printf("%d\n",ht1[i].weight);
fprintf(fpw,"%d\n",ht1[i].weight);
count=count-1;
j=ht1[i].lchild;
low[t]=j; //
//
跳入下一行
记录根节点右子树，用数组
low[]
t++;
k=ht1[i].rchild;
//
记录根节点左子树
low[t]=k;
t++;
for(c=0;c<2*count;c++)
//
打空格
{
printf(" ");
fprintf(fpw," ");
}
printf("%d ",ht1[j].weight);
//
打印根节点的右子树和左子树
fprintf(fpw,"%d ",ht1[j].weight);
printf(" ");
fprintf(fpw," ");
printf("%d\n",ht1[k].weight);
fprintf(fpw,"%d\n",ht1[k].weight);
count=count-1;
}
}
p=0;
while(p<maxlen-2)
//p
来控制打印的结束标志
{
for(j=0;j<2*count;j++)
{
printf(" ");
fprintf(fpw," ");
}
y=t;
t=0;
for(i=0;i<y;i++)
//y
//
作为每一行节点数的记录用下面就是一个循环过程
{
if(ht1[low[i]].lchild!=0)
{
printf("%d ",ht1[ht1[low[i]].lchild].weight);
fprintf(fpw,"%d ",ht1[ht1[low[i]].lchild].weight);
}
else
{
printf("0 ");
fprintf(fpw," ");
}
if(ht1[low[i]].rchild!=0)
{
printf("%d ",ht1[ht1[low[i]].rchild].weight);
fprintf(fpw,"%d ",ht1[ht1[low[i]].rchild].weight);
}
else
{
printf("0 ");
fprintf(fpw," ");
}
if(ht1[low[i]].lchild!=0) // 记录本层的孩子数量和位置，用数组 d[]
{
d[t]=ht1[low[i]].lchild;
t++;
}
if(ht1[low[i]].rchild!=0)
{
d[t]=ht1[low[i]].rchild;
t++;
}
}
for(i=0;i<t;i++) // 转移
{
low[i]=d[i];
}
printf("\n");
fprintf(fpw,"\n");
p++;
count=count-1;
}
fclose(fpw); // 记住关文件 fclose(fpr);
}
}
return 0;
}
)
Tobetran.txt
THIS PROGRAME IS MY FAVORITE
Date.txt
A64B13C22D32E103F21G15H47I57J1K5L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1
Codefile.txt
Codeprint.txt
Hfmtree.txt
Textfile.txt