文档介绍：数据结构哈弗曼编码译码器课程设计
数据结构与算法
课程设计报告
课程设计题目:哈弗曼编码/译码器专业班级: 信息与计算科学1001班姓名: 学号:
设计室号: 理学院机房设计时间: 2011-12-26 批阅时间: 指导教师: 成绩:
哈夫曼算法的编码和译码系统目录
设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
1)将权值数据存放在数据文件(,位于执行程序的当前目录中)
2)分别采用动态和静态存储结构
3)初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;
4)编码:利用建好的哈夫曼树生成哈夫曼编码;
5)输出编码;
6)设字符集及频度如下表:
字符空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
1)译码功能;
2)显示哈夫曼树;
3)界面设计的优化。
Main函数中包裹四个主要功能函数,即
用于构造和初始哈夫曼树的HuffmanCoding函数
用于对指定文件进行编码的void Coding函数
用于对哈夫曼编码进行译码的void Decoding函数
用于在屏幕终端上显示哈弗满树的void Print_tree函数
其相互联系如下图所示
其中用于初始化哈夫曼树的 Huffman coding()函数包含两个子函数,即
(1)void select(HuffmanTree HT,int j,int *s1,int *s2)
从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点
(2)void Init()
输入n个字符及其对应的权值,根据权值建立哈夫曼树,其相互联系如图所示
在本程序中,主界面为一个功能选择界面,根据提示,使用者可以选择不同的功能进行操作。但由于在编制写程序的源代码中,出于方便编写的考虑,我们对一些功能所要引用的文件进行了提前的命名,因此在使用之前使用者应该提前知晓操作程序所需要的特定文件名,现总结如下:
:用于存储待编码的文本文件
:
:
:用于存储哈夫曼树的文本文件
:
基本思想:首先根据使用者输入的待编码字符和相应的权重值,再根据哈夫曼树的建立过程机型哈夫曼树的构造
主要步骤及主要功能函数:
(1)首先根据给定的权重构造n棵二叉树的森林,其中每个二叉树都只有一个权值为w[i]的根节点
(2)在森林中选取两个权值最小的根节点作为一个新二叉树的左右结点
其具体函数为
void select(HuffmanTree HT,int j,int *s1,int *s2) //其中s1,s2为权值最小的两个根节点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{
*s1=i;
break;
}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
*s1=i;
HT[*s1].parent=1;
通过遍历所有节点找到权值最小的结点
(3)设新二叉树的根节点为左右子结点的权值和
其函数表达为
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;
(4)从森林中删除选中的那两棵二叉树,同时加入新构造的那个二叉树
(5)重复上