东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术
四、 详细设计
creattreehuffman creatcodehuffman writecodehuffman main transcodehuffman printtreehuffman printcodehuffman 4.1哈夫曼树的建立
4.1.1哈夫曼树的存储结构
为了实现通过哈夫曼算法建立哈夫曼树，首先要定义哈夫曼树的存储结构。由于构造哈
夫曼树之后，编码时要从叶结点出发走一条从叶结点到根的路径，而译码时要从根结点出发走一条从根到叶结点的路径。对于每个结点而言，既需知道双亲的信息，又需知道孩子的信息。因此，可以使用带双亲的孩子链表作为结点的存储结构。由哈夫曼算法可知，如果哈夫曼有n个叶结点，则最终生成的哈夫曼树共有2n-1个结点。因此，可以用一个长度为2n的一维数组存放哈夫曼树的所有结点。详细定义如下： #defineLeafnum27 #define Hufnum2*Leafnum typedefcharDataType; typedefstructTnode {
DataTypename; double weight;
intlchild, rchild, parent;
}Huftree;
Huftree Tree[Hufnum];
其中，name表示结点数据的名称（即字符名称），weight表示结点的权值（即字符使用
频度），lchild、rchild分别是结点的左、右孩子在数组中的下标值，叶结点的左右孩子的下标值均为0；parent表示结点双亲在数组中的位置。它的主要作用有两点：第一，区分根结点和非根结点；第二，使得查找某个结点的双亲变的更为简单。若parent=0，则该结点是树的根结点，否则为非根结点。因为把森林中的两棵二叉树合并成一棵二叉树时，必须从森林的所有结点中选取两个根结点的权值为最小的结点，此时就是根据parent来区分根与非根结点的。
东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术
4.1.2建立哈夫曼树
本设计只对26个英文大写字符及空格进行了哈夫曼编码，各字符及对应使用频度如下
表所示：
表4.1 字符及其使用频度
字符 频度 字符 频度 186 N 57 A 64 O 63 B 13 P 15 C 22 Q 1 D 32 R 48 E 103 S 51 F 21 T 80 G 15 U 23 H 47 V 8 I 57 W 18 J 1 X 1 K 5 Y 16 L 32 Z 1 M 20 需要定义全局数组来存放这些字符名称和对应频度： char ch[] = {'\\0','
','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; float w[] =
{0,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};
定义函数CreatTreeHuffman，其中包括对已建立好的哈夫曼树的初始化，即将结点数
据名称初始化为’\\0’，将结点权值、结点双亲及左右孩子的下标值都初始化为0；对已初始化的哈夫曼树赋值，将全局数组ch中存放的字符名称赋到叶结点的name上，将全局数组w中存放的字符使用频度赋到叶结点的weight上；最后根据哈夫曼算法对27个结点（每个结点可以看做是一棵树）构造出哈夫曼树。
4.2哈夫曼编码表的建立
4.2.1哈夫曼编码表的存储结构
利用哈夫曼树对字符进行哈夫曼编码，实际上就是求出从根结点到叶结点的路径。由于采用带双亲的孩子链表作为存储结构，因此，对于输入的每个字符，可以从哈夫曼树的叶结点出发，沿结点的双亲链回溯到根结点，在这个过程中，每回溯一步都会经过哈夫曼树的一个分支，从而得到一个哈夫曼编码。因此，可设置一个位串数组bits，将生成的代码序列从后到前依次存放到数组bits中。哈夫曼编码表存储结构定义如下： typedefstructCnode {
char bits[Leafnum+1]; intstart;
东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术
char ch;
}hufcode;
由于叶子结点总数即字符个数为Leafnum，故不等长编码的长度不会超过Leafnum，再
加上结束符号’\\0’，位串数组bits的大小应为Leafnum+1，整型变量start用来指示编码在数组中的起始位置，当某个字符编码完成时，从变量的start处开始将编码复制到该字符对应的数组bits中去即可。
4.2.2建立哈夫曼编码表
建立哈夫曼编码表即建立一个表格用来存储每个字符名称和对应的哈夫曼编码，此过程
建立在已经构造好的哈夫曼树上，从叶结点开始，沿着双亲链向上，记录沿途经过分支上的二进制编码，直到到达根结点，于是对应每一个字符都有一个二进制串，即它的哈夫曼编码，用上面定义的哈夫曼编码表存储结构数组存放起来，即存在位串数组bits中。
4.3编码
本程序的功能是能对从键盘输入的任意有限长度的字符串（限定在大写英文字符和空格）进行哈夫曼编码，因此需要定义函数WritecodeHuffman来实现对输入的字符串逐个进行编码，此过程实质上是将字符与编码表里的字符名称相比较，当名称一致时，就输出对应字符的bits数组中的二进制编码，然后依次输出每个字符的哈夫曼编码，将他们连续的显示在屏幕上。
4.4文件写入
由于要将这些二进制串写入文件，所以事先再定义一个全局字符数组Huffmancode来存储这些二进制串。在主函数先在某目录下建立一个.txt文件，名为codefile，再定义了一个输出流类ofstream的对象ofs，定义ofs的同时将其与文件codefile关联，于是，就可以通过操作ofs来实现文件数据的写入，即将字符数组Huffmancode中的二进制编码写入文件。
[1]
4.5译码
译码的过程与编码的过程相反，先将codefile文件中的二进制编码读出来，这时在主
函数中也定义一个输入流类ifstream的对象ifs，同时将它与文件codefile关联，通过ifs读取codefile文件中的二进制编码，存放到数组buffer中，再通过译码函数进行译码，TranscodeHuffman译码函数定义如下：
东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术
voidTranscodeHuffman(Hufcode code[], Huftree tree[], char s[]) { }
该函数带三个参数，分别是已建立好的哈夫曼树结点数组，哈夫曼编码表数组和需要进inti; char *q=NULL; i=Hufnum-1; q=s; while (*q!='\\0') { }
cout< if (*q=='0') i=tree[i].lchild; if (*q=='1') i=tree[i].rchild; if ((tree[i].lchild==0)&&(tree[i].rchild==0)) { } q++; cout<< code[i].ch; i = Hufnum - 1; 行译码的字符数组，该字符数组存放的即为由0、1组成的一串编码，函数中设置字符类型指针q开始指向字符数组的第一个字符，若为0，则进入左孩子，否则进入右孩子，再执行q++，直到某结点的左右孩子下标值均为0的时候，此时的结点即为叶结点，于是输出对应字符，再将起始结点设为根结点，重复上述过程，直到翻译出所有字符。 五、 测试结果 5.1 哈夫曼树输出 根据所给的27个字符及使用频度所建立的的哈夫曼树结构输出如图5.1． 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术