哈夫曼树录与正文.doc

目 录 1 问题描述及基本要求 1 2 需求分析 1 3 概要设计 2 3.1抽象数据类型定义 2 3.2模块划分 2 4 详细设计 3 4．1数据类型的定义 3 4.2 主要模块的算法描述 3 4.3流程图 5 5 测试分析 8 6 课程设计总结 11 参考文献 11 附录（源程序清单） 12 1 问题描述及基本要求 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，设计哈夫曼译码器，对输入的一串电文实现哈夫曼编码，然后对哈夫曼编码生成的代码进行译码，最后输出电文字符串。 基本要求： （1）初始化：键盘输入字符集大小n，n个字符和n个权值，建立哈夫曼树； （2）编码：利用建好的哈夫曼树生成哈夫曼编码； （3）输出编码； （4）译码； （5）设字符集及频度如下表： 字符 空格A B C D E F G H I J K L M N O P Q U V W X Y Z 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 char info、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中的每个结点的值、权重、双亲结点、左孩子、右孩子、再定义一个变量名为HT；另外定义一个变量名为HuffmanCode字符类型，再定义一个变量名为HC来存放哈夫曼编码，此外定义一个数组名为w[27]，包含题目所给的各结点字符的权重， （2void Select(HuffmanTree HT, int j,int s1,int s2)：把调用的字符按权值从小到大排序，挑出最小权值供HuffmanCoding（）调用并且根节点的权值等于他的左右孩子的权值。 （3）void HuffmanCoding(HuffmanTree HT, int w[], int n,char *info)：初始化哈夫曼树，处理 Select(HuffmanTree HT, int j,int s1,int s2)函数得到的数据，按照哈夫曼规则建立二叉树。此函数块调用了Select（）函数。 （4）void CheckCoding( )编码功能函数：利用已建立好的哈夫曼树（如不在内存，则从文件 hfmTree.txt 中读入） 对文件中的字符进行编码，然后将结果存入文件codefile.txt中。如果正文中没有编码的字符，先从键盘读入并存储到ToBeTra.txt中,然后从ToBeTra.txt读取，将编码结果存入到文件codefile.txt中。 （5）void HuffmanTranslate( )译码功能函数：利用已建立好的哈夫曼树将文件 codefile.txt 中的代码进行译码，结果存入文件 textfile.txt中 3 概要设计 3.1抽象数据类型定义 （1）树的抽象类型定义 ADT Stack{ 数据对象：D=｛ai|ai∈ElemSet,i=1,2,……，n, n≧0｝D为空集，则称为空树。 若D仅为一个数据元素，则R=｛H｝，H1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱。 （2）在D-｛root｝D-｛root｝D1，D2Dm（m0）3）对应于D-｛root｝H-{root,x1,……root,xm}有唯一的划分H1,H2,……Hm，(m0)2）基本操作： InitTree(T) 操作结果：构造空树T。 ClearTree(T) 操作结果：将树T清空为空树。 TreeDepth(T) 初始条件：树T已存在。 操作结果：返回T的深度。 Parent(T,cur_e) 初始条件：树T已存在，cur_e是T中的某个结点。 操作结果：若cur_e是树T的非根结点，则返回它的双亲，否则函数值为空。 3.2模块划分 本程序包括三个模块?: 主程序模块 void main() {初始化； 选择最小与次小权值的结点 构造哈夫曼树； 求哈夫曼编码； 求哈夫曼译码； ｝ （2）哈夫曼编码模块---实现哈夫曼树转换成编码； （3）哈夫曼译码模块---实现哈夫曼编码转换成电文。 4 详细设计 4．1数据类型的定义 （1）哈夫曼树类型 typedef struct { char info;//结点权值 int weight; //权重 int parent; //双亲结点 int lchild；//左孩子 int rchild; //右孩子 }HTNode,*HuffmanTree ； 4.2 主要模块的算法描述 （1）主函数 main() { int op,a; char *str=” ABCDEFGHIJKLMNOPQRSTUVWX