1、目录 1. 问题描述 1 2. 算法思想 2.1 Huffman 编码算法思想 1 2.2 各函数模块功能一览表 2.2.1 符号说明 2 2.2.2 各函数模块功能表 2 3. 算法设计 3.1 Huffman 编码程序清单 3.1.1 建立“mm.h”头文件2 3.1.2 源程序 nn.cpp3 3.1.3 源程序 main.cpp 6 3.2 输入报文 7 4. 程序测试情况与运行结果分析 4.1 程序运行结果 8 4.2 算法分析和总结 9 5. 课程设计心得体会 9 6. 参考文献 10 1 1 问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降 低传输成本
2、，试设计一个哈夫曼编码系统。功能要求：从键盘输入一段报文（如 “what did you do that made you so happy“） ，输出这段报文的哈夫曼编码。 2 算法思想 2.1 Huffman 编码算法思想 对一段报文进行 Huffman 编码，则要统计报文中每个字符出现的频率，本文 首先以报文中每个字符出现的次数作为本字符的权值来构造 huffman 树，构造 huffman树步骤如下所示： 根据给定的 n个权值w1， w2， .，wn构成 n棵二叉树的集合 F=T1,T2,Tn， 其中每颗二叉树 Ti中只有一个带权为 Wi的根结点，其左右子树为空。 （2） 在 F 中选
3、取两颗根结点的权值最小的树作为左右子树构造一颗新的二叉树， 且置新的二叉树根结点的权值为其左、右子树上根结点的权值之和。 （3）在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。 （4）重复（2）和（3） ，直到 F 只含一棵树为止。这棵树便是赫夫曼树。 建立 huffman树后， 需从叶子结点出发走一条从叶子到根的路径对每个字符进行 huffman编码。编码如下步骤： （1）从序号为 c=1（c 表示字符的序号）的字符开始，找到序号 1 对应字符的父 母，然后查看父母的左孩子，如果左孩子的序号对于 c，则编码为 0，否则编码 为 1. （2）然后将此时的父母序号赋给 c，找到此时 c
4、 的父母的序号，查看此刻父母 的左孩子，如果左孩子对于的序号等于 c，则编码为 0，否则编码为 1。 （3）重复（2）的步骤，编码到最后父母为空为止。然后记录 （4）对于剩下的每个字符，同理（2）和（3）进行编码。 2 2.2 各函数模块功能一览表 2.2.1 符号说明 zgeshu 记录总的字符个数 num 不同的字符个数 pa 父母 lc 左子树（左孩子） rc 右子树（右孩子） 2.2.2 各函数模块功能表 void Huffmancoding(Huffmantree int pa,lc,rc; 3 HTNode,*Huffmantree; typedef struct char wei
5、1; int count; KO,*KOKO;/记录字符和权值的结构体 typedef char *Huffmancode; void Huffmancoding(Huffmantree /根据权值 的大小，进行编码 void select(Huffmantree Ht,int ,int /找出父为 0 的两个最小的 权值 void Weight(KOKO /统计输入字符的不同 字符个数 num，并统计各字符的权值 void OutputHuffmanCode(Huffmantree,Huffmancode,KOKO /输出不 同字符的编码 void ShowAbout(); #endif / MM_H_INCLUDED 3.1.2 源程序 nn.cpp #include #include “mm.h“ #include “iomanip“ using namespace std; void ShowAbout() coutpa=0; p-lc=0; p-rc=0; for ( ;i=m;+i,+p) HTi.wei=0; HTi.pa=0; HTi.lc=0; HTi.rc=0; for (i=n+1;i=m;+i) select(HT,i-1,s1,s2); HTs1.pa=i; HT
