文档介绍：*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2007年春季学期
算法与数据结构课程设计
题目:哈夫曼编译码器设计
专业班级:05计算机科学与技术3班
姓名:徐玉霞
学号:05240317
指导教师:李睿
成绩:_____________________
目录
摘要 2
前言 3
正文 4
1. 采用类c语言定义相关的数据类型 4
2. 各模块的伪码算法 4
3. 函数的调用关系图 7
4. 调试分析 7
5. 测试结果 8
6. 源程序(带注释) 10
参考文献 18
致谢 19
附件Ⅰ部分源程序代码 20
摘要
该设计是对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串。在该设计中把数据压缩过程称为编码,解压缩的过程称为译码。此程序中建立了哈夫曼树,并利用建好的哈夫曼树对文件中的正文进行编码,对文件中的代码进行译码,显示输出等功能。
关键词:哈夫曼树,哈夫曼编码,哈夫曼译码。
前言
哈夫曼编码的应用很广泛,利用哈夫曼树求地的二进制编码称为哈夫曼编码。哈夫曼树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为对应的编码,这就是哈夫曼编码。我们在对一些问题进行求解时,会发现有些问题很难找到规律,或者根本无规律可寻。对于这样的问题,可以利用计算机运算速度快的特点,先搜索查找所有可能出现的情况,再根据题目条件从所有可能的情况中,删除那些不符合条件的解。
由哈夫曼算法的定义可知,初始森林中共有n棵只含有根结点的二叉树。算法的的第二步是:算法的的第二步是:将当前森林中的两棵根结点权值最小的二叉树,合并成一棵新的二叉树,每合并一次,森林中就减少一棵树,产生一个新结点。则要进行n-1次合并,所以共产生n-1个新结点。由此可知,最终求得的哈夫曼树中一共有2n-1个结点。其中, n个结点是初始森林中的n个孤立结点。并且哈夫曼树中没有度数为1的分支的结点。
采用哈夫曼编码方案,即应用哈夫曼树构造使电文的编码总长最短的编码方案。
正文
(1)哈夫曼树的存储结构定义为:
typedef struct /* 字符集的元素结构*/
{char data;
int weight; //权值
}elemtype;
typedef struct /* 哈夫曼树的元素结构*/
{char data;
int flag;
int weight; //权值
int parent,lchild,rchild; //左右孩子及双亲指针
}htnode,*huffmantree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表
(2)哈夫曼树的存储结构描述:
#include<>
#include<>
#include<>
#define n 27 /* 字符集的容量*/
#define MAXVALUE 1000 /*权值的最大值*/
#define MAXNODE 35 //哈夫曼树最多节点数
#define MAXD 100
2. 各模块的伪码算法:
(1)构造哈夫曼树的算法
void ChuffmanTree(HuffmanTree HT,Huffmancode Hc,t[],char str[])
{/*t中存放每类字符在电文中出项的频率,str中存放电文中不同类的字符*/
int i,s1,s2;
for(i=1;i<=2;*num-1;i++)
{
HT[i].lchild=0;HT[i].rchild=0;
HT[i].parent=0;HTweight=0;
}
for(i=1;i<=2*num;i++) /*输入num个结点的权值*/
HT[i].t[i];
for(i=num+1;i<=2*num-1;i++)
{/*在HT[1..i-1]中选择parent为0且权值最小的两个结点*/
selext(Ht,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
Ht[i].lchild=s;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
for(i=0;i<=num;i++) /*输入字符集中字