输入一个字符串
#include <stdio.h> #include <stdlib.h> #include <string.h> #define cmax 0x3f3f3f3f // 宏定义一个较大的数，作为比较数据 #define cmaxsize 10000 // 宏定义数组的长度 // ---构建哈夫曼树 // ---定义哈夫曼树的每一个叶子节点 typedef struct { int weight; int parent; int lchild; int rchild; } HNodeType; typedef struct { char c; int numbers; }LeafNode; typedef struct { int bit[cmaxsize]; int start; }HCodeType; HNodeType HFMTree[cmaxsize]; HCodeType HuffCode[cmaxsize]; // ---哈夫曼的构造 void Create_HuffMTree(HNodeType HFMTree[],LeafNode Lnode[],int n) { int m1,m2,x1,x2; for(int i=0;i<2*n-1;i++) { HFMTree[i].weight=0; HFMTree[i].lchild=-1; HFMTree[i].rchild=-1; HFMTree[i].parent=-1; } for(int i=0;i<n;i++) { HFMTree[i].weight=Lnode[i].numbers; } for(int i=0;i<n-1;i++) { x1=x2=cmax; m1=m2=0; for(int j=0;j<n+i;j++) { if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1) { x2=x1; m2=m1; x1=HFMTree[j].weight; m1=j; } else if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2) { x2=HFMTree[j].weight; m2=j; } } HFMTree[m1].parent=n+i; HFMTree[m2].parent=n+i; HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight; HFMTree[n+i].rchild=m1; HFMTree[n+i].lchild=m2; } } //哈弗曼编码 void HuffmanCode(HNodeType HFMTree[],HCodeType HuffCode[],int n) { HCodeType middle; int i,j,c,p; for(i=0;i<n;i++) { middle.start=n-1; c=i; p=HFMTree[c].parent; while(p!=-1) { if(HFMTree[p].lchild==c) middle.bit[middle.start]=0; else middle.bit[middle.start]=1; middle.start--; c=p; p=HFMTree[c].parent; } for(j=middle.start+1;j<n;j++) HuffCode[i].bit[j]=middle.bit[j]; HuffCode[i].start=middle.start+1; } } int main() { char mystr[cmaxsize]; // 用来缓存你读入的电文 memset(mystr,'\0',sizeof(mystr)); // 将mystr字符数组里面的内容清空 scanf("%s",mystr); // 输入要读入的电文 printf("%s\n",mystr); int keep[130]; // 记录每一个字符出现的次数 memset(keep,0,sizeof(keep)); for(int i=0;i<strlen(mystr);i++) keep[mystr[i]]++; int num=0; LeafNode Lnode[130]; for(int i=0;i<130;i++) { if(keep[i]!=0) { Lnode[num].c=i; Lnode[num].numbers=keep[i]; num++; } } Create_HuffMTree(HFMTree,Lnode,num); // 构建哈夫曼树 for(int i=0;i<2*num-1;i++){ printf("哈弗曼树的构造为：\n下标：\t字符：\tlchild\trchild\tparent\tweight\n"); printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,Lnode[i].c,HFMTree[i].lchild,HFMTree[i].rchild,HFMTree[i].parent,HFMTree[i].weight); } printf("\n"); HuffmanCode(HFMTree,HuffCode,num); //哈弗曼编码 printf("对应字母的对应编码为：\n"); for(int i=0;i<num;i++) { printf("字符：%c 权值：%d 编码：",Lnode[i].c,Lnode[i].numbers); for(int j=HuffCode[i].start;j<num;j++) printf("%d",HuffCode[i].bit[j]); printf("\n"); } return 0; }