数据结构课程设计哈夫曼编码译码器.doc

(完整word版)数据结构课程设计哈夫曼编码译码器

《数据结构》课程设计报告

学生姓名:
陈 洋
学 号：
1009300109

刘 睿

1009300122

张学阳

1009300132
学 院:
理学院
班 级:
数学101
题 目:
哈夫曼编码/译码器

指导教师： 郭新辰 职称： 教 授
胡建平 副教授
刘 力 实验师

2011年12月27日
II
目 录
目 录 I
一、选题背景 1
1.1 实验目的及要求 1
1.2指导思想 1
二、算法设计 2
2.1 设计原理 2
2.2算法特点 2
三、程序及功能说明 3
3.1 主要函数 3
3.2结构展示 3
3.3哈夫曼树的建立过程 4
四、结果分析 7
五、总 结 10
六、课程设计心得体会 11
参考文献 12
源程序 13

一、选题背景
1.1 实验目的及要求
本次试验主要目的有6点要求：
1）将字符的频率及权值数据存放在文件名为data.txt的数据文件中；
2）分别采用动态和静态存储结构来存储数据；
3)建立一棵哈夫曼树
4）利用建好的哈夫曼树生成哈夫曼编码，并输出哈夫曼编码；
5）实现译码功能；
6）显示哈夫曼树并优化界面
1.2指导思想
以输入的字符作为叶子结点，每个字符在文件出现的次数作为叶子上的权值来构造一颗哈夫曼树，并规定哈夫曼树中所有左分支表示0，所有右分支表示1，把依据从根结点到每个叶子节点所经过的分支而组成的二进制位的序列作为该叶子对应字符的编码。由哈夫曼树定义可知，在哈夫曼树中没有度为1的结点，根据二叉树的性质可知，具有n个节点的哈夫曼树共有2n-1个结点，故可以设置一个长度为2n-1的数组来存储哈夫曼树。另外，为求每个字符的编码需要从叶子结点出发一直搜索到根结点，而为解码则要从根结点出发逢0走左分支，封1走右分支一直到某个叶子为止，因此，在哈夫曼树中既要求从某个节点找双亲，又要求从某个节点找左、右孩子，所以存储哈夫曼树的数组中的元素应该是包含权值weight、双亲位置parent、左孩子位置lchild、右孩子位置rchild和标示字符flag共5个成员的结构体类型。静态存储时主要用到了”w+”方式打开文件，动态存储时为”a+”方式打开文件。译码时将字符对应的编码与输入的二进制数字比较，若相比配则输出相应的字符，以此来达到编码的目的，而哈夫曼树的现实主要用递归算法实现，若该节点无左孩子节点，说明它也无右孩子节点，直接输出结点，否则，他有左右孩子节点，输出节点后，他的左右孩子利用递归算法判断。

二、算法设计
2.1 设计原理
本次试验的主要要点是哈夫曼树的建立过程，这种算法的思路是：
1）依据给定的n个权值{W0，W1，……，Wn-1}构造n棵只有一个根结点的二叉树，这些二叉树组成一个森林F={T0，T1，……，Tn-1}。
2）在森林F中选取两棵根结点的权值最小的二叉树作为左、右子树合并成一棵新的二叉树，这棵新的二叉树的根结点的权值等于其左、右子树根结点的权值之和。这样一来，森林中就减少了一棵树。
3）重复上一步，直到森林F中只有一棵二叉树为止，这棵二叉树便是要得到的哈夫曼树
二叉树建立好之后，通过创建文件分静态存储和动态存储方式来存储数据，通过显示文件中的数据来查看是否数据以存储到文件中，哈夫曼树中所有左分支表示0，所有右分支表示1，把依据从根结点到每个叶子节点所经过的分支而组成的二进制位的序列作为该叶子对应字符的编码，输入编码通过与以编号的代码比对输出字符。

2.2算法特点
该算法主要是一个递归过程，初始状每个叶子节点是一棵树，构成森林，合并森林中根结点最小的的两棵二叉树，以此类推，直到最后只剩下一颗二叉树，并规定权值较小的子树放在左分支上，若权值相等，较简单的子树放在左分支上，这样递归算法不但思路清晰，程序也比较简单。当哈夫曼树建立起来之后，对字符进行赋权值，并通过循环语句来实现译码过程，在显示哈夫曼树的过程中，也用到了递归算法，函数的自身循环

