数据结构中哈夫曼树的问题_百度知道
数据结构中哈夫曼树的问题
用5个权值{3,1}构造的哈夫曼树的带权路径长度是,5,4,2？
提问者采纳
而结点的带权路径长度为结点到根节点之间的路径长度与该节点上权的乘积：
/【1】 【2】树的带权路径长度为树中所有叶子结点的带权路径长度之和;
【3】【4】 【5】
&#47哈夫曼树为
提问者评价
其他类似问题
为您推荐：
哈夫曼树的相关知识
其他1条回答
WPL＝3*2+2*3+4*2+5*2+1*3＝33有什么不清楚再讨论
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁数据结构 哈夫曼树的实验报告_中华文本库
第1页/共7页
软件学院设计性实验报告
理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。
二、实验仪器或设备
学院提供公共机房，1台/学生微型计算机。
三、总体设计（设计原理、设计方案及流程等）
1． 问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。
2．一个完整的系统应具有以下功能：
1）初始化（Initialzation）。从数据文件DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.dat中的文本进行编码形成报文，将报文写在文件Code.txt中；
3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.dat中的代码进行解码形成原文，结果存入文件Textfile.txt中；
4）输出（Output）: 输出DataFile.dat中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.dat及其报文Code.txt；输出CodeFile.dat及其原文Textfile.txt；
要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.dat、ToBeTran.dat和CodeFile.dat三个文件，以保证系统的通用性。
四、实验步骤（包括主要步骤、代码分析等）
1）编写C语言程序
#include&string.h&
#include&malloc.h&
#include&stdio.h&
#include&iostream.h&
#include&math.h&
河南师范大学软件学院
第1页/共7页
寻找更多 ""数据结构课程设计 哈夫曼树_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构课程设计 哈夫曼树
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩15页未读，继续阅读
你可能喜欢数据结构哈夫曼树的应用
一、实验名称
数据结构哈夫曼树的应用
二、问题描述
&利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
三、基本要求
一个完整的系统应具有以下功能：
(1)&I：初始化（Initialization）。从终端读入字符集大小，以及个字符和个权值，建立赫夫曼树，并将它存于文件中。
(2)&E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。
(3)&D：译码（Decoding）。利用已建好的赫夫曼树将文件中的代码进行译码，结果存入文件中。
以下为选作：
(4)&P：印代码文件（）。将文件以紧凑格式显示在终端上，每行个代码。同时将此字符形式的编码文件写入文件中。
(5)&T：印赫夫曼树（&&）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件中。
四、测试要求
&&&&(1)&已知某系统在通信联络中只可能出现八种字符，其频率分别为，试设计赫夫曼编码。
(2)&用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS&PROGRAME&&IS&&MY&&FAVORITE”。
(3)&编码结果以文本方式存储在文件Codefile中。
(4)&用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
(5)&在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
五、源代码/数据测试
#include&iostream.h&
#include&stdio.h&
#include&stdlib.h&
#include&string.h&
#include&fstream.h&
typedef&struct{&&&&&&&&&//赫夫曼树的结构体
int&&&&&&&&&&&&&&&//权值
int&parent,lchild,
typedef&char&**
void&Select(hfmtree&&HT,int&a,int&*p1,int&*p2)&//Select函数，选出HT树到a为止，权值最小且parent为0的2个节点
int&i,j,x,y;
for(j=1;j&=a;++j){
if(HT[j].parent==0){
for(i=j+1;i&=a;++i){
if(HT[i].weight&HT[x].weight&&HT[i].parent==0){
x=i;&&&&&&&&&&&&&&&&&&//选出最小的节点
for(j=1;j&=a;++j)
if(HT[j].parent==0&&x!=j)
for(i=j+1;i&=a;++i)
if(HT[i].weight&HT[y].weight&&HT[i].parent==0&&x!=i)
y=i;&&&&&&&&&&&&&&&&&&//选出次小的节点
void&hfmcoding(hfmtree&&HT,hfmcode&&HC,int&n)&//构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC
int&i,start,c,f,m,w;
int&p1,p2;
char&*cd,z;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i&=n;++i)&&&&&&&&&&&&//初始化n个叶子结点
printf("请输入第%d字符信息和权值：",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
for(;i&=m;++i)&&&&&&&&//初始化其余的结点
HT[i].ch='0';
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,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].
HC=(hfmcode)malloc((n+1)*sizeof(char&*));
cd=(char&*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i&=n;++i)&&&&&&&&&&&&&&//给n个字符编码
start=n-1;
for(c=i,f=HT[i].f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0';
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
int&main(){
char&code[100],h[100],hl[100];
int&n,i,j,k,l;
ifstream&input_&&&&//文件输入输出流
ofstream&output_
char&choice,str[100];
hfmtree&HT;
hfmcode&HC;
cout&&"\n";
cout&&"&&&&&&&&&&"&&"计算机（3）班"&&"&&&&"&&"&\n";
while(choice!='Q'&&choice!='q')&&&&&&&&&&&&&&&&//当choice的值不为q且不为Q时循环
cout&&"&&&&&&&"&&"*************************赫夫曼编码/译码器*************************\n";
&&&&cout&&"&&&&&&&&&&&&"&&"I.Init"&&"&&&&&&&&"&&"E.Encoding"&&"&&&&&&&&"&&"D.Decoding"&&"&&&&&&&&"&&"Q.Exit\n";
&&&&cout&&"请输入您要操作的步骤：";
&&&&if(choice=='I'||choice=='i')&&&&&&&&&&&&&&//初始化赫夫曼树
cout&&"请输入字符个数：";
hfmcoding(HT,HC,n);
for(i=1;i&=n;++i)
cout&&HT[i].ch&&":"&&HC[i]&&
output_file.open("hfmTree.txt");
if(!output_file){
cout&&"can't&oen&file!"&&
for(i=1;i&=n;i++)
output_file&&"("&&HT[i].ch&&HC[i]&&")";
output_file.close();
cout&&"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"&&
&&&&else&if(choice=='E'||choice=='e')&&&&&&&&&&&//进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中
printf("请输入字符：");
gets(str);
output_file.open("ToBeTran.txt");
if(!output_file)
cout&&"can't&open&file!"&&
output_file&&str&&
output_file.close();
output_file.open("CodeFile.txt");
if(!output_file){
cout&&"can't&oen&file!"&&
for(i=0;&i&strlen(str)&;&i++){
for(j=0;j&=n;++j)
if(HT[j].ch==str[i])
output_file&&HC[j];
output_file.close();
cout&&"\n";
cout&&"编码完毕，并且已经存入CodeFile.txt文件！\n";
input_file.open("CodeFile.txt");&&&&&&&&&//从CodeFile.txt中读入编码，输出在终端
if(!input_file)
cout&&"can't&oen&file!"&&
input_file&&
cout&&"编码码值为："&&code&&
input_file.close();
&&&&else&if(choice=='D'||choice=='d')&&&&&//读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中
input_file.open("CodeFile.txt");
if(!input_file){
cout&&"can't&oen&file!"&&
input_file&&h;
input_file.close();
output_file.open("Textfile.txt");
if(!output_file)
cout&&"can't&oen&file!"&&
while(h[k]!='\0')&&&&&&&&&&&//先用编码中的前几个和字符的编码相比较，然后往后移
for(i=1;i&=n;i++){
for(j=0;&j&strlen(HC[i])&;&j++,l++){
hl[j]=h[l];
hl[j]='\0';
if(strcmp(HC[i],hl)==0)
output_file&&HT[i].
k=k+strlen(HC[i]);
output_file.close();
input_file.open("Textfile.txt");
if(!input_file){
cout&&"can't&oen&file!"&&
input_file&&h;&
input_file.close();
cout&&"译码结束，字符已经存入Textfile.txt文件中！"&&
&&&&else&if(choice=='Q'||choice=='q')&&&&&&&&&&&&//退出程序
&&&&else&&&&&&&&&&&&&&&//如果选了选项之外的就让用户重新选择
cout&&"您没有输入正确的步骤，请重新输入！"&&
六、测试情况
数据存储情况
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。一、哈夫曼树的概念和定义
什么是哈夫曼树？
让我们先举一个例子。
&&&&&&&&在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：
若考虑上述程序所耗费的时间，就会发现该程序的缺陷。在实际中，学生成绩在五个等级上的分布是不均匀的。当学生百分制成绩的录入量很大时，上述判定过程需要反复调用，此时程序的执行效率将成为一个严重问题。
但在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：&
下面我们就利用哈夫曼树寻找一棵最佳判定树，即总的比较次数最少的判定树。
第一种构造方式：
第二种构造方式：
这两种方式，显然后者的判定过程的效率要比前者高。在也没有别地判定过程比第二种方式的效率更高。
我们称判定过程最优的二叉树为哈夫曼树，又称最优二叉树
===================================================================================================
&定义哈夫曼树之前先说明几个与哈夫曼树有关的概念：
路径： 树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&之积称为该结点的带权路径长度（weighted path length）
& 什么是权值?( From 百度百科&)
&&& 　计算机领域中（）
　　权值就是定义的路径上面的值。可以这样理解为节点间的距离。通常指字符对应的二进制编码出现的概率。
　　至于树中的权值可以理解为：权值大表明出现概率大！
　　一个结点的权值实际上就是这个结点子树在整个树中所占的比例.
　　abcd四个的权值为7,5,2,4. 这个7,5,2,4是根据实际情况得到的,比如说从一段文本中统计出abcd四个字母出现的次数分别为7,5,2,4. 说a结点的权值为7,意思是说a结点在系统中占有7这个份量.实际上也可以化为百分比来表示,但反而麻烦,实际上是一样的.
树的带权路径长度：如果树中每个叶子上都带有一个权值，则把树中所有叶子的带权路径长度之和称为树的带
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 权路径长度。
&&&&&&&&&&&&&设某二叉树有n个带权值的叶子结点，则该二叉树的带权路径长度记为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
公式中，Wk为第k个叶子结点的权值；Lk为该结点的路径长度。
======================================================================================================
一般来说，用n（n&0）个带权值的叶子来构造二叉树，限定二叉树中除了这n个叶子外只能出现度为2的结点。
那么符合这样条件的二叉树往往可构造出许多颗，
其中带权路径长度最小的二叉树就称为哈夫曼树或最优二叉树
===============================================================================
&&二、哈夫曼树的构造
根据哈弗曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点
越远离根结点。
哈弗曼依据这一特点提出了一种构造最优二叉树的方法，其基本思想如下：
下面演示了用Huffman算法构造一棵Huffman树的过程：
三、哈夫曼树的在编码中的应用
在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
1. 等长编码
&&&&&&&&&&& 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
2. 不等长编码
&&&&&&&&&&& 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀，这宗编码称为前缀编码（prefix& code）
（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码
假设一个文本文件TFile中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}
利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码
具体做法：
1. 将TFile中7个字符都作为叶子结点，每个字符出现次数作为该叶子结点的权值
2. 规定哈夫曼树中所有左分支表示字符0，所有右分支表示字符1,将依次从根结点到每个叶子结点所经过的分支的二进制位的序列作为该
& && 结点对应的字符编码
3. 由于从根结点到任何一个叶子结点都不可能经过其他叶子，这种编码一定是前缀编码，哈夫曼树的带权路径长度正好是文件TFile编码
&&&&的总长度
通过哈夫曼树来构造的编码称为哈弗曼编码（huffman code）
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：40143次
积分：1610
积分：1610
排名：第17534名
原创：118篇
转载：17篇
(1)(10)(30)(32)(16)(9)(4)(14)(22)}