实验六哈夫曼树的建立与操作
一、实验要求和实验内容
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<<"请输入二叉树的个数"< cin>>count; element *s=new element[count];//s为指向数组的指针，保存指向数组的地址 for(int i=0;i { cout<<"输入第"< cin>>s[i].weight; cout<<"输入第"< cin>>s[i].date; s[i].lchild=NULL; s[i].rchild=NULL; }//以上为初始化每一个结点 element * *m=new element*[count];//m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址 for(int i=0;i { m[i]=s+i;//把数组成员i地址赋给m[i]（m[i]大致意思等效于*m）} //以下为哈夫曼的构造过程 element*q; for(int i=0;i { int a=32767,b=32767;//a,b为两个存当前最小值的两个临时变量，初始化为32767（int型能达到的最大的值） for(int i=1;i { if(m[i]!=NULL) if(m[i]->weight { a=m[i]->weight; return1=i; } } for(int i=0;i { if(m[i]!=NULL) if(m[i]->weight { 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 cout<<"哈夫曼树构造成功"< } void HufumanCoding(element* bt,int len=0)//求哈夫曼编码,len为哈夫曼编码的位数默认为0 { if(bt)//当bt不为空时进入 { if(!bt->lchild&&!bt->rchild)//当此结点为叶子结点时进入 { cout<<"权值为"< for(int i=0;i cout< cout< } else { m[len]=0; HufumanCoding(bt->lchild,len+1); m[len]=1; HufumanCoding(bt->rchild,len+1); } } } element* ReturnBoot() { return boot; } private: int count;//结点数 int return1,return2;//权值最小的节点的在数组中的位置 element* boot; int m[20];//存储哈夫曼编码 }; int main() { element* m; HuffmanTree a; m=a.ReturnBoot(); a.HufumanCoding(m); } 三、运行结果 计算机科学与技术学院数据结构实验报告 班级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序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： 数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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.求每个字符的哈夫曼编码并显示。 授课时间11.9 第17 次课 2007-07-18 哈夫曼树（Huffman树）是带权路径长度最小的二叉树。根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其基本思想是： ⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1， T2，…，Tn}； ⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点权值之和； ⑶删除与加入：在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； ⑷重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。 通过上述Huffman树的构造过程，我们可以得到如下要点： ⑴当有n个权值（相应的Huffman树中有n个叶子），共需合并n-1次； ⑵每合并一次产生一个分支结点，经过n-1次合并后得到的Huffman树中共有2n-1个结点，其中有n-1个分支结点； ⑶在Huffman树中只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点； ⑷算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的； ⑸对同一组权值可以构造出不同的huffman树，但是他们的带权路径长度相同。 在建立Huffman树的过程中有以下三种常见的错误： ⑴在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并的），而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并，如图5-10所示。 ⑵每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树，如图5-11所示。 ⑶有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。 一、需求分析 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 实验二二叉树的遍历及霍夫曼编码 班级：计科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 目录 一、程序设计目的与要求 (3) 1.1程序设计目的 (3) 1.2程序设计要求 (3) 二、需求分析 (4) 三、概要设计 (4) 3.1哈夫曼树的构造过程 (4) 3.2译码过程是编码过程的逆过程 (5) 3.3 构造哈夫曼树和哈夫曼编码类的描述 (5) 四、详细设计 (6) 五、调试分析 (11) 5.1程序编译界面 (11) 5.2程序运行界面 (12) 六、测试结果 (13) 七、附录 (15) 7.1设计心得 (15) 7.2参考文献 (15) 一、程序设计的目的与要求 1.1程序设计目的 课程设计是《数据结构》课程教学必不可缺的一个重要环节，通过课程设计，使学生对整个课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习，毕业设计环节以及将来的实际工作打好坚实的基础。本课程设计的目是： 1.培养学生将所学的算法知识应用于程序设计过程中，设计出运行效率更高的 程序； 2.了解数据的三种逻辑结构（线性结构、树结构、图结构）和四种存储结构（顺 序、链接、索引、散列）的基本特性和相互关系； 3.掌握算法知识，学会设计算法并对算法进行分析和评价。 1.2程序设计要求 在设计时严格按照题意独立进行设计，不得随意更改。要求熟悉C、C++等某一种高级程序设计语言。通过本课程的学习与实践，学生应做到： 1.掌握数据结构的基本概念和基本理论。 2.熟练掌握顺序表、链表、队列、栈、树以及二叉树、图等基本数据结构的设 计和分析。 3.熟练地掌握常用算法（递归、遍历、查找、排序）的知识。 4.能对所求解的问题进行分析，抽象出逻辑结构，选择合适的存储结构，定义 所需的运算，设计相应的算法。 5.对算法进行分析和评价。 数据结构实验报告 实验名称：实验三树 学生姓名： 班级： 班内序号： 学号： 日期：2012年12月7号 1、实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频 度，并建立赫夫曼树 2、建立编码表(CreateT able)：利用已经建好的赫夫曼树进行编码，并将每个字符 的编码输出。 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、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 2、程序分析 2.1存储结构 （1）二叉树 template 哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout< 常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫 ******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2007年春季学期 算法与数据结构课程设计 题目：赫夫曼编译码器设计 专业班级：软件工程05－1班 姓名：张龙 学号：05350507 指导教师：王燕 成绩： 目录 摘要 (1) 前言 (2) 正文 (3) 1.采用类C语言定义相关的数据类型 (3) 2.各模块的伪码算法 (7) 3.函数的调用关系图 (13) 4.调试分析 (13) 5.测试结果 (14) 6.源程序（带注释） (14) 总结 (20) 参考文献 (20) 附件Ⅰ部分源程序代码 (21) 摘要 哈夫曼编译码器主要用于通信领域，能够实现数据的快速，有效的传输。它利用哈夫曼树对数据进行编码，形成前缀编码，实现数据的有效压缩存放。然后又通过某种遍历实现译码，从而达到快速远距离通信的目的。 关键词：哈夫曼树；前缀编码；译码 前言 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。通过该题目的设计过程，可以加深理解树及二叉树的逻辑结构、存储结构，掌握树及二叉树上基本运算的实现。进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。 正文 1.采用类c语言定义相关的数据类型 （1）结构体定义 typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存贮哈夫曼树。 typedef struct { char ch; char *chs; }HuffmanCode; typedef struct { char ch; int weight; }sw; typedef struct { HuffmanTree HT; HuffmanCode *HC; }huf;//哈夫曼树结构体。 从HT[i-1]选择parent为零且weight最小的两个节点，分别编号为n1,n2. （2）调用函数 1）在给定权值中选择权值最小的两个节点。 void select(HTNode * HT,int n,int *n1,int *n2) { int i=1; int n3; while(HT[i].parent!=0) i++; 实验报告 欧阳光明（2021.03.07） 实验名称 Huffman 编码 专业班级 计科三班 姓名 学号 指导教师 日期 .12.20 一、实验目的 熟练掌握二叉树应用（Huffman 编码）的基本算法实现。 二、实验内容 ● 1．对输入的一串电文字符实现Huffman 编码，再对Huffman 编码生成的代码串进行译码， 输出电文字符串。实现功能如下： ? Huffman 树的建立 ? Huffman 编码的生成 编码文件的译码 三、实验要求 设计思路： 数据结构： #define n 100 //叶子结点数 #define m 2*n1 //Huffman 树中结点总数 typedef struct { int weight; //权值 int lchild , rchild , parent; //左右孩子及双亲指针 }HTNode; //树中结点类型 typedef HTNode HuffmanTree[m+1]; //0号单元不用 主要实现函数： ? 统计字符串中字符的种类以及各类字符的个数的函数 ? 构造Huffman 树的函数 ? Huffman 编码的函数 ? 建立正文的编码文件的函数 ? 代码文件的译码函数 ? 主函数 四、实验概要设计 1)功能框图 五. 使用说明 1.运行环境：VC++ 6.0 2.首先选择主控菜单中的操作１，即建表，然后进行其它操作． 六．实验截图 Huffman 编码程序 Huffman 树的建立 从叶子到根逆向求编码Huffman 编码的生成 编码文件的译码 退出 七实验体会 1、构建哈夫曼树的关键在于找最小树；在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 2、由于学习的不足没有实现编码文件的译码，今后会加以改进 (╯﹏╰） 3、在逆向求编码的for循环里犯了一个逻辑错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。 附源程序： #include 哈夫曼树实验报告 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作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 专业基础实践报告 题目哈夫曼树及应用 起讫日期2008年6月30日至2008年7月11日所在院系软件学院 学生姓名专业计算机 班级学号 指导教师职称 所在单位软件学院 2008年7 月11 日 目录 一、任务及要求 (1) 二、总体设计 (3) 三、运行效果 (16) 四、总结 (22) 五、附录 (23) 参考文献 1.唐策善?《数据结构---用C语言描述》?高等教育出版社?1995 ?p50~p120 2.谭浩强?《C程序设计》?清华大学出版社? 2005 ? p330！p348 一、任务及要求 在本专业基础实践中，综合C语言程序设计、离散数学、数据结构等学过的 专业基础课程中的基本概念、基础知识和基本理论，进行软件设计的思想、方法 和过程的训练，提高综合素质和动手能力，达到加强专业基础知识理解程度和熟 练程度的目的。具体任务及要求如下： 1、任务 （1）给定一个包含10个以上字符的字符串，长度不少于100个字符，统计各个字符的概率，存放在数组中。 （2）根据上面统计的结果建立哈夫曼树。 （3）实现哈夫曼编码。 （4）实现哈夫曼译码。 （5）自己选做1～2个附加的任务。 2、要求 （1）算法中处理的数据要存放在文件中，实现文件的读写操作。 （2）设计程序中的各个C函数、画出模块图。 （3）程序的代码要规范、有详细的注释。 （4）按照指导教师给出的模板进行专业基础实践报告书写。 二、工作量 在2周（10个工作日）时间里，完成15-20个C函数，150-200行代码。并提交专业实践报告一份，字数不少于5000字（包括英文字符）。 三、计划安排 第1个工作日－第2个工作日：查找相关资料、书籍；确定逻辑结构并进行运算的 定义；选择存储结构并进行算法设计。 第3个工作日－第7个工作日：完成程序的编码，并且自己调试、测试。穿插进行 实践报告的撰写。 第8个工作日－第9个工作日：整理并完成专业基础实践报告，提交指导教师。第10个工作日：由教师检查软件测试效果、审阅实践报告，评定成绩。 指导教师签字： 2008年6月26日 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 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是最小的。 哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 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; 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日 课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将 数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期： 程序分析： 存储结构：二叉树 程序流程： 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. 根据哈夫曼树创建编码表 哈夫曼树的建立数据结构课程设计文档 班级： 小组组长: 成员： 指导老师： 第一章前言 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 通过此次课程设计主要达到以下目的： 一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。哈夫曼树 实验报告
哈夫曼树及其应用(完美版)
哈夫曼树及其应用教案
哈夫曼树的实验报告1
霍夫曼树实验报告
哈夫曼树
实验三哈夫曼树实验报告
构建哈夫曼树及输出哈夫曼代码及算法思想
哈夫曼树及应用
哈夫曼树
2021年哈夫曼树实验报告 (1)之令狐采学创编
哈夫曼树实验报告
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼树及其应用
哈夫曼树及其操作-数据结构实验报告(2)
哈夫曼树实验报告(付原C语言程序)
哈夫曼树课程设计报告(DOC)
哈夫曼树实验报告
数据结构课程设计(赫夫曼树的建立)
相关主题
文本预览