数据库实验哈夫曼编译码器

1、数据结构实验报告实验名称： 实验3XXXX学生姓名： 班 级： 班内序号： 学 号： 日 期： 1实验要求利用二叉树结构实现哈夫曼编解码器。基本要求：1、 初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、 建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3、 编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印：以直观的方式打印哈夫曼树（选作）额外要求： 1、用户界面可以设计为“菜单”方式，能够进行交互。 2、根据输入的字符串中每个字符出现

2、的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1 存储结构 以构造的结构HuffNode的数组来表示哈夫曼树，同时也将字符对应的编码存储在其中。本题只适用于小写字符的问题，只有26个小写字符，又考虑到构造哈夫曼树的结点，所以共需要51个结点。struct HuffNode int Weight; int Left;int Right;int Parent;string Code;HTree数组结构如下：0 1 2 3 4 5 6 49 50WeightLeftRightParentCode000000000-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-

3、1-1-1-1-1-1-1-1-1-1“ ”“ ”“ ”“ ”“ ”“ ”“ ”“ ”“ ”类Translatorclass Translatorpublic:void Init(char a) void CreateTable() void Encoding(char a) void Decoding() void Print() private:HuffNode HTree51; ;2.2 关键算法分析关键函数和算法1. 初始化函数void Init(char a)1.1使用for循环对Htree数组赋初值。1.2 依次提取a字符数组，对下边为ak-a的Htree数组元素权值加一。1.3对

4、Htree数组下边从0到25的元素，若其权值不为零，则字符种类Num加一。1.4对Htree数组下边从26到25+Num-1的元素赋值，选出在此之前权值最小且不为任意一个元素孩子的结点。将其父亲设为该结点下标，将其权值之和赋给该结点的权值，分别将两结点作为该结点的左右孩子。 2. 创建编码表函数void CreateTable() 2.1遍历Htree数组中的前26个元素，相当于26个字符。当他有父节点时。 22如果他是他父节点的左孩子，则在其编码（该字符，不是其父节点）code之前加上0。 23如果他是他父节点的右孩子，则在其编码（该字符，不是其父节点）code之前加上1。 24此时，将操作

5、结点变为其父节点，循环操作。 3. 编码函数 void Encoding(char a)3.1 依次提取a字符数组，直到取完a数组。3.2 如果下标为ak-a的元素权值为0，输出错误信息。3.3 反之输出下标为ak-a的元素的编码code。4. 译码函数void Decoding()4.1寻找根节点的下标。遍历HTree数组，找出其权值不为0且没有父节点的元素下标。4.2输入一串要解码的01序列。4.3依次从序列中取出字符。4.4如果为0，将操作结点变为其左孩子，若此时结点没有左孩子和右孩子，则输出与只对应的字符，再将操作结点变为根节点，循环操作。4.5如果为1，将操作结点变为其右孩子，若此时

6、结点没有左孩子和右孩子，则输出与只对应的字符，再将操作结点变为根节点，循环操作。5. 打印哈夫曼树函数void Print()5.1寻找根节点的下标。遍历HTree数组，找出其权值不为0且没有父节点的元素下标。5.2打印出根节点的权值。递归操作，依次打出其左孩子和右孩子。6.寻找下标不为给定值的最小函数 int SelectMin(HuffNode a,int n,int order) 6.1定义最小的权值，将HTree数组中第一个权值不为0且没有父节点且不为指定下标的元素权值赋给最小值，其下标赋给find。6.2遍历HTree数组，将权值不为0且没有父节点且不为指定下标的元素权值小于最小值的

7、元素权值赋给最小值，其下标赋给find。循环操作。6.3返回find。2.3 其他交互界面的实现：1. 使用While循环。持续的进行操作。2. 输出提示信息，让用户进行选择，输入字符。3用if去判断输入的字符是否也设定的字符相同。若相同就执行相应的操作。3. 程序运行结果 1.测试主函数流程：开始初始化编码表等待用户输入选择4123对输入的01序列进行译码根据输入的字符串重新创建编码表，并对其进行编码退出打印哈夫曼树结束4. 总结调试过程中，编码过程出输出的始终是0或1。在改变造作结点的时候，没有注意改变code的结点是不能改变的，必须是最下层的，也就是叶子结点。这样才会累加起来。cin.getline（）函数有出现在cin一个int后无法再输入的情况。问题出现在输入的缓存区。里面有一个换行符，直接就结束了输入，在之前加一个cin.ignore（）即可。通过这次课程设计使我充分的理解了用数组实现哈夫曼树的基本原理，知道了哈夫曼树的创建，遍历，及其他的应用，同时也学会了编写比较综合的程序。虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候