共有回帖数 0 个
-
#include stdio.h
#include stdlib.h
#define MaxSize 50
typedef struct{
char c; //代码;
int w; //代码权值;
char code[MaxSize]; //代码的Huffman编码;
}HuffCode[MaxSize];
typedef struct{
int Weight; //权值;
int LChild,RChild,Parent;
}HTNode,HuffTree[MaxSize];
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc); //生成Huffman树;
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2); //查找最小和次小序号;
void HuffmanCode(HuffTree HT,int len,HuffCode hc); //生成Huffman编码;
//================================================================================
int main(void)
{
HuffTree HT; //Huffman树;
HuffCode HC; //Huffman编码;
int i,len;
printf(" Huffman编码生成程序 ttby Haroldi.nn 请帮助评价一下思路及改善意见!t多谢了:-)...nnnn");
printf("n输入代码数量："); scanf("%d",&len); system("cls");printf("代码数量：%2dnn",len);
printf("输入代码及权值(e.g.: "a16[回车]" )：n");
for(i=1;i = len;i++)
{
while(getchar() != 'n') NULL;
printf("No.%2d： ",i);
HC.c = getchar();
scanf("%d",&HC.w);
}
HuffmanTree(HT,len,HC);
HuffmanCode(HT,len,HC);
printf("n输出Huffman编码：n");
for(i = 1;i=len;i++)
{
printf("n %c :",HC.c);
puts(HC.code);
}
//测试Huffman树结构;
printf("nn输出Huffman树结构：");system("pause");
printf("nHT:t权值t双亲t左孩子t右孩子n");
for(i = 1;i2*len;i++)
{
if(i = len) printf("(%c)",HC.c);
printf("%2d:t %2d;t%2d,t %2d,t %2d.n",
i,HT.Weight,HT.Parent,HT.LChild,HT.RChild);
}
return 0;
}
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc) //Huffman树初始化;
{
int i,min1,min2;
HT[0].Weight = 65535;
for(i = 1;i = length;i++)
{
HT.Weight = hc.w;
HT.LChild = HT.RChild = HT.Parent = -1;
}
for(;i 2*length;i++) //i初值 = length+1;
{
HT.LChild = HT.RChild = HT.Parent = -1;
}
for(i = length+1;i 2*length;i++)
{
SelectHTNode(HT,i,&min1,&min2);
HT[min1].Parent = i;
HT[min2].Parent = i;
HT.LChild = min1;
HT.RChild = min2;
HT.Weight = HT[min1].Weight + HT[min2].Weight;
}
}
//================================================================================
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2) //查找最小和次小序号;
{
int i;
*min1 = *min2 = 0;
for(i = 1;i n;i++)
{
if(HT.Parent == -1)
{
if(HT[*min1].Weight = HT.Weight)
{
*min2 = *min1;
*min1 = i;
}
else if(HT[*min2].Weight HT.Weight) *min2 = i;
}
}
}
//================================================================================
void HuffmanCode(HuffTree HT,int len,HuffCode hc) //生成Huffman编码;
{
int i,j,tc,Stack[MaxSize],top = -1;
char flag[MaxSize];
HTNode th;
for(i = 1;i = len;i++)
{
top = -1; //栈初始化;
j = 0; //hc.code串首位置偏移;
th = HT; //当前结点th;
tc = i; //当前结点标记tc;
while(th.Parent != -1)
{ //当前结点th双亲P入栈,由P的孩子是th,确定flag;确定下次结点标记tc;
Stack[++top] = th.Parent;
if(HT[th.Parent].LChild == tc) {flag[top] = 'L'; tc = th.Parent;}
if(HT[th.Parent].RChild == tc) {flag[top] = 'R'; tc = th.Parent;}
th = HT[Stack[top]]; //下一结点;
}
while(top != -1)
{
if(flag[top] == 'L') hc.code[j++] ='0';
else hc.code[j++] ='1';
Stack[top--]; //出栈;
}
hc.code[j] =' '; //当前串结束;
}
}
//================================================================================
哈夫曼树
在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(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中只有一棵二叉树为止��
给定4个叶子结点① ，②，③ 和④，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
©WPL=7*1+5*2+2*3+4*3=35
其中©树的WPL最小，可以验证，它就是哈夫曼树。
(a)
○
/
○ ○
7/ 5 2/ 4
① ② ③ ④
(b)
○
/ 2
○ ③
4/
④ ○
7/ 5
① ②
©
○
7/
① ○
5/
② ○
2/ 4
③ ��
楼主 2016-06-09 09:48 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
