- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
C应用_赫夫曼树
1. 设计思想
本程序将实现从键盘输入一组字线的权值等相关信息,然后
对这些字母进行赫夫曼编码。
主要思想即为赫夫曼算法。
(1 ) 根据给定的 N 个权值构成的 N 棵二叉树的集合 F ,
其中每棵二叉树中只有一个带权为 W 的根结点,其
左右子树均空。
(2 ) 在 F 中选取两棵根结点权值最小的树作为左右子树
构造一棵新的二叉树,且置新的二叉树的根结点的
权值为其左,右子树上根结点的权值之和。
(3 ) 在 F 中删除这两棵树,同时将新得到的二树加入 F
中
(4 ) 重复(2 )和(3 ),直到F 只含一棵树为止。这棵树
便是赫夫曼树。
由于赫夫曼树中没有度为1 的结点则一棵有N 个叶子结点的
赫夫曼树共有 2N-1 个结点,可以存储在一个大小为 2N-1 的
一维数组。如何选定结点结构?由于在构成赫夫曼树之后,
为求编码需从叶子结点出发走一条从叶子到根的路径;而为
译码需从根出发走一条从根到叶子的路径。则对每个结点而
言,既需知双亲的信息,又需知孩子结点的信息。由此,则
作如下程序。
2. 源程序代码
运行结果如下:
#includeiostream.h
#includeiomanip.h
struct huffmantree
{//weight存放字母的权值。
int weight;
int parent,lchild,rchild;
};
void select(huffmantree a[],int p,int s1,int s2)
{//在数组a[1,p]中选择 parent为 0 且 weight 最小的两个结点,其序号分别为
s1,s2.
int q=1;
while(a[q].parent !=0)
++q;
s1=q;
while(q=p)
{
if(a[q].weight a[s1].weight a[q].parent 0)
s1=q;
q++;
}
q=1;
while(a[q].parent !=0q!=s1)
++q;
s2=q;
while(q=p)
{
if(a[q].weight a[s2].weight q!=s1a[q].parent 0)
s2=q;
q++;
}
}
void main()
{
int n;
int m;
do
{cout请输入字母个数;(=10)endl;
cinn;}while(n10);
m=2*n-1;
huffmantree ht[20];
int hc[101];
char s=A;
int i=1;
int j;
int k,a,b;
int start=100;
int s1;
int s2;
for(i,s;i=n;++i,++s)
{//输入数组中前 项的权值,对其余部分全部初始化为 0。
coutPlease enter s`s weightendl;
cinht[i].weight ;
ht[i].parent =0;
ht[i].lchild=0;
ht[i].rchild=0;
}
for(i;i=m;+
您可能关注的文档
- 心率在16排螺旋CT冠状动脉CTA造影成像质量的影响.doc
- xx中学民主评议工作自查自纠报告.doc
- 哥本哈根后展望.pdf
- 如何编制发改委立项用(甲级)盐渍山竹笋项目可行性研究报告(可研报告+甲级+立项+贷款).pdf.pdf
- windows安装与配置习题1-4.doc
- 花生粕生产蛋白纤维-何丽云.doc
- SMT实训日志-模板.doc
- 八大家电企业骗补近亿元 长虹承认格力推诿.doc
- JRC4558中文资料.pdf
- 喜堡西餐咖啡加盟优势.doc
- DB37T 4789-2024 道路路面低噪抗滑超表处技术规程.docx
- DB3301T 0478-2024 义警管理规范.docx
- DB11T 2377-2024 超低能耗公共建筑节能工程施工及验收规程.docx
- DB11T 2385-2024 外保温复合装饰线应用技术规程.docx
- DB37T 4798-2024 国有储备土地资产负债核算技术规.docx
- DB3309T 110-2024 网络攻击诱捕系统管理规范.docx
- DB3502T 168-2024 排水管道非开挖修复技术指南.pdf
- DB3301T 1147-2024 地理标志产品 天目笋干.pdf
- DB3301T 1148-2024 地理标志产品 天目青顶茶.pdf
- DB14T 1293-2016 盆栽百合生产技术规程.docx
文档评论(0)