哈夫曼编码

实验内容

利用哈夫曼树对文件进行编码和解码。 目的与要求

掌握哈夫曼树的数据结构和其基本应用。 设计方法和步骤

1. 用文本编辑器输入一段英文文章，保存成.txt文件。 2. 哈夫曼树的结点数据结构定义和单词的编码数据结构。

3. 读入该文本文件，统计单词频率；完成哈夫曼树和单词编码，保存成码本文件.cde。

4. 利用码本文件对该文本文件编码，保存成编码文件.huf。 5. 利用码本文件对编码文件进行解码，保存成文本文件.txt。

为了查看方便，我把所有的文件都定义为文本文件，当然不会影响程序的运行。 程序概述：

程序中的函数有：

建立文件：输入一段英文字符，建立“文本文件.txt”。 打印文件：一种是对文件进行逐字符的打印；

另一种是对文件以结构体为单位进行打印。

计算文件：对文件进行初步统计，求出字符的种类和权重，为生成哈夫曼树做

准备。

哈夫曼树函数：求出哈夫曼树，保存每个字符的哈夫曼编码在“字符代码.txt”。 求最值函数：此函数在求哈夫曼树时应用，保证每次选定的达到哈夫曼树要求。 转化成字符函数：即用字符代码来代替字符，保存在“码本文件.txt”。 破译函数：把“码本文件.txt”转化为可读的“破译文件.txt”。

程序如下：

#include #include #include #include

#define N 50 //输入字符的最多数目,可根据具体需要而定 typedef struct {

int weight; //权重

int parent,lchild,rchild; //左右孩子 }HTNode,*HuffmanTree; typedef char **HuffmanCode;

//建立原文件\"文本文件.txt\" void Creat_message(){ FILE *fp; char c;

