构造哈夫曼树及哈夫曼编码

《数据结构》实验报告

实验名称：构造哈夫曼树及哈夫曼编码专业：计算机科学与技术专业

班级：计算机科学与技术

姓名：

学号：

完成日期：2012/11/22

2012年11月22 日

一、问题描述

构造一个哈夫曼树，并根据所构造的哈夫曼树求其哈夫曼树的编码；

二、需求分析

哈夫曼树有叫做最优二叉树，它是指对于一组带有确定的权值的叶节点，构造具有最小的带权路径程度的二叉树。

在数据通信中，经常需要将传送的文字转换成由二进制字符0,1组成的二进制串，称之为编码。如果在所有的编码中每个字符的编码都一样的长短则有的字符在应用中出现的次数多有的字符在应用中出现的次数少，这样的话有的电文的编码会很长，所以就想用不同长度的编码区代表字符，及在电文中出现的概率大的用短的字符表示，而出现的概率小的用长的字符表示，则得到的电文可能就比较短。

基于以上的需求与要求，就出现了哈夫曼编码。

三、概要设计

1、先建立哈夫曼树的结构，即哈夫曼树的构造算法；

2、再建立哈夫曼树编码的结构，即哈夫曼树编码的算法；

3、再带入数据进行验证。

四、详细设计

1.、哈夫曼树构造算法的编码：

#include

using namespace std;

#define MAXV ALUE 100

#define MAXLEAF 30

#define MAXNODE MAXLEAF*2-1

#define MAXBIT 10

typedef struct

{

int weifht; //权值

int parent; //双亲节点

int lchild; //左孩子

int rchild; // 右孩子

}HNodeType;

typedef struct

{

int bit[MAXBIT];

int start;

}HCodeType;

void HuffmanTree(HNodeType HuffNode[],int n)

{

int i,j,m1,m2,x1,x2;

for(i = 0;i < 2*n-1;i++) //对数组进行初始化

{

HuffNode[i].weifht = 0;

HuffNode[i].parent = -1;

HuffNode[i].lchild = -1;

HuffNode[i].rchild = -1;

}

for(i = 0;i < n;i++) //输入各个节点的权值

{

cout<<"输入第"<

cin>>HuffNode[i].weifht;

}

for(i = 0;i < n-1;i++) //构造哈夫曼树

{

m1 = MAXV ALUE;

m2 = MAXV ALUE;

x1 = x2 = 0;

for(j = 0;j < n + i;j++) //找出两棵权值最小的树

{

if(HuffNode[j].weifht < m1&&HuffNode[j].parent == -1)

{

m2 = m1;

x2 = x1;

m1 = HuffNode[j].weifht;

x1 = j;

}

else if(HuffNode[j].weifht < m2&&HuffNode[j].parent == -1)

{

m2 = HuffNode[j].weifht;

x2 = j;

}

}

HuffNode[x1].parent = n + i; //合并两个子树

HuffNode[x2].parent = n + i;

HuffNode[n+i].weifht = HuffNode[x1].weifht + HuffNode[x2].weifht;

HuffNode[n+i].lchild = x1;

HuffNode[n+i].rchild = x2;

}

}

void HaffmanCode() //哈夫曼编码

{

HNodeType HuffNode[MAXNODE];

HCodeType HuffCode[MAXLEAF],cd;

int i,j,c,p,n;

cout<<"输入节点的个数："<>n;

HuffmanTree(HuffNode,n);

for(i = 0;i < n;i++)

{

cd.start = n - 1;

c = i;

p = HuffNode[c].parent;

while(p != -1)

{

if(HuffNode[p].lchild == c)

cd.bit[cd.start] = 0;

else

cd.bit[cd.start] = 1;

cd.start--;

c = p;

p = HuffNode[c].parent;

}

for(j = cd.start+1;j < n;j++)

HuffCode[i].bit[j] = cd.bit[j];

HuffCode[i].start = cd.start;

}

cout<<"哈夫曼编码为："<

for(i = 0;i < n;i++)

{

for(j = HuffCode[i].start + 1;j < n;j++)

cout<

cout<

}

}

