標(biāo)題: 哈夫曼編碼源程序 [打印本頁(yè)]
作者: liufendou 時(shí)間: 2017-5-27 17:24
標(biāo)題: 哈夫曼編碼源程序
// 哈夫曼編碼(算法)
#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ǔ)哈夫曼樹//選擇兩個(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)造哈夫曼樹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)，建哈夫曼樹
{
//在(*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");
} //哈夫曼樹建立完畢//從葉子結(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);
| 歡迎光臨 (http://www.torrancerestoration.com/bbs/) |
Powered by Discuz! X3.1 |