淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：树形数据结构实验班级：软件112学号：姓名：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告--树型数据结构实验报告要求1目的与要求:1）熟练掌握Huffman树的创建算法与编程实现；2）熟练掌握Huffman编码算法的实现与编程应用；3）创建较为实用的通信报文Huffman编码系统和译码系统;4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告,并按时提交。2实验内容或题目实验四：树型数据结构实验——创建通信报文编码与译码系统构造通信报文编码和译码系统（要求Huffman编码与译码）。条件：1、使用英文报文实施加密通信。设组成报文的字符集为26个英文字母（不分大小写）和两个标点符号字符“,”、“.”和一个空格字符（共29个字符）。2、字符集中每个字符（含字母和两个标点符号）的使用概率自己根据英文行文合理给出。3、以字符集中各个字符为叶结点、字符的使用频率为权重构造Huffman树，并求得各个字符的Huffman编码（参考教材P147教材算法6.12)。同时，输出构造的Huffman树和字符编码结果。4、在上述通信报文编码和译码系统中实现：输入一报文原文（明文），给出要发送的密码报文（密文）；输入一密文（0、1序列），输出对应的报文原文（明文）。其中报文原文或编码序列自己设定，尽量是一句话或一段文字的对应编码序列，这样可以验证输出结果的正确性。3实验步骤与源程序步骤先创建一个Huffman树，然后输入相应的英文字母，再根据英文行文合理给出它的使用概率，这样编码就可以实现明文和密文的转换。源代码#include<stdlib.h>#include<iostream.h>#include<stdio.h>#include<string.h>#defineOVERFLOW-1typedefstruct{charletter;floatweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTree&ht,inti,int&s1,int&s2){intj,k;for(k=1;k<i;k++){if(ht[k].parent!=NULL)continue;s1=k;break;}for(j=1;j<i;j++){if(ht[j].parent!=NULL)continue;if(ht[j].weight<ht[s1].weight)s1=j;}for(k=1;k<=i;k++){if(ht[k].parent!=NULL||k==s1)continue;s2=k;break;}for(j=1;j<i;j++){if(ht[j].parent!=NULL)continue;if(ht[j].weight<=ht[s2].weight&&j!=s1)s2=j;}}voidHuffmanCoding(HuffmanTree&ht,HuffmanCode&hc,char*zi,float*w,intn){HuffmanTreep;intm,i,s1,s2,f,r;intIstart=1;char*cd;if(n<=1)return;m=2*n-1;if(!(ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))exit(OVERFLOW);for(p=ht+1,i=1;i<=n;++i,++zi,++p,++w){p->parent=NULL;p->letter=*zi;p->lchild=NULL;p->rchild=NULL;p->weight=*w;}for(;i<=m;++i,++p){(*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(i=n+1;i<=m;++i){Select(ht,i-1,s1,s2);ht[s1].parent=i;ht[s2].parent=i;ht[i].lchild=s1;