|
// 哈夫曼编码(算法) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树//选择两个parent为0，且weight最小的结点s1和s2 char alpha[53] = {'a','b','c','d','e','f','g','h','i','j','k','l','m', 'n','o','p','q','r','s','t','u','v','w','x','y','z', 'A','B','C','D','E','F','G','H','I','J','K','L','M', 'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; char alpha_1[53]; int num1[52] = {0}; int num2[52] = {0}; double num3[52] = {0}; int k = 0; double add[52]; double HX = 0.0; double MX = 0.0; void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht).parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht).parent==0) { if((*ht).weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) { if((*ht).parent==0 && i!=(*s1)) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht).parent==0 && i!=(*s1)) { if((*ht).weight<(*ht)[min].weight) min=i; } } *s2=min; }//构造哈夫曼树ht。w存放已知的n个权值 void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) { int m,i,s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化 { (*ht).weight=w; (*ht).LChild=0; (*ht).parent=0; (*ht).RChild=0; } for(i=n+1; i<=m; i++) { (*ht).weight=0; (*ht).LChild=0; (*ht).parent=0; (*ht).RChild=0; } //非叶子结点初始化 // printf("\nHuffmanTree: \n"); for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树 { //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0 //且weight最小的结点，其序号分别赋值给s1、s2 Select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht).LChild=s1; (*ht).RChild=s2; (*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight; // printf("%d (%d, %d)\n",(*ht).weight,(*ht)[s1].weight,(*ht)[s2].weight); } printf("\n"); } //哈夫曼树建立完毕//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码 void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n,char str[],double num[],double HX) { int shu[n]; char *cd; int i,start,p; unsigned int c; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针 cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间 cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符 for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码 { start=n-1; //初始化编码起始指针 for(c=i,p=(*ht).parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码 if( (*ht)[p].LChild==c) cd[--start]='1'; //左分支标0 else cd[--start]='0'; //右分支标1 hc=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(hc,&cd[start]); } free(cd); for(i=1; i<=n; i++) printf("HFMC %c is %s\n",str,hc); for(i=1; i<=n; i++) { shu = strlen(hc); //测出码长 MX += shu*num3; //计算平均码长 } MX = HX/MX;//计算效率 printf("\n编码效率n %f\n",MX); printf("\n"); } int countchar(char str[],char a,int n_value) { int n=0; int i = 0; while(i < n_value) { if((str) == a) n++; i++; } return n; } int main() { HuffmanTree HT; HuffmanCode HC; int *w,i,wei,m,value = 0,count = 0,n1 = 0,n2 = 0,j = 0,n = 0; char data; FILE *fp=fopen("in.txt","r"); if(!fp) { printf("can't open file\n"); return -1; } while(!feof(fp)) { value++; data=fgetc(fp); printf("%c",data); if(data>='a'&&data<='z'||data>='A'&&data<='Z') n1++; else if(data>='0'&&data<='9') n2++; } printf("\n字母：%d\n",n1); printf("\n"); fclose(fp); char disbuf[value]; FILE *fq=fopen("in.txt","r"); if(!fq) { printf("can't open file\n"); return -1; } while(count <= value) { fscanf(fq,"%c",&disbuf[count]); count++; } fclose(fq); printf("\n"); for(j = 0; j < 52; j++) num1[j] += countchar(disbuf, alpha[j],n1);//找出各个字母的个数 for( i = 0; i < 52; i++ ) //求每个字母的概率 { add= double(num1)/double(n1); } for( i = 0,j = 1;i < 26; i++) { printf("字母%c\t\t数量%d\t概率%0.3f\t",alpha,num1,add); printf("字母%c\t\t数量%d\t概率%0.3f\t",alpha[i+26],num1[i+26],add[i+26]); } for(i = 0,j = 1; i < 52; i++)//把不为零的字母统计出来，统计他们的个数与符号 { if(num1 != 0) { n++; num2[j] = num1; alpha_1[j] = alpha; j++; } } for( i = 0,j = 1; i < 52; i++ ) //把不为零的字母概率挑选出来 ,计算信源熵 { if(num1 != 0) { HX += add*log10(add); num3[j] = add; //挑选出有概率的字符和其概率； j++; } } HX = - HX/log10(2); //计算信源熵 printf("\n信源熵H(X) %f\n",HX); w=(int *)malloc((n+1)*sizeof(int)); for(i=1; i<=n; i++) { w= num2 ; } CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n,alpha_1,num3,HX);
| 
