下载后可任意编辑实验五 哈夫曼编码与译码的设计与实现一、 问题描述利用哈夫曼编码进行通信能够大大提高信道利用率, 缩短信息传输时间, 降低传输成本。可是, 这要求在发送端经过一个编码系统对待传数据预先编码, 在接收端将传来的数据进行译码( 复原) 。对于双工信道( 即能够双向传输信息的信道) , 每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。基本要求: ( 1) 接收原始数据: 从终端读入字符集大小 n, 以及 n 个字符和 n 个权值, 建立哈夫曼树, 并将它存于文件 nodedata.dat中。( 2) 编码: 利用已建好的哈夫曼树( 如不在内存, 则从文件 nodedata.dat 中读入) , 对文件中的正文进行编码, 然后将结果存入文件 code.dat 中。( 3) 译码: 利用已建好的哈夫曼树将文件 code.dat 中的代码进行译码, 结果存入文件 textfile.txt 中。( 4) 打印编码规则: 即字符与编码的一一对应关系。( 5) 打印哈夫曼树: 将已在内存中的哈夫曼树以直观的方式显示在终端上。二、 数据结构设计1、 构造哈夫曼树时, 使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时, 设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息, 根据二叉树的性质可知, 具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点, 因此数组 HuffNode 的大小设置为 2n-1, 描述结点的数据类型为: 下载后可任意编辑typedef struct {int weight;int parent;int lchild;int rchild;char inf;}HNodeType;2.求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中, 从叶子结点开始, 沿结点的双亲链域回退到根结点, 每回退一步, 就走过了哈夫曼的一个分支, 从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的 0、 1 序列, 因此先得到的分支代码为所求编码的低位码, 后得到的分支代码为所求的高位码。因此设计如下数据类型: #define MaxBit 10struct HcodeType{int bit[MaxBit];int start;};3、 文件 nodedata.dat、 code.dat、 textfile.txt三、 功能函数设计1、 初始化功能模块下载后可任意编辑此功能模块的功能为从键盘接受字符集大小 n, 以及 n 个字符和 n 个权值。2、 建立哈夫曼编码的功能模块此模块功能为使用 1 中得到的数据根据...
