|
// 哈夫曼編碼(算法) #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> typedef char *HuffmanCode; //動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼 typedef struct { unsigned int weight; //用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值 unsigned int parent,LChild,RChild; //指向雙親、孩子結(jié)點(diǎn)的指針 } HTNode, *HuffmanTree; //動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹(shù)//選擇兩個(gè)parent為0，且weight最小的結(jié)點(diǎn)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; }//構(gòu)造哈夫曼樹(shù)ht。w存放已知的n個(gè)權(quá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號(hào)存放葉子結(jié)點(diǎ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; } //非葉子結(jié)點(diǎn)初始化 // printf("\nHuffmanTree: \n"); for(i=n+1; i<=m; i++) //創(chuàng)建非葉子結(jié)點(diǎn)，建哈夫曼樹(shù) { //在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個(gè)parent為0 //且weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給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"); } //哈夫曼樹(shù)建立完畢//從葉子結(jié)點(diǎn)到根，逆向求每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼 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個(gè)編碼的頭指針 cd=(char *)malloc(n*sizeof(char)); //分配求當(dāng)前編碼的工作空間 cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結(jié)束符 for(i=1; i<=n; i++) //求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼 { start=n-1; //初始化編碼起始指針 for(c=i,p=(*ht).parent; p!=0; c=p,p=(*ht)[p].parent) //從葉子到根結(jié)點(diǎn)求編碼 if( (*ht)[p].LChild==c) cd[--start]='1'; //左分支標(biāo)0 else cd[--start]='0'; //右分支標(biāo)1 hc=(char *)malloc((n-start)*sizeof(char)); //為第i個(gè)編碼分配空間 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); //測(cè)出碼長(zhǎng) MX += shu*num3; //計(jì)算平均碼長(zhǎng) } MX = HX/MX;//計(jì)算效率 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);//找出各個(gè)字母的個(gè)數(shù) for( i = 0; i < 52; i++ ) //求每個(gè)字母的概率 { add= double(num1)/double(n1); } for( i = 0,j = 1;i < 26; i++) { printf("字母%c\t\t數(shù)量%d\t概率%0.3f\t",alpha,num1,add); printf("字母%c\t\t數(shù)量%d\t概率%0.3f\t",alpha[i+26],num1[i+26],add[i+26]); } for(i = 0,j = 1; i < 52; i++)//把不為零的字母統(tǒng)計(jì)出來(lái)，統(tǒng)計(jì)他們的個(gè)數(shù)與符號(hào) { if(num1 != 0) { n++; num2[j] = num1; alpha_1[j] = alpha; j++; } } for( i = 0,j = 1; i < 52; i++ ) //把不為零的字母概率挑選出來(lái) ,計(jì)算信源熵 { if(num1 != 0) { HX += add*log10(add); num3[j] = add; //挑選出有概率的字符和其概率； j++; } } HX = - HX/log10(2); //計(jì)算信源熵 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);
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
