1、数据结构数据结构课程设计课程设计 1 哈夫曼编码哈夫曼编码/译码器译码器 一一 目的目的 通过本次课程设计：复习学过的数据结构的内容；巩固和加深对线性表、栈、队列、 字符串、树、图、查找、排序等理论知识的理解，这里主要用到二叉树和栈；掌握现实复 杂问题的分析建模和解决方法；提高利用计算机分析解决综合性实际问题的基本能力。 二二 需求分析需求分析 目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二进制的 字符组成的字符串。在传送电文时，希望总长度尽可能地短。如果对每个字符设计长度不 等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长度便 可减少。如果要设
2、计长短不等的编码，则必须是任一个字符的编码都不是另外一个字符的 编码的前缀，这种编码叫前缀编码。设计电文总长最短的二进制前缀编码，要以 n 种字符 出现的频率做权，设计一棵哈夫曼树，由此得到的二进制前缀编码就叫做哈夫曼编码。 编码时，从待编译文件 ToBeTran.txt 中获得出现的字符及其出现的次数（出现次数即 为此字符的权值）；或从终端获取各个字符及其权值据此建立哈夫曼树。建好的哈夫曼树 以凹凸表的形式存到文件 TreePrint.txt 中。利用建好的哈夫曼树对各个字符进行编码，编得 的哈夫曼码存到文件 HuffmanCodes.txt 中。利用已建好的各字符的哈夫曼码对 ToBeTr
3、an.txt 进行逐字编码，编好的二进制字符串存到文件 CodeFile.txt 中。 在编码期间，用户可以选择是否观看：建好的哈夫曼树；建好的各字符的哈夫曼码； ToBeTran.txt 中的原文；原文经编译产生的二进制字符串。 译码时，从 HuffmanCodes.txt 中获取各字符的哈夫曼码，据此建好哈夫曼树，然后利 用建好的哈夫曼树对文件 CodeFile.txt 中的二进制字符串进行译码，将二进制字符串译成对 应字符集，并把它们存到文件 TextFile.txt 中。 在译码期间，用户可以选择是否观看：CodeFile.txt 中的哈夫曼码集；建好的各字符 的哈夫曼码；哈夫曼码集经
4、译码产生的字符集。 三三 概要设计概要设计 1、程序抽象数据类型的定义程序抽象数据类型的定义 （1） typedef struct char character;/字符 unsigned int weight;/权值 unsigned int parent;/父母节点 数据结构数据结构课程设计课程设计 2 unsigned int lchild;/左孩子 unsigned int rchild;/右孩子 HTNode,*PHTNode,*HuffmanTree; HuffmanTree：哈夫曼树；HTNode：哈夫曼树的节点；PHTNode：指向哈夫曼树节点 类型数据的指针类型。 （2） typedef HTNode StackElementType; typedef struct StackElementType *base;/栈底指针，在栈构造前和销毁后，base 的值为 0 。 StackElementType *top;/栈顶指针。 int stack_max_capacity;/栈的最大容量。 int stack_length;/
