武汉理工大学《数据结构》课程设计说明书 哈夫曼编码 1．问题分析与

1、哈夫曼编码1问题分析与任务定义1.1 需求分析.1 用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发射端通过一个编码系统对待传输的数据预先编码，在接受端将传来的数据进行译码(复原)。对于双工信息道(既可以双向传输信息的通道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译/码系统。.2 本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码。.3 演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去

2、输入中的非法字符）和运算结果显示在其后。.4 在本系统中，用户可以对任意长的字符串可进行编码/译码。1.2 设计基本要求： 一个完整的系统应该包括以下功能： 初始化（initalization）. 从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树, 中. 编码(Encoding)。利用已建立好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码,然后将结果代码存(传输)到文件codeFile中. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中. 印文件代码(Print)。将文件Cod

3、eFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。.5 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 任务定义 1.3.1 程序执行的命令包括：1）初始化 2）编码 3）译码 4）印代码文件 5）印哈夫曼树 6）退出 1.3.2 测试数据: 1) 利用教科书例6-2中的数据调试程序。2)用程序文件夹中的text.txt文件进行测试,并把得到的哈夫曼编码写入codefile.txt文件中。2数据类型和系统设计 2.1逻辑设计

4、 为实现上述程序，须将程序分模块设计，具体设计为四个模块：分别是二叉树节点模块，二叉树实现的模块，哈夫曼树的实现模块及测试模块。各模块的抽象数据类型如下： 二叉树节点模块： 本模块中主要定义二叉树节点的类型，包括：.1树的节点值 m_data.2指向左孩子节点的指针 left_child.3指向右孩子节点的指针 right_child 二叉树实现的模块 本模块中主要根据二叉树的节点，来建立一系列的操作，即:.1 初始化一棵二叉树 BinaryTree_T(void);.2二叉树的赋值BinaryTree_T<T>& operator=(const BinaryTree_T&

5、lt;T>& bt).3 二叉树的遍历 void PreOrder(void); .4 二叉树的清空 void Clear(void);.5 二叉树的访问 void Visit(const TreeNode_T<T>*ptr) 哈夫曼树的实现模块 本模块中根据二叉树来建立哈夫曼树，主要包括： .1 哈夫曼树的初始化 HfmTree_T(void) .2 哈夫曼树的创建 void CreatHfmTree(void); .3 哈夫曼树的创建 HfmTree_T<W>& operator=(const HfmTree_T<W> &r

6、hs); .4 文件译码 void Code(char *&code);； .5 文件的解码 void GenerateCode(BinaryTree_T<int> &P); 主测试模块 int main() HfmTree_T<int>hfmTree;hfmTree.CreatHfmTree(); hfmTree.GenerateCode(); hfmTree.DeCode(); return 0; 2.2 详细设计 本部分内容主要包括对模块的抽象，及将其抽象出一般的定义，各模块的抽象数据类型如下： 抽象数据类型TreeNode_h 用以实现二叉树的节

7、点，其定义如下： Template<class T> Class TreeNode_T Private:T m_data;/树的节点值TreeNode_T<T> *left_child;/指向左孩子节点的指针 TreeNode_T<T> *right_child;/指向右孩子节点的指针Public:/成员函数 TreeNode_T(const T &data,TreeNode_T<T> *lchild=NULL, TreeNode_T<T> *rchild=NULL);T Data(void)const; TreeNode_T

8、<T>*& LeftChild(void); TreeNode_T<T>*& RightChild(void); .2 抽象数据类型BinaryTree_h用以实现二叉树的操作，其定义如下：template<class T>class BinaryTree_T Public:BinaryTree_T(void); BinaryTree_T(const T &element); BinaryTree_T(const BinaryTree_T<T> &bt);BinaryTree_T(void);/赋值 BinaryT

9、ree_T<T>& operator=(const BinaryTree_T<T>& bt); TreeNode_T<T>* CopyBinaryTree(TreeNode_T<T>*ptr); /构造二叉树 Void MakeTree(constT&data,BinaryTree_T<T>&lhs, BinaryTree_T<T>&rhs); /前置条件:当前树为空 lhs rhs 不等 /后置条件:lhs rhs 为空/拆开二叉树 Void BreakTree(T&dat

10、a,BinaryTree_T<T>&lhs, BinaryTree_T<T>&rhs);/前置条件:当前树非空,rhs lhs为空,且不等/后置条件:当前树指空 void PreOrder(void);/前序 void InOrder(void);/中序void PostOrder(void);/后序/清空 void Clear(void); /访问节点void Visit(const TreeNode_T<T>*ptr);/得到树的根结点 TreeNode_T<T>* GetTreeNode(void);protected: /

11、树的保护成员只想二叉树节点的指针 TreeNode_T<T>* m_root;private:/树的遍历的私有成员函数 void PreOrder(TreeNode_T<T>*ptr); void InOrder(TreeNode_T<T>*ptrvoid PostOrder(TreeNode_T<T>*ptr);void Clear(TreeNode_T<T>*ptr);.3 抽象数据类型HfmTree_h用以实现哈夫曼树的操作，其定义如下： template<class W>class HfmTree_Tpublic:

12、 /几种构造函数 HfmTree_T(void); HfmTree_T(const BinaryTree_T<int> &rhs); HfmTree_T(const HfmTree_T<W> &rhs); /析构函数HfmTree_T(void); bool operator>(const HfmTree_T<W> &rhs)const; bool operator=(const HfmTree_T<W> &rhs)const; bool operator<(const HfmTree_T<W&g

13、t; &rhs)const; HfmTree_T<W>& operator=(const HfmTree_T<W> &rhs); /创建Hfm树 void CreatHfmTree(void); operator W()const;/重载()运算符 以得到劝值 /void ShowTree(void); /记录频率 void GetWeight(char c); /译码 void Code(char *&code);； int GetNumber(int x); int GetNumber(char c); void GenerateCo

14、de(void); void DeCode(void);private: void GenerateCode(BinaryTree_T<int> &P);void GenerateCode(TreeNode_T<int> *ptr,char *c,char *&code,int &count,int k,int lev); BinaryTree_T<int>m_tree; /哈夫曼树的权值W m_weight;3调试报告 由于文件text.txt的内容较多，结果造成程序运的较慢，并造成部分的字母没有被编码。导致程序调试时间花费较多，且

15、最后并没很好的解决。 3.2 本程序有些代码重复出现，从而减少了空间的利用率和增加了程序的杂乱性，特别是文件操作方面，如果可能的话，可以把文件的读入读出分别写成一个函数，将会大大增强程序的可读性。 3.3 算法的时空分析：此程序中使用了大量的指针，且是动态申请，释放内存的，有效的利用了系统的空间，使程序执行起来更高效。 3.4 本程序采用数据抽象的程序设计方法，将程序分为四个模块，使得设计时思路清晰，实现时调试顺利完成，各个模块具有较好的可重用性，确实做到了一次良好的程序设计训练。 3.5 程序运行结果如下： 在text.txt文档中输入要编码的文件，结果程序顺利把该文件中包含的字符编码，并进行了解码，结果如下：4经验和体会、通过实验更好的掌握了哈夫曼树，并对哈夫曼树有了深一步的了解、掌握了用get