最优二叉树(哈夫曼树)
实验4.2 最优二叉树（哈夫曼树）
一、实验的目的要求
1、了解树和哈夫曼树的特性，以及它们在实际问题中的应用。
2、掌握树和哈夫曼树的实现方法以及它们的基本操作，学会运用树和二叉树来解决问
题。
二、实验的主要内容
1、请设计一个算法，对于给定的n个结点的权值，建立一棵哈夫曼树。具体要求如下：
①算法输入：n个结点的权值。
②算法输出：哈夫曼树，打印出哈夫曼树的所有的结点序号、双亲结点、左孩子、右孩
子和权值。
③测试数据：
⑴设结点数n=7，权值分别为7、5、2、3、8、10、20；
⑵设结点数n=8，权值分别为7、19、2、6、32、3、21、10。
三、解题思路
1、哈夫曼树的存储结构：用哈夫曼算法求得的哈夫曼树中共有2n-l个结点，其中n个叶结点是初始森林中的n个孤立结点，其余n-1个结点是构造过程中生成的度为2的结点。因此，有2n-l个结点的哈天曼树可用大小为2n-l的向量来存储。每个结点包括4个域：权值域、左/右孩子域和双亲域，双亲域不但可用来存放双亲在向量中的下标，而且可区分该结点是否为根结点。因为在当前森林中合并两棵二叉树时，必须在森林的所有结点中先取两个权值最小的根结点，所以有必要为每个结点设置一个标记以区分根和非根结点。
2、解题步骤如下：
①将哈天曼树向量tree中的2n-l个结点初始化：即将各结点中的三个指针和权值均置为0。
②读入n个权值放入向量tree的前n个分量中，它们是初始森林中的n个孤立的根结点上的权值。
③对森林中的树进行n一l次合并，共产生n一l个新结点，依次放入向量tree的第t 个分量中(n+l≤t≤m)(第t个分量的下标值为t一l)。每次合并的方法如下：
⑴在当前森林的所有结点tree[j](0≤j≤i一l，i=t-l)中，选取具有最小权值和次小权值的两个根结点，分别用pl和p2记住这两个根结点在向量tree中的下标。
⑵将根为tree[pl]和tree[p2]的两棵树合并，使其成为新结点tree[i]的左右孩子，得到一棵以新结点tree[i]为根的二叉树。同时修改tree[pl]和tree[p2]的双亲域，使其指向新结点tree[i]，这意味着它们在当前森林中已不再是根，将tree[pl]和tree[p2]的权值相加后，作为新结点tree[i]的权值。
四、原程序清单
//c++程序
#include
#include
#include
using namespace std;
#define MAXVAL 10000000 //定义一个足够大的数，方便之后的操作typedef int datatype;
typedef struct //定义哈夫曼树结构体类型
{
double weight; //结点的权值
int num;
datatype lchild,rchild,parent; //结点的左、右孩子指针和父指针
} htree;
htree tree[100]; //定义全局变量，方便操作
int n,m,flag=1; //n表示预处理的结点数，m表示处理的结点总数void create() //建立哈夫曼树的函数
{
int i,j,p1,p2; //i,j用于循环语句，p1、p2用于记录操作结果
double small1,small2,w; //操作的中间变量
cout<<"\n 请输入预处理的结点数：";
cin>>n;
m=2*n-1;
if(n==0)
{
printf("\n*****************************************************\n");
printf(" 这是一棵空树\n");
printf("*****************************************************\n");
return;
}
printf("\n*****************************************************\n"); printf(" 请依次输入个结点的权值(各权值以空格隔开)\n");
printf("*****************************************************\n");
for(i=1;i<=n;i++) //为n个结点初始化
{
cin>>w;
tree[i].weight=w;
tree[i].num=i;
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
p1=0;
p2=0;
small1=MAXV AL;
small2=MAXV AL;
for(j=1;j<=i-1;j++)
if(tree[j].parent==0)
{
if(tree[j].weight { small2=small1; small1=tree[j].weight; p2=p1; p1=j; } else if(tree[j].weight { small2=tree[j].weight; p2=j; } } tree[p1].parent=i; tree[p2].parent=i; tree[i].num=i; tree[i].parent=0; tree[i].lchild=p1; tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; } printf("\n*****************************************************\n"); printf(" 哈弗曼树初始化完毕\n"); printf("*****************************************************\n"); } void print1(htree t) //用于输出哈夫曼树的先序序列 { cout<<'\t'<<'\t'< if(t.lchild!=0) print1(tree[t.lchild]); if(t.rchild!=0) print1(tree[t.rchild]); } void print2(htree t) //用于输出哈夫曼树的中序序列 { if(t.lchild!=0) print2(tree[t.lchild]); cout<<'\t'<<'\t'< if(t.rchild!=0) print2(tree[t.rchild]); } void print3(htree t) //用于输出哈夫曼树的中序序列 { if(t.lchild!=0) print3(tree[t.lchild]); if(t.rchild!=0) print3(tree[t.rchild]); cout<<'\t'<<'\t'< } int high(htree t) //计算哈夫曼树的高度 { int a,b; if(t.lchild==0&&t.rchild==0) return 1; a=high(tree[t.lchild])+1; b=high(tree[t.rchild])+1; if(a>b) return a; return b; } int main() { string i,j; while(1) { printf("\n*****************************************************\n"); printf(" 欢迎使用菜单驱动程序\n"); printf("*****************************************************\n"); if(flag==1) { printf(" 1.初始化哈弗曼树\n"); //第一级菜单 printf("\n 请选择您要的操作:"); cin>>i; if(i=="1") { create(); flag=0; } else { printf("\n*****************************************************\n"); printf(" 操作错误\n"); printf("*****************************************************\n"); } continue; } printf(" 1.重新初始化哈弗曼树\n"); //第二级菜单 printf(" 2.输出哈弗曼树的高度\n"); printf(" 3.输出哈弗曼树的叶子结点的个数\n"); printf(" 4.输出哈弗曼树\n"); printf(" 5.清屏\n"); printf(" 0.结束操作\n"); printf("\n 请选择您要的操作:"); cin>>i; if(i=="1") create(); else if(i=="2") { if(n==0) { printf("\n*****************************************************\n"); printf(" 这是一棵空树，高度为0\n"); printf("*****************************************************\n"); } else { printf("\n*****************************************************\n"); printf(" 该树的高度为%d\n",high(tree[m])); printf("*****************************************************\n"); } } else if(i=="3") { if(n==0) { printf("\n*****************************************************\n"); printf(" 这是一棵空树，叶子结点的个数为0\n"); printf("*****************************************************\n"); } else { printf("\n*****************************************************\n"); printf(" 该树的叶子结点的个数为%d\n",n); printf("*****************************************************\n"); } } else if(i=="4") { if(n==0) { printf("\n*****************************************************\n"); printf(" 这是一棵空树\n"); printf("*****************************************************\n"); continue; } while(1) { printf("\n*****************************************************\n"); printf(" 欢迎使用菜单驱动程序\n"); printf("*****************************************************\n"); printf(" 1.输出哈弗曼树的先序序列\n"); //第三级菜单 printf(" 2.输出哈弗曼树的中序序列\n"); printf(" 3.输出哈弗曼树的后序序列\n"); printf(" 4.返回上层\n"); printf(" 5.清屏\n"); printf(" 0.结束操作\n"); printf("\n 请输入您要的操作:"); fflush(stdin); cin>>j; if(j=="1") { printf("\n*****************************************************\n"); printf(" 哈弗曼树的先序序列如下(左为结点序号，右为为结点权值)\n"); printf("*****************************************************\n"); print1(tree[m]); } else if(j=="2") { printf("\n*****************************************************\n"); printf(" 哈弗曼树的中序序列如下(左为结点序号，右为为结点权值)\n"); printf("*****************************************************\n"); print2(tree[m]); } else if(j=="3") { printf("\n*****************************************************\n"); printf(" 哈弗曼树的后序序列如下(左为结点序号，右为为结点权值)\n"); printf("*****************************************************\n"); print3(tree[m]); } else if(j=="4") break; else if(j=="5") system("cls"); else if(j=="0") { printf("\n*****************************************************\n"); printf(" 谢谢使用，再见\n"); printf("*****************************************************\n"); return 1; } else { printf("\n*****************************************************\n"); printf(" 操作错误\n"); printf("*****************************************************\n"); } } } else if(i=="5") system("cls"); else if(i=="0") { printf("\n*****************************************************\n"); printf(" 谢谢使用，再见\n"); printf("*****************************************************\n"); return 1; } else { printf("\n*****************************************************\n"); printf(" 操作错误\n"); printf("*****************************************************\n"); } } } 运行结果 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.初始化哈夫曼树 请选择您要的操作:op ***************************************************** 操作错误 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.初始化哈夫曼树 请选择您要的操作:1 请输入预处理的结点数：0 ***************************************************** 这是一棵空树 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:2 ***************************************************** 这是一棵空树，高度为0 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:3 ***************************************************** 这是一棵空树，叶子结点的个数为0 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:4 ***************************************************** 这是一棵空树 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:6 ***************************************************** 操作错误 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:1 请输入预处理的结点数：5 ***************************************************** 请依次输入个结点的权值(各权值以空格隔开) ***************************************************** 1 2 3 4 5 ***************************************************** 哈夫曼树初始化完毕 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:2 ***************************************************** 该树的高度为4 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:3 ***************************************************** 该树的叶子结点的个数为5 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:4 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.输出哈夫曼树的先序序列 2.输出哈夫曼树的中序序列 3.输出哈夫曼树的后序序列 4.返回上层 5.清屏 0.结束操作 请输入您要的操作:1 ***************************************************** 哈夫曼树的先序序列如下(左为结点序号，右为为结点权值) ***************************************************** 9 15 7 6 3 3 6 3 1 1 2 2 8 9 4 4 5 5 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.输出哈夫曼树的先序序列 2.输出哈夫曼树的中序序列 3.输出哈夫曼树的后序序列 4.返回上层 5.清屏 0.结束操作 请输入您要的操作:2 ***************************************************** 哈夫曼树的中序序列如下(左为结点序号，右为为结点权值) ***************************************************** 3 3 7 6 1 1 6 3 2 2 9 15 4 4 8 9 5 5 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.输出哈夫曼树的先序序列 2.输出哈夫曼树的中序序列 3.输出哈夫曼树的后序序列 4.返回上层 5.清屏 0.结束操作 请输入您要的操作:3 ***************************************************** 哈夫曼树的后序序列如下(左为结点序号，右为为结点权值) ***************************************************** 3 3 1 1 2 2 6 3 7 6 4 4 5 5 8 9 9 15 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.输出哈夫曼树的先序序列 2.输出哈夫曼树的中序序列 3.输出哈夫曼树的后序序列 4.返回上层 5.清屏 0.结束操作 请输入您要的操作:6 ***************************************************** 操作错误 ***************************************************** ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.输出哈夫曼树的先序序列 2.输出哈夫曼树的中序序列 3.输出哈夫曼树的后序序列 4.返回上层 5.清屏 0.结束操作 请输入您要的操作:4 ***************************************************** 欢迎使用菜单驱动程序 ***************************************************** 1.重新初始化哈夫曼树 2.输出哈夫曼树的高度 3.输出哈夫曼树的叶子结点的个数 4.输出哈夫曼树 5.清屏 0.结束操作 请选择您要的操作:0 ***************************************************** 谢谢使用，再见 ***************************************************** Press any key to continue 五. 调试小结 （1）.遇到的问题及解决方法 1.输出函数中没有提示语句； 2.p1,p2赋值错误； （2）. 算法复杂度分析 本实验纯属一般操作。 （3）. 关于程序的特色及改进设想 特色和改建：1.采用了三级菜单驱动程序，使操作界面更加美观，层次更加清晰， 进一步方便了用户的使用。 2.在原有的基础上新增加了两个操作，使程序不断趋于完美。（4）. 经此实验得到的收获 进一步的加深了对菜单驱动程序在层次上的理解，将原有的两级菜单扩展为层次更加清晰的三级菜单。 课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能： （1）建立二叉排序树； （2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 排序二叉树的建立及其遍历的实现 摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据 组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言 我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归 调用，这将极大的方便算法设计。 1．需求分析 建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。 该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 数据结构实验报告实验题目: Huffman编码与解码 姓名: 学号: 院系: 实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1、输入电文串 2、统计电文串中各个字符及其出现的次数 3、构造哈弗曼树 4、进行哈弗曼编码 5、将电文翻译成比特流并打印出来 6、将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2、void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2、 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root就是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下: 实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。 五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree wyf 实现二叉排序树的各种算法 一.需求分析 (1)系统概述： 本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) 二.总体设计 (1)系统模块结构图 (2)数据结构设计 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针} BiTNode,*BiTree; typedef BiTree SElemType; typedef BiTree QElemType; typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; typedef struct { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 Status InitStack(SqStack &S) { // 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE // 请补全代码 S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) return (ERROR); S.top = S.base ; 数据结构课程设计---二叉排序树和平衡二叉树的判别 二叉排序树和平衡二叉树的判别 1引言 数据结构是软件工程的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数据模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，在进行编程调试，最后获得问题的解答。 本次课程设计的题目是对二叉排序树和平衡二叉树的扩展延伸应用。首先我们得建立一个二叉树，二叉树有顺序存储结构和链式存储结构两种存储结构，此次我选用的是二叉链表的存储结构。对于判断平衡二叉树，需要求出其每个叶子结点所在的层数，这里我采用的边遍历边求的方式，遍历采用的是先序遍历。二叉树的建立以及二叉排序树和平衡二叉树的判别中都用到了递归思想。 2需求分析 2.1在日常生活中，人们几乎每天都要进行“查找”工作。所谓“查找”即为 在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），即关键字。 2.2本程序意为对一个已经建立的动态查找表——二叉树——判断其是否是二 叉排序树和平衡二叉树。 3数据结构设计 3.1抽象数据类型二叉树的定义如下： ADT BinaryTree{ 3.1.1数据对象D：D是具有相同特性的数据元素的集合。 3.1.2数据关系R: 若D=NULL，则R=NULL，称BinaryTree为空的二叉树； 若D!=NULL,则R={H}，H是如下的二元关系: 3.1.2.1在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 3.1.2.2若D-{root}!=NULL,则存在D-{root}={Dl,Dr},且Dl与Dr相交为空； 3.1.2.3若Dl！=NULL，则Dl中存在唯一的元素xl, 二叉树的各种算法.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。 /*用函数实现如下二叉排序树算法： （1）插入新结点 （2）前序、中序、后序遍历二叉树 （3）中序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 Input 第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 第十一行~第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列 第十四行~第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列 第十七行：二叉树的深度 第十八行：叶子结点数 */ #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if(!T){p=f;return FALSE;} else if(key==T->data){p=T;return TRUE;} else if(key 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 5.1树的概念 树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4； 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林； 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。 5.树的表示 树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树 1.二叉树的基本形态： 二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——(a)； (2)只有一个根结点的二叉树——(b)； (3)右子树为空的二叉树——(c)； (4)左子树为空的二叉树——(d)； (5)完全二叉树——(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。 2.两个重要的概念： (1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图： 完全二叉树 1页 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期： 程序分析： 存储结构：二叉树 程序流程： template 2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链 表中字符的个数) 3.从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的 字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为 i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i 结点的双亲设置为空 4. 根据哈夫曼树创建编码表 学号 数据结构课程设计 设计说明书 排序二叉树的遍历 起止日期：2011 年12月12日至2011 年12月16日 学生姓名 班级 成绩 指导教师(签字) 电子与信息工程系 2011年12月16日 天津城市建设学院 课程设计任务书 2011 —2012 学年第二学期 电子与信息工程系软件工程专业班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2011 年12月12 日至2011 年12月16 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 指导教师（签字）： 教研室主任（签字）： 批准日期： 2011 年 12 月 17 日 主要内容： 一、需求分析： 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 我自己的思想：首先设想把源程序分成头文件，调用和主函数三部分。在头文件中申明类和定义结构体，把先序，中序，后序，层次和叶子节点数的函数定义在类中。然后在调用文件中，把几个函数的实现定义写在里面。最后在主函数中把输出结果以菜单的样式输出来的方式写完主函数程序。实现的过程是先想好自己要输入的是什么，然后通过输入节点制，判断其是否是满足前序遍历，满足则可以实现下后面的功能。 二、问题求解： 现实中的问题：给同学排队问题。 层次是从头开始每一层一层的排，然后分别记号码。 前序是先从最上面的那一个开始往左手边开始排，排之前先计算好人数，然后开始排，排玩左边排右边。 中序是先从最左边开始，然后左斜上角，然后右下角，再左斜上角，直到最上层为止，然后安这个顺序继续排右边的。 后序是先从最左边开始的，左边的一次排过来，然后直接排右边的，也是安依次的顺序，最后才是最上层的。 哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。 2、对hfmTree进行编码，建立hfm编码表。 3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码，结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。 抽象的数据定义如下： 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; 实验报告 课程名称：数据结构实验课程 实验四、串的基本操作练习 一、实验目的 1. 掌握二叉树的存储实现 2. 掌握二叉树的遍历思想 3. 掌握二叉树的常见算法的程序实现 二、实验环境 VC++6.0 三、实验内容 1.输入字符序列，建立二叉树的二叉链表结构。（可以采用先序序列） 2.实现二叉树的先序、中序、后序的递归遍历算法。 3.实现二叉树的先序、中序、后序的非递归遍历算法。 4.求二叉树的高度。 5.求二叉树的结点个数。 6.求二叉树的叶子结点的个数。 四、实验要求： 分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述子函数。 五、实验步骤和结果 1.打开vc，新建文本，命名二叉树算法，编写代码。 2.编写代码： #include BiTNode *base; BiTNode *top; int stacksize; } SqStack;//栈类型 void InitStack(SqStack *S)//创建二叉树 { S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } void Push(SqStack *S,BiTNode e)//进栈 { if(S->top - S->base >= S->stacksize)//如果栈空间不足 { S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(B iTNode)); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *(S->top)=e; S->top++; } BiTNode Pop(SqStack *S)//出栈 { S->top --; return *S->top; } int StackEmpty(SqStack *S)//判断栈是否非空 { if(S->top == S->base ) return 1; else return 0; } /*---------------------------------------------递归部分-------------------------------------------*/ 数据结构实验三哈夫曼树实验报告 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0. 二、概要设计： 数据结构： typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用：构造一个哈夫曼树，并循环构建 int main () 作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组HuffNode[] 中的结点*/ while (i 数据结构实验报告实验题目：Huffman编码与解码 姓名： 学号： 院系： 实验名称： Huffman编码与解码实验 问题描述： 本实验需要以菜单形式完成以下功能： 1.输入电文串 2.统计电文串中各个字符及其出现的次数 3.构造哈弗曼树 4.进行哈弗曼编码 5.将电文翻译成比特流并打印出来 6.将比特流还原成电文 数据结构的描述： 逻辑结构： 本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构： 使用结构体来对数据进行存储： typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述： 本次实验一共构造了10个函数： 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。 2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2. 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)； 此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长，返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析： 输入任意一个字符串，如输入welcometoustc:运行结果如下：二叉排序树的建立及遍历的实现
哈夫曼树编码译码实验报告(DOC)
数据结构实验报告哈夫曼树
霍夫曼树实验报告
哈夫曼树 实验报告
哈夫曼树的实验报告1
实现二叉排序树的各种算法
数据结构课程设计---二叉排序树和平衡二叉树的判别
二叉树的各种算法
哈夫曼树实验报告
各类型二叉树例题说明
哈夫曼树及其操作-数据结构实验报告(2)
哈夫曼树实验报告
数据结构 课程设计 排序二叉树
哈夫曼树实验报告(付原C语言程序)
二叉树排序算法
数据结构实验三哈夫曼树实验报告
数据结构实验报告(哈夫曼树)