偶看新闻芜湖方特一期美食:哈弗曼压缩实例（一）
来源：百度文库 编辑：偶看新闻 时间：2024/04/29 19:48:02
哈弗曼压缩实例（一） #include
#include
#include
#include
/***********************************************/
typedef struct HTNode{/*Huffman Tree 的结构定义*/
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,* HuffmanTree;
typedef char** HuffmanCode;/*指向字符指针的指针的数据的定义*/
int stat[27];/*存储总数,存储26个字母出现的次数*/
HuffmanTree HT;
HuffmanCode HC;
/***********************************************/
void CreatFile(){/*自动产生文件*/
FILE *Fopen,*Fout;
int i;
srand( (unsigned)time(NULL));
Fout=fopen("./Run.txt","w");
fprintf(Fout,"NO.1: Creating a file by rand()\n");
Fopen = fopen("./input.txt", "w");
for(i=0; i<10000; i++){
char ch=(char)(97+rand()%26);
fputc(ch, Fopen);
}
fclose(Fopen);
fclose(Fout);
}
/***********************************************/
void ReadStat(char *Filename){/*每个字符出现的次数统计*/
int c;
FILE *Fopen=fopen(Filename, "r");
while((c=fgetc(Fopen))!=EOF){
stat[c%96]++;
stat[0]++;
}
}
/***********************************************/
void Select(HuffmanTree HT, int d, int *s){
int temp=0,i;
for(i=1; i<=d; i++){
if(HT[i].parent!=0)
continue;
if(temp==0)
temp=i;
else if(HT[temp].weight>HT[i].weight)
temp=i;
}
*s=temp;
}
/***********************************************/
void HuffmanCoding(int* w, int n){
int m= 2*n-1;
int i, s1, s2, start;
unsigned int c, f;
char *cd;
if(n<=1)
return;
HT=(HTNode*)malloc((m+1)*sizeof(HTNode));/*0号单元未用*/
for(i=1; i<=n; i++, w++){
/***p={*w,0,0,0}; 初始化*/
HT[i].weight=*w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(; i<=m; i++){
/**p={0,0,0,0};*/
HT[i].weight=*w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1; i<=m; i++){
Select(HT, i-1, &s1);/*选择HT[1…i-1]中Parent为0且Weight最小的一个点*/
HT[s1].parent=i;
Select(HT, i-1, &s2);
HT[s2].parent=i;
HT[i].lchild=s1;/*左右孩子对编码没有影响，也说明的Huffman树的不唯一性*/
HT[i].rchild=s2;
HT[i].weight= HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode) malloc ((n+1) * sizeof(char*));/*分配n个字符编码的头指针向量*/
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]);
}
free(cd);
}
/***********************************************/
void WriteCode(){
FILE *Fopen;
int i;
Fopen=fopen("./Run.txt","a+");
fprintf(Fopen,"NO.2: The array of the structure of HuffmanTree:\n");
for(i=1;i<52;i++)
fprintf(Fopen,"%-2d: p:%-3d w:%-5d l:%-3d r:%-3d\n",i, HT[i].parent,HT[i].weight,HT[i].lchild,HT[i].rchild);
fprintf(Fopen,"NO.3: The Huffman codes:\n");
for(i=1;i<27;i++)
fprintf(Fopen,"%c: %3d %s\n",'a'+i-1,stat[i],HC[i]);
}
/***********************************************/
void OutCompress(){
FILE *Fin,*Fout;
int c;
Fin=fopen("./input.txt","r");
Fout=fopen("./bytes.txt","w");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while((c=fgetc(Fin))!=EOF){/*output the bit stream*/
fprintf(Fout,"%s",HC[c-96]);
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
void Compress(){
FILE *Fin,*Fout;
unsigned char out=0;
char c,*buf;
int i,count=0;
buf=(char *)malloc(sizeof(char)*20);
Fin=fopen("./input.txt","r");
Fout=fopen("./compress.txt","wb");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while((c=fgetc(Fin))!=EOF){/*output the bit stream*/
buf=HC[c-96];
for(i=0;buf[i]!='\0';i++){
if(count==8){
fprintf(Fout,"%c",out);
count=0;
out=0;
}
out<<=1;
count++;
if(buf[i]=='1')
out=out|1;
}
}
if(count!=8){
out<<=(8-count);
fprintf(Fout,"%c",out);
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
void UnCompress(){
FILE *Fin,*Fout,*Fout1;
unsigned char c=0; char *buf;
int i,k,t=51;
buf=(char *)malloc(sizeof(char)*10);
Fin=fopen("./compress.txt","rb");
Fout=fopen("./uncompress.txt","wb");
Fout1=fopen("./output.txt","wb");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while(!feof(Fin)){/*output the bit stream*/
c=fgetc(Fin);
for(i=7;i>=0;i--){
k=(c>>i)&1;
fprintf(Fout,"%d",k);
if(k==0)
t=HT[t].lchild;
else
t=HT[t].rchild;
if(HT[t].lchild==0&&HT[t].rchild==0){
fprintf(Fout1,"%c",96+t);
t=51;
}
}
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
int main(int arg, char *argv[]){/*存放Huffman编码*/
CreatFile();
ReadStat("./input.txt");
HuffmanCoding(&stat[1], 26);
WriteCode();
OutCompress();
Compress();
UnCompress();
system("Echo Pree any key to kill the program");
system("PAUSE>NUL 2>NUL");
return 0;
}
#include
#include
#include
/***********************************************/
typedef struct HTNode{/*Huffman Tree 的结构定义*/
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,* HuffmanTree;
typedef char** HuffmanCode;/*指向字符指针的指针的数据的定义*/
int stat[27];/*存储总数,存储26个字母出现的次数*/
HuffmanTree HT;
HuffmanCode HC;
/***********************************************/
void CreatFile(){/*自动产生文件*/
FILE *Fopen,*Fout;
int i;
srand( (unsigned)time(NULL));
Fout=fopen("./Run.txt","w");
fprintf(Fout,"NO.1: Creating a file by rand()\n");
Fopen = fopen("./input.txt", "w");
for(i=0; i<10000; i++){
char ch=(char)(97+rand()%26);
fputc(ch, Fopen);
}
fclose(Fopen);
fclose(Fout);
}
/***********************************************/
void ReadStat(char *Filename){/*每个字符出现的次数统计*/
int c;
FILE *Fopen=fopen(Filename, "r");
while((c=fgetc(Fopen))!=EOF){
stat[c%96]++;
stat[0]++;
}
}
/***********************************************/
void Select(HuffmanTree HT, int d, int *s){
int temp=0,i;
for(i=1; i<=d; i++){
if(HT[i].parent!=0)
continue;
if(temp==0)
temp=i;
else if(HT[temp].weight>HT[i].weight)
temp=i;
}
*s=temp;
}
/***********************************************/
void HuffmanCoding(int* w, int n){
int m= 2*n-1;
int i, s1, s2, start;
unsigned int c, f;
char *cd;
if(n<=1)
return;
HT=(HTNode*)malloc((m+1)*sizeof(HTNode));/*0号单元未用*/
for(i=1; i<=n; i++, w++){
/***p={*w,0,0,0}; 初始化*/
HT[i].weight=*w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(; i<=m; i++){
/**p={0,0,0,0};*/
HT[i].weight=*w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1; i<=m; i++){
Select(HT, i-1, &s1);/*选择HT[1…i-1]中Parent为0且Weight最小的一个点*/
HT[s1].parent=i;
Select(HT, i-1, &s2);
HT[s2].parent=i;
HT[i].lchild=s1;/*左右孩子对编码没有影响，也说明的Huffman树的不唯一性*/
HT[i].rchild=s2;
HT[i].weight= HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode) malloc ((n+1) * sizeof(char*));/*分配n个字符编码的头指针向量*/
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]);
}
free(cd);
}
/***********************************************/
void WriteCode(){
FILE *Fopen;
int i;
Fopen=fopen("./Run.txt","a+");
fprintf(Fopen,"NO.2: The array of the structure of HuffmanTree:\n");
for(i=1;i<52;i++)
fprintf(Fopen,"%-2d: p:%-3d w:%-5d l:%-3d r:%-3d\n",i, HT[i].parent,HT[i].weight,HT[i].lchild,HT[i].rchild);
fprintf(Fopen,"NO.3: The Huffman codes:\n");
for(i=1;i<27;i++)
fprintf(Fopen,"%c: %3d %s\n",'a'+i-1,stat[i],HC[i]);
}
/***********************************************/
void OutCompress(){
FILE *Fin,*Fout;
int c;
Fin=fopen("./input.txt","r");
Fout=fopen("./bytes.txt","w");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while((c=fgetc(Fin))!=EOF){/*output the bit stream*/
fprintf(Fout,"%s",HC[c-96]);
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
void Compress(){
FILE *Fin,*Fout;
unsigned char out=0;
char c,*buf;
int i,count=0;
buf=(char *)malloc(sizeof(char)*20);
Fin=fopen("./input.txt","r");
Fout=fopen("./compress.txt","wb");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while((c=fgetc(Fin))!=EOF){/*output the bit stream*/
buf=HC[c-96];
for(i=0;buf[i]!='\0';i++){
if(count==8){
fprintf(Fout,"%c",out);
count=0;
out=0;
}
out<<=1;
count++;
if(buf[i]=='1')
out=out|1;
}
}
if(count!=8){
out<<=(8-count);
fprintf(Fout,"%c",out);
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
void UnCompress(){
FILE *Fin,*Fout,*Fout1;
unsigned char c=0; char *buf;
int i,k,t=51;
buf=(char *)malloc(sizeof(char)*10);
Fin=fopen("./compress.txt","rb");
Fout=fopen("./uncompress.txt","wb");
Fout1=fopen("./output.txt","wb");
if(Fin==NULL)
printf("Can't find the file of 'input'!\n");
while(!feof(Fin)){/*output the bit stream*/
c=fgetc(Fin);
for(i=7;i>=0;i--){
k=(c>>i)&1;
fprintf(Fout,"%d",k);
if(k==0)
t=HT[t].lchild;
else
t=HT[t].rchild;
if(HT[t].lchild==0&&HT[t].rchild==0){
fprintf(Fout1,"%c",96+t);
t=51;
}
}
}
fclose(Fin);
fclose(Fout);
}
/***********************************************/
int main(int arg, char *argv[]){/*存放Huffman编码*/
CreatFile();
ReadStat("./input.txt");
HuffmanCoding(&stat[1], 26);
WriteCode();
OutCompress();
Compress();
UnCompress();
system("Echo Pree any key to kill the program");
system("PAUSE>NUL 2>NUL");
return 0;
}
HP86140A系列光谱仪操作实例有哪些？（一到两个）
能否就一实例详细说明，谢谢！
vc如何访问oracle？求一实例
什么是发光材料？举一实例说明
求一课件的文字脚本实例
怎么压缩一首MTV
如何压缩一首MP3
请各位高手推荐一本有关SolidWorks2005方面有关实例详解（例子多些的）方面的书籍
关于35kv变电所调查研究报告举一实例说明
对于编写批处理文件能否举一实例说明，谢谢！
如何在一台计算机上建创多个SQL SERVER服务实例
观察一辆自行车,找出几个简单机械的应用实例
通过一实例论证邓小平理论对马克思主义的发展
哪位有vc++扩展编程实例一书的源代码
哪位有vc 扩展编程实例一书的代码
求作为一名体育教师的工作实例子
求《Solid Edge 实例精华》一书的配套光盘！！！
求一压缩文本文件的超强算法！
ASP数据显示（实例：电影）
什么是散文？（最好有实例）
哪有flash习题（实例）？
平面实例的网站（论坛）
网页制作实例教材下载（谢谢）
（压缩）是什么意思？