嘉应学院计算机学院实验报告课程名称：数据结构课程设计开课学期：2017-2018学年第2学期班级：指导老师：实验题目：哈夫曼树学号：姓名：上机时间：一、实验目的本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。
二、实验问题描述利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。
系统应该具备如下的几个功能。
1、求出各个叶子节点的权重值输入一个字符串，统计其中各个字母的个数和总的字母个数。
2、构造哈夫曼树统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈夫曼树。
3、打印哈弗曼树的功能模块按照一定形式打印出哈夫曼树。
4、编码利用已经建立好的哈夫曼树进行编码。
5、译码根据编码规则对输入的代码进行翻译并将译码。
三、实验步骤1、实验问题分析（1）设计一个结构体数组保存字母的类型和个数。
{; 字母的种类; 字母的个数};（2）在构造哈夫曼树时，设计一个结构体数组保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有21个结点，所以数组大小设置为21,描述结点的数据类型为：{; 权值; 双亲; 左孩子; 右孩子};[]; 定义此类型的数组（3）求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始，沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类型：10;{[]; 每个结点的哈夫曼编码; 开始位置};（4）设置全局变量。
s; 为输入的字符串0; 记录输入的字符串中字母的种类，即叶子结点个数0; 记录字符串中字母的总个数[]叶子结点类型2、功能（函数）设计（1）统计字母种类和个数模块此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结点个数，每种字母出现次数即各叶子结点的权值。
全局变量s保存输入的字符串，将种类和个数保存到[]中。
函数原型：（）如输入的字符串是“”则显示如下。
（2）哈夫曼树的建立模块此模块的功能为从（1）中计算出的结点个数和各个叶子结点的权值构造一棵哈弗曼树。
函数原型：* ()函数返回结点类型的数组（3）打印哈弗曼树的功能模块此模块的功能是将由(2)建立的哈弗曼树按照一定规则<>打印在屏幕上。
函数原型： ( *)如输入的字符串是””，则构造的哈夫曼树为（4）建立哈夫曼编码的功能模块此模块功能为将（2）中建立的哈夫曼树进行哈弗曼编码，然后将字符与对应的0、1代码串打印到屏幕上。
函数原型： ( *)如输入的字符串是“”，则每个字母的代码和输入的字符串的哈夫曼编码是（5）译码的功能模块此模块的功能为接收需要译码的0和1代码串，按照（4）中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，并将翻译的结果在屏幕上打印出来。
函数原型： ( *)如输入的代码串是“110111100”，则对应的字符串是“”四、实验结果（程序）及分析1、实验主要模块代码(一)函数功能：统计字母种类和个数模块(){;<<"请输入字符串"<<;>>s; 为输入的字符串(s[v]){;}<<"共有字符"<<v<<"个"<<; v是全局变量[0][0][0]1;(1<) 统计s中字母种类和个数{(0<){([m][k]){[m];}}(m>n){[][k][n]1;}}(0<) 输出种类和个数<<"字符"<<[m]<<"有"<<[m]<<"个"<<;}(二)函数功能:哈弗曼树的建立模块* (){* ;1212; 1记录最小的重权值，m2为次小(0<2*1){ 结点初始化[i]1;[i]0;[i]1;[i]1;}(0<) 将每个字母的个数当做叶子结点的权值[i][i];(0<1){m12;x12=0;(0<){([j]1 [j]<m1){m21;x21;m1[j];x1; 1记录最小重权值在数组中的下标 }([j]1 [j]<m2){m2[j];x2; 2记录次小重权值在数组中的下标}}[x1];[x2];[]12;[]1;[]2;}; 返回数组首地址}(三)函数功能：打印哈弗曼树的功能模块( *){<<<<<<; 界面优化<<"哈弗曼树"<<;<<" "<<""<<" "<<"" <<" "<<""<<""<<""<<; 界面优化( 0<2*1)<<" "<<[i]<<" "<<[i]<<" "<<[i]<<" "<<[i]<<;}(四)函数功能：建立哈弗曼编码的功能模块( *){[];;(0<){ 求每个结点的哈弗曼编码1;;[c];(1){ 由叶子结点向上直到树根([p])[]=0;[]=1;;;[c];}(1<) 将结果保存[i][j][j]保存每位号码[i]; 保存开始位置}<<<<<<;<<"哈弗曼编码"<<;(0<) 打印各个字母对应的编码{<<""<<;<<[i]<<"的代码是";([i]1<)<<[i][j];<<;}<<""<<;<<<<"输入的字符串的哈夫曼编码为："<<;(0<)打印输入的字符串的编码结果( 0<)(s[i][y]){( [y]1<)<<[y][j];}<<;}(五)函数功能：译码的功能模块( *){; 记录输入的0，1代码t;<<<<<<;<<"请输入代码串:";>>;0;([]); 确定0，1代码长度 *[2*2];<<<<<<;<<"译码结果"<<;( 0<){([i]'0') 从根向下[>];[>];(>1 >1){ 如果到达叶子结点>; 保存叶子结点的权值( 0<)([j]){<<[j]; 输出权值的对应的字母;}[2*2]; 重新从根节点开始}}<<;}2、测试数据实验结果截图3、调试过程中出现的问题以及解决策略译码模块中，如果输入的代码串无对应的字母，则会出错。
解决办法：提示用户输入时注意附最终代码：<><>121223;0;0;s;{;;};[12];{;权值;;;};[];10;{[];;};(){;<<"请输入字符串"<<;>>s;<<"共有字符"<<v<<"个"<<;[0][0][0]1;(1<){(0<){([m][k]){[m];}}(m>n){[][k][n]1;}}(0<)<<"字符"<<[m]<<"有"<<[m]<<"个"<<;}* (){* ;1212;1记录最小的重权值，m2为次小(0<2*1){ 结点初始化[i]1;[i]0;[i]1;[i]1;}(0<) 将每个字母的个数当做叶子结点的权值[i][i];(0<1){m12;x12=0;(0<){([j]1 [j]<m1){m21;x21;m1[j];x1;1记录最小重权值在数组中的下标}([j]1 [j]<m2){m2[j];x2;2记录次小重权值在数组中的下标}}[x1];[x2];[]1;[]2;};返回数组首地址}( *){[];;(0<){求每个结点的哈弗曼编码1;;[c];(1){由叶子结点向上直到树根([p])[]=0;[]=1;;;[c];}(1<) 将结果保存[i][j][j]保存每位号码[i]; 保存开始位置}<<<<<<;<<"哈弗曼编码"<<;(0<) 打印各个字母对应的编码{<<""<<;<<[i]<<"的代码是";([i]1<)<<[i][j];<<;}<<""<<;<<<<"输入的字符串的哈夫曼编码为："<<;(0<)打印输入的字符串的编码结果( 0<)(s[i][y]){( [y]1<)<<[y][j];}<<;}( *){<<<<<<;<<"哈弗曼树"<<;<<" "<<""<<" "<<""<<" "<<""<<" "<<""<<;界面优化( 0<2*1)<<" "<<[i]<<" "<<[i]<<" "<<[i]<<" "<<[i]<<;}( *){; 记录输入的0，1代码t;<<<<<<;<<"请输入代码串:";>>;0;([])确定0，1代码长度*[2*2];<<<<<<;<<"译码结果"<<;( 0<){([i]'0')[>];[>];(>1 >1){如果到达叶子结点>; 保存叶子结点的权值( 0<)([j]){<<[j]输出权值的对应的字母;}[2*2]重新从根节点开始}}<<;}(){();*h;();(h);(h);(h);("");0;}。