…
三、程序及功能说明
3.1 主要函数
save1()-----------------------静态存储
save2()-----------------------动态存储
void save()------------------存储权值
put()-------------------------从文件中输出数据
PreOrderPrint()------------显示哈夫曼树
main()-----------------------主要实现哈夫曼树的建立、编码过程、译码过程

3.2结构展示

save1() ------静态存储

save()--------------------存储权值

save2()----- 动态存储

main()

主

函

数

put()---------------------从文件中输出数据

PreOrderPrin（）--------显示哈夫曼树

图-1

3.3哈夫曼树的建立过程

例：已知A,B,C,D,E的权值{28,10,20,7,35}，构建哈夫曼树。
哈夫曼树的构造过程树下：
1） 森林的初始状态如图-1所示，共有5棵二叉树。
2） 在森林中根节点的权值最小的两棵二叉树是权值为10和7的树，把它们合并，如图-2所示，森林中共有4棵二叉树。
3） 在森林中根结点的权值最小的两棵二叉树是权值为17和20的树，把它们合并，如图-3所示，森林中共有3棵二叉树。
4） 在森林中根结点的权值最小的两棵二叉树是权值为28和35的树，把它们合并，如图-4所示，森林中共有2棵二叉树。
5） 在森林中根结点的权值最小的两棵二叉树是权值为37和63的树，把它们合并，如图-5所示，森林中共有1棵二叉树。至此构造完毕。

A
B
C
A
C
B
D
E
D
E
28
20
20
7
35
35
7
10
28
10
28
图-2
图-3
C
B
D
A
E
28
17
37
20
35
10
7
图-4

E
A
C
B
D
20
37
17
35
28
7
10
63
图-5

E
A
C
D
B
28
20
63
17
37
100
35
7
10
图-6

四、结果分析
首先输入字符和其相应的频率及权值，之后会自动输出字符及相应的权值和编码，此时二叉树已经建立完成，且编码完成，接着是译码过程，输入编码个数，然后输入编码会自动输出译码结果，之后会输出一个选择对话框，选择1为存储数据，会输出存储方式，1为静态存储，输入权值，2为动态存储，输入权值，之后输入文件名，当再次存储时，静态存储的数据会自动更新，而动态存储则会保留所有记录的数值，选择2，选择文件名会显示文件所存储的内容，查看是否存储上了数据，选择3会自动将名为data.txt的文件中的数据显示出来，它返回一个数组可以将里面的内容对编码数组赋值，就可以不用输入编码实现译码，只是在转换时有问题，暂没处理，这一点总结内容会具体说明，选择4会显示出哈夫曼树。

图-7

图-8

图-9

图-10

图-11

五、总 结
本次课程设计内容主要是围绕哈夫曼树来实现一些操作的，同时还包含数据保存和数据的显示等内容，我们首先是通过递归思想建立了一棵哈夫曼树，输入编码和权值对哈夫曼树赋值，构造思想是每次合并权值最小的两棵树，树的数目不断减小，直到只剩下一棵二叉树为止，同时按约定，权值较小的子树放在左分支上，若权值相等，简单的二叉树放在左分支上，哈夫曼树中所有左分支表示0，所有右分支表示1，把依据从根结点到每个叶子所经过的分支而成的二进制位的序列作为该叶子对应字符的编码。输入编码通过解码来输出相应的字符。数据储存分为静态存储和动态存储两种方式，静态存储方式对建立的文件只能存储一次数据，而动态存储方式则可以连续向建立的文件存储数据，且不掩盖上一次输入的值。对于哈夫曼树的显示，则是通过函数递归思想来实现的，根据建立起来的结构，根据结点和其孩子结点的位置和对空格的控制来显示哈夫曼树。
从整个课程设计来看，整体思路很清晰，可实现起来比较复杂，数据存储这方面比较简单，而二叉树的建立和显示感觉很困难，最后显示这方面还有缺陷，每次输入新的字符都需要对空格更改，这一点带来很大的不便，还有当我们想输入很多编码来翻译时，只能一个字符一个字符的输入，这一点也可以改进，可以将数据存入一个txt文件中，通过文件的调用，将文件里的编码输入到一个数组里，将这个数组里的数字编码，就不用一个字符一个字符的输入了，增加了可用性，这方面再实现时遇到的问题是二进制和十进制不能合理的转化，用了很多方法，都无济于事。还有一点就是界面优化问题，可以通过某个接口来调用窗口将二叉树更好的显示出来，如果能将这3方面加以改进，整个过程中就应该更合理，适用性更强了。

