实验四 哈夫曼树与哈夫曼编码
实验四 哈夫曼树与哈夫曼编码
一、实验内容
[问题描述]
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
[基本要求]
1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman
树。（具体算法可参见教材P147的算法6.12）
2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。
对给定的待编码字符序列进行编码。
二、概要设计
算法设计：
要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。
流程图：
算法：
模块：
在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：
首先建立一个哈夫曼树和哈夫曼编码的存储表示：
typedef struct {
int weight;
int parent,lchild,rchild;
char elem;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。
构造哈夫曼树：
for(i=n+1;i<=m;++i)
{//在HT[1……i]选择parent为0且weight最小的两个
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].weig ht+HT
[Select(HuffmanTree &HT,int n,int *s1,int *s2)：在所给的权值中，选择出权值最小的两个值。
int i, min;
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
{
min=i;
i=n+1;
}
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[min].weight)
min=i;
}
}
*s1=min;
在选择s2的时候和s1相似，只有在判断是否为最小的时候就，要加上一个条件：if(HT[i].parent==0&&i!=*s1)，就可以了，否则，选出来的最小权值和s1 就相等了，失去了选择的意义了。
CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)：从叶子到根逆向求编码：左孩子为0，右孩子为1，这样一直循环下去，而最重要的是：
for(int i=1;i<=n;++i)
{
star=n-1; //从右向左逐位存放编码，首先存放编码结束符
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码
if(HT[f].lchild==c)
cd[--star]='0'; //左分支标0
else
cd[--star]='1';//右分支标1
HC[i]=new char[n-star]; //为第i个编码分配空间
strcpy(HC[i],&cd[star]);//从cd复制编码串到HC
}
outputHuffman(HuffmanTree HT, int m)：显示出哈夫曼树的编码和字符以及权重，与二叉树的遍历相似：
if(m!=0)
{
cout<<HT[m].elem<<" "<<HT[m].weight<<endl;
outputHuffman(HT,HT[m].lchild);
outputHuffman(HT,HT[m].rchild);
}
三、测试数据
测试一：字符为：A B C 权重：10 12 8
测试数据二：字符为：ABCDEFG权重为：7 8 8 12 15 9 6
四、结果调试
调试一：
调试二：
五．总结
在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次又一次的过程，还是一次又一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深层次的了解就去问，那样对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。
六、附录：
#include<iostream.h>
#include <string.h>
typedef struct {
int weight;
int parent,lchild,rchild;
char elem;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表
////////////////////////求赫夫曼编码
void Select(HuffmanTree &HT,int n,int *s1,int *s2)
{
int i, min;
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
{
min=i;
i=n+1;
}
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if(HT[i].parent == 0 && i!=*s1)
{
min = i;
i = n+1;
}
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0&&i!=*s1)
{ if(HT[i].weight<HT[min].weight)
min=i;
}
}
*s2=min;
}
////////////////////
void Huffmantree(HuffmanTree &HT,int*w,int n,char *e)
{ //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
int m,i,s1,s2;
if(n<=1) return;
m=2*n-1;//总的结点
HT=new HTNode[m+1];
for(i=1;i<=n;++i)
{/*1-n号放叶子结点，初始化*/
HT[i].weight=w[i];
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
HT[i].elem=e[i];
}
for(i=n+1;i<=m;++i)
{/*非叶子结点初始化*/
HT[i].weight=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
HT[i].elem=0;
}
for(i=n+1;i<=m;++i)
{//在HT[1……i]选择parent为0且weight最小的两个
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 CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)
{
char *cd;
int c,f,star;
HC=new char*[n+1];
cd=new char[n];
cd[n-1]='\0';//编码结束符
for(int i=1;i<=n;++i)
{
star=n-1; //从右向左逐位存放编码，首先存放编码结束符
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码
if(HT[f].lchild==c)
cd[--star]='0'; //左分支标0
else
cd[--star]='1';//右分支标1
HC[i]=new char[n-star]; //为第i个编码分配空间
strcpy(HC[i],&cd[star]);//从cd复制编码串到HC
}
delete cd;//释放工作空间
for(i=1;i<=n;i++)
cout<<HT[i].elem<<" "<<HT[i].weight<<":"<<HC[i]<<endl;
}
////////////////////////////
/////////////////////////
void outputHuffman(HuffmanTree HT, int m)
{
if(m!=0)
{
cout<<HT[m].elem<<" "<<HT[m].weight<<endl;
outputHuffman(HT,HT[m].lchild);
outputHuffman(HT,HT[m].rchild);
}
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w;
char *e;
char c;
int i,n,m,wei;
cout<<"请输入赫夫曼树的带权数目：";
cin>>n;
w=new int[n+1];
e=new char[n+1];
for(i=1;i<=n;i++)
{
cout<<"请输入第"<<i<<"个元素的权值:";
cin>>wei;
w[i]=wei;
cout<<"请输入第"<<i<<"个字符:";
cin>>c;
e[i]=c;
}
Huffmantree(HT,w,n,e);
m=2*n-1;
outputHuffman(HT,m);
CHuffmancode(HT,HC,n);
}
第二篇：实验四 哈夫曼树与哈夫曼编码报告
软 件 学 院
实验名称： 哈夫曼树与哈夫曼编码
专 业： 软件工程
班 级： 卓越121班
学 号： 201207092235
学生姓名： 刘焕超
指导教师： 高艳霞
20##年 06 月 02 日
一、实验目的：
1、熟悉并掌握栈的创建、入栈和出栈等基本用法并能运用栈完成一些特定的任务。
2、将理论知识与实践相结合，提高自己的实际动手能力。
3、通过实践来及时发现自己的缺点与不足，以便为接下来更加有效的学习做铺垫。
4、通过对上机来检测自己所学知识的程度，为以后更好的掌握知识改进学习方法。
二、实验要求
1．预习 C 语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告.
[问题描述]
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
[基本要求]
1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman
树。（具体算法可参见教材P147的算法6.12）
2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。
对给定的待编码字符序列进行编码。
[选作内容]
１. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。
译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。
4. 打印 Huffman树。
［测试数据］
利用教材P.148 例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH”(也可自己设定数据进行测试)。
四、算法设计思想及步骤：
要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的为新的两个结点创建一个的二叉树的子树；我并没有像书上那种创建select()函数，而是我用了两个for()循环，先找到一个最小的记录其下标，在进行下一次for循环把找到的最小的除外，这样以此循环，就可以找到最小的了。创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。
算法流程：
首先建立一个哈夫曼树和哈夫曼编码的存储表示：
typedef struct //定义哈夫曼的结构体
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
HuffmanTree p;
typedef char * *HuffmanCode;
CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。
五、算法运行结果
六、收获及体会及总结
通过这次数据结构试验，我学习了哈夫曼的建立及其一些基本的操作方法。通过这次实践操作学会了完成一个设计的基本方法和步骤，拿到一个问题不能急于开始书写代码要将问题理清楚、找清思路、分好模块再开始敲代码，代码只是实现一个功能的工具，只有好的解决问题的思路，才能做出好的程序。
写完一个程序，只是完成一个设计的一小部分，后期的调试和验证也是重要的一部分，这次设计完成代码后编译都没错，但运行结果却不正确，通过调试后才的找出错误，运行成功，但经过一些数据的验证却又发现问题，再经过改正和完善代码才完成整个设计。所以一个设计的完成是需要不断的改进、调试和验证的，其中耐心和细心更是不可缺少的。
总结：
1、认真上好专业实验课，多在实践中锻炼自己。
2、写程序的过程中要考虑周到，严密。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，
以便能节省调试程序的时间。
-
哈夫曼编码实验报告
哈夫曼编码器实验报告学院：计算机学院班级：计科0801班姓名：***学号：***一．实验目的练习树和哈夫曼树的有关操作，和各个算法…
-
C语言-哈夫曼编码实验报告
福建工程学院课程设计课程数据结构题目哈夫曼编码和译码专业信息管理信息系统班级座号15号姓名林左权20xx年6月27日1实验题目哈夫…
-
哈夫曼编码实验报告
数据结构作业报告哈夫曼编码实验报告姓名班级学号摘要本程序能执行让一段字符以哈夫曼编码的形式被转存或将一段哈夫曼编码翻译成字符通过字…
- 哈夫曼编码实验报告
-
哈夫曼编码实验报告
北京邮电大学信息与通信工程学院数据结构实验报告实验名称实验三哈夫曼编码学生姓名牛佳宁班级20xx211107班内序号27学号102…
-
哈夫曼编码译码器实验报告
中北大学数据结构课程设计说明书20xx年12月20日目录1问题描述错误未定义书签2需求分析错误未定义书签3概要设计131抽象数据类…
-
云南大学软件学院数据结构实验六实验报告——赫夫曼编码译码器
云南大学软件学院数据结构实验报告本实验项目方案受教育部人才培养模式创新实验区X3108005项目资助实验难度ABC学期任课教师实验…
-
哈夫曼编码实验报告
哈夫曼编码器实验报告学院：计算机学院班级：计科0801班姓名：***学号：***一．实验目的练习树和哈夫曼树的有关操作，和各个算法…
-
C语言-哈夫曼编码实验报告
福建工程学院课程设计课程数据结构题目哈夫曼编码和译码专业信息管理信息系统班级座号15号姓名林左权20xx年6月27日1实验题目哈夫…
-
哈夫曼编码实验报告
数据结构作业报告哈夫曼编码实验报告姓名班级学号摘要本程序能执行让一段字符以哈夫曼编码的形式被转存或将一段哈夫曼编码翻译成字符通过字…
- 哈夫曼编码实验报告