哈夫曼算法及其应用
一、问题描述
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼编码是一种根据哈夫曼树对文件进行编码的方式。哈夫曼编码是可变字长编码的一种。本次课程设计是对一个已建文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。压缩文件即读文件，统计文件中的字符个数，对文件进行哈夫曼编码和译码，并将编码译码后的字符存储在文件中。
二、基本要求
程序要求实现以下功能：
1．统计文本文件中各字符的出现次数（涉及读文件，统计字符个数）；
2．对文件中的字符进行哈夫曼编码，并存储入字符编码文件；
3．根据字符编码文件对文本文件内容进行编码；
4．根据字符编码文件和已编码文件的内容进行译码；
5．能够输出原文、编码表、文本文件编码、译文。
三、测试数据
In its medical literature, the Food and Drug Administration states that hot water comfortable enough for washing hands is not hot enough to kill bacteria, but is more effective than cold water because itremoves oils from the hand that can harbor bacteria.
四、算法思想
1、哈夫曼树建立算法：
1）根据给定的n个权值{ W1，W2，W3……Wn } 构成n棵二叉树的集合{T1， T2，……Tn}，其中Ti中只有一个权值为Wi的根结点，左右子树均为空。
2）在F中选取两棵根结点的权值最小的树作为左、右子树一构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
3）在F中删除这两棵中权值最小的树，同时将新得到的二叉树加入F中。
4）重复2）3）直到F中仅剩一棵树为止，这棵树就是哈夫曼树。
2、哈夫曼编码算法：
通过从哈夫曼树根结点开始，对左子树分配代码“1”，右子树分配代码“0”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
3、对文件字符编码算法：
逐一读取文件中字符，在哈夫曼编码表查找对应字符，读取其编码并写入文件，如此循环直至结束。
4、哈夫曼译码算法：
根据编码用的哈夫曼树，从根结点出发，逐个读入电文中的二进制码；若代码为“1”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。
五、模块划分
1．Void InitHT(HuffmanT T)
初始化Huffman树。
2．Void SelectMin(HuffmanT T, int n, int &p1, int &p2)
找到权重最小的叶子。
3．Void LoadHuffmanFile(HuffmanT T)
加载文件。
4．Void CreatHT(HuffmanT T)
构造Huffman树。
5．Void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)
根据Huffman树求Huffman编码表。
6．Void EncodingHuffmanT(HuffmanT T, HuffmanCode H)
对文件编码。
7．Void DecdingHuffmanT(HuffmanT T, HuffmanCode H)
根据Huffman编码、译码。
8．Void PrintHuffmanT(HuffmanT T)
打印Huffman权重表。
9．Void PrintHuffmanH(HuffmanT T, HuffmanCode H)
打印Huffman编码表。
10．Void MainMenue（）
主菜单。提供相关的操作提示。
11．Int main（）
主函数。用个while循环和switch选择结构进行进行循环交互性操作。
六、数据结构//(ADT)
1、哈夫曼树的存储结构：
typedef struct {
char ch; //字符
int weight; //字符权重
int lchild; //左子
int rchild; //右子
int parent; //双亲
} THNODE;
2、哈夫曼编码表的存储结构：
typedef struct {
char ch; //存储字符
char bits[MAX_C + 1]; //字符编码位串
} CodeNode;
七、源程序
//Huffman.cpp 源代码如下：
#include
#include
#include
#define MAX_C 256 //定义最大字符数
#define MAX_N 512 //定义最大Huffman节点个数#define N 50
/*Huffman Tree 结构*/
typedef struct
{ char ch; //字符
int weight; //字符权重
int lchild; //左子
int rchild; //右子
int parent; //双亲
}THNODE;
typedef THNODE HuffmanT[MAX_N];
/******Huffman 编码表结构*****/
typedef struct
{ char ch; //存储字符
char bits[MAX_C + 1]; //字符编码位串
}CodeNode;
typedef CodeNode HuffmanCode[MAX_C];
HuffmanCode H;
/*********全局变量**********/
int n; //指示待编译文件的字长
char filename[20];
/*初始化Huffman树*/
void InitHT(HuffmanT T)
{ int i;
for (i = 0; i < MAX_N; i++)
{ T[i].ch = '\0';
T[i].weight = 0;
T[i].lchild = -1;
T[i].rchild = -1;
T[i].parent = -1;
}
}
/*找到权重最小的叶子*/
void SelectMin(HuffmanT T, int n, int &p1, int &p2)
{ int i;
int j;
for (i = 0; i < 2 * n -1; i++)
{
if (T[i].parent == -1 && T[i].weight > 0)
{
p1 = i;
break;
}
}
for (j = i + 1; j < 2 * n - 1; j++)
{
if (T[j].parent == -1 && T[j].weight > 0)
{
p2 = j;
break;
}
}
for (i = 0; i < 2 * n - 1; i++)
{
if ((T[p1].weight > T[i].weight) && (T[i].parent == -1) && (p2 != i) && (T[i].weight > 0))
p1 = i;
}
for (j = 0; j < 2 * n - 1; j++)
{
if ((T[p2].weight > T[j].weight) && (T[j].parent == -1) && (p1 != j) && (T[j].weight > 0))
p2 = j;
}
}
/*******加载文件*******/
void LoadHuffmanFile(HuffmanT T)
{ unsigned int i;
int j = 0;
char c;
int a[MAX_C];
FILE *fp;
printf("Input file name: ");
scanf("%s", filename);
if ((fp = fopen(filename, "rb")) == NULL)
{ printf("Can't open %s\n", filename);
exit( 0 );
}
for (i = 0; i < MAX_C; i++)
a[i] = 0;
fseek(fp, 0, SEEK_SET);
while ( 1 )//( !feof(fp) )
{
fread(&c, sizeof(unsigned char), 1, fp);
if (feof(fp)) break;
a[(unsigned int)c]++;
}
fclose(fp);
/*统计输入文件的字符及其权重并存放到树T[]*/
for (i = 0; i < MAX_C; i++)
{
if (a[i] != 0)
{
T[j].ch = (unsigned char)i;
T[j++].weight = (unsigned int)a[i];
}
}
n = j;
}
/*******构造huffam树，T[2 * n - 1]为其根********/
void CreatHT(HuffmanT T)
{
int i,p1,p2;
LoadHuffmanFile(T); //加载被编码文件 for (i = n; i < 2 * n - 1; i++)
{ SelectMin(T, i - 1, p1, p2);
T[p1].parent = T[p2].parent = i;
T[i].lchild = p1;
T[i].rchild = p2;
T[i].weight = T[p1].weight + T[p2 ].weight;
}
}
/*根据Huffman T 求Huffman编码表H*/
void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)
{ int c; //指示T中孩子的位置
int p; //指示T中双亲的位置
int i;
int start; //指示编码在cd中的位置
char cd[N]; //临时存放编码
for (i = 0; i < n; i++) //依次求叶子的编码
{ H[i].ch = T[i].ch; //读入叶子T[i]对应的字符 if (i==0 || i==1) start=n;
else start=n-i+1;
cd[--start]='\0'; //编码起始位置的初值 c = i; //从叶子T[i]开始回溯
while ((p = T[c].parent) >= 0) //直到回溯到T[c]是树根位置 { cd[--start] = (T[p].lchild == c) ? '0' : '1';
c = p;}
strcpy(H[i].bits, &cd[start]); //复制临时编码到编码表中
}
}
/*对文件编码，将结果保存到codefile.txt中*/
void EncodingHuffmanT(HuffmanT T, HuffmanCode H)
{ char c;
FILE *in,*fp;
int j,l;
char encodefile[20],temp[MAX_C];
if ((in = fopen(filename, "rb")) == NULL)
{ printf("Read %s fail!\n", encodefile);
exit(1);}
CharSetHuffmanEncoding(T, H);
printf("Input encode file name: ");
gets( encodefile );
if ((fp = fopen(encodefile, "wb")) == NULL)
{ printf("Write %s fail!\n", encodefile);
exit(1);}
fread(&c, sizeof(unsigned char), 1, in);
fwrite(&c, sizeof(unsigned char), 1, fp);
fseek(in, 0, SEEK_SET);
fseek(fp, 0, SEEK_SET);
while ( 1 )//( !feof( in ))
{ fread(&c, sizeof(unsigned char), 1, in);
if (feof(in)) break;
for (j = 0; j < n; j++)
{if (c == H[j].ch)
{ l = 0;
while (H[j].bits[l] != '\0')
{ temp[l] = H[j].bits[l];
l++;}
int m = 0;
while ( l-- )
{fwrite(&temp[m++], sizeof(unsigned char), 1, fp);}
}
}
}
fclose(fp);
printf("Encoding file has saved into %s!\n", encodefile);
}
/*根据Huffman编码、译码*/
void DecodingHuffmanT(HuffmanT T, HuffmanCode H)
{ int i; //指示Huffman tree叶子个数
FILE *fp,*fp1;
char ch,ch1[20],ch2[20];
printf("Input encode file name: ");
scanf("%s", ch1);
printf("Input decode file name: ");
scanf("%s", ch2);
fp = fopen(ch1, "rb");
fp1 = fopen(ch2, "wb");
//根据Huffman树对Huffman编码译码
i = 2 * n - 2;
fseek(fp, 0L, SEEK_SET);
fseek(fp1, 0L, SEEK_SET);
while (!feof(fp))
{ fread(&ch, sizeof(unsigned char), 1, fp);
if (ch == '0') //若编码为o，则找此结点的左子树；
i = T[i].lchild;
if (ch == '1') //若编码为１，则找此结点的右子树；
i = T[i].rchild;
if (i < n)
{ fwrite(&T[i].ch, sizeof(unsigned char), 1, fp1);
i = 2 * n - 2;
}
}
fclose(fp);
fclose(fp1);
printf("Decoding accomplished!\nThe result has save input %s.\n",ch2); getchar();
}
/*打印Huffman权重表*/
void PrintHuffmanT(HuffmanT T)
{ int i;
FILE *fp;
if ((fp = fopen("treeprint.txt", "wb")) == NULL)
{ printf("Open treeprint.txt fail!\n");
exit(1);
}
printf("\nLeaf&weight of the Huffman tree is below:\n");
for (i = 0; i < n ; i++)
{ if (i % 5 == 0 && i > 0)
printf("\n");
if (T[i].weight > 0)
{ fprintf(fp, "%c:%d ", T[i].ch, T[i].weight);
printf("%c: %d ", T[i].ch, T[i].weight);
}
}
fclose(fp);
printf("\nLeaf&weight of the Huffman tree saved in treeprint.txt\n\n"); }
/*打印Huffman编码表*/
void PrintHuffmanH(HuffmanT T, HuffmanCode H)
{ int i;
FILE *fp;
CharSetHuffmanEncoding(T, H);
if ((fp = fopen("codeprint.txt", "wb")) == NULL)
{ printf("Open codeprint.txt fail!\n");
exit(1);
}
for (i = 0; i < n; i ++)
{ if (i % 10 == 0 && i > 0) printf("\n");
printf("%c: %s\n", T[i].ch, H[i].bits);
fprintf(fp, "%c:%s ", T[i].ch, H[i].bits);
}
fclose(fp);
printf("\nHuffman tree code saved in codeprint.txt!\n\n");
}
/*主菜单*/
void MainMenue()
{ fflush( stdin );
printf("\n********************** Main Menue **************************\n"); printf("** **\n"); printf("** 1. Load to be dealt file. **\n"); printf("** 2. Show Huffman code list. **\n"); printf("** 3. Show Huffman weight list. **\n"); printf("** 4. Encoding Huffman file. **\n"); printf("** 5. Decoding Huffman file. **\n"); printf("** 6. Exit. **\n"); printf("** **\n"); printf("************************************************************\n"); }
/*主函数开始*/
int main()
{
int flag = 1;
char ch[10];
HuffmanT T; //定义Huffman树
HuffmanCode H; //定义Huffman编码表
InitHT(T); //初始化Huffman树
while ( flag )
{ MainMenue();
printf("Please input your choice(1~6): ");
gets( ch );
switch ( ch[0] )
{
case '1': CreatHT(T); break;
case '2': PrintHuffmanH(T, H); break;
case '3': PrintHuffmanT(T); break;
case '4': EncodingHuffmanT(T, H); break;
case '5': DecodingHuffmanT(T, H); break;
case '6': exit(1);
default: printf("Input error!\n"); break;
}
}
return 0;
}
八、测试情况
程序的测试结果如下：
建立哈夫曼树、打印编码表正确。
打印权重表正确。
哈夫曼编码正确。
哈夫曼译码正确，退出正确。 九、参考文献
1、严蔚敏，《数据结构 C 语言》，清华大学出版社。
2、谭浩强，《c 语言程序设计》，清华大学出版社。
小结
课程设计是《数据结构》课程教学必不可缺的一个重要环节，是培养学生综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节。同时可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高分析问题、解决问题，从而运用所学知识解决实际问题的能力。
通过本次数据结构的课程设计，我理解很多之前上课没懂的知识，对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。
这次课程设计是我们大三来做的第一次了，我在编辑中犯了不应有的错误，如设计统计字符和合并时忘记应该怎样保存保存数据，在其他同学的帮助下明确并改正了错误和疏漏，使我们的程序有了更高的质量。在设计过程中逐渐积累了一些基本的经验，所以做到后来逐渐顺利，但也还是会遇到一些这样或那样的问题，通过本次课程设计，进一步适应团队合作开发规模稍大的程序，体会个人开发与团队开发的利弊，加强团队协作与团队内的沟通，表达能力。感受对本专业说学习的多门课程知识进行综合应用，将多门课程的知识融合贯通。
同时通过这次设计也获得一些编程经验：编程时要认真，出现错误要及时找出并改正，遇到问题要去查相关的资料。反复的调试程序，把各个注意的问题要想到；同时要形成自己的调试程序的风格，从每个细节出发，不放过每个知识点。另外，要注意符号的使用。
本次课程设计虽然实现了哈夫曼编码/译码等要求，但由于时间等各方面原因，仍有一些问题没有解决，例如一些要求输入判断时判断不严格、操作界面不够美观等，总体上还有待改进。
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图：
三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include
软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include
授课时间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所示。 ⑶有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。
实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include
//选择两个parent为0，且weight最小的结点s1和s2 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; break; } } 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++)
#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.求每个字符的哈夫曼编码并显示。
实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include
哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include
实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include
cout<<"输入第"<
#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) {
计算机科学与技术学院数据结构实验报告 班级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序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：
常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫
0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。
译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为：
哈夫曼树描述文档 一、思路 通过一个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<
淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅
实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include
int min=11000; int min1; for(int k=0;k 专业基础实践报告 题目哈夫曼树及应用 起讫日期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日 实验八哈夫曼编码的方法和实现 一、实验目的 1.掌握哈夫曼编码的基本理论和算法流程； 2. 用VC++6.0编程实现图像的哈夫曼编码。 二、实验内容 1．画出哈夫曼编码的算法流程； 2．用VC++6.0编程实现哈夫曼编码。 三、实验步骤 （1）启动VC++6.0，打开Dip工程。 （2）在菜单栏→insert→resouce→dialog→new,在对话框模版的非控制区点击鼠标右键，在弹出的对话框中选properties,设置为ID：IDD_DLG_Huffman,C标题：哈夫曼编码表。 （3）在弹出的对话框中，添加如下的按钮等控件： （4）在ResourceView栏中→Menu→选IDR_DIPTYPE ,如图 在图像编码菜单栏下空的一栏中，右键鼠标， 在弹出的对话框中选属性properties，在弹出的对话框中，进行如下的设置 （5）右击哈夫曼编码表菜单栏，在建立的类向导中进行如下设置 （6）在DipDoc.cpp中找到void CDipDoc::OnCodeHuffman()添加如下代码void CDipDoc::OnCodeHuffman() { int imgSize; imgSize = m_pDibObject->GetWidth()*m_pDibObject->GetHeight(); //在点处理CPointPro类中创建用来绘制直方图的数据 CPointPro PointOperation(m_pDibObject ); int *pHistogram = PointOperation.GetHistogram(); //生成一个对话框CHistDlg类的实例 CDlgHuffman HuffmanDlg; /******************************************/ /********* 哈夫曼树的编写与输出***********/ /******************************************/ /*用静态三叉链表实现哈夫曼树类型定义如下：*/ #define N 20 #define M 2*N-1 typedef struct { int weight; int parent; int LChild; int RChild; } HTNode,HuffmanTree[M+1]; /*select函数主体程序代码*/ void select(HuffmanTree ht,int j,& s1,& s2 ) { int i,k; int n=0; HuffmanTree rt; for(k=0;k<=j;k++) { if(ht[k].parent ==0) { rt[k]=ht[k]; n=n+1; } } for(k=0;k int m; m=2*n-1; for(i=n+1;i<=m;i++) { ht[i]={0,0,0,0}; } /*--------初始化完毕，对应算法步鄹(1)---------*/ for(i=n+1;i<=m;i++) { int s1,s2; select(ht,i-1,&s1,$s2); ht[i].weight=ht[s1].weight +ht[s2].weight ; ht[s1].parent=i;ht[s2].parent=i; ht[i].LChild=s1;ht[i].RChild=s2; } } 数据结构实验报告 专业: 班级: 姓名: 学号: 指导老师: 评分: 实验四哈夫曼树的建立及应用 一、实验目的 1、掌握哈夫曼树的基本概念及所有的存储结构。 2、掌握哈夫曼树的建立算法。 3、掌握哈夫曼树的应用（哈夫曼编码和译码）。 二、实习内容 1、给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。 2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一 串二 进制编码，输出它的哈夫曼译码。 三、算法描述 将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。 建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。 要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。 四、程序清单: #include int huff[100];//存储100个权值的数组 void Select(element huffTree[],int m) { int min,min2,i; min=min2=1000; for(i=0;i哈夫曼树及其应用
数字图像实验 哈夫曼编码的方法和实现1234
哈夫曼树的编写与输出
哈夫曼树的建立及应用
相关主题
文本预览