- //作者:石金南
- //功能:赫夫曼编码
- //日期:2013.5.19
- #include<stdio.h>
- #include<malloc.h>
- #include<string.h>
- #include<math.h>
- #include<conio.h>
- #define Len 1000//输入字符的长度
- #define kind 256//字符至多的的种类数目
- #include <stdlib.h>
- struct hfmNum
- {
- char hc;//赫夫曼编码的字符
- char h[10];//字符对应的赫夫曼01编码
- };
- typedef struct hfmTree//赫夫曼树节点
- {
- bool b;//判定是否已有parent节点
- int weight;
- int rchild,lchild,parent;
- }hfm;//动态分配数组存贮赫夫曼树
- void setInchar(char a[Len]);//从键盘获取字符
- void printchar(char a[]);//输出字符串
- void classifyChar(char c[],char cTyde[],int n[]);//对输入字符串分类,并求出每一类的数目
- int numClass(char a[]);//求出字符串C中有多少个字符
- hfm *CreatHfmTree(char cTyde[],int num[],int numKind);
- struct hfmNum *SureHfm(char cTyde[],hfm *p,int numKind);
- void print(struct hfmNum *q,int numKind);//输出每个字符及它相对应的赫夫曼编码
- void printl();
- char* wordExchange(char c[],struct hfmNum a[],int numKind);
- int main()
- {
- char c[Len]={'\\0'};
- int numKind;
- char cTyde[kind]={'\\0'},*hfmNumber;//字符的种类
- int num[kind]={0};//每一类字符的数目
- struct hfmNum *q;
- hfm *p;
- setInchar(c);//从键盘获取组成赫夫曼树的字符
- classifyChar(c,cTyde,num);
- numKind=numClass(cTyde);//求出有cTyde字符串中有多少种字符类
- p=CreatHfmTree(cTyde,num,numKind);
- q=SureHfm(cTyde,p,numKind);
- print(q,numKind);
- hfmNumber=wordExchange(c,q,numKind);
- {//输出输入字符对应的赫夫曼编码
- int i=0;
- while(hfmNumber[i]!='\\0')
- {
- printf("%c",hfmNumber[i]);
- i++;
- }
- }getch();
- return 0;
- }
- void setInchar(char a[Len])//
- {
- gets(a);//得到字符串
- }
- void printchar(char a[])//输出字符串
- {
- puts(a);
- }
- void classifyChar(char c[],char cTyde[],int n[])//对输入字符串分类,并求出每一类的数目
- {
- int t,i;
- for( i=0;c[i]!='\\0';i++)//判定是否到字符串是否到尽头
- {
- for(t=0;cTyde[t]!='\\0';t++)//判定cTyde分类字符中是否有c[t]
- {
- if(cTyde[t]==c[i])//判定c[i]字符是否在cTyde分类字符中
- {
- n[t]++;break;//如果在对应的类数目加一,跳出循环
- }
- }
- if(cTyde[t]=='\\0')//如果不在,则在cTyde分类字符后添加一个c[i]的类
- {
- cTyde[t]=c[i];
- n[t]++;
- }
- }
- }
- int numClass(char a[])
- {
- int i=0;
- while(a[i]!='\\0')//求出字符串c中有多少个字符
- {
- i++;
- }
- return i;//返回字符数目
- }
- hfm *CreatHfmTree(char cTyde[],int num[],int numKind)//建立赫夫曼树
- {
- int m=2*numKind-1,i=0,n1,n2,m1,m2;//确定树有多少个节点
- hfm *p;
- p=(hfm*)calloc(m,sizeof(hfm));//开辟连续的存贮空间
- while(i<numKind)//对前numkind个单位进行初始化
- {
- p[i].b=0;//
- p[i].weight=num[i];//前numKind个单位与字符串cTyde中的字符相对应
- p[i].rchild=-1;
- p[i].lchild=-1;
- p[i].parent=-1;
- i++;
- }
- while(i<m)//对后numKind-1个单位进行初始化
- {
- p[i].b=0;
- p[i].weight=0;
- p[i].rchild=-1;
- p[i].lchild=-1;
- p[i].parent=-1;
- i++;
- }
- for(;numKind<m;numKind++)//
- {
- m2=m1=0;
- n1=n2=Len;//将n1,n2取最大
- for(i=0;i<numKind;i++)//求出节点数组中没parent节点的权值最小的两个数
- {
- if(p[i].b==0&&p[i].weight<n1)
- {
- n2=n1;
- m2=m1;
- m1=i;
- n1=p[i].weight;
- }
- else if(p[i].b==0&&p[i].weight<n2)
- {
- n2=p[i].weight;
- m2=i;
- }
- }
- p[numKind].weight=n1+n2;//将两个最小的权值相加赋给numKind
- p[m1].b=p[m2].b=1;//确定m1m2它们有父亲了
- p[m1].parent=p[m2].parent=numKind;//m1,m2的父母是numKind
- p[numKind].rchild=m1;//numKind+1的儿子是m1,m2
- p[numKind].lchild=m2;//最后numKind+1
- }
- return p;
- }
- struct hfmNum *SureHfm(char cTyde[],hfm *p,int numKind)
- {
- struct hfmNum *q=(struct hfmNum*)malloc(numKind*sizeof(struct hfmNum));//建立numKind个地址连续的hfmNum节点
- int a=0;
- char s[10]={'\\0'};//
- int l,m1,m2,m3,i;
- for(i=0;i<numKind;i++)
- {
- l=10;
- m1=i;
- while(p[m1].parent!=-1)
- {
- l--;
- m2=p[m1].parent;
- if(p[m2].lchild==m1)
- s[l]='0';
- else if(p[m2].rchild==m1) s[l]='1';
- m1=m2;
- }
- q[i].hc=cTyde[i];//将cTyde的字符种类赋给q[i].hc
- m3=0;
- while(l<10)//确定q[i].hc字符相应的赫夫曼编码
- {
- q[i].h[m3]=s[l];
- l++;
- m3++;
- }
- q[i].h[m3]='\\0';
- }
- return q;
- }
- void print(struct hfmNum *q,int numKind)
- {
- //int a=0;
- for(int i=0;i<numKind;i++)
- {
- putchar(q[i].hc);
- printl();
- puts(q[i].h);
- //while(q[i].h[a]!='\\0'){printf("%c",q[i].h[a]);a++;}a=0;
- }
- }
- void printl()//为了简便输出:的赫夫曼编码:
- {
- printf("的赫夫曼编码:");
- }
- char* wordExchange(char c[],struct hfmNum a[],int numKind)//将输入的字符转换为对应的赫夫曼编码
- {
- int i=0,m,l=0;
- char *s=(char*)malloc(l*sizeof(char));
- //SqStack *s;//
- //if(!InitStack(s))exit(0);//
- while(c[i]!='\\0')//
- {
- for(m=0;m<numKind;m++)//
- {
- if(c[i]==a[m].hc)
- {
- for(int b=0;a[m].h[b]!='\\0';b++)
- {
- l++;
- s=(char*)realloc(s,l*sizeof(char));
- s[l-1]=a[m].h[b];
- }
- }
- }
- i++;
- }
- s[l]='\\0';
- return s;
- }
- //该片段来自于http://www.codesnippet.cn/detail/240220148748.html
来源: http://www.codesnippet.cn/detail/240220148748.html