哈夫曼编码

《哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include"stdio.h"//输入、输出函数#include"stdlib.h"//定义杂项函数及内存分配函数#include"string.h"#defineM100#defineN20typedefcharElemType;intn=0,m;//叶子结点个数，编码总长charcode[M];charcode2[M];charresult[M];typedefstruct//哈夫曼树的结点类型{chardata;doubleweight;intparent;//双亲节点intlchild;//左孩子结点intrchild;

2、//右孩子结点}HTNode;typedefstruct//每个哈夫曼编码的类型{intcd[N];intstart;}HCode;typedefstruct//串的类型定义{ElemTypedata[M];intlen;}sqstring;intmenu()//菜单系选择函数{intc;do{printf("********************************************************");printf("tt****哈夫曼树的应用****");printf("tt1.输入字符统计

3、后输出");printf("tt2.构造哈夫曼树并输出");printf("tt3.进行哈夫曼编码并输出");printf("tt4.保存编码到文件");printf("tt5.从文件读出编码后译码输出");printf("tt0.退出程序");printf("tt请选择(0-6):");printf("********************************************************");scanf("%d",&c);}while(c<0

4、

5、c>

6、6);returnc;/*返回选择*/}voidshuru(sqstring&s,charcstr[])//输入字符串并统计后输出{intp;inti=0,k=0;printf("请输入一串字符:");getchar();gets(cstr);for(i;cstr[i]!='';i++)//只把a-z或A-Z赋给串s{if((cstr[i]>='a'&&cstr[i]<='z')

7、

8、(cstr[i]>='A'&&cstr[i]<='Z')){s.data[k]=cstr[i];k++;}}s.len=k;if(s.len>0){

9、printf("输入的字符串为:");for(p=0;p='a'&&s.data[j]<='z')a[s.data[j]-'a']++;if(s.dat

10、a[j]>='A'&&s.data[j]<='Z')a[s.data[j]-'A']++;}for(intk=0;k<26;k++)//计算叶子结点的个数{if(a[k]!=0)n++;}j=0;for(k=0;k<26;k++)//计算频率，把字符送入ht{if(a[k]!=0){ht[j].data=(char)(k+97);ht[j].weight=1.0*a[k]/s.len;j++;}}printf("字符种类为:%d",n);printf("");}voidCreateHT(HTNodeht[],intn)//构

11、造哈夫曼树后输出{inti,k,lnode,rnode;doublemin1,min2;for(i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for(i=n;i<2*n-1;i++)//构造哈夫曼树{min1=min2=32767;lnode=rnode=-1;//最小权值的两个位置for(k=0;k<=i-1;k++)if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找{if(ht[k].weight

12、de=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weight