if((fp=fopen(\"文本文件.txt\ printf(\"cannot open this file!\\n\"); return ; }

printf(\"输入原文件（一段英文，字符间无间隔，以'#'表示结束）！\\n\"); do{ //以#表示输入结束 scanf(\"%c\ fputc(c,fp); }while (c!='#'); fclose(fp); }

//逐字符打印文件（以字符为单位） void print1(char *name){ FILE *fp; char c;

if((fp=fopen(name,\"rb\"))==NULL){ printf(\"cannot open this file\\n\"); return ; }

c=fgetc(fp); while(c!='#'){ printf(\"%c\ c=fgetc(fp); } }

//统计字符种类及个数，用来作为哈夫曼编码时的权重（频率） char kind[N]={'\\0'}; //字符种类

int num[N]={0}; //字符相映的个数 int count=0; //字符总数 void Calculate(){ char c;

int i=1,k; FILE *fp;

if((fp=fopen(\"文本文件.txt\ printf(\"cannot open this file\\n\"); return ; }

c=fgetc(fp); while(c!='#'){

for (k=0;k=i&&kind[k-1]!=c){ kind[i]=c;num[i]++;i++; } c=fgetc(fp); }

count=i-1; }

//哈夫曼编码，求最小生成树及字符的哈夫曼编码 int s1,s2; //标记select函数调用时返回的最值 struct charcode{ char data; char code[20];

}Code[N],d[N],e[N];//结构体包括字符元素和字符相映的代码

void HuffmanCoding (){

void select(HuffmanTree Hu,int j); HuffmanTree HT; //哈夫曼树 HuffmanCode HC; //哈夫曼编码 int m,i,start,f,c; char *cd; FILE *fp;

if (count<=1) return; m=2*count-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1;i<=count;i++) HT[i].weight=num[i]; for(i=1;i<=m;i++){ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0;}

for(i=count+1;i<=m;i++){

select(HT,i-1); HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;}

HC=(HuffmanCode)malloc((count+1)*sizeof(char*)); //从叶子到根逆向求每个字符的哈夫曼编码 cd=(char*)malloc(count*sizeof(char)); cd[count-1]='\\0';

for(i=1;i<=count;i++){ start=count-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((count-start)*sizeof(char)); strcpy(HC[i],&cd[start]);} //复制字符串

if((fp=fopen(\"字符代码.txt\ //字符与对应的编码 printf(\"cannot open this file\\n\"); return ; }

for(i=1;i<=count;i++){ Code[i].data= kind[i]; strcpy(Code[i].code,HC[i]);

fwrite(&Code[i],sizeof(struct charcode),1,fp); }

fclose(fp); }

//在HT[1~j]选择parent为0且weight最小的两个结点，序号为s1,s2 void select(HuffmanTree Hu,int j){ int k=1,t;

while(Hu[k].parent!=0) k++; //找第一个parent不为0的结点 for(t=k;t<=j;t++) if(Hu[t].parent==0 && Hu[t].weightwhile(Hu[k].parent!=0 ||k==s1) k++; for(t=k;t<=j;t++) if(Hu[t].weight//结构体struct charnode的文件的打印 void print2(char *name){ FILE *fp; int i=1;

if((fp=fopen(name,\"rb\"))==NULL){ printf(\"cannot open this file\\n\"); return ; }

while(!feof(fp)){

fread(&e[i],sizeof(struct charcode),1,fp); printf(\"%c--%s\\n\ i++; } }

//使文本文件转化成码本文件 void Transform(){ FILE *fp1,*fp2,*fp3; int i; char c;

if((fp1=fopen(\"字符代码.txt\ printf(\"cannot open this file\\n\"); return ; }

if((fp2=fopen(\"文本文件.txt\ printf(\"cannot open this file\\n\"); return ; }

if((fp3=fopen(\"码本文件.txt\ printf(\"cannot open this file\\n\"); return ; }

for(i=0;ifread(&d[i],sizeof(struct charcode),1,fp1); while(!feof(fp2)){ c=fgetc(fp2); for(i=0;i}

fputc('#',fp3); //使该文件也可用print1 fclose(fp3); }

//把码本文件转化为可读的破译文件 void Translate(){

FILE *fp1,*fp2,*fp3; int i,j,k;

char c[20]={'\\0'};

if((fp1=fopen(\"码本文件.txt\ printf(\"cannot open this file\\n\"); return ; }

if((fp2=fopen(\"字符代码.txt\ printf(\"cannot open this file\\n\"); return ; }

if((fp3=fopen(\"破译文件.txt\ printf(\"cannot open this file\\n\"); return ; }

for(i=1;i<=count;i++) fread(&d[i],sizeof(struct charcode),1,fp2); i=0;

c[i]=fgetc(fp1); while(c[i]!='#'){ for(k=1;k<=count;k++) if(!strcmp(c,d[k].code)){ fputc(d[k].data,fp3); for(j=0;j<=i;j++) c[j]='\\0'; i=-1; break; } i++;

c[i]=fgetc(fp1); }

fputc('#',fp3); fclose(fp1); fclose(fp2); fclose(fp3);

}

void main(){

Creat_message(); //建立原文本文件 printf(\"您输入的文本文件是：\\n\");

print1(\"文本文件.txt\"); //打印原文本文件 printf(\"\\n\");

Calculate(); //对文本文件进行统计，计算字符种类和权重 HuffmanCoding (); //建立哈夫曼树，计算出哈夫曼编码 printf(\"每个字符相应的哈夫曼编码是：\\n\"); print2(\"字符代码.txt\"); printf(\"\\n\");

Transform(); //把原文本文件转化为码本文件 printf(\"原文件的码本文件（即全为字符编码）为:\\n\"); print1(\"码本文件.txt\"); printf(\"\\n\");

Translate(); //把码本文件转化为可读的破译文件 printf(\"用码本文件和字符代码求出的破译文件为:\\n\"); print1(\"破译文件.txt\"); printf(\"\\n\"); }

程序运行如下：

输入原文件（一段英文，字符间无间隔，以'#'表示结束）！ Hello! Good morning! Wlecome to USTC!# 您输入的文本文件是： Hello! Good morning! Wlecome to USTC!

每个字符相应的哈夫曼编码是： H--00100 e--1011 l--1110 o--110 !--1111 --100 G--00101 d--00110 m--0000

r--00111 n--0001 i--01000 g--01001

--01010 W--01011 c--01100 t--01101 U--01110 S--01111 T--10100 C—10101

原文件的码本文件（即全为字符编码）为:

00100101111101110110111110000101110110001101000000110001110001010000001010011111100010100101111101011011001100000101110001101110100011100111110100101011111

用码本文件和字符代码求出的破译文件为: Hello! Good morning! Wlecome to USTC!

Press any key to continue

程序运行完之后，在桌面上会有四个文件，分别对应着以上创建的文件，可以点击查看，和打印的完全一样。