文档介绍：山东轻工业学院课程设计专用纸成绩
课程名称《数据结构》指导教师杨春花
院(系) 信息学院专业班级计科(高职)10-2班
学生姓名于孟田学号 201003014062 设计日期
课程设计题目赫夫曼编/译码器
1、需求分析
利用赫夫曼编码进行通信可大大提高信道利用率,缩短信息传输时间。试编写一个赫夫曼编/译码系统。要求:(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树。(2) E: 编码(Encoding)。利用已建好的赫夫曼树对文件ToBeTran中的正文进行编码,然后将结果存入CodeFile文件中。(3) D: 译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码,结果存入TextFile中。(4) P: 打印(Print)。打印CodeFile和TextFile中的内容。
概要设计
(1)设计思想
赫夫曼树用邻接矩阵作为存储结构,借助静态链表来实现遍历。
函数间的关系
函数间的关系如图所示:
主函数
显示表头
初始化树
输入字符
编码
译码
打印编码
打印赫夫曼树
选最小两个权值
Select()
山东轻工业学院课程设计专用纸(附页)
(3)数据结构与算法设计
赫夫曼编\译码器的主要功能是先建立赫夫曼树,然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。
在数据通信中,经常需要将传送的文字转换成由二进制字符0、1组成的二进制串,称之为编码。构造一棵赫夫曼树,规定赫夫曼树中的左分支代表0,右分支代表1,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码,称之为赫夫曼编码。
最简单的二进制编码方式是等长编码。若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。
(4)模块划分
班级
学号
姓名
负责模块
组长
计科高职10-2
201003014062
于孟田
编码、译码、打印编码、打印赫夫曼树
组员
计科高职10-2
201003014065
毕雪晴
显示表头、初始化树、输入编码、
。
山东轻工业学院课程设计专用纸(附页)
开始
结点数是否大于1
将data和权值赋给ht
输出根结点和权值
调用SELECT函数
计算根结点函数
父结点为两子结点之和
输出两子结点和已构造的结点
是否为根结点?
左子是否为空?
此时编码为0
I<2*N?
I++
编码为1
结束
否
否
否
右子是否为空
是
是
否
否
是
是
是
山东轻工业学院课程设计专用纸(附页)
3、详细设计
赫夫曼树编、译码设计功能如下:
(1)赫夫曼树抽象数据类型定义
ADT HuffmanCoding{
数据对象T:具有相同特性的数据元素的集合
数据关系R:满足最优二叉树的关系
基本操作P:
Init(&t)
操作结果:构造一个空赫夫曼树t。
encode()
操作结果:利用赫夫曼树进行编码
Decode()
操作结果:利用赫夫曼树进行译码
}
(2) 主函数
Void mian()
{打印表头;
While(选择项不为q){
输入选择项;
Switch(选择项)
{Case i: 初始化;break;
Case w: 输入要编码的字符; break;
Case e: 编码字符; break;
Case d; 译码操作;break;
Case p; 打印代码;break;
Case t; 打印赫夫曼树; break;
Default:输入错误,重新选择;
}
(3)求赫夫曼编码
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j; //flag为标志符,为不小于可能的值
t[flag].parent=1;
(4) 建赫夫曼树
HT[s1].parent=HT[s2].parent=i;//将选好的两个结点设置成有同一个双亲结点
HT[i].lchild=s1;//左孩子的权值
HT[i].rchild=s2;//右孩子的权值
HT[i].weight=HT[s1].weight+HT[s2].weight;//将两个权值相加作为新的权值
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//为赫夫曼代码分配空间
山东轻工业