main.c

数据压缩

#include<stdio.h>
#include<stdlib.h> 
#include<string.h> 

typedef char ElemType; //huffman元素类型 
typedef struct 
{ 
ElemType elem; 
float m_weight; 
unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree; 

typedef char** HuffmanCode; 
typedef int Status; 
typedef struct weight 
{ 
char elem; 
float m_weight; 
}Weight; // huffman元素的概率

void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); 
void Select(HuffmanTree,int,int *,int *); 
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int); 
//主函数 
int main() 
{ 
HuffmanTree HT; 
HuffmanCode HC; 
Weight *w; 
char c; // 使用的符号;
int i,n; // huffman元素个数; 
float wei; // 元素的概率; 

printf("输入要编码元素个数:" ); 
scanf("%d",&n); 
w=(Weight *)malloc(n*sizeof(Weight)); 
for(i=0;i<n;i++) 
{ 
printf("输入元素及概率:"); 
scanf("%1s%f",&c,&wei); 
w[i].elem=c; 
w[i].m_weight=wei; 
} 

HuffmanCoding(&HT,&HC,w,n); 
OutputHuffmanCode(HT,HC,n); 
system("PAUSE");
return 0; 

} 

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n) 
{ 
int i,m,s1,s2,start,c,f; 
char *cd; 
HuffmanTree p; 
if(n<=1) 
return; 

m=2*n-1; 
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
for(i=1;i<=n;++i) 
{ 
(*HT)[i].elem=w[i-1].elem; 
(*HT)[i].m_weight=w[i-1].m_weight; 
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
} 

for(;i<=m;++i) 
{ 
(*HT)[i].elem='0'; 
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
} 

for(i=n+1;i<=m;++i) 
{ 
Select(*HT,i-1,&s1,&s2); 
(*HT)[s1].parent=i;(*HT)[s2].parent=i; 
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2; 
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight; 
} 

(*HC)=(HuffmanCode)malloc(n*sizeof(char*)); 
cd=(char *)malloc(n*sizeof(char)); 
cd[n-1]='\0'; 
for(i=1;i<=n;++i) 
{ 
start=n-1; 
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) 
{ 
if((*HT)[f].lchild==c) cd[--start]='0'; 
else cd[--start]='1'; 
} 

(*HC)[i]=(char *)malloc((n-start)*sizeof(char)); 
strcpy((*HC)[i],&cd[start]); 
} 
} 

void Select(HuffmanTree HT,int n,int *s1,int *s2) 
{ 
int i; 
(*s1)=(*s2)=0; 
for(i=1;i<=n;i++) 
{ 
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0) 
{ 
if(HT[i].m_weight<HT[(*s1)].m_weight) 
{ 
(*s2)=(*s1); 
(*s1)=i; 
} 
else (*s2)=i; 

} 

if(((*s1)==0||(*s2)==0)&&HT[i].parent==0) 
{ 
if((*s1)==0) (*s1)=i; 
else if((*s2)==0) 
{ 
if(HT[i].m_weight<HT[(*s1)].m_weight) 
{ 
(*s2)=(*s1); 
(*s1)=i; 
} 
else (*s2)=i; 
} // end of else if 
} // end of if 
} // end of for 

if((*s1)>(*s2)) 
{ 
i=(*s1); 
(*s1)=(*s2); 
(*s2)=i; 
} 
return; 
} 

void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) 
{ 
int i; 
printf("\序号---元素---概率---huffman code\n"); 
for(i=1;i<=n;i++) 
printf(" %d %c %f %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]); 
}