


下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、#include<string.h>#include<stdlib.h> #include<stdio.h> int m,s1,s2;typedef structunsigned intweight;unsigned intparent,lchild,rchild;HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树 typedef char *HuffmanCode;/ 动态分配数组存储哈夫曼编码表void Select(HuffmanTree HT,int n) int i,j;for(i = 1;i <= n;i+)if(!HT
2、i.parent)s1= i;break;for(j = i+1;j <= n;j+)if(!HTj.parent)s2= j;break;for(i = 1;i <= n;i+) if(HTs1.weight>HTi.weight)&&(!HTi.parent)&&(s2!=i)s1=i;for(j = 1;j <= n;j+) if(HTs2.weight>HTj.weight)&&(!HTj.parent)&&(s1!=j)s2=j;*w,0号n)/算法 6.13/w存放n个字符的权值(均0),
3、构造哈夫曼树/并求出 n 个字符的哈夫曼编码HCinti, j;char*cd;intp;intcdlen;void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC, intintHT,if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 单元未用for (i=1; i<=n; i+) / 初始化 HTi.weight=wi-1; HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for (i=n
4、+1; i<=m; i+) / 初始化HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;puts("n 哈夫曼树的构造过程如下所示: "); printf("HT 初态 :n结点 weight parent lchild rchild"); for (i=1; i<=m; i+)printf("n%4d%8d%8d%8d%8d",i,HTi.weight,HTi.parent,HTi.lchild, HTi.rchild);printf(" 按任意键,继续 .
5、");getchar();for (i=n+1; i<=m; i+) / 建哈夫曼树/ 在 HT1.i-1 中选择 parent 为 0 且 weight 最小的两个结点,/ 其序号分别为 s1 和 s2。Select(HT, i-1);HTs1.parent = i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight printf("nselect: s1=%d printf(" 结点 weight for (j=1; j<=i; j+)+ HTs2.w
6、eight; s2=%dn", s1, s2); parent lchild rchild");HTj.parent,HTj.lchild,按任意键,继续 .");HTj.rchild);printf("n%4d%8d%8d%8d%8d",j,HTj.weight,printf(" getchar();/ 无栈非递归遍历哈夫曼树,求哈夫曼编码cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空间 p = m; cdlen = 0;for (i=1; i<=m; +i) / 遍历哈夫曼树时
7、用作结点状态标志 HTi.weight = 0;while (p) if (HTp.weight=0) / 向 左HTp.weight = 1;if (HTp.lchild != 0) p = HTp.lchild; cdc dlen+ ='0' else if (HTp.rchild = 0) / 登记叶子 结点的字符的编码HCp(char *)malloc(cdlen+1)sizeof(char);cdcdle n ='0'strcpy(HCp, cd);/复制编码(串) else if (HTp.weight=1) / 向右HTp.weight = 2;i
8、f (HTp.rchild !=0) p = HTp.rchild;cdcdlen+ ='1' else / HTp.weight=2,退回退到父结点,编码长度减1HTp.weight = 0; p = HTp.pare nt; -cdle n;/Huffma nCodi ngintmai n()HuffmanTreeHT;HuffmanCode *HC;int *w,n,i;puts("输入结点数:");sca nf("%d",&n); getchar();HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode);w = (i nt*)malloc( n*sizeof(i nt);printf("输入c个结点的权值n",n);for(i = 0;i< n;i+)sca nf("%d",&wi);getchar();Huf
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 呼和浩特市中医院临床路径管理与优化考核
- 呼和浩特市人民医院介入治疗并发症处理考核
- 2025中医院护理科研国际交流考核
- 2025年秋外研版(三起)(2024)小学英语四年级上册(期末)综合词汇句子专项训练题及答案
- 2025年中国染料制造项目投资计划书
- 阳泉市人民医院乳房自查健康教育能力考核
- 黑河交通局安全培训课件
- 2025年邢台松香树脂项目可行性研究报告
- 2025年子母带项目可行性研究报告
- 2024年湖北省新八校协作体高三10月联考政治答案
- 北京市海淀区2023-2024学年七年级上学期数学期中考试试卷(含答案)
- 医院感染管理科十五五发展规划
- 【《基于Java Web的网络题库和考试系统设计与实现》8900字(论文)】
- 学堂在线 实验室安全教育 章节测试答案
- 《教育强国建设规划纲要(2024-2035年)》及三年行动计划全面解读
- 医院应急知识培训课件
- 2025-2030中国抗骨质疏松药物市场调研及未来增长预测报告
- 2025年注册道路工程师执业资格基础考试应试辅导(公共基础)(上下册)
- 终极焊工考试试题及答案
- 临床用药监测管理制度
- (高清版)DZT 0399-2022 矿山资源储量管理规范
评论
0/150
提交评论