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

数据结构实验报告实验名称： 实验三题目2哈夫曼树学生姓名： 班 级：班内序号： 学 号：日 期： 1．实验要求实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法学习指针、模板类、异常处理的使用掌握线性表的操作实现方法培养使用线性表解决实际问题的能力实验内容：利用二叉树结构实现赫夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1 存储结构二叉树：示意图： root lchild parent rchild （静态三叉链表存储）weightLChildRChildparent02-1-1-113-1-1-126-1-1-139-1-1-14-1-1-15-1-1-16-1-1-1 （a）初始化哈夫曼树weightLChildRChildparent02-1-1413-1-1426-1-1539-1-164501551142662035-1 （b）创建好的哈夫曼树哈夫曼编码的存储结构 data code 0 Z 100 1 C 101 2 B 11 3 A 0 01 01 0 12.2 关键算法分析1 初始化 算法步骤： ①统计字符串字符综述并申请动态数组存储字符串； ②对所存储字符串进行排序； ③统计不同字符的个数； ④释放动态内存空间； ⑤创建哈夫曼数的数组； ⑥创建哈夫曼编码表。 源代码：void Huffman::Init(char *s){int n=0;while (*(s+n)!=\0){n++;//统计字符串字符数}char *temp=new char[n];//申请动态数组存储字符串以便之后对字符串排序for (int i=0;in;i++){temp[i]=*(s+i);}char ctemp;for (int i=0;in-1;i++)//冒泡排序法,排序以后方便统计不同字符串出现的个数{for (int j=0;jn-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;in;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;in;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];k++;l=1;HTree[k].c=ctemp;HTree[k].weight=l;}}delete []temp;//释放动态内存空间Creat();//创建哈夫曼数的数组CodeTable();//创建哈夫曼编码表}时间复杂度：n2 创建哈夫曼树动态数组算法步骤： ①根据权重数组初始化哈夫曼树； ②选取权值最小的两个结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和； ③删除这两棵子树，将新构成的树加入到T中，重复②③直至T中只含有一棵树。 源代码：void Huffman::Creat(){int n=(m+1)/2;//n表示不同字符的个数for (int i=0;in;i++){HTree[i].LChild=-1;HTree[i].RChild=-1;HTree[i].parent=-1;}int x,y;for (int i=n;i2*n-1;i++){SelectMin(x,