……

-26-

六、课程设计心得体会
在题目选取时，考虑到题目的新颖性和挑战性，便选取了哈夫曼树编码这个题目，因为之前自己从未做过数据保存这类的题目，虽然看过类似的代码，但没有实际的操作过，想借此机会实际操作一下，哈夫曼树建立之前也从未做过，想了解一下它的建立过程。
具体操作时，主要参考了C语言课本中的文件保存中的代码，虽然在改代码时遇到了许多问题，但还是成功了，数据保存确实很有意思。接着就是哈夫曼树的建立过程，这部分数据课本上有，便根据课本上的代码改编，本想改编成几部分，但当与自己编的解码程序一起调用时，发现不能实现需要的功能，这个问题困扰了我很长时间，最后也没能解决，只能把它们放在主函数里了，接下来是哈夫曼树的输出，自己感觉这是最不好实现的功能，由于特殊的存储结构，要把字符按顺序输出已是不容易的事了，还要按照哈夫曼树的结构输出，就更难了，在网上找了很久也没有找到一个令人满意的程序，不过找到了一个递归思想，通过这个递归思想，可以将字符按顺序输出，再通过空格的控制，大致的数的形状终于出来了，不过还有问题，那就是换一组数据后，就需要改变空格，否则就不能显示哈夫曼树，这个问题调整了几天也没有解决，只能改一次数据改一下空格了。
通过这次课程设计，感觉最大的收获就是只要你有想法，就能通过代码来实现，只是一时还没有找到而已。同时自己还学会了数据保存，显示文件中的数据，哈夫曼树的建立，编码译码等操作，这个编码思想对以后的学习应该会很有帮助。

参考文献
[1] 曲朝阳, 郭晓利, 王晓慧, 孙鸿飞. 数据结构中国电力出版社,2007
[2] 谭浩强C程序设计(第三版).北京:清华大学出版社,2005

源程序
#include<stdio.h>
#include"stdlib.h"
#define max 1000
#define maxsymbs 30//最多有30个叶结点
#define maxbits 10//每个叶子节点编码最多十位
#define maxnode 59//允许有2*n-1个结点
#define maxinnum 100//解码时允许输入的最大编码
#define size 100

typedef struct
{
int weight;//保存结点得权值
int flag;//判定一个结点是否加入哈夫曼树中的标志，0为未加入，1为加入
int parent;//保存结点的双亲在huff_node中的序号
int lchild;//保存结点左右孩子在数组huff_node中的序号
int rchild;
}huffnode;

typedef struct
{
int bits[maxbits];//保存各字符的哈弗曼编码
int start;//表示该编码在数组bits中的开始位置
}huffcode;

//静态存储
void save1()
{
FILE *fp;
char ch,filename[10];
printf(" **************************************************************\n");
printf(" * 请写入文件名:");
scanf("%s",filename);
printf(" * 请输入权值(#键结束):");
if((fp=fopen(filename,"w+"))==NULL)
{
printf("cannot open file\n");
exit(0);
}
ch=getchar();
ch=getchar();
printf(" * 显示结果:");
while(ch!='#')
{
fputc(ch,fp);
putchar(ch);
ch=getchar();
}
putchar(10);
fclose(fp);
printf(" **************************************************************\n");
}

