13、利用贪婪法构造哈夫曼编码(1)

数学与计算机学院

课程设计说明书课程名称: 算法设计与分析-课程设计

课程代码: 7106620

题目: 利用贪婪法构造哈夫曼编码

年级/专业/班:

学生姓名:

学号:

开始时间:2010 年12 月26日

完成时间:2011 年01 月09 日课程设计成绩：

学习态度及平时成绩（30）技术水平与实际

能力（20）

创新（5）说明书撰写质量（45）

总分

（100）

指导教师签名：年月日

目录

1 引言 (1)

1.1问题的提出 (1)

1.2国内外研究的现状 (1)

1.3任务与分析 (4)

2 程序的主要功能 (4)

2.1定义结构体 (4)

2.2动态存储 (4)

2.3静态存储 (4)

2.4哈夫曼算法 (4)

2.5选择结点编码 (4)

3 总体设计 (5)

3.1数据存储结构设计 (5)

3.2操作模块设计 (6)

3.3建树算法设计 (6)

4 结构体的说明 (7)

5 模块分析 (7)

5.1静态存储选择最小结点的算法 (7)

5.2静态存储哈夫曼编码 (8)

5.3动态存储选择最小结点的算法 (9)

5.4动态存储哈夫曼编码 (10)

6 系统测试 (12)

6.1设计测试数据 (12)

6.2静态存储测试结果及分析 (12)

6.3动态存储测试结果及分析 (13)

7 结论 (14)

8 参考文献 (14)

致谢 (15)

摘要

哈夫曼编码是哈夫曼树的一个应用。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

关键词：哈夫曼树，哈夫曼编码，最优二叉树，贪婪法

1 引言

1.1 问题的提出

随着计算机的普及，网络进入大众的家庭，算法在现实生活中也越来越重要，算法在现实生活中应用节约大量时间和空间，算法是计算机专业重要的一门专业基础课,也是学生最先接触到的专业课,该课程的掌握情况直接影响后继课程的深入学习以及学生软件开发能力的培养及提高。

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。

1.2国内外研究的现状

随着计算机科学的蓬勃发展，社会已进入信息时代。电子计算机和通信网络的广泛应用，一方面为人们的工作和生活提供了很大的方便，另一方面也提出了许多亟待解决的问题，其中信息的安全性就是一个突出的问题。因此，密码学理论和技术已成为信息科学和技术中的一个重要领域。随着计算机网络的迅速发展，特别是近年来电子商务的兴起，现代密码学的应用已不仅仅局限于政治、军事以及外交等领域，其商用价值和社会价值也已得到了充分的肯定。而哈夫曼编码是其中一个重要应用之一。

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG 中就应用了哈夫曼编码。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL 是最小的。

哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最

短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）

然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述：

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步，直到集合F中只有一棵二叉树为止。

用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构：struct tree{

float weight; /*权值*/

union{

char leaf; /*叶结点信息字符*/

struct tree *left; /*树的左结点*/

};

struct tree *right; /*树的右结点*/

};

struct forest{ /*F集合，以链表形式表示*/

struct tree *ti; /* F中的树*/

struct forest *next; /* 下一个结点*/

};

例：若字母A，B，Z，C出现的概率为：0.71,0.54,0.28,0.43；则相应的权值为：75，54，28，43。

构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c 的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。

这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes 的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。

因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。

前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编

码和解码的程序。

1.3任务与分析

本课题主要的任务是使用贪婪法构造哈夫曼编码，就是要通过构造哈夫曼树来实现。主要任务：

（1）给出静态存储方式下的Huffman编码算法并编程实现；

（2）给出动态存储方式下的Huffman编码算法并编程实现；

通过此课题，能加深对贪婪法的理解，具有初步的独立分析和设计能力，提高综合运用所学理论知识和方法独立分析和解决问题的能力。

2 程序的主要功能

2.1定义结构体

定义一个结构体反映二叉树每个结点的包含内容，包含数据域和左右指针域

2.2动态存储

按照动态存储方式存储结点。

2.3 静态存储

了解存储的长度分配存储空间，。

2.4哈夫曼算法

熟悉贪婪法，选择贪婪发进行哈夫曼编码。

第一步：初始化n个单节点的树，并为它们标上字母表中的字符。把每个字符的概率记在树的根中，用来指出树的权重。