int main(void)

{

HaffmanCode();

return 0;

}

五、测试分析

结果：

输入节点的个数：

5

输入第0个叶节点的权值：

1

输入第1个叶节点的权值：

2

输入第2个叶节点的权值：

3

输入第3个叶节点的权值：

4

输入第4个叶节点的权值：

5

哈夫曼编码为：

010

011

00

10

11

Press any key to continue

六、总结

在本次编写程序的时候开始把哈夫曼树的判断的时候叶节点将（p！= -1）写成了（p!= 1）结果导致不能读出哈夫曼树的编码。

贪心算法构造哈夫曼树

软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include #include #include #include typedef struct Node{ //定义树结构 int data; struct Node *leftchild; struct Node *rightchild; }Tree; typedef struct Data{ //定义字符及其对应的频率的结构 int data;//字符对应的频率是随机产生的 char c; }; void Initiate(Tree **root);//初始化节点函数 int getMin(struct Data a[],int n);//得到a中数值（频率）最小的数 void toLength(char s[],int k);//设置有k个空格的串s void set(struct Data a[],struct Data b[]);//初始化a,且将a备份至b char getC(int x,struct Data a[]);//得到a中频率为x对应的字符 void prin(struct Data a[]);//输出初始化后的字符及对应的频率 int n; void main() { //srand((unsigned)time(NULL));

数据结构哈夫曼树的实现

#include #include #include #include using namespace std; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 int m,s1,s2; HuffmanTree HT; void Select(int n){ //选择两个权值最小的结点 int i,j; for(i=1;i<=n;i++){ if(!HT[i].parent){ s1 = i;break; } } for(j=i+1;j<=n;j++){ if(!HT[j].parent){ s2 = j;break; } } for(i=1;i<=n;i++){ if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){ s1=i; } } for(j=1;j<=n;j++){ if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)) s2=j; } } void HuffmanCoding(HuffmanCode HC[], int *w, int n) { // w存放n个字符的权值(均>0)，构造哈夫曼树HT，// 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; int start; if (n<=1) return;

哈夫曼树编码译码实验报告(DOC)

数据结构课程设计设计题目：哈夫曼树编码译码

目录 第一章需求分析 (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) 编码文件的译码。

哈夫曼树及其应用(完美版)

数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 131 学号：1308060312 学生姓名：谢进 指导教师：叶洁 2015年7 月12 日

设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 1、熟悉树的二叉树的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100），对这六种字符进行哈夫曼编码。 设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。

哈夫曼树的建立与操作

实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include using namespace std; typedef char Elemtype; struct element { int weight; Elemtype date; element* lchild,*rchild; }; class HuffmanTree { public: HuffmanTree()//构造函数 { cout<<"请输入二叉树的个数"<>count; element *s=new element[count];//s为指向数组的指针，保存指向数组的地址 for(int i=0;i>s[i].weight;

cout<<"输入第"<>s[i].date; s[i].lchild=NULL; s[i].rchild=NULL; }//以上为初始化每一个结点 element * *m=new element*[count];//m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址 for(int i=0;iweightweight; return1=i; } } for(int i=0;iweightweight>a) { b=m[i]->weight; return2=i; } } q=new element;//构建一棵新树 q->weight=m[return1]->weight+m[return2]->weight; q->lchild=m[return1]; q->rchild=m[return2]; m[return1]=q; m[return2]=NULL; //用新树替换原来的两子树,并置空一个数 } boot=q;//把最后取得的哈夫曼树的头结点即q赋值给boot

数据结构哈夫曼树和代码

