哈夫曼树的建立
学院计算机科学与技术
专业
学号
学生姓名
指导教师姓名
2011年12月29 日
一、程序设计的内容与目的
内容：1.哈夫曼树也就是最优二叉树，构建带有权值的二叉树是本程序的核心数据
结构，使用链表实现二叉树节点信息的存储，链表中的结点结构如下：
typedef struct node
{
elem data; //二叉树节点信息
int weight; //二叉树的节点的权重
struct node *rChild; //二叉树节点的左孩子
struct node *lChild; //二叉树节点的右孩子
struct node *next; //连接二叉树节点的指针
}BinaryTreeNode;
2．程序应具有以下基本功能：
1．由键盘输入各个节点，并建立二叉树，能实现对二叉树的查询、插入、删除操作，构造其哈夫曼树。
2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息，可先建立二叉树，然后构造其哈夫曼树，有兴趣的同学可以将树直接画在显示屏幕
上。
3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注
释清楚。对程序其它部分也进行必要的注释。
6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。
目的：数据结构课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动
脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
（1）进一步巩固和复习数据结构的基础知识。
（2）培养学生结构化程序、模块化程序设计的方法和能力。
（3）提高学生调试程序的技巧和软件设计的能力。
（4）提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。
（5）了解软件的编制过程。
二、算法的基本思想
这是一个简单的哈夫曼树建立的程序，由键盘输入二叉树各个节点的信息（包括节点的权重）实现对二叉树的查询、插入、删除操作，并且可以构造其相应的哈夫曼树。
本程序使用了结构体来存放学生信息。将学生的信息以链表的形式存储在内存中。
typedef struct node
{
elem data;
int weight;
struct node *rChild;
struct node *lChild;
struct node *next;
}BinaryTreeNode;
程序运行前先创建二叉树，创建完成后显示刚才创建的信息，然后根据需要进行删除二叉树节点，插入节点和对二叉树进行查找并且构造其对应的哈夫曼树等汇总操作。
创建二叉树的函数如下：
BinaryTreeNode * CreateBinaryTree(int *sum)
{
elem data;
int weight;
BinaryTreeNode *root=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode *));
root=NULL;
printf("请输入二叉树的节点值和权重节点值为-1时结束\n");
getchar();
printf("请输入二叉树的节点值(整形)：");
scanf("%d",&data);
while(data!=-1)
{
printf("输入节点的权值：");
scanf("%d",&weight);
root=InsertNode(root,data,weight);
printf("请输入二叉树的节点值(整形)：");
scanf("%d",&data);
}
return root;
}
构建二叉树节点信息时必须输入权值，以便后面生成哈夫曼树。当输入二叉树的节点值和权重节点值为-1时结束输入。二叉树构建完毕，下面可以对二叉树进行一系列操作：打印二叉树、删除二叉树节点、插入节点、查找节点、生成哈夫曼树、保存二叉树、读取二叉树等汇总操作。
打印二叉树的函数：
void printBinary(BinaryTreeNode *root)
{
if(root!=NULL)
{
if(root->lChild!=NULL)
{
printf("节点值：%d：权值：%d:",root->data,root->weight);
printf("左孩子节点值是：%d,权值
是：%d\n",root->lChild->data,root->lChild->weight);
}
else
{
printf("节点值：%d：权值：%d:",root->data,root->weight);
printf("左孩子节点值是：空,权值是：空\n");
}
printBinary(root->lChild);
if(root->rChild!=NULL)
{
printf("节点值：%d：权值：%d:",root->data,root->weight);
printf("右孩子节点值是：%d,权值
是：%d\n",root->rChild->data,root->rChild->weight);
}
else
{
printf("节点值：%d：权值：%d:",root->data,root->weight);
printf("右孩子节点值是：空,权值是：空\n");
}
printBinary(root->rChild);
}
}
插入节点的函数：
BinaryTreeNode *InsertNode(BinaryTreeNode *tptr,elem key,int weight) {
BinaryTreeNode *f=NULL,*p=NULL; //p的初值指向根结点
p=tptr;
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲{
if(p->data==key) //树中已有key，无须插入
return tptr;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(key
}
p=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode *)); //生成新结点
p->data=key;
p->weight=weight;
p->lChild=p->rChild=NULL;
if(tptr==NULL) //原树为空，新插入的结点为新的根
{
tptr=p;
}
else
{
if(key
{
f->lChild=p;
}
else
{
f->rChild=p;
}
}
return tptr;
}
删除节点的函数：
BinaryTreeNode * DeleteNode(BinaryTreeNode *tptr,elem key)//删除{
BinaryTreeNode *p=NULL,*tmp=NULL,*parent=NULL;
p=tptr;
while(p)
{
if(p->data==key)
break;
parent=p;
p=(key
}
if(!p) return NULL;
tmp=p;
if(!p->rChild&&!p->lChild) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->rChild)
parent->rChild=NULL;
else
parent->lChild=NULL;
}
else if(!p->rChild) //p的右子树为空，则重接p的左子树{
p=p->rChild;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->lChild)
parent->lChild=p;
else
parent->rChild=p;
}
else if(!p->lChild) //的左子树为空，则重接p的左子树{
p=p->rChild;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->lChild)
parent->lChild=p;
else
parent->rChild=p;
}
else if(p->rChild&&p->lChild) //p有左子树和右子树，用p的后继覆盖p然后删去后继
{ //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->rChild;
while(p->lChild)
{
parent=p;
p=p->lChild;
}
tmp->data=p->data;
if(p==parent->lChild)
parent->lChild=NULL;
else
parent->rChild=NULL;
return tptr;
}
查找节点的函数：
BinaryTreeNode * FindNode(BinaryTreeNode *root,elem data) {
BinaryTreeNode *l=NULL;
BinaryTreeNode *r=NULL;
if(root!=NULL)
{
if(data==root->data)
{
return root;
}
l=FindNode(root->lChild,data);
r=FindNode(root->rChild,data);
}
if(l!=NULL)
{
return l;
}
else if(r!=NULL)
return r;
}
else
{
return NULL;
}
}
函数的重点当然是把建造处理的二叉树构造成其相对应的哈夫曼树了。其函数如下：while (head.next)
{
BinaryTreeNode *pN1=NULL, *pN2=NULL, *pRoot=NULL;
if (!head.next->next) //只剩最后一个结点，这就是根
{
return head.next;
}
//取前两个出来构造一棵新树（因为链表已经按权值升序排列了，前两个就是最小的两个）
pN1 = head.next; //第一个结点
pN2 = pN1->next; //第二个结点
head.next = pN2->next; //将这两个结点从链表中删除
pRoot = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode *)); //为这两个结点建立根
pRoot->weight = pN1->weight + pN2->weight; //权值相加
pRoot->data=pN1->data + pN2->data;
pRoot->lChild = pN1; //左分支为第一个结点
pRoot->rChild = pN2; //右分支为第二个结点
//将新的根加入哈夫曼森林
AddNode(&head, pRoot);
}
return NULL;
}
其要调用以下几个函数：
void GetAllBinaryInfo(BinaryTreeNode *root)
{
k++;
if(root==NULL)
{
data[k]=0;
power[k]=0;
}
else
{
data[k]=root->data;
power[k]=root->weight;
GetBinaryInfo(root->lChild);
GetBinaryInfo(root->rChild);
}
}
//加载所有节点信息
void GetBinaryInfo(BinaryTreeNode *root) {
if(root!=NULL)
{
k++;
data[k]=root->data;
power[k]=root->weight;
GetBinaryInfo(root->lChild);
GetBinaryInfo(root->rChild);
}
}
void GetNumber(BinaryTreeNode *root)
{
if (root!=NULL)
{
sum++;
GetNumber(root->lChild);
GetNumber(root->rChild);
}
}
//给Huffman森林（按各树根结点的值升序排列的带头结点的链表）添加一棵Huffman树//使得链表仍然有序
void AddNode(BinaryTreeNode *headNode, BinaryTreeNode *pNode)
{
BinaryTreeNode *p = headNode;
//找到第一个权值小于给定结点的结点，p指定该结点的前一个结点
while (p->next && p->next->weight < pNode->weight)
p = p->next;
if(p->next!=NULL)
{
pNode->next = p->next;
}
else
{
pNode->next=NULL;
}
p->next = pNode;
}
//功能：构造哈夫曼树
//参数说明
//n: 字符的个数
//datas: 要统计的字符
//powers: 字符对应的权值(出现的次数)
BinaryTreeNode* CreateHuffmanTree(int n, int datas[], int powers[])
{
BinaryTreeNode head;
int i;
head.next = NULL; //初始化森林
for ( i= 0; i < n; i++)
{
BinaryTreeNode *pNode = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode *));
pNode->data = datas[i];
pNode->weight = powers[i];
pNode->lChild = pNode->rChild = pNode->next = NULL;
AddNode(&head, pNode);
}
四、系统测试
程序运行实例如下：
1．选择1，运行界面如下：
2．选择2，运行界面如下：
3．选择3，运行界面如下：
4．选择4，运行界面如下：
5．选择5，运行界面如下：
6．选择6，运行界面如下：
7．选择7，运行界面如下：
8：选择8和9 程序运行正常
五、结论
通过这次长达两个星期的程序设计，我受益匪浅。深刻认识到自己知识的不牢固以及编程实践能力的低下。自学能力和自我认识都有一定的增强，也对编程有更深刻的认识。在做这个程序的时候，我遇到了不少问题。
1、通过实验更好的掌握了哈夫曼树，并对哈夫曼树有了深一步的了解
2、更进一步掌握了有关类的操作
3、由于算法推敲不足，使程序调试时费时不少
4、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性
5、更熟悉了文件的操作
6、更好的掌握了对程序的调试，并从中感受到调试的巨大的力量，特别是当程序不能实现预想结果时
总之，课程设计考察的是一个学生理论联系实际并真正理解知识的能力，在这次考察中，我收获了很多，也使我对C语言的理解运用有一定的提高。
很期待能在下一次的设计中有更好的表现。希望老师能多多开展这样的课程。
参考文献：
1 朱昌杰、肖建于编著，数据结构(C语言版)，北京：清华大学出版社
2 谭浩强著，C程序设计（第三版），北京：清华大学出版社
软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include
#include
数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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
cout<<"输入第"<
计算机科学与技术学院数据结构实验报告 班级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序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：
目录 一、程序设计目的与要求 (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.对算法进行分析和评价。
#include
哈夫曼树描述文档 一、思路 通过一个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<
******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 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++;
#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) {
哈夫曼树的压缩与解压 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的编码。 函数LinkList
源代码中创建了一个哈夫曼树结点类，其中有数据成员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()解压缩用哈夫曼编码压缩的文件。 在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。
实验报告 （ 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
}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;
课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 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个代码。同时将
哈夫曼树的建立数据结构课程设计文档 班级： 小组组长: 成员： 指导老师：
第一章前言 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 通过此次课程设计主要达到以下目的： 一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
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.由于编码要求从根结点开始，所以需要前序遍历哈夫曼树，故编码过程是以前序遍历二叉树
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.结点结构的存储方式：
哈夫曼树的结构算法12 利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。 一个完整的系统应具有以下功能： （1）（1） I：初始化。从终端读入字符集大小 n ，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。 （2） C：编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。 （3） D：译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。 （4） P：打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 （5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。 实现提示： 1、用户界面可以设计为“菜单”方式：显示上述功能号，再加上“E”表示结束运性行结束，用户键入一个选择功能字符，则执行相应的功能，此功能执行完毕后再显示此菜单，直至用户选择了“E”为止。 2、在程序的一次执行过程中，第一次执行了I、D 或 C 命令之后，哈夫曼树已经在内存中存在了，不必再读入。每次执行中不一定执行 I 命令，因为文件hfmtree 可能早已建好。 我写的源程序如下： #include
闽江学院 课程设计说明书 题目：哈夫曼编译码器 院系：计算机科学系 专业班级：10软件工程 学号： 学生姓名： 指导教师： 2011年12 月30 日
课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)译码。先初始化默认哈夫曼树，手动输入二进制代码进行译码存于WriteTextFile中；
题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为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
相关主题
文本预览