第二步：重复下面的步骤，直到只剩一棵单独的树。找到两棵权重最小的树。把它们作为新树中的左右子树，并把权重之和作为新的权重记录在新树的根中。

2.5选择结点编码

选择合适的算法，从中选择连个最小的结点编码。

3 总体设计

图1 总体结构设计

3.1 数据存储结构设计

(1) 哈夫曼树的存储结构设计

对于哈夫曼编码问题，在构造哈夫曼树时要求能方便地实现从双亲点到左右孩子结点的操作，在进行哈夫曼编码时又要求能方便地实现从孩子到双亲结点的操作。因此，设计哈夫曼树的存储结构为双亲孩子存储结构如图(一)。

weight

Parent

leftChild ringthChild

表(一)

哈夫曼树的结点存储结构设计如下： typedef struct {

int weight; //权值

int parent;

//双亲结点下标 int leftChild;

//左孩子下标 int rightChild; //右孩子下标 }HaffNode;

//哈夫曼树的结点结构

(2) 哈夫曼编码的存储结构设计

对于存放哈夫曼编码数据元素的结构，由于哈夫曼编码是不等长编码，所以存放编码的数组必须有 一个start 来存储数组中码字的起始位置。如图(二)。 start

Bit[0]

Bit[1]

………… Bit[MaxBit-1]

表(二)

主函数

哈夫曼编码

调用选择算法 输出哈夫曼编码

存放哈夫曼编码的数组元素的存储结构设计如下：

typedef struct { int bit[MaxN];

//数组

int start; //编码的起始下标值

int weight;

//字符的权值

}Code;

//哈夫曼编码的结构

3.2 操作模块设计

(1) 此模块构造了一个函数Haffman()用来建立叶结点的个数为n 权值数组为

weight 的哈夫曼树haffTree

(2) 此模块构造了一个函数HaffmanCode()用来将n 个结点的哈夫曼树

haffTree 构造成哈夫曼编码haffCode

(3) 此模块构造了一个函数HaffmanCoding()根据每个结点的编码hcode 对哈夫

曼编码strcode 进行译码，此函数调用了一个字符匹配函数BFIndex()。 (4) 字符匹配函数BFIndex(),由BF 算法改造而成，函数的功能是确认当前子串

是否在母串的前部，如果是返回1否则返回0。

(5) 主函数模块main()用来进行字符串的输入和各个函数模块的调用和结果的

显示等。

3.3 建树算法设计

(3) 在给定的n 个取值12{,,}n w w w 构造n 棵只有根结点的二叉树，从而得到

一个二叉树森林12{,,}n F T T T 。

(4) 在二叉树森林F 中选取根结点的权值最小和次小的两棵二叉树作为左右树

构造心的二叉树，此时，新的二叉树的根结点权值为左右子树根结点权值之和。

(5) 在二叉树森林F 中删除作为心二叉树左右子树的两棵二叉树，将新二叉树

假如到二叉树森林F 中。 (6) 重复步骤（2）和（3），当二叉树森林F 中只剩下一棵二叉树时，这棵二叉

树就是所构造的哈夫曼树。

4 结构体的说明

静态存储结构体定义

typedef struct

{

int weight;

int parent,lchild,rchild;

}HTnode,*Huffmantree;

typedef char **Huffmancode;

动态存储结构体定义

typedef struct node

{

int weight;

int parent,lchild,rchild;

int loca;

struct node *next,*father;

}node,*Huffmantree;

5 模块分析

5.1 静态存储选择最小结点的算法

依次遍历静态存储结构选出权值最小的两个结点；核心代码如下：

void select(Huffmantree HT,int k,int *s1,int *s2)

{ //赫夫曼树HT中选paren为0且权值最小的两结点，s1，s2 int i,j=1,min,e;

while(HT[j].parent !=0) j++;

if(j>k) {printf("无空闲结点！\n");exit(0);}

else min=HT[j].weight ;

for(i=1;i<=k;i++)

if((HT[i].weight

{ j=i;min=HT[i].weight ;}

e=*s1=j;j=1;

while(HT[j].parent !=0||j==*s1)

j++;

if(j>k) {printf("无空闲结点！\n");exit(0);} else min=HT[j].weight ;

for(i=1;i<=k;i++)

if((HT[i].weight

{ j=i;min=HT[i].weight ;}

*s2=j;

}

5.2静态存储哈夫曼编码

选择贪婪法在静态存储方式下编制哈夫曼；核心代码如下：

void Huffmancoding(Huffmantree *HT,Huffmancode *HC,int w[],int n) {

int i,m,c,s1,s2,start,f;

//char * cd;

Huffmantree p;

if(n<=1) {printf("无法构成树！\n");exit(0);}

m=2*n-1;

*HT=(Huffmantree)malloc((m+1)*sizeof(HTnode)); //0号单元未用

for(p=*HT+1,i=1;i<=n;i++,++p )

{ (*p).weight =w[i];

printf("HT[%d].weight=%d\n",i,(*p).weight );

(*p).lchild =0; (*p).parent =0; (*p).rchild =0;

}

for(;i<=m;i++,++p)

{ (*p).weight =0; (*p).lchild =0; (*p).parent =0;

(*p).rchild =0;

}

for(i=n+1;i<=m;++i)

{ 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;

printf("HT[%d] andHT[%d] --> HT[%d].weight\n",s1,s2,i,(*HT)[i].weight);

}

*HC=(Huffmancode)malloc((n+1)*sizeof(char *));

char *cd;

cd=(char *)malloc(n*sizeof(char));

cd[n-1]='\0';

printf("HuffmanTree Code is as follows :");

for(i=1;i<=n;++i)

{ start=n-1;

for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)

if((*HT)[f].lchild==c)

cd[--start]='0';

else cd[--start]='1';

(*HC)[i]=(char*)malloc((n-start)*sizeof(char));

strcpy((*HC)[i],&cd[start]);

printf("\nHT[%d].weight=%d node's Huffman code is: %s",i,(*HT)[i].weight,(*HC)[i]);

}

free(cd);

}

5.3动态存储选择最小结点的算法

依次遍历动态存储结构选出权值最小的两个结点；核心代码如下：

void select(Huffmantree HT,int k,Huffmantree *s1,Huffmantree *s2)

{

int i,j=1,min,e; Huffmantree p,q; p=HT;

while(p)

{ if(p->parent!=0)

{ j++;p=p->next ; }

else break;

}

if(j>k) {printf("无空闲结点！\n");exit(0);}

else min=p->weight ;q=HT;

for(i=1;i<=k;i++)

{ if((q->weight parent ==0))

{ j=i;min=q->weight ;p=q;}

q=q->next ; if(q==NULL) break;

}*s1=p; e=j;j=1; p=HT;

while(p)

{ if(p->parent !=0||j==e)

{j++;p=p->next ;}

else break;

}

if(j>k) {printf("无空闲结点！\n");exit(0);} else min=p->weight ;q=HT;

for(i=1;i<=k;i++)

{ if((q!=(*s1))&&(q->weight parent ==0))

{ j=i;min=q->weight ;p=q;}

if(q==NULL) break;

q=q->next ;

}*s2=p;

}

5.4动态存储哈夫曼编码

选择贪婪法在动态态存储方式下编制哈夫曼；核心代码如下：

void Huffmancoding(Huffmantree *HT,Huffmancode *HC,int w[],int n) {int i,m,c,start,f;

Huffmantree s1,s2, p,q,q1;

if(n<=1) {printf("无法构成树！\n");exit(0);}

m=2*n-1;

*HT=(Huffmantree)malloc(sizeof(node));

for(p=*HT,i=1;i<=n;i++)

{ (*p).weight =w[i];

printf("HT[%d].weight=%d\n",i,(*p).weight );

(*p).lchild =0; (*p).parent =0; (*p).rchild =0;

(*p).loca =i;

if(i<=n-1)

{q=(Huffmantree)malloc(sizeof(node));

p->next=q; p=q;}

}

p->next =NULL;

for(i=n+1;i<=m;++i)

{ q1=(Huffmantree)malloc(sizeof(node));

select(*HT,i-1, &s1,&s2);

s1->parent =i; s2->parent =i;

q1->lchild =s1->loca ; q1->rchild =s2->loca;

q1->loca=i;q1->parent=0;

q1->weight =s1->weight+s2->weight;

s1->father=q1;s2->father=q1;

p->next=q1;p=q1;

printf("HT[%d]andHT[%d]-->HT[%d].weight\n",s1->loca ,s2->loca ,i,p->weight);

}p->next =NULL;

*HC=(Huffmancode)malloc((n+1)*sizeof(char *));

char *cd;

cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0';

printf("HuffmanTree Code is as follows :"); p=*HT;

for(i=1;i<=n;++i)

{ start=n-1; q=p;

for(c=i,f=q->parent,q1=q->father;f!=0;c=f,f=q1->parent,q1=q1->father)

if(q1->lchild==c) d[--start]='0'; else cd[--start]='1';

(*HC)[i]=(char*)malloc((n-start)*sizeof(char)); strcpy((*HC)[i],&cd[start]);

printf("\n %d node's Huffman code is: %s",p->weight,(*HC)[i]); p=p->next ;

}free(cd); printf(" \n "); }

6 系统测试

6.1设计测试数据

图2

6.2静态存储测试结果及分析

当运行程序时首先跳出界面如下：

图3

1

6

7

2

5

输入各结点权值后运行结果如下：

图4 6.3动态存储测试结果及分析

当运行程序时首先跳出界面如下：

图5

输入各结点权值后运行结果如下：

图6

7 结论

通过这次实验，我掌握了哈夫曼树的建立方法，以及哈夫曼编码的方法，从而设计出了哈夫曼编码算法。本程序中规定了字符串的长度，如果超过定义的长度程序后给出提示并且退出，字符串的长度可在程序开始处进行修改。通过这次实验，使我对哈夫曼树和哈夫曼编码以及译码有了更深的认识并且有了一定的掌握，通过编写程序，还提高了我C语言的使用能力和程序纠错能力。

8 参考文献

[1] 严蔚敏吴伟民编著. 数据结构（c语言版）. 清华大学出版社，2004

[2] 陈天华编著. 面向对象程序设计与Visual C++ 6.0教程 .清华大学出版社 2006

[3] Anany Levitin 著. 潘彦译. 算法设计与分析基础（第2版）.清华大学出版社2007

致谢

首先需要感谢的是指导老师谢春芝老师和分别教我数据结构、算法设计与分析的宋文老师、黄襄念老师，感谢他们给了我们这个自己独立做课程设计的机会。在整个完成的过程中周围的同学给了不少帮助，而且帮忙解决了很多想不通的问题，在此衷心地感谢他们！有进步是因为有帮助！真诚地谢谢你们！

附录：

动态代码：

#include

#include

#include

typedef struct node

{

int weight;

int parent,lchild,rchild;

int loca;

struct node *next,*father;

}node,*Huffmantree;

typedef char **Huffmancode;

void select(Huffmantree HT,int k,Huffmantree *s1,Huffmantree *s2)

{

int i,j=1,min,e;

Huffmantree p,q;

p=HT;

while(p)

{

if(p->parent!=0)

j++;p=p->next ;

else break; }

if(j>k) {printf("无空闲结点！\n");exit(0);}

else min=p->weight ;q=HT;

for(i=1;i<=k;i++)

{

if((q->weight parent ==0))

{ j=i;min=q->weight ;p=q;}

q=q->next ;

if(q==NULL) break; }

*s1=p;e=j;j=1; p=HT;

while(p)

{

if(p->parent !=0||j==e)

{j++;p=p->next ;}

else break; }

if(j>k) {printf("无空闲结点！\n");exit(0);}

else min=p->weight ;q=HT;

for(i=1;i<=k;i++)

{

if((q!=(*s1))&&(q->weight parent ==0))

{ j=i;min=q->weight ;p=q;}

if(q==NULL) break;

q=q->next ; }

*s2=p;}

void Huffmancoding(Huffmantree *HT,Huffmancode *HC,int w[],int n)

{

int i,m,c,start,f;

//char * cd;

Huffmantree s1,s2, p,q,q1;

if(n<=1) {printf("无法构成树！\n");exit(0);}

m=2*n-1;

*HT=(Huffmantree)malloc(sizeof(node));

for(p=*HT,i=1;i<=n;i++)

{ (*p).weight =w[i];

printf("HT[%d].weight=%d\n",i,(*p).weight );

(*p).lchild =0; (*p).parent =0;

(*p).rchild =0; (*p).loca =i;

if(i<=n-1)

{q=(Huffmantree)malloc(sizeof(node));

p->next=q; p=q;}}

p->next =NULL;

for(i=n+1;i<=m;++i)

{

q1=(Huffmantree)malloc(sizeof(node));

select(*HT,i-1, &s1,&s2);

s1->parent =i; s2->parent =i; q1->lchild =s1->loca ; q1->rchild =s2->loca;

q1->loca=i;q1->parent=0; q1->weight =s1->weight+s2->weight;

s1->father=q1;s2->father=q1; p->next=q1;p=q1;

printf("HT[%d]andHT[%d]-->HT[%d].weight\n",s1->loca ,s2->loca ,i,p->weight);

}p->next =NULL;

*HC=(Huffmancode)malloc((n+1)*sizeof(char *));

char *cd; cd=(char *)malloc(n*sizeof(char));

cd[n-1]='\0'; printf("HuffmanTree Code is as follows :");

p=*HT;

for(i=1;i<=n;++i)

{ start=n-1; q=p;

for(c=i,f=q->parent,q1=q->father;f!=0;c=f,f=q1->parent,q1=q1->father)

if(q1->lchild==c) cd[--start]='0';

else cd[--start]='1';

(*HC)[i]=(char*)malloc((n-start)*sizeof(char));

strcpy((*HC)[i],&cd[start]);

printf("\n %d node's Huffman code is: %s",p->weight,(*HC)[i]); p=p->next ; } free(cd); printf(" \n ");}

void main()

{

Huffmantree HT;

Huffmancode HC;

int w[20],i,n;

w[0]=0;

printf("\n 动态存储方式\n输入编码个数n=");

scanf("%d",&n);

printf("输入结点值：\n");

for(i=1;i<=n;i++)

scanf("%d",&w[i]);

Huffmancoding(&HT,&HC,w,n);

}

静态代码：

#include

#include

#include

typedef struct

{

int weight; int parent,lchild,rchild;

}HTnode,*Huffmantree;

typedef char **Huffmancode;

void select(Huffmantree HT,int k,int *s1,int *s2)

{ //赫夫曼树HT中选paren为0且权值最小的两结点，s1，s2 int i,j=1,min,e;

while(HT[j].parent !=0) j++;

if(j>k) {printf("无空闲结点！\n");exit(0);}

else min=HT[j].weight ;

for(i=1;i<=k;i++)

if((HT[i].weight

{ j=i;min=HT[i].weight ;}

e=*s1=j;j=1;

中衡算法分析与【设计明细】-实验二-哈夫曼编码

昆明理工大学信息工程与自动化学院学生实验报告 （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 #include #include typedef struct { unsigned int weight; unsigned int parent,LChild,RChild; } 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; 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++) { if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { if((*ht)[i].weight<(*ht)[min].weight)

贪心算法构造哈夫曼树

软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include #include #include #include typedef struct Node{ //定义树结构 int data; struct Node *leftchild; struct Node *rightchild; }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));

哈夫曼树及其应用(完美版)

数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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.求每个字符的哈夫曼编码并显示。

实验三.哈夫曼编码的贪心算法设计

实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include #include #include typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 ∑=j i k k a

//选择两个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++)

哈夫曼树的建立与操作

实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include using namespace std; typedef char Elemtype; struct element { int weight; Elemtype date; element* lchild,*rchild; }; class HuffmanTree { public: HuffmanTree()//构造函数 { cout<<"请输入二叉树的个数"<>count; element *s=new element[count];//s为指向数组的指针，保存指向数组的地址 for(int i=0;i>s[i].weight;

cout<<"输入第"<>s[i].date; s[i].lchild=NULL; s[i].rchild=NULL; }//以上为初始化每一个结点 element * *m=new element*[count];//m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址 for(int i=0;iweightweight; return1=i; } } for(int i=0;iweightweight>a) { b=m[i]->weight; return2=i; } } q=new element;//构建一棵新树 q->weight=m[return1]->weight+m[return2]->weight; q->lchild=m[return1]; q->rchild=m[return2]; m[return1]=q; m[return2]=NULL; //用新树替换原来的两子树,并置空一个数 } boot=q;//把最后取得的哈夫曼树的头结点即q赋值给boot

哈夫曼编码算法实现完整版

实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include #include #include #include typedef struct{ char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree &HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weights2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp;} p[s1].parent=j;

0023算法笔记——【贪心算法】哈夫曼编码问题

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的前缀码长。则平均码长定义为：

数据结构哈夫曼树的实现

#include #include #include #include using namespace std; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild,ch; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 int m,s1,s2; HuffmanTree HT; void Select(int n){ //选择两个权值最小的结点 int i,j; for(i=1;i<=n;i++){ if(!HT[i].parent){ s1 = i;break; } } for(j=i+1;j<=n;j++){ if(!HT[j].parent){ s2 = j;break; } } for(i=1;i<=n;i++){ if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){ s1=i; } } for(j=1;j<=n;j++){ if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)) s2=j; } } void HuffmanCoding(HuffmanCode HC[], int *w, int n) { // w存放n个字符的权值(均>0)，构造哈夫曼树HT，// 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; int start; if (n<=1) return;

哈夫曼树建立、哈夫曼编码算法的实现

#include /*2009.10.25白鹿原*/ #include /*哈夫曼树建立、哈夫曼编码算法的实现*/ #include typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/ typedef struct { unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/ }HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/ void select(HuffmanTree *ht,int n, int *s1, int *s2) { int i; int 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 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) {

哈夫曼编码_贪心算法

淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验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 #include using namespace std; struct huffman { double weight; int lchild,rchild,parent; }; static int i1=0,i2=0; int Select(huffman huff[],int i) { ∑=j i k k a

int min=11000; int min1; for(int k=0;k

4+四+贪心算法+习题参考答案

第四章作业 部分参考答案 1． 设有n 个顾客同时等待一项服务。顾客i 需要的服务时间为n i t i ≤≤1,。应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。 策略： 对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,n i i i 即可。 解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为 ,2)2()1(1221--+++-+-=n n j j j j t t t n t n T 则在总等待时间T 中1j t 的权重最大，jn t 的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。 证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。 记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T 都不减。即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~ ，则有.~ T T ≥ 由于 ,2)2()1(1221--+++-+-=n n i i i i t t t n t n T ,2)()()2()1(1221--+++-++-++-+-=n n j i i i i i i i t t t j n t i n t n t n T ,2)()()2()1(~ 1221--+++-++-++-+-=n n i j i i i i i i t t t j n t i n t n t n T 则有 .0))((~ ≥--=-i j i i t t i j T T 同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。

贪心法构造哈夫曼树

实验报告 （ 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 #include #include #include typedef struct Node{ //定义树结构 int data; struct Node *leftchild; struct Node *rightchild;

}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;

贪心算法概论

贪心算法概论 贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间 复杂度低等特点。是信息学竞赛中的一个有为武器，受到广大同学们的青睐。本 讲就贪心算法的特点作些概念上的总结。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入，它的解是由这n 个输入的某个子集组成，并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。目标函数最大（或最小）的可行解，称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。 除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最 优解进行分枝定界。 b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。 动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模）得到当前最优策略，从而避免了重复的搜索。 举例说明：求多段图的最短路径。

在图（1）中，我们省略了各线段的长度。 如果用回溯法，搜索树大致如下： 显然，上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别被调用了9次，从节点5、6、7到节点11也分别搜索了3次。 如果先算出节点8、9、10到11的最短路，由于它与前面的点无关，因此最优值确定下来，再用它们求定节点5、6、7 到节点11 的最短路径。同理，再用节 点5、6、7 的最优值，来求节点2、3、4 优值。最后从节点2、3、4 推出1 到 11的最优值。显然复杂度大为降低。 当然，如果本题把简单搜索改为搜索＋记忆化的方法，则就是得能动态规划的原理，本质上就是动态规划，只是实现的方法不同与传统的表格操作法。搜索＋记忆化算法有其特有的特点，以后再讨论。 c)贪心算法则不同，它不是建立在枚举方案的基础上的。它从前向后，根据当前情况，“贪心地”决定出下一步，从而一步一步直接走下去，最终得到解。 假如上面的例子中，我们定下这样的贪心策略：节点号k%3= =1。则有图3：

哈夫曼编码的JAVA实现课程设计

哈夫曼编码的JAVA实现课程设计 目录 摘要 (2) 一、问题综述 (2) 二、求解方法介绍 (3) 三、实验步骤及结果分析 (4) 四、程序设计源代码 (5) 参考文献 (8)

摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。 关键字：哈夫曼编码JA V A语言类方法 一、问题综述 1 哈夫曼编码的算法思想 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树 把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。 1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。 1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。 1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。 1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。 1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。 2 构造哈夫曼树的算法 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。

哈夫曼编码及其应用论文

青岛农业大学本科生课程论文 题目：哈夫曼编码及其应用姓名： 学院： 专业： 班级： 学号： 指导教师： 2012 年06 月27 日

青岛农业大学课程论文任务书 论文题目哈夫曼编码及其应用 要求完成时间 2012年 06 月 29 日 论文内容（需明确列出研究的问题）：研究哈夫曼编码的目的就是为了更深入的了解哈夫曼编码，更好的了解哈夫曼编码的作用，更好地使用它解决现实生活中的问题。假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出二进制码字，平均码长和编码效率，总结此编码方法的特点和应用。 资料、数据、技术水平等方面的要求论文要符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点和见解。内容要理论联系实际，计算数据要求准确，涉及到他人的观点、统计数据或计算公式等要标明出处，结论要写的概括简短。参考文献的书写按论文中引用的先后顺序连续编码。 指导教师签名：年月日

哈夫曼编码及其应用 信息与计算科学专业（姓名） 指导教师（老师姓名） 摘要：哈夫曼在1952年提出了一种构造最佳码得方法,我们称之为哈夫曼编码(Huffman Coding)。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的不足直接制约了它的广泛应用。范式哈夫曼编码及译码算法的出现, 解决了其应用的不足。本文主要介绍了哈夫曼编码及范式哈夫曼编码的诸多应用。 关键词：哈夫曼编码；应用；范式哈夫曼编码；多元哈夫曼编码

Huffman coding and its application Student majoring in Information and Computing Science Specialty （英文名） Tutor （老师英文姓名） Abstract: in 1952 Huffman proposes a structure optimal coding method, we call the Huffman code ( Huffman Coding ). Huffman coding applied to how far the independent source for multiple independent sources, it is the optimal code. But its shortcomings directly restrict its wide application. Canonical Huffman coding and decoding algorithm, solves the shortcomings of the application. This paper mainly introduced the Huffman coding and Huffman coding of many application paradigm. Key words :The Huffman code Application Canonical Huffman coding Multiple Huffman coding

贪心法-C语言-霍夫曼编码

贪心算法 霍夫曼编码 学院计算机科学与软件姓名XXX 班级XXXXXX 学号XXXX 课程名称计算机算法设计与分析教师韩其睿 日期： 2015 年 4 月 22 日

【实验题目】 设需要编码的字符集为{ d 1,d 2,…,d n }它们出现的频率为{ p 1,p 2,…,p n },应用霍夫曼树构造最短的非等长编码。 【实验要求】 证明霍夫曼编码问题具有最优子结构性质和贪心选择性质，设计贪心算法求解霍夫曼编码问题，编写实验程序，给出测试数据和测试结果。 【实验目的】 1）掌握贪心选择性质的证明方法。 2）掌握贪心法的设计思想并能熟练运用。 【实验思路】 设需要编码的字符集为{ d 1,d 2,…,d n }它们出现的频率为{ p 1,p 2,…,p n }, 以d 1,d 2,…,d n 作为叶子结点，p 1,p 2,…,p n 作为叶子结点的权值，构造一棵霍夫曼树，规定霍夫曼树的左子树代表0，右子树代表1，由根结点到叶子结点经过的路径组成的0和1的序列是该叶子结点对应字符的编码，即霍夫曼编码。 霍夫曼树共有2n-1个结点，设置一个数组ht[2n-1]保存霍夫曼树中各结点的信息。数组元素结构为 weight ：结点的权值 lchild ：结点的左孩子结点在数组中的下标. rchild ：结点的右孩子结点在数组中的下标 parent ：结点的双亲结点在数组中的下标 【算法源码】 #include #include #include typedef struct { unsigned int weight; //存放权值 unsigned int parent,LChild,RChild; } HTNode, *HuffmanTree; typedef char *HuffmanCode; //选择两个双亲为0，且权重最小的结点s1和s2

哈夫曼树 实验报告

计算机科学与技术学院数据结构实验报告 班级 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作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10

哈夫曼编码的方法

1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律

使用缺省的哈夫曼编码表有

解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;