#include #include #include #define N 50 //叶?子哩?结á点?数簓 #define M 2*N-1 //树骸?中D结á点?总哩?数簓 typedef struct { char data; //结á点?值μ int weight; //权ü?重? int parent; //双?亲×结á点? int lchild; //左哩?孩￠子哩?结á点? int rchild; //右 ?孩￠子哩?结á点? } HTNode; typedef struct { char cd[N]; //存?放?哈t夫え?曼?码? int start; } HCode; HTNode ht[M]; HCode hcd[N]; int n; void CreateHT(HTNode ht[],int n) { int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++) //所ù有瓺结á点?的?相à关?域 ?置?初?值μ0 ht[i].parent=ht[i].lchild=ht[i].rchild=0; printf("哈t夫え?曼?树骸?初?态?为a:\n"); printf("data weight parent lchild rchild\n"); for (i=0;i<2*n-1;i++) { printf("%-6c %-6d %-6d %-6d %-6d\n",ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild, ht[i].rchild); } for (i=n;i<2*n-1;i++) //构1造ì哈t夫え?曼?树骸? {

完整word版数据结构课程设计：电文编码译码哈夫曼编码

福建农林大学计算机与信息学院 数据结构课程设计 设计：哈夫曼编译码器 姓名：韦邦权 专业：2013级计算机科学与技术 学号：13224624 班级：13052316 完成日期：2013.12.28

1 哈夫曼编译码器 一、需求分析 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和

各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 二、设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的2 代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 三、概要设计 哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。 在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的

数据结构课程设计哈夫曼编码

