哈夫曼算法的实现及应用文库

哈夫曼算法的实现及应用文库

ID:44066293

大小:166.00 KB

页数:5页

时间:2019-10-18

哈夫曼算法的实现及应用文库_第1页
哈夫曼算法的实现及应用文库_第2页
哈夫曼算法的实现及应用文库_第3页
哈夫曼算法的实现及应用文库_第4页
哈夫曼算法的实现及应用文库_第5页
资源描述:

《哈夫曼算法的实现及应用文库》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、摘要:哈夫曼树是带权路径长度(WPL)最小的二叉树,通过对哈夫曼算法的研究,提出一种求取哈夫曼树带权路径长度的计算方法和应用。关键词:哈夫曼算法、二叉树、WPL、编码1引言:哈夫曼树是一种特殊的二叉树,又称最优二叉树:假设有一组(无序)实数(wl,w乙w3,w4,...,wm},现要构造一棵以wi(i=l,2,3,4...,m)为权的m个外部结点的扩充二叉树,使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。若I表示从根到第i个外部结点的路径长度,m为外部结点的个数,wi为第i个外部结点的权值,则有WPL=Zw

2、ili(0

3、外部结点离根越近,权值越小的离根越远。2.1.1程序实现:/*哈夫曼树的构造方法*/#include#include#defineMAXINT50#defineMAXNUM50/*数组w屮最多容纳的元素个数,注意m<=MAXNUM*/#defineMAXNODE100/*哈夫曼树中的最大结点数,注意2*m-l

4、uctHtNodeht[MAXNODE];};typedefstructHtTree*PHtTree;/*哈夫曼树类型的指针类型*//*构造具冇m个叶结点的哈夫曼树*/PHtTreehuffmanfintm,int*w){PHtTreepht;inti,j,xl,x2,ml,m2;pht=(PHtTree)malloc(sizeof(structHtTree));/*创建空哈夫曼树*/if(pht==NULL){printf("Outofspace!!H);returnpht;}for(i=0;i<2*m-l;i++){/*置初态*/pht-

5、>ht[i].llink=-1;pht->ht[i].rlink=-1;pht->ht[i].parent=・1;讦(iht[i].ww=w[i];elsepht->ht[i].ww=-1;}for(i=0;iht[j].wwht[j].parent==-1){m2==ml;x2=xl;

6、ml==pht->ht[j].ww;Xl=j;}elseif(pht->ht[j].wwht[j].parent==-1){m2=pht->ht[j].ww;x2=j;}pht->ht[xl].parent=m+i;/*构造一个内部结点*/pht->ht[x2].parent=m+i;pht->ht[m+i].ww=ml+m2;pht->ht[m+i].llink=xl;pht->ht[m+i].rlink=x2;pht->root=m+i;}returnpht;}intmain(){intm=0,j=0,i=0,parent

7、=0;int*w;PHtTreepht;printf("pleaseinputm=”);/*输入外部结点个数*/scanf(”%du,&m);printf("misnotreasonable!");return1;}w=(int*)malloc(sizeof(int)*m);if(w==NULL){printf("overflow!");return1;}printf("pleaseinputthe%dnumbers:",m);/*输入权值*/for(j=0;j

8、w);for(j=0;j

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。