《2022年数据结构_哈弗曼树编 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构_哈弗曼树编 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、#include #include #include #include #define MaxLength 1000 /输入文本最大长度#define N 20 /* 叶子结点数*/ typedef int DataType ; typedef struct char ch; DataType weight; /*假设叶子权值为整型*/ int lchild,rchild,parent; Htnode; /* 哈夫曼树结点类型*/ typedef struct char *code; char leaf ; int length; /*编码的长度 */ CodeType ; /* 叶编码类型*
2、/ void selectsort(Htnode huftree,int end,int *s1,int* s2) int min,min2; int i,j,k; for(i=1;i=end;i+) if(huftreei.parent=-1)/找父节点是 -1 的点 min=i; break; for(j =2;j=end;j+) if(huftreej.parent=-1 & huftreej.weighthuftreemin.weight) min=j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
3、- - - - - - 第 1 页，共 6 页 - - - - - - - - - *s1=min; for(i=1;i=end;i+) if(huftreei.parent=-1& i!=min) min2=i; break; for(k=2;k=end;k+) if(k=min) continue; if(huftreek.parent=-1 & huftreek.weighthuftreemin2.weight) min2=k; *s2=min2; /void Hufcoding(Htnode huftree , CodeType cd , int w ,int n) void Hufc
4、oding(Htnode huftree, CodeType cd ,char chs,int w ,int n) /* 哈夫曼树存放在静态链表huftree 中,w 存放结点权重,n 是叶子个数 ,最后的编码放在cd*/ int i,j,k,s1,s2,s,m,f,c,sum; char tempN; /*暂存叶子编码字符串，最后需要转置*/ m=2*n-1; /* 计算哈夫曼树的结点总数*/ char ch; for(i=1;i=n;i+) /* 初始化每个结点自成一棵树*/ huftreei.weight=wi-1; huftreei.lchild=huftreei.rchild=huf
5、treei.parent=-1; huftreei.ch=chsi-1; for(i=n+1;i=m;i+) /*初始化 */ huftreei.weight=-1; huftreei.lchild=huftreei.rchild=huftreei.parent=-1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - for(i=1;i=n-1;i+) /* 生成 n-1 个非叶子结点的循环*/ selectsort(huftr
6、ee,n+i-1,&s1,&s2); /* 对数组huftree 1.n+i-1 中无双亲的结点权值进行排序，s1,s2将是无双亲且权重最小的两个结点下标*/ sum=huftrees1.weight+huftrees2.weight;/计算它的权重huftreen+i.weight=sum;/ huftrees1.parent=huftrees2.parent=n+i; huftreen+i.lchild=s1; / 左孩子节点指向S1 huftreen+i.rchild=s2;/右孩子节点指向S1 for(i=1;i=0) cdi.codek+=tempc-;/*将 temp 转置到 cd
7、 中*/ cdi.leaf=huftreei.ch; cdi.length=k; /*end for */ void encode(char text,CodeType cd,char bits)/ 把输入的字符按所编的哈夫曼树的规则译成二进制码 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - int i,j,k,index=0; int len=strlen(text); memset(bits,0,sizeof(bits);
8、/ 把一片连续的内存填充第二个参数的值char ch; for(i=0;ilen;i+) ch=texti; j=1; while(ch!=cdj.leaf) j+; for(k=0;kcdj.length;k+) bitsindex+=cdj.codek; bitsindex=0; void decode(char bits,Htnode* huftree,char forText)/解码过程 /找根节点int root=1,cur=1; while(cur!=-1) root=cur; cur=huftreecur.parent; int index=0; int len=strlen(b
9、its); int j=0; char c; Htnode cNode=huftreeroot; for(j=0;jlen;j+) c=bitsj; if(c=0) cNode=huftreecNode.lchild;/左孩子节点当叶节点 else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - cNode=huftreecNode.rchild;/ 右孩子节点当叶节点 if(cNode.lchild=-1&cNode.rchi
10、ld=-1) forTextindex+=cNode.ch; cNode=huftreeroot; forTextindex=0; int main() char textMaxLength; / 输入文本printf( 请输入测试文本:); scanf(%s,text); printf( 测试文本如下:%snn,text); int length=strlen(text);/ 计算输入字符串长度int wtemplength; /权重统计int i; for(i=0;ilength;i+) wtempi=0; char ctemplength; /存放字符int n=0; /字符个数（叶子节
11、点个数）char ch; int j; for(i=0;ilength;i+) ch=texti; j=0; while(ch!=ctempj&jn) j+; if(j=n) /从未出现的字符，权重值都一样为1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - ctempj=ch; wtempj=1; n+; else /已经出现的字符，权重值就加1 wtempj+; char cn; int wn; for(i=0;in;i+)
12、 ci=ctempi; wi=wtempi; CodeType cdn+1;/ 叶子结点Htnode huftree2*n;/ 哈夫曼数Htnode* node=huftree; Hufcoding(huftree,cd,c,w,n);/ 创建哈夫曼树/打印字符不等长编码信息printf( 测试文本中各字符的编码如下:n); for(int i=1;i=n;i+) printf(%c:,cdi.leaf); printf(%s ,cdi.code); int bitmaxLength=1+n*(int)floor(log(n)/log(2); char bitsbitmaxLength; encode(text,cd,bits); /编码printf(nn 测试文本编码如下:%snn,bits); char forTextMaxLength; decode(bits,node,forText); /解码printf( 上述编码原文本如下:%snn,forText); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -