![应用数据结构课程设计(哈夫曼树)[1]](https://img.doczj.com/imgfa/07ipqh9pknn3tljtif7v-a1.webp)
![应用数据结构课程设计(哈夫曼树)[1]](https://img.doczj.com/imgfa/07ipqh9pknn3tljtif7v-92.webp)
学号：0120803490117
课程设计
题目Huffman编／译码器
学院管理学院
专业信息管理与信息系统
班级0801
姓名王涛
指导教师燕翔
2010 年07 月09 日
课程设计任务书
学生姓名：王涛专业班级：信管0801
指导教师：燕翔工作单位：管理学院
题目：Huffman编／译码器
初始条件：
利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个Huffman码的编／译码系统。
要求完成的主要任务:（包括课程设计工作量及其技术要求、说明书撰写等具体要求）
一个完整的系统应具有以下功能：
（l）I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：编码。利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：译码。利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50 个代码。
（5）T：印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
时间安排：
序号设计内容所用时间
1 问题分析和任务定义0.5天
2 数据类型和系统设计0.5天
3 编码实现和静态检查3天
4 上机准备和上机调试2天
5 总结和整理设计报告1天
合计7天指导教师签名： 2010年 07月02日系主任（或责任教师）签名： 2010年 07月02日
1. 需求分析
1.1程序的任务：
利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。此程序就是为这样的信息收发站写一个Huffman 码的编／译码系统。
1.2程序的输入和输出：
从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
1.3程序要达到的功能：
用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。
1.4测试数据如下表：
（l）利用教材中的数据调试程序。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码："THIS PROGRAM IS MY FAVORITE"。
字符 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
选择E，输入THIS PROGRAM IS MY FAVORITE，屏幕上显示110100010110001111110001000101001100001001010101100101110110001111111001 0100011111110011101011000001001001001101101010
同时文件codefile里面也出现相应的代码
选择D，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，
并且文件textfile中也相应的存入了这段话。
选择P，文件CodeFile以紧凑格式显示在终端上。
选择T，将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
选择其他的字母，将出现出错提示，并重新回到选择菜单。
2. 概要设计
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素集合。
数据关系R：
若D为空，则R为空，称Huffmantree为空霍夫曼树；
若D不为空，则R={H}，H是如下的二元关系：
1、H满足二叉树的所有要求；
2、H中所有数乘以该数所在节点的深度值之后和最小。
基本操作P：
InputHuffman(Huffman Hfm)
操作结果：输入并存储字符和相应权值。
Select(HuffmanTree HT,int end,int *s1,int *s2)
初始条件：频率数组已经建立。
操作结果：选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2。
HuffmanCoding(Huffman Hfm)
初始条件：频率数组已经建立。
操作结果：w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC。
InitHuffman(Huffman Hfm)
初始条件：频率数组已经建立。
操作结果：要求用户输入字符和相应权值，初始化赫夫曼数
Encoding(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：利用已建好的Huffman树（如不在内存，则从文件
hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存
入文件CodeFile中。
Decoding(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
Print(Huffman Hfm)
初始条件：霍夫曼树HoffmanTree已经存在。
操作结果：将文件CodeFile以紧凑格式显示在终端上，每行50 个代码。
Treeprint(Huffman Hfm)
初始条件：霍夫曼树HuffmanTree已经存在。
操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
}ADT HuffmanTree
2.2 主程序流程
Void main()
{
显示菜单；
Switch(k)
{
I：初始化
E：编码
D：译码
P：印代码文件
T：印哈夫曼树
Q：退出运行
}
}
2.3程序调用模块
Main函数
InitHuffman Encoding Decoding Print Treeprint Quit
3. 详细设计
3.1数据类型：
typedef char **HuffmanCode;//动态分配数组存储霍夫曼表码表
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储霍夫曼树
typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//分配数组存储字符串及其对应的霍夫曼树
Huffman Hfm;
char k; /*控制循环的标志*/
3.2 伪码算法：
主程序
main()
{
InitHuffman(Huffman Hfm)；
Encoding(Huffman Hfm)；
Decoding(Huffman Hfm)；
Print(Huffman Hfm)；
Treeprint(Huffman Hfm)；
}
其他模块：
void Select(HuffmanTree HT,int end,int *s1,int *s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
FOR (i=1;i<=end;i++)
{
IF(HT[i].parent是最小的)
THEN HT[i].parent——>*s1
IF(HT[i].parent是次最小的)
THEN HT[i].parent——>*s2
}
Huffman HuffmanCoding(Huffman Hfm) //w存放n个字符的权值（均〉0），构造赫夫曼树HT，并求出n个字符的构造赫夫曼编码HC
{
FOR(i=n+1;i<=2*n-1;++i) //选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
{
Select(Hfm.HT,i-1,&s1,&s2);
修改父亲位置；
修改孩子位置；
父亲结点权值为左右孩子权值之和；
}
//从叶子结点到根逆向求每个字符的赫夫曼编码
FOR(i=1;i<=n;++i)
//逐个字符求赫夫曼编码
{ start=n-1;//编码结束符位置
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
//从叶子到根逆向求编码
{
IF(c==Hfm.HT[f].lchild) cd[--start]='0';
ELSE cd[--start]='1';
}
再从cd复制编码到Hfm.HC
}
RETURN Hfm;
}
Huffman InitHuffman(Huffman Hfm)//初始化赫夫曼数，要求用户输入字符和相应权值{
对文件hfmTree以读文本的形式打开
IF(fp==NULL)
调用InputHuffman函数，用户输入字符和相应权值存入赫夫曼数中
ELSE
输出"The Huffmantree has already existed!\nPlease choose again!\n\n");
读入hfmTree中文本
FOR(i=1;i<=n;i++)
作为独立结点对结点的parent，lchild，rchild分别赋值0
FOR(;i<=2*n-1;++i)
作为独立结点对结点的weight，parent，lchild，rchild分别赋值0
Hfm=HuffmanCoding(Hfm);
RETURN Hfm;
}
void Encoding(Huffman Hfm)//利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile 中。
{
输出"\n\n*******************Encoding**************************\n\n"
IF((ffp=fopen("ToBeTran","rt"))==NULL)
提示输入"Please input the sentence: "
scanf("%s",ch);
printf("\n");
以写文本的形式打开CodeFile
ELSE
读入ToBeTran文件中的字符;
WHILE(ch[j])
FOR(i=1;i<=n;i++)
IF(ch[j]==Hfm.c[i])
分别在终端和文件CodeFile输入Hfm.HC[i]
void Decoding(Huffman Hfm)//利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
{ 定义char d[500]
输出"\n\n******************Decoding************************\n\n"
IF((fp=fopen("CodeFile","rt"))==NULL)
输出Please input the code:;
ELSE
将文件Codefile中的内容读到d数组中
输出The file is :
以写文本的方式打开TextFile
WHILE(d[j])
根到叶子结点遍历，并按照lchild——>0，rchild——>1来输出
入到文件TextFile中
关闭文件
}
void Print(Huffman Hfm)//将文件CodeFile以紧凑格式，示在终端上，每行50 个代码。
{
FOR(i=1;i<=n;i++)
输出Hfm.c[i]
输出Hfm.HT[i].weight
以只读二进制的方式打开CodeFile文件
while ( feof(fprint)==0 )
逐个输出
IF (m%50==0)
输出"\n"
关闭文件
}
void Treeprint(Huffman Hfm)//将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
{
打开hfmTree文件
将字符及其对应的代码赋给变量Hfm.c[i]和Hfm.c[i][j]
输出Hfm.c[i]，对Hfm.c[i][j]进行判断，不是\n则输出*，否则停止输出
}
3.3函数调用关系图
InputHuffman(Huffman Hfm)
接收数据Select（）供HuffmanCoding()调用
调用HuffmanCoding()构造哈夫曼树
编码调用Encoding() 译码调用
Decoding（）
打印编码
Print()
打印哈夫曼树
Treeprint() InitHuffman(Huffman Hfm)
初始化
4. 调试分析
4.1 调试过程中遇到的问题：
第一个问题是一直比较棘手的问题就是文件的调用与写入，因为文件方面的知识一直就掌握的不是很好，在写代码时产生很大困难，所以在解决这个问题的时候我把文件部分系统的看了一下，这才从自身角度解决了这个问题。而实际中遇到的问题就是如何判断已经有了hfmtree这个文件，并且怎么调用到内存中来。
解决方案：设置一个全局结构体变量来存放已经在文件中存放的霍夫曼树。
第二个问题是关于界面的美观设计方面，因为很多代码在文本中编辑时是比较整齐美观的，但是在程序运行中却出现很多问题，不对齐等等。还有就是换行符的使用，一不小心就会产生偏差。
解决方案：进入程序进行调试，检查每段输出代码的显示。
第三个问题是Huffman树的打印，方式为凹入式打印，由于在当时学习的时候这部分内容没有留意，根本没有概念，所以在编写程序过程中出现了严重的问题。导致该项功能无法完成。
解决方案：尚未完善解决，只是将内存中的哈夫曼树中各节点的值及其孩子输出。
4.2 算法的时空分析：
算法的时间复杂度：
Select(HuffmanTree HT,int end,int *s1,int *s2) O(n)
HuffmanCoding(Huffman Hfm) O(n2)
InputHuffman(Huffman Hfm) O(n)
InitHuffman(Huffman Hfm) O(n)
Encoding(Huffman Hfm) O(n)
Decoding(Huffman Hfm) O(n)
Print(Huffman Hfm) O(n)
4.3 经验与体会：
整个程序在编的时候思路是很明朗的，包括菜单的设置都是很清晰的，但是如何通过一个菜单将所有涉及到的文件与终端联系起来还有打印哈夫曼树都是比较困难的问题，由于文件这一章节我们以前学习的时候并没有很重视，所以在运用的时候遇到了很大的困难，同时通过这次的设计我也看到其实文件这一章是很重要的，我们做了一个程序，必须要把有些必要的数据进行保存，如果只是停留在内存中那就很难在以后被重复利用，
会很大程度上提高我们调试的效率；另外凹入式打印哈夫曼树更是让我头疼了一整天的问题，由于根本不知道其概念是什么，更不用说去编写代码了。同时我也觉得有些细节问题是很重要的，不管是一个整型变量还是一个结构体变量，有时候对整个程序起着至关重要的作用。
5. 用户使用说明
1．本程序的运行环境为DOS操作系统，执行文件为：hfmtree.exe。
2. 运行程序后出现选择菜单。
3．根据提示选择相应的操作，初始化，编码，译码，印代码文件，印哈夫曼树
退出，每次选择完，都会再次弹出选择菜单供用户选择。结束符为回车键。
6. 测试结果
在进入系统以后，选择第一个初始化，按要求键入要求的字符及其频度
字符
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
—
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 截图如下所示：
图1
进入程序，显示的菜单界面
图2
输入I，选择进行初始化
图3 初始化时对字符的个数进行限制，不得少于2个。
图4、5
在字符个数处输入“27”，之后依次输入各字符及其权值。
图6
在菜单界面选择E，出现提示语句，要求输入句子。
图7
输入“THIS_PROGRAM_IS_MY_FAVORITE”，回车之后，显示出该句的哈夫曼编码。（此处为求简捷，将空格用下划线“_”作为代替）
图8
在菜单界面选择D，则对文件中已有的哈夫曼编码进行反译，将译出的字符显示出来。
图9
在菜单界面选择P，将文件中的哈夫曼编码紧凑输出，每行50个。结果如下图：
图10、11
该程序中，我加入了将初始化的各字符的编码输出的语句，可以看到各个字符的哈弗曼编码。
图12
这3行数字便是紧凑输出哈夫曼编码的结果。
图13
同时，不同的人使用本程序进行不同的哈夫曼编码时，由于前一位使用者初始化的数据后一位不一定同样适用，为了避免这种情况，因此当已经初始化后再进行初始化时会出现提示是否重新初始化的信息提示，如上图所示。
图14
在菜单界面选择T，打印处内存中的哈夫曼树各节点的值及其双亲节点和子节点。
图15
TEXTFILE.TXT文本文件，记录用户输入的需要进行编码的句子。
图16 CODEFILE.TXT文本文件，记录TEXTFILE.TXT文本文件中字符的哈弗曼编码。
图17 HFMTREE.TXT文本文件，记录输入的各字符及其权值
7. 附录
源程序文件名清单：
TEXTFILE.TXT 记录待编码的句子
CODEFILE.TXT 记录哈夫曼编码
HFMTREE.TXT 记录字符个数、名称及权值
源代码：
#include
#include
#include
#include
#include
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 32767
#define MAX 60
typedef char **HuffmanCode;//动态分配数组存储哈夫曼表码表
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//全局结构体变量，来存储字符与代码
void Select(HuffmanTree HT,int end,int *s1,int *s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)//遍历查找权值最小的结点S1
{
if (HT[i].parent==0&&HT[i].weight { *s1=i; min1=HT[i].weight; } } min2=MAX_NUM; for(i=1;i<=end;i++)//遍历查找除S1外权值最小的结点S2 { if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight) { *s2=i; min2=HT[i].weight; } } } Huffman HuffmanCoding(Huffman Hfm) //存放n个字符的权值（均〉0），构造哈夫曼树HT，并求出n个字符的构造哈夫曼编码HC { int i,n,m,s1,s2,start; int c,f; char *cd; n=Hfm.length; if(n<=1) return Hfm; m=2*n-1; for(i=n+1;i<=m;++i) //选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2 { Select(Hfm.HT,i-1,&s1,&s2); Hfm.HT[s1].parent=i;//修改父亲位置 Hfm.HT[s2].parent=i; Hfm.HT[i].lchild=s1;//修改孩子位置 Hfm.HT[i].rchild=s2; Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父亲结点权值为左右孩子权值之和 } //从叶子结点到根逆向求每个字符的哈夫曼编码 Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间 cd[n-1]='\0';//编码结束符 for(i=1;i<=n;++i)//逐个字符求哈夫曼编码 { start=n-1;//编码结束符位置 for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//从叶子到根逆向求编码 { if(c==Hfm.HT[f].lchild) cd[--start]='0'; 数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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所示。 ⑶有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。 实验二二叉树的遍历及霍夫曼编码 班级：计科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 计算机科学与技术学院数据结构实验报告 班级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.问题描述 (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中。 课程论文 题目：哈夫曼树及其应用课程设计报告学号： 201230210115 姓名：黄文宣 班级： 1232101 专业：信息安全 课程名称：数据结构 课程老师：王晓燕 二零一肆年一月 目录 1、课程设计的题目及简介 (3) 2、实验目的 (3) 3、设计说明 (4) 4、总体流图 (4) 5、详细设计 (5) 6、实现部分 (6) 7、测试程序 (9) 8、心得与体会 (10) 一、课程设计题目 哈夫曼树及其应用 数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理 建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。 二、实验目的 1 熟悉树的各种存储结构及其特点。 2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 三、设计说明 建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 四、总体流图 哈夫曼树编码系统 初始化 编码 重新建立哈夫 曼树 译码 打印编码 一、需求分析 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 目录 一、程序设计目的与要求 (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.对算法进行分析和评价。 实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include cout<<"输入第"< 哈夫曼树描述文档 一、思路 通过一个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）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：2017-2018学年第2学期 班级： 指导老师： 实验题目：哈夫曼树 学号： 姓名： 上机时间： 一、实验目的 本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。 1、求出各个叶子节点的权重值 输入一个字符串，统计其中各个字母的个数和总的字母个数。 2、构造哈夫曼树 统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈夫曼树。 3、打印哈弗曼树的功能模块 按照一定形式打印出哈夫曼树。 4、编码 利用已经建立好的哈夫曼树进行编码。 5、译码 根据编码规则对输入的代码进行翻译并将译码。 三、实验步骤 1、实验问题分析 （1）设计一个结构体数组保存字母的类型和个数。 { ; 字母的种类 ; 字母的个数 }; （2）在构造哈夫曼树时，设计一个结构体数组保存哈夫曼树中各结点 的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有21个结点，所以数组大小设置为21,描述结点的数据类型为： { ; 权值 ; 双亲 ; 左孩子 ; 右孩子 }; []; 定义此类型的数组 （3）求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始，沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类型： 10; { []; 每个结点的哈夫曼编码 ; 开始位置 }; （4）设置全局变量。 s; 为输入的字符串 0; 记录输入的字符串中字母的种类，即叶子结点个数 0; 记录字符串中字母的总个数 []叶子结点类型 2、功能（函数）设计 （1）统计字母种类和个数模块 此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结 点个数，每种字母出现次数即各叶子结点的权值。全局变量s保存输 入的字符串，将种类和个数保存到[]中。 函数原型：（） 如输入的字符串是“”则显示如下。 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 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个代码。同时将 ******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 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++; 哈夫曼树实验报告 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日 计算机学院信管专业 数据结构课程设计 题目：哈夫曼树的应用班级： 姓名：学号： 同组人姓名： 起迄日期： 课程设计地点: 指导教师： 评阅意见： 成绩评定： 评阅人：日期： 完成日期：2012年12月 目录 一、需求分析 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析和测试结果 (7) 五、心得体会和总结 (10) 六、参考文献 (10) 七、附录 (11) 一、需求分析 （一）实验要求 要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。 要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。 问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。 综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。 （二）实验任务 一个完整的系统应具有以下功能： 功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 （三）实验步骤 分步实施： 1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2）完成最低要求：完成功能1； 3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求： 1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 4) 要提供程序测试方案 5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 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
哈夫曼树
哈夫曼树的建立与操作
构建哈夫曼树及输出哈夫曼代码及算法思想
哈夫曼树及应用
数据结构课程设计-哈夫曼树
哈夫曼树课程设计报告(DOC)
哈夫曼树
哈夫曼树实验报告
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼树及其应用
数据结构课程设计实验报告哈夫曼树的应用
哈夫曼树及其操作-数据结构实验报告(2)
相关主题
文本预览