《数据结构实验三 哈夫曼编解码器.》由会员分享，可在线阅读，更多相关《数据结构实验三 哈夫曼编解码器.（15页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验三树学生姓名：大学霸班 级： xxxxxxxxxx班内序号： xx学 号： xxxxxxxxxx日 期： 2012年12月1日1实验要求a. 实验目的通过选择两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力b. 实验内容利用二叉树结构实现赫夫曼编/解码器。基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的
2、编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个
3、字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1 存储结构哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。只有度为0和2的结点的二叉树成为正则二叉树。哈夫曼树就是这样。根据二叉树的性质，一颗有n个叶子的哈夫曼树共有2n-1个叶子结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个节点。由于每个结点同时还包括其双亲信息和孩子信息，所以用一个静态三叉链表来存储哈夫曼树。weightlchildrchildparent2-1-143-1-146-1-159-1-165015114262035-1012345620115ABZC10011020115ABZC00
4、1C+描述如下struct HNode/静态三叉链表元素int weight; /结点权值int parent; /双亲指针int lchild;/左孩子指针110int rchild;/右孩子指针int mark;/标记是否已经访问过;如图所示的哈夫曼树，其对应的编码表可以是如图所示的结构，实际上字符的编码应该用bit表示，即对于1个字符Z使用三个比特001表示哈夫曼编码表的C+描述：struct HCode/哈夫曼编码表 char ch2; /字符 int freq; /频度 char code100;/字符编码;2.2 关键算法分析核心算法思想：1. 哈夫曼编码(Huffman Codi
5、ng)是不等长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。2. 哈夫曼编码可以实现无损数据压缩。单个字符用一个特定长度的位序列替代：在字符串中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。关键算法思想描述和实现：关键算法1：初始化函数用字符串记录用户输入的原始数据，统计一共出现了多少种字符，各出现了多少次即为字符的权值。对未出现的字符不予统计编码。将统计的叶子节点编制成数组。为创建哈夫曼树作准备。1 用字符串str接收用户输入的数据2 用数组frequency存储字符出现的个数3 如果字符出现过，叶子节点数加14 创建哈夫曼树Htree，哈夫
6、曼编码表HcodeTable5 初始化哈夫曼编码表 5.1 判断字符是否出现过 5.1.1 记录权值和字符 5.1.2 编码形式置空6 初始化哈夫曼树6.1 标记叶子节点，无左子树右子树及父节点C+实现如下void Huffman:Initial()1cin.getline(str,MAXSIZE); /从键盘接收字符串short frequency128=0;leaf=0;2for(int i=0;stri!=0;i+)/统计字符频度frequency(short)stri+;3for(int j=0;j128;j+)/统计字符种类个数if(frequencyj!=0) leaf+;4HTr
7、ee = new HNodeleaf*2-1; /创建哈夫曼树HCodeTable = new HCodeleaf; /创建哈夫曼编码表5for(int k=0,m=0;k128;k+)/初始化哈夫曼编码表 5.1 if(frequencyk!=0) /字符串是否出现k对应的字符5.1.1HCodeTablem.freq=HTreem.weight=frequencyk; /字符的频度即为权值HCodeTablem.ch0=(char)k; /字符数据HCodeTablem.ch1=0;5.1.2HCodeTablem.code0=0; /字符编码先设为空HTreem.mark =0;m+;
8、6for(int k=0;kleaf;k+) /初始化哈夫曼树HTreek.lchild=HTreek.rchild=HTreek.parent=-1;/标记叶子节点，无左右孩子及父节点cout编码初始化完成！n;时间复杂度：因为操作每次都需要把str遍历一遍，如果str长度为n，则时间复杂度为o（n）关键算法2：建立哈夫曼树建立哈弗曼树即最优二叉树。这里实现时：每建立一个父节点就需要扫描权值序列得到两个最小的权值。由于节点个数逐渐增多，因而扫描次数动态变化，程序里设置计数变量来控制扫描次数的变化。另外设置标记来标识节点是否已经被取出。由于前面得出了总的叶子节点个数，根据哈弗曼树建立的规律可以
9、知道总的节点数和建立哈弗曼树过程中的父子节点间的对应关系，因而可以通过下标准确定位节点，动态建立哈弗曼树。1初始化最小权值min，最小权值点num，扫描次数front，查找最小值的次数count，左、右子树权值lcvaule、rcvaule2 在前front个节点中找到最小权值点，记录结点和权值3 最小节点已被访问，4 找到第一个最小权值点即为新节点的左孩子 4.1 记录权值，建立此节点和新节点的关系5 找到第二个最小权值点即为新节点的右孩子 5.1 记录权值，建立此节点和新节点的关系 5.2 新节点的权值等于孩子结点权值之和 5.3 新节点下移，查找次数count清零6 根节点的父节点为空C
10、+实现：void Huffman:CreateTree()1int min=MAXSIZE;int num(0),front(leaf),count(0),lcvalue(0),rcvalue(0);for(int s=0;s(2*leaf-2);s+)2for(int i=0;ifront;i+) /遍历编码表中所有元素寻找最小值if(HTreei.mark!=1 & HTreei.weight=min) /找到权值最小的结点 min=HTreei.weight; num=i; /记录最小权值，结点下标3HTreenum.mark=1; /标记已读count+;4if(count=1) /第
11、一个最小节点即左孩子4.1lcvalue=min; /lcvaule保存左孩子的权值HTreenum.parent=front; /修改左孩子的父节点HTreefront.lchild=num; /记录新节点的左孩子5if(count=2) /第二个最小节点即右孩子5.1rcvalue=min; /rcvalue保存右孩子的权值HTreenum.parent=front; /修改第二个节点的父节点HTreefront.rchild=num; /记录新节点的右孩子5.2HTreefront.weight=lcvalue+rcvalue; /新节点的权值等于lcvalue+rcvalue5.3front+; /新节点下移count=0; /计数器清零min=MAXSIZE;6HTree2*leaf-2.parent=-1; /根节点时间复杂度：假设有n个叶子节点，在原有叶子节点的基础上还要新创建n-1个结点才能构成哈夫曼树，每次创建新节点时还要在前n个节点中找到最小的两个结点做为左子树和右子树，则时间复杂度为o(n2)关键算法3：建立哈