题目：哈夫曼编码器 班级：031021班姓名：李鑫学号：03102067 完成日期：2011/12 1. 问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 2.基本要求 一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 以下为选做： (4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。 3.测试 (1)利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FA VORITE”。 字符 A B C D E F G H I J K L M 频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z 频度57 63 15 1 48 51 80 23 8 18 1 16 1 4.实现提示 (1) 编码结果以文本方式存储在文件Codefile中。 (2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 (3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

哈夫曼树解压与压缩

哈夫曼树的压缩与解压 1.算法简要描述 1.哈夫曼算法 1.哈弗曼算法是根据给定的n个权值{w1，w2，w3.......wn}，构造由n棵 二叉树构成的深林F={T1,T2,。。。。Tn}，其中每个二叉树Ti分别都是只 含有一个权值wi的根结点，其左右子树为空（i=1，，，，，,2）。 2.在深林F中选取其根结点的权值最小的两棵二叉树，分别作其左右子树 构造一颗新的二叉树，并置这棵新的二叉树根结点的权值为其左右子树 的根结点之和。 3.从F中删去这两棵二叉树，同时刚新生成的二叉树加入到深林F中。 4.重复2,3,步骤，直至深林F中只含有一颗二叉树为止。 2.哈夫曼树的实现 函数String EnCode(Char Type ch)：表示哈夫曼树已存在，返回字符ch的编码。 函数LinkListUnCode(String strCode)：表示对哈夫曼树进行译码，返回编码前的字符序列。根据算法可以看出，在具有n个结点权值的哈夫曼树的构造过程中，每次都是从F中删去两棵树，增加一棵树，即每次结束后减少一棵树，经过n-1次处理后，F中就只剩下一棵树了。另外，每次合并都要产生一个新的结点，合并n-1次后共产生了n-1个新结点，并且这n-1个新节点都是具有左右子树的分支结点。则最终得到的哈夫曼树中共有2n-1个结点，并且其中没有度为1的分支结点，最后一次产生的新结点就是哈夫曼树的根结点。

源代码中创建了一个哈夫曼树结点类，其中有数据成员weight，parent，leftChild，rightChild分别代表了权值，双亲，左孩子，右孩子。 在哈夫曼树类中有数据成员*nodes，*LeafChars，*LeafCharCodes，curPos，num，分别用来存储结点信息，叶结点字符信息，叶结点字符编码信息，译码时从根结点到叶结点路径的当前结点，叶结点个数。哈夫曼树类中含有多个函数，有构造函数，析构函数等。由函数HuffmanTree(CharType ch[],WeightType w[],int n)来构造由字符，权值，和字符个数构造哈夫曼树，在根据哈夫曼算法很容易实现哈夫曼类的函数以及构造函数。在在算法中，求叶结点字符的编码时，需要从叶结点出发走一条从高叶结点到根结点的路径，而编码却是从根结点出发到叶结点的路径，由左分支为编码0，右分支为编码1，得到的编码，因此从叶结点出发到根结点的路径得到的编码是实际编码的逆序，并且编码长度不确定，又由于可以再线性链表中构造串，因此将编码的信息储存在一个线性立案标准，每得到一位编码都将其插入在线性链表的最前面。 在求某个字符的编码是由函数EnCode(CharType ch)来求，返回字符编码。在进行译码时，用一个线性链表存储字符序列，由函数Decode(String strCode)来求，对编码串strCode进行译码，返回编码前的字符序列。函数Compress()用哈夫曼编码压缩文件。函数Decompress()解压缩用哈夫曼编码压缩的文件。 在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。

哈夫曼树及其操作-数据结构实验报告(2)

电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 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是最小的。

贪心法构造哈夫曼树

实验报告 （ 2013 / 2014 学年第二学期） 学院贝尔学院 学生姓名任晓强 班级学号 Q12010218 指导教师季一木 指导单位计算机软件教学中心 日期 2014年3月12日

实验一：贪心算法构造哈夫曼树 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......w }是一组权值，以每个权值作为根结点值，构造n棵只有根的 n-1 二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为止 一、实验目的 （1）了解贪心算法和哈夫曼树的定义 （2）掌握贪心法的设计思想并能熟练运用 （3）设计贪心算法求解哈夫曼树 （4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树 （2）设计函数，先序遍历输出哈夫曼树各结点 (3)设计函数，按树形输出哈夫曼树 三、程序源代码 #include #include #include #include typedef struct Node{ //定义树结构 int data; struct Node *leftchild; struct Node *rightchild;

}Tree; typedef struct Data{ //定义字符及其对应的频率的结构int data;//字符对应的频率是随机产生的 char c; }; void Initiate(Tree **root);//初始化节点函数 int getMin(struct Data a[],int n);//得到a中数值（频率）最小的数void toLength(char s[],int k);//设置有k个空格的串s void set(struct Data a[],struct Data b[]);//初始化a,且将a备份至b char getC(int x,struct Data a[]);//得到a中频率为x对应的字符void prin(struct Data a[]);//输出初始化后的字符及对应的频率 int n; void main() { //srand((unsigned)time(NULL)); Tree *root=NULL,*left=NULL,*right=NULL,*p=NULL; int min,num; int k=30,j,m; struct Data a[100]; struct Data b[100]; int i;

数据结构哈夫曼编码实验报告

数据结构实验报告 ――实验五简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结 构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat 中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat中读入），对文件中的正 文进行编码，然后将结果存入文件code.dat中。 3、译码。利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根 据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode 的大小设置为2n-1，描述结点的数据类型为： typedef struct { int weight;//结点权值 int pare nt; int lchild; int rchild; char inf; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链 域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #defi ne MAXBIT 10 typedef struct

2020年最新数据结构哈夫曼编码实验报告

数据结构实验报告 ――实验五简单哈夫曼编 / 译码的设计与实现 本实验的目的是通过对简单哈夫曼编 / 译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编 / 码系统。系统应该具有如下的几个功能 1、接收原始数据。 从终端读入字符集大小 n ，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 nodedata.dat 中。 2 、编码。 利用已建好的哈夫曼树（如不在内存，则从文件 nodedata.dat 中读入），对文件中的正文进行编码，然后将结果存入文件 code.dat 中。 3 、译码。利用已建好的哈夫曼树将文件code.dat 中的代码进行译码，结果存入文件 textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode 的大小设置为 2n-1 ，描述结点的数据类型为 typedef struct {

int weight;// 结点权值 int parent; int lchild; int rchild; char inf; }HNodeType; 2 、求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的、 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型 #define MAXBIT 1 typedef struct HaffNode[i].parent=-1; HaffNode[i].parent=-1; HaffNode[i].parent=-1; HaffNode[i].parent=-1; { { int bit[MAXBIT]； int start； }HcodeType； 3 、文件 nodedata.dat 、code.dat 和 textfile.dat 。

数据结构课程设计哈夫曼编码

概要设计 1)问题分析哈夫曼树的定义 1.哈夫曼树节点的数据类型定义为： typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }htnode,*hfmtree; 2）所实现的功能函数如下 1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。 2、void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点 2、int main() 主函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入） 对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。 3、Encoding 编码功能：对输入字符进行编码 4、Decoding 译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。 Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。 5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。 使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。 2)系统结构图（功能模块图） 五．程序说明

c++数据结构实验哈夫曼树

c++数据结构实验哈夫曼树

数据结构实验报告 1．实验要求 i.实验目的: （1）掌握二叉树基本操作的实现方法 （2）掌握二叉树基本操作的实现方法 （3）了解哈夫曼树的思想和相关概念 （4）学习使用二叉树解决实际问题的能力 （5）熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方法。 （6）熟悉设计算法的过程 （7）进一步掌握指针、异常处理的使用 ii.实验内容： 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度 的字符串s进行统计，统计每个字符的频 度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经 建好的赫夫曼树进行编码，并将每个字符

的编码输出。 3、编码(Encoding)：根据编码表对输入 的字符串进行编码，并将编码后的字符串 输出。 4、译码(Decoding)：利用已经建好的赫 夫曼树对编码后的字符串进行译码，并输 出译码结果。 5、打印(Print)：以直观的方式打印赫夫 曼树（选作） 6、计算输入的字符串编码前和编码后的 长度，并进行分析，讨论赫夫曼编码的压 缩效果。 测试数据： I love data Structure, I love Computer.I will try my best to study data structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现 的次数统计频度，对没有出现的

字符一律不用编码。 iii.代码要求： 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析 树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是每个结点最多两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。 2.1 存储结构 1.结点结构的存储方式：

数据结构 实验三 题目二：哈夫曼树

2008级数据结构实验报告 实验名称：实验三树 学生姓名： 班级： 班内序号： 学号： 日期：20013年11月26日 1．实验要求 实验目的 通过选择下面两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 实验内容 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1.初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建 立赫夫曼树 2.建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输 出。 3.编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结 果。 5.打印(Print)：以直观的方式打印赫夫曼树（选作） 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 2. 程序分析 哈夫曼树结点的储存结构除了二叉树所有的双亲域parents，左子树域lchild，右子树域rchild。还需要有字符域word，权重域weight，编码域code。其中由于编码是一串由0和1组成的字符串，所以code是一个字符数组。 进行哈夫曼编码首先要对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。统计每个字符出现的次数（频度）作为叶子的权重，统计次数可以根据每个字符不同的ASCII 码。并根据叶子结点的权重建立一个哈夫曼树。 建立每个叶子的编码从根结点开始，规定通往左子树路径记为0，通往右子树路径记为 1.由于编码要求从根结点开始，所以需要前序遍历哈夫曼树，故编码过程是以前序遍历二叉树

数据结构实验三哈夫曼树实验报告

题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为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

HuffNode[i].rchild =-1; scanf("%c",&x); scanf("%c",&HuffNode[i].value); //实际值，可根据情况替换为字母 i++; } /* 输入 n 个叶子结点的权值 */ scanf("%c",&x); for(i=0;i

哈夫曼树 实验报告

计算机科学与技术学院数据结构实验报告 班级 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作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10