//动态存储
void save2()
{
FILE *fp;
char ch,filename[10];
printf(" * 请写入文件名:");
scanf("%s",filename);
printf(" * 请输入权值(#键结束):");
if((fp=fopen(filename,"a+"))==NULL)
{
printf(" * cannot open file\n");
exit(0);
}
ch=getchar();
ch=getchar();
printf(" * 显示结果:");
while(ch!='#')
{
fputc(ch,fp);
putchar(ch);
ch=getchar();
}
putchar(10);
fclose(fp);
printf(" **************************************************************\n");
}

//存储权值
void save()
{
int d;
printf(" * 选择存储方式:1为静态存储;\n");
printf(" * 2为动态存储\n");
printf(" * ");
scanf("%d",&d);
switch(d)
{
case 1:save1();break;
case 2:save2();break;
default:printf(" * 输入错误!");
}
}

//从文件中显示数据
void show()
{
FILE *fp;
int i=0;
char ch,filename[10];
printf(" * 请写入文件名:");
scanf("%s",filename);
if((fp=fopen(filename,"a+"))==NULL)
{
printf("cannot open file\n");
exit(0);
}
ch=fgetc(fp);
printf(" * 显示结果:");
while(!feof(fp))
{
putchar(ch);
ch=fgetc(fp);
}
fclose(fp);
printf("\n");
printf(" **************************************************************\n");
}

//从文件中输出数据
void put()
{
int i;
char a[size];
FILE *fp;
if((fp=fopen("data1.txt","rb"))==NULL)
{
printf("can not open file\n");
exit(0);
}
printf(" * 显示结果:\n");
printf(" *");
for(i=0;i<size/2;i++)
{
fread(&a[i],sizeof(char),1,fp);
printf("%c",a[i]);
}
fclose(fp);
printf("\n");
printf(" **************************************************************\n");
}

void put2(int a[size])
{
int i;
//char a[size];
FILE *fp;
if((fp=fopen("data1.txt","rb"))==NULL)
{
printf("can not open file!\n");
exit(0);
}
for(i=0;i<size;i++)
{
fread(&a[i],sizeof(char),1,fp);
printf("%c",a[i]);
}
fclose(fp);
printf(" **************************************************************\n");
}

int PreOrderPrint(huffnode huff_node[maxnode],int c,int count1,int count2,int n)
{

if(huff_node[c].lchild!=-1)
{
for(int i=0;i<count2;i++)
printf(" ");
if(huff_node[huff_node[c].parent].lchild>n-1&&huff_node[huff_node[c].parent].rchild>n-1&&huff_node[huff_node[huff_node[c].parent].lchild].flag==-1&&huff_node[huff_node[huff_node[c].parent].rchild].flag==-1)
{
printf("%d",huff_node[huff_node[huff_node[c].parent].lchild].weight);
printf("%d\n",huff_node[huff_node[huff_node[c].parent].rchild].weight);
if(huff_node[c].lchild<n&&huff_node[c].lchild>=0&&huff_node[c].rchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].lchild].weight);
}
if(huff_node[c].rchild<n&&huff_node[c].rchild>=0&&huff_node[c].lchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].rchild].weight);
}
if(huff_node[c].rchild<n&&huff_node[c].rchild>=0&&huff_node[c].lchild<n&&huff_node[c].lchild>=0)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].lchild].weight);
for(i=0;i<count2;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].rchild].weight);
}

