数据结构——实验四哈夫曼树与哈夫曼编码

1、精选优质文档-倾情为你奉上软 件 学 院哈夫曼树与哈夫曼编码实验报告课程名称： 数据结构 姓 名： 郑斌 学 号： 7 班 级： 卓越131 专心-专注-专业实验四 哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容本次实验提供3个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一、哈夫曼树和哈夫曼编码问题描述一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。测试数据利用教材P.148 例62中的数据调试程序 (可自己设定测试数据)。 选作内容1、

2、打印出该哈夫曼树2、若从终端输入任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。提示：如何快速统计不同字符的出现频率3、译码：将上述1的编码结果还原成电文。三、算法设计1) 本程序包含三个模块1 void Select(HuffmanTree HT,int i,int &s1,int &s2) /选择函数2 voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n)w存放n个权值, 构造哈夫曼树p, 3 Void Huffmancode(HuffmanTree &

3、amp;HT,HuffmanCode &HC,int n)求出哈夫曼编码hc并输出哈弗曼编码4、 实验结果图1-1 输入哈弗曼树的权值图1-2 显示哈弗曼树表与其编码五、总结通过做哈弗曼树实验让对最优二叉树这种结构有了更深的了解和应用，对我以后的编程产生了比较深远的影响。六、源程序（带注释）#include<iostream>#include<iomanip>#include<stdlib.h>#include<string.h>#include<stdio.h>using namespace std;typedef stru

4、ct int weight; int parent,lchild,rchild;char charr;HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int i,int &s1,int &s2) int j,k=1; while(HTk.parent!=0)k+;s1=k;for(j=1;j<=i;+j)if(HTj.parent=0&&HTj.weight<HTs1.weight)s1=j;k=1;while(HTk.parent!=0|k=s1)k+

5、;s2=k;for(j=1;j<=i;+j)if(HTj.parent=0&&HTj.weight<HTs2.weight&&j!=s1)s2=j;void HuffmanCoding(HuffmanTree &HT,int *w,int n)int m,i,s1,s2;if(n <= 1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m + 1) * sizeof(HTNode);for(i = 1;i <= n;+i)HTi.weight = wi;HTi.lchild = 0;

6、HTi.rchild = 0;HTi.parent = 0;for(i = n + 1;i <= m;+i)HTi.weight = 0;HTi.lchild = 0;HTi.rchild = 0;HTi.parent = 0;/构建哈弗曼树 for(i = n + 1;i <= m;+i)Select(HT,i - 1,s1,s2);/选择parent为0且weight最小的两个结点，期序号分别为s1，s2 HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weig

7、ht + HTs2.weight;cout<<"n哈弗曼树表如下："<<endl;/打印哈弗曼树表cout<<" i weight parent lchild rchild"<<endl;HuffmanTree p;for(p=HT+1,i=1;i<=m;i+,p+)cout<<setw(2)<<i<<setw(7)<<p->weight<<setw(6)<<p->parent<<setw(7)<&l

8、t;p->lchild<<setw(8)<<p->rchild<<endl;void Huffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)char *cd;int c,f,start; int i;HC = (HuffmanCode)malloc(n + 1) * sizeof(char *);cd = new charn;cdn - 1 = '0'/编码结束标志 for(i = 1;i <= n;+i)start = n - 1;for(c = i,f = H

9、Ti.parent;f != 0;c = f,f =HTf.parent)if(HTf.lchild = c)cd-start = '0'else cd-start = '1'HCi = (char *)malloc(n - start) * sizeof(char);strcpy(HCi,&cdstart);cout << endl; cout<<"哈夫曼编码如下:"for(i=1;i<=n;+i)/逐个字符求赫夫曼编码 start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f

10、=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,&cdstart);/从cd复制编码到HC printf("nHT%d 节点的哈夫曼编码是: %s 对应权值为：%d",i,HCi,HTi.weight);cout<<endl;free(cd);int main()HuffmanTree HT;HuffmanCode HC;int *w;char *e;char c;int i,n,m,wei;cout << "-请输入哈弗曼树的带权数目-" << endl;cin >> n;w = new intn + 1;e = new charn + 1;for(i = 1;i <= n;