承诺书
郑重声明：本人所呈交的课程设计是本人在导师指导下独立撰写并完成的，课程设计没有剽窃、抄袭、造假等违反学术道德、学术规范和侵权行为。本课程设计不包含任何其他个人或集体已经发表或撰写过的研究成果，如果引用则标识出了出处。对本课程设计的研究做出贡献的个人和集体，均已在文中以明确方式标明。
课程设计与资料若有不实之处，本人承担一切相关责任。特此声明。
签名：
年月日
目录
一．需求分析 (3)
1.问题描述 (3)
2.功能要求 (3)
二．系统总框图和功能模块说明.4
1.系统总框图 (4)
2.功能模块说明 (4)
2.功能模块说明 (4)
3.系统设计 (4)
3.1主要链表 (4)
3.2主要功能函数 (6)
3.3关键函数的流程图 (6)
4.系统调试： (9)
5.总结 (13)
6.源程序： (13)
一．需求分析
哈夫曼编/译码器
1.问题描述
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。
2.功能要求
I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。
T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
二．系统总框图和功能模块说明
图1. 系统总框图
2.功能模块说明
（1）.初始化； Initialization(LiHTNode *&ht)；
（2）.编码； Encoding(LiHTNode *&ht,LeafCode *&lc)；（3）.译码； Decoding(LeafCode *&lc)；
（4）.印代码模块； Print()；
（5）.印哈夫曼树。 Tree_Printing(LiHTNode *&ht)；
3.系统设计
3.1主要链表
struct LiHTNode //用于建立哈夫曼树
{
char data; //节点
double weight; //权值
char code; //编码
LiHTNode *parent; //双亲
LiHTNode *lchild; //左孩子
LiHTNode *rchild; //右孩子
};
存储结构如图所示
图2. 哈夫曼树节点存储结构
struct LeafCode //用于存储叶子节点和哈夫曼编码{
char leaf; //叶子
char code[N]; //叶子到根节点的编码串
int top; //栈顶指针
LeafCode *next;
};
存储结构如图所示
图3. 叶子哈夫曼编码存储结构
3.2主要功能函数
Initialization(LiHTNode *&ht) //初始化
Encoding(LiHTNode *&ht,LeafCode *&lc) //编码 Decoding(LeafCode *&lc) //译码
Print() //印代码模块
Tree_Printing(LiHTNode *&ht) //印哈夫曼树
3.3关键函数的流程图
（1）. Initialization(LiHTNode *&ht) //初始化
图4. 初始化
（2）. Encoding(LiHTNode *&ht,LeafCode *&lc) //编码
图5. 编码
（3）. Decoding(LeafCode *&lc) //译码
图6. 译码
（4）. Print() //印代码模块
图7. 印代码模块
（5）. Tree_Printing(LiHTNode *&ht) //印哈夫曼树
图8. 印哈夫曼树
4.系统调试：
（1）.调试结果如下：
图9. 调试结果
（2）.终端显示如下：
图10. 终端显示
图11. 终端显示
图12. 终端显示
（3）.各文件如下：
1).文件hfmTree.txt
2）.文件ToBeTran.txt
3).文件CodeFile.txt
图15. 文件CodeFile.txt
4).文件TextFile.txt
图16. 文件TextFile.txt 5）.文件Codeprint.txt
图17. 文件Codeprint.txt
6).文件TreePrint.txt
图18. 文件TreePrint.txt
5.总结
本程序为哈夫曼编/译器的制作，主要是对文件的操作，在创建哈夫曼树的过程中有点难度，创建哈夫曼编码时也有一定难度，译码时不难；但是在用凹入表形式打印哈夫曼树时，有点难度。
通过本程序，我对二叉树的递归操作更加熟练了，对了解并掌握了树和二叉树这一章节的内容，尤其是二叉树。
6.源程序：
#include
#include
#define N 150 //存放哈夫曼编码的最大长度
#define M 200 //存放字符的最大长度
#define Max 1000 //存放原文的哈夫曼编码的最大长度
struct LiHTNode
{
char data; //节点
double weight; //权值
char code; //编码
LiHTNode *parent; //双亲
LiHTNode *lchild; //左孩子
LiHTNode *rchild; //右孩子
};
struct LeafCode
{
char leaf; //叶子
char code[N]; //叶子到根节点的编码串
int top; //栈顶指针
LeafCode *next;
};
void DisplayHT(LiHTNode *&ht) //哈夫曼树的输出{
LiHTNode *p=ht;
ofstream out("F:\\hfmTree.txt",ios::out|ios::app);
if(p!=NULL)
{
out<
if(p->parent!=NULL)
{
out<
}
else
{
out<<"NULL"<<" ";
}
if(p->lchild!=NULL)
{
out<
}
else
{
out<<"NULL"<<" ";
}
if(p->rchild!=NULL)
{
out<
}
else
{
out<<"NULL"<<"\n";
}
DisplayHT(p->lchild);
DisplayHT(p->rchild);
}
out.close();
}
void Initialization(LiHTNode *&ht) //初始化{
LiHTNode *p,*q,*g;
int temp;
char ch;
ht=new LiHTNode;
ht->parent=NULL;
ht->lchild=NULL;
ht->rchild=NULL;
ht->data=0;
ht->weight=0;
p=ht;
for(int i=1;i<=128;i++) //存储ASCLL码字符作为哈夫曼树的叶子，权值设为对应ASCLL码
{
p->parent=new LiHTNode;
p=p->parent;
p->data=i;
p->weight=i;
p->lchild=NULL;
p->rchild=NULL;
p->parent=NULL;
}
p=ht;
q=p->parent;
while(p->parent!=NULL) //对权值大小进行排序
{
while(q!=NULL)
{
if(p->weight>q->weight)
{
temp=p->weight;
ch=p->data;
p->weight=q->weight;
p->data=q->data;
q->weight=temp;
q->data=ch;
q=q->parent;
}
p=p->parent;
q=p->parent;
}
p=ht;
q=p->parent;
while(p->parent!=NULL) //哈夫曼树的构造{
g=new LiHTNode;
g->lchild=p;
g->rchild=q;
g->parent=q->parent;
p->parent=g;
q->parent=g;
g->weight=p->weight+q->weight;
p=g;
q=p->parent;
while(q!=NULL)
{
if(g->weight
{
ht=g->parent;
g->parent=q;
p->parent=g;
g=ht;
break;
}
if(q->parent==NULL&&g->weight>q->weight)
ht=g->parent;
g->parent=q->parent;
q->parent=g;
g=ht;
break;
}
p=q;
q=q->parent;
}
p=g;
q=p->parent;
}
ht=g;
ofstream out("F:\\hfmTree.txt",ios::out);
out<<"节点\t权重\t双亲权重\t左孩子权重\t右孩子权重\n";
out.close();
DisplayHT(ht); //输出哈夫曼树各个节点以及权重}
void CreateHCode(LiHTNode *&ht) //哈夫曼编码的创建
{
LiHTNode *p=ht;
if(p!=NULL)
{
if(p->lchild!=NULL)
{
p->lchild->code='0';
}
if(p->rchild!=NULL)
{
p->rchild->code='1';
}
CreateHCode(p->lchild);
CreateHCode(p->rchild);
}
}
void FindLeaf(LiHTNode *&ht,LeafCode *&lc) //查找叶子节点{
LiHTNode *p=ht,*g;
LeafCode *q=lc;
while(q->next!=NULL)
q=q->next;
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
{
q->next=new LeafCode;
q=q->next;
q->next=NULL;
q->leaf=p->data;
g=p;
q->top=-1;
while(g->parent!=NULL)
{
q->top++;
q->code[q->top]=g->code;
g=g->parent;
}
cout<
}
FindLeaf(p->lchild,q);
FindLeaf(p->rchild,q);
}
}
void Encoding(LiHTNode *&ht,LeafCode *&lc) //编码{
LiHTNode *p=ht;
int temp,i=0,k;
char str[M],ch;
CreateHCode(p);
cout<<"叶子以及权重的形式为（叶子：权重）："< FindLeaf(ht,lc); LeafCode *q=lc->next; ifstream in("F:\\ToBeTran.txt",ios::in); while(in.get(ch)) { str[i]=ch; i++; } k=i; in.close(); cout< ofstream out("F:\\CodeFile.txt",ios::out); for(i=0;i { q=lc->next; while(q!=NULL) { if(str[i]==q->leaf) { 计算机科学与技术学院数据结构实验报告 班级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序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #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.求每个字符的哈夫曼编码并显示。 南京邮电大学 毕业论文 题目哈夫曼编码在文件压缩中的应用专业计算机科学与技术（计算机通信）学生姓名 班级学号090028 09002829 指导教师孙知信 指导单位物联网学院 日期：年月日至年月日 毕业设计（论文）原创性声明 本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期：年月日 摘要 在信息技术飞速发展的今天，大数据量的信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。压缩机制是一种很方便的发明，尤其是对网络用户，因为它可以减小文件中的比特和字节总数，使文件能够通过较慢的互联网连接实现更快传输，此外还可以减少文件的磁盘占用空间。在下载了文件后，计算机可使用WinZip或Stuffit这样的程序来展开文件，将其复原到原始大小。如果一切正常，展开的文件与压缩前的原始文件将完全相同。 哈夫曼压缩一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。本课题使用哈夫曼编码方法实现对文本、图像或其他格式文件进行压缩和解压缩，研究各种文件类型在采用哈夫曼编码进行压缩的差别，并寻找一种使用哈夫曼编码对任意文件进行压缩和解压缩的解决方案。 本论文着重介绍了现有的哈夫曼编码现状，利用哈夫曼编码的原理，利用C++编写程序压缩软件，在针对文本压缩的基础上丰富对图片进行压缩的功能，然后再尝试对声音和视频压缩进行尝试。 关键词：压缩压缩算法哈夫曼编码 一、需求分析 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 软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #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.对算法进行分析和评价。 2017人大软件工程硕士考研学费多少钱 凯程人大软件工程硕士考研老师给大家一些学费意见，希望广大考生可作为参考，总结经验。同时本文也介绍人大软件工程硕士考研难度，人大软件工程硕士考研就业，人大软件工程硕士考研辅导，人大软件工程硕士考研参考书，人大软件工程硕士考研专业课五大方面的问题。凯程就是王牌的人大考研机构！ 一、人大软件工程硕士学费介绍 人大软件工程硕士学费总额4万元，学制2年。 软件工程硕士专业学位分为以下几个培养方向： 基础软件方向 金融信息工程方向 计算机取证与司法鉴定方向 企业信息化与电子政务方向 大数据与云计算方向 其考试科目是一样的： 101-思想政治理论（满分100分） 204-英语二（满分100分） 302-数学二（满分150分） 408-计算机学科专业基础综合（满分150分） 二、人大软件工程硕士考研难不难，跨专业的学生多不多? 最近几年软件工程硕士考研很火，特别是人大这样的名校。2015年人大软件工程硕士研究生计划招收30人（含20人推免），相对来说招生人数还是比较多的，跨专业考生是可以报考的。在考研复试的时候，老师更看重跨专业学生的能力，而不是本科背景。其次，考试科目里，计算机专业基础本身知识点难度并不大，跨专业的学生完全能够学得懂。即使本科学计算机的同学，专业课也不见得比你强多少（大学学的内容本身就非常浅）。所以记住重要的不是你之前学得如何，而是从决定考研起就要抓紧时间完成自己的计划，下定决心，就全身心投入，要相信付出总会有回报。在凯程辅导班里很多这样三凯程生，都考的不错，主要是看你努力与否。 三、人大软件工程硕士就业怎么样？ 作为名牌院校的中国人民大学，本身的学术氛围好，有良好的师资力量，人脉资源也不错，出国机会也不少，硕士毕业生社会认可度高，自然就业就没有问题。2014年中国人民大学硕士毕业生就业率高达99.15%，就业率居于全国同类专业院校的首位。 人大软件工程硕士研究生毕业后主要到计算机软件专业公司﹑信息咨询公司﹑以及金融等其它独资、合资企业工作。 就业岗位：软件工程师、项目经理、软件开发工程师、高级软件工程师、java软件工程师、软件测试工程师、嵌入式软件工程师、.net软件工程师、java开发工程师、java软件开发工程师、android开发工程师、java高级软件工程师、等。 四、人大软件工程硕士考研辅导班有哪些？ 数据结构实验报告 实验名称：实验三树 学生姓名： 班级： 班内序号： 学号： 日期：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 #include 各专业完整优秀毕业论文设计图纸 题目：哈夫曼树应用 学生姓名： 学号： 201317010201 专业班级：计科13102 同组姓名： 指导教师： 设计时间：2014年下学期第18周 目录 一、需求分析 (3) 1. 分析问题 (3) 2. 确定解决方案 (3) 3. 输入的形式和输入值的范围 (3) 4.输出的形式 (3) 5.程序所能达到的功能 (3) 二、概要设计 (4) 1. 主程序的流程图： (4) 2．程序中数据类型的定义： (5) 3．各程序模块之间的层次(调用)关系： (5) 三、详细设计 (6) 1．哈夫曼树存储及类的定义： (6) 2.哈夫曼树的基本操作: (6) 3.主函数 (7) 四、调试分析和测试结果. (8) 1. 测试数据及其输出结果： (8) 2. 调试过程中遇到的问题及解决办法: (12) 五、总结 (13) 六、参考文献 (13) 七、致谢 (13) 八、附录 (13) 一、需求分析 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 （1）I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n 个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进 常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫 实验报告 欧阳光明（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 《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4）、串的定义及其基本操作。 （5）、数组的定义、运算和顺序存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其各种操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能阅读用类C语言编写的算法。 （2）、能分析算法所完成的功能、运行结果和时间复杂度。 （3）、能根据要求用类C语言编写算法。 二、考核知识点及考核要求 第一章绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类C语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类C语言描述算法 哈夫曼树实验报告 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作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 哈夫曼树的压缩与解压 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()解压缩用哈夫曼编码压缩的文件。 在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。 数据结构课程设计题目 1.飞机订票系统（限1 人完成）（顺序或链式存储） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息，客户信息的存储结构，设计程序完成功能； 2.宿舍管理查询软件（限1 人完成） 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： 采用交互工作方式 建立数据文件，包括学生信息、宿舍信息、住宿信息，学生信息按关键字（姓名、学号）进行排序(排序方法自选，不能相同)； 查询: (用二分查找实现以下操作) 按姓名查询 按学号查询 (用顺序查找实现以下操作) 按房号查询 3.校园导航问题（限1 人完成） 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 要求：能增加场所 4.图书借阅管理系统（限1 人完成）（顺序或链式存储） 主要分为两大功能： 1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)； 2)会员管理(增加会员、查询会员、删除会员、借书信息)； 5.学生成绩管理（限1 人完成）（顺序或链式存储） 包括：课程信息，学生信息等；能增加课程或学生。 实现功能：输入、输出、插入、删除、查找、显示、保存、排序、退出。6.活期储蓄帐目管理（限1 人完成） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求： 1)能比较迅速地找到储户的帐户，以实现存款、取款记账； #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) { 实验报告 （ 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;哈夫曼树 实验报告
数据结构哈夫曼树的实现
哈夫曼树及其应用(完美版)
哈夫曼编码在文件压缩中的应用
哈夫曼树的实验报告1
贪心算法构造哈夫曼树
哈夫曼树
2017人大软件工程硕士考研学费多少钱
实验三哈夫曼树实验报告
数据结构哈夫曼树和代码
哈夫曼树的应用数据结构_学位论文
哈夫曼树及应用
2021年哈夫曼树实验报告 (1)之令狐采学创编
2019广东专插本韩山师范学院《数据结构》考试大纲
哈夫曼树实验报告
哈夫曼树解压与压缩
数据结构毕业设计题目整理
哈夫曼树建立、哈夫曼编码算法的实现
贪心法构造哈夫曼树
相关主题
文本预览