if(huff_node[huff_node[huff_node[c].parent].rchild].lchild<n&&huff_node[huff_node[huff_node[c].parent].rchild].lchild>=0&&huff_node[huff_node[huff_node[c].parent].rchild].rchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[huff_node[huff_node[c].parent].rchild].lchild].weight);
}
if(huff_node[huff_node[huff_node[c].parent].rchild].rchild<n&&huff_node[huff_node[huff_node[c].parent].rchild].rchild>=0&&huff_node[huff_node[huff_node[c].parent].rchild].lchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[huff_node[huff_node[c].parent].rchild].rchild].weight);
}
if(huff_node[huff_node[huff_node[c].parent].rchild].rchild<n&&huff_node[huff_node[huff_node[c].parent].rchild].rchild>=0&&huff_node[huff_node[huff_node[c].parent].rchild].lchild<n&&huff_node[huff_node[huff_node[c].parent].rchild].lchild>=0)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[huff_node[huff_node[c].parent].rchild].lchild].weight);
for(i=0;i<count2;i++)
printf(" ");
printf("%d",huff_node[huff_node[huff_node[huff_node[c].parent].rchild].rchild].weight);
}
huff_node[huff_node[huff_node[c].parent].lchild].flag++;
huff_node[huff_node[huff_node[c].parent].rchild].flag++;
}
else if(huff_node[c].flag==-1)
{
printf("%d\n",huff_node[c].weight);
if(huff_node[c].lchild<n&&huff_node[c].lchild>=0&&huff_node[c].rchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].lchild].weight);
}
if(huff_node[c].rchild<n&&huff_node[c].rchild>=0&&huff_node[c].lchild>n-1)
{
for(i=0;i<count1-1;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].rchild].weight);
}
if(huff_node[c].rchild<n&&huff_node[c].rchild>=0&&huff_node[c].lchild<n&&huff_node[c].lchild>=0)
{
for(i=0;i<count1+2;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].lchild].weight);
for(i=0;i<count2-2;i++)
printf(" ");
printf("%d",huff_node[huff_node[c].rchild].weight);
}
}
if( PreOrderPrint(huff_node,huff_node[c].lchild,++count1,++count2,n))
if (PreOrderPrint(huff_node,huff_node[c].rchild,++count1,++count2,n))
return 1;
return 0;
}
else
return 1;
}

void num()
{
printf(" ************************************************\n");
printf(" * 1.储存权值 *\n");
printf(" * 2.显示储存的数据 *\n");
printf(" * 3.输出文件数据 *\n");
printf(" * 4.输出二叉树 *\n");
printf(" * 0.退出 *\n");
printf(" ************************************************\n");
}

void main()
{
huffnode huff_node[maxnode];
huffcode huff_code[maxsymbs],ad,cd;
int i=0,j,m1,m2,x1,x2,n=4,c,p,k=0,a=0,m,b=0,d,t,e,count1=10,count2=2,a1[size];
char symbs[maxsymbs],symb,data[maxsymbs];
for(i=0;i<2*n-1;i++)//数组huff_node初始化
{
huff_node[i].weight=0;
huff_node[i].parent=-1;
huff_node[i].flag=0;
huff_node[i].lchild=-1;
huff_node[i].rchild=-1;
}
printf(" **************************************************************\n");
printf(" **************************************************************\n");
printf(" * 请输入字符和其相应的频率:");
for(i=0;i<n;i++)
{
scanf("%c",&data[i]);
scanf("%d",&huff_node[i].weight);
}
printf(" **************************************************************\n");
for(i=0;i<n-1;i++)//构造哈夫曼树
{
m1=m2=max;
x1=x2=0;
for(j=0;j<n+i;j++)//构造n棵只有一个叶子节点的二叉树，并找出根结点权值最小的二叉树
{
if(huff_node[j].weight<m1&&huff_node[j].flag==0)
{
m2=m1;
x2=x1;
m1=huff_node[j].weight;
x1=j;
}
else
if(huff_node[j].weight<m2&&huff_node[j].flag==0)
{
m2=huff_node[j].weight;
x2=j;
}
}
huff_node[x1].parent=n+i;//将找出的两棵树合并为一棵子树
huff_node[x2].parent=n+i;
huff_node[x1].flag=1;
huff_node[x2].flag=1;
huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
huff_node[n+i].lchild=x1;
huff_node[n+i].rchild=x2;
}
for(i=0;i<n;i++)//求字符的哈夫曼编码
{
cd.start=n;//哈夫曼编码存放在从cd.start到n的分量上
c=i;
p=huff_node[c].parent;
while(p!=-1)
{
if(huff_node[p].lchild==c)
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
cd.start=cd.start-1;
c=p;
p=huff_node[p].parent;
}
for(j=cd.start+1;j<=n;j++)
huff_code[i].bits[j]=cd.bits[j];
huff_code[i].start=cd.start;
}
printf(" * 字符和其相应的编码:\n");
for(i=0;i<n;i++)//输出字符的哈夫曼编码
{
printf(" * %c-",data[i]);
printf("%d:",huff_node[i].weight);