北邮数据结构实验三题目2哈夫曼树.docx

北京邮电大学信息与通信工程学院第 1页数据结构实验报告实验名称: 实验三题目 2哈夫曼树学生姓名: 班级: 班内序号: 学号: 日期: 1 .实验要求实验目的: ?熟悉 C++ 语言的基本编程方法,掌握集成编译环境的测试方法?学****指针、模板类、异常处理的使用?掌握线性表的操作实现方法?培养使用线性表解决实际问题的能力实验内容: 利用二叉树结构实现赫夫曼编/ 解码器。基本要求: 1、初始化(Init) :能够对输入的任意长度的字符串 s 进行统计,统计每个字符的频度,并建立赫夫曼树 2、建立编码表(CreateTable) : 利用已经建好的赫夫曼树进行编码, 并将每个字符的编码输出。 3、编码(Encoding) :根据编码表对输入的字符串进行编码,并将编码后的字符串输出。 4、译码(Decoding) :利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。 5、打印(Print) :以直观的方式打印赫夫曼树(选作) 6、计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。测试数据: I love data Structure, I puter 。I will try my best to study data Structure. 提示: 1 、用户界面可以设计为“菜单”方式:能够进行交互。 2 、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的字符一律不用编码。北京邮电大学信息与通信工程学院第 2页 2. 程序分析 存储结构二叉树: 示意图: root lchild parent rchild (静态三叉链表存储) (a )初始化哈夫曼树 weight LChild RChild parent 02 -1 -1 -1 13 -1 -1 -1 26 -1 -1 -1 39 -1 -1 -1 4 -1 -1 -1 5 -1 -1 -1 6 -1 -1 -1 北京邮电大学信息与通信工程学院第 3页(b )创建好的哈夫曼树哈夫曼编码的存储结构 关键算法分析 1 初始化算法步骤: ①统计字符串字符综述并申请动态数组存储字符串; ②对所存储字符串进行排序; ③统计不同字符的个数; ④释放动态内存空间; ⑤创建哈夫曼数的数组; ⑥创建哈夫曼编码表。源代码: void Huffman::Init(char *s) { int n=0; while (*(s+n)!='\0') { n++;// 统计字符串字符数} weight LChild RChild parent 02 -1 -14 13 -1 -14 26 -1 -15 39 -1 -16 45015 5 11426 6 2035 -1 data code 0Z 100 1C 101 2B 11 3A0 20 11 5 AC Z B 北京邮电大学信息与通信工程学院第 4页 char *temp=new char[n];// 申请动态数组存储字符串以便之后对字符串排序 for (int i=0;i<n;i++) { temp[i]=*(s+i); } char ctemp; for (int i=0;i<n-1;i++)// 冒泡排序法, 排序以后方便统计不同字符串出现的个数{ for (int j=0;j<n-1-i;j++) { if (temp[j]>temp[j+1]) { ctemp=temp[j]; temp[j]=temp[j+1]; temp[j+1]=ctemp; }}} int k=1; for (int i=1;i<n;i++)// 统计不同字符个数{ if (temp[i]!=temp[i-1]) { k++; }} HTree=new HNode[2*k-1]; m=2*k-1;// 存储哈夫曼数组大小 int l=0;// 统计不同字符出现的频度 k=0;// 控制哈夫曼数组下标 ctemp=temp[0];// 做标记 for (int i=0;i<n;i++) { if(temp[i]==ctemp) { l++;// 统计不同字符出现的频度 if (i==n-1) HTree[k].weight=l; } else { HTree[k].c=ctemp; HTree[k].weight=l; ctemp=temp[i]; 北京邮电大学信息与通信工程学院第 5页 k++; l=1; HTree[k].c=ctemp; HTree[k].weight=l; }} delete []temp;// 释放动态内存空间 Creat();// 创建哈夫曼数的数组 CodeTable();// 创建哈夫曼编码表} 时间复杂度: n2 创建哈夫曼树动态数组算法步骤: ①根据权重数组初始化哈夫曼