哈弗曼编码实验报告

实验题目：哈弗曼编码译码

实验目的:（1）熟悉对文件的有关操作

（2）掌握哈弗曼树的概念和存储结构 （3）利用哈弗曼方法对指定文件进行编码和译码

实验内容：给定一个电文文件进行编码，编码后进行哈弗曼译码，译码后的结果

存储在文件2中，对文件2进行解码并将结果储存在文件3中。

一、需求分析

1.本实验需要先给出一个文件1.txt，程序对文件进行统计，构造哈弗曼树，进行哈弗曼编码和解码的相关操作。

2.程序应能输出字符的及每个字符的个数，并输出每个字符的哈弗曼编码 3.程序能将哈弗曼编码后的文件存储在2.txt中，并将解码文件存储在3.txt中

二、概要设计

为了完成本次实验，应以树为存储结构： 首先设计结构体 typedef struct{ int weight;

int parent,lchild,rchild; }HTNode,HuffmanTree;

其中： weight:权值域,保存该结点的权值;

lchild:指针域,保存该结点的左孩子结点在数组中的下标; rchild:指针域,保存该结点的右孩子结点在数组中的下标; parent:指针域,保存该结点的双亲结点在数组中的下标. 1.基本操作： (1) CountFre() 初始条件：文件1.txt存在 操作结果：统计文件中字符种类个数和每个字符出现的次数 (2) Select(HT,i-1,s1,s2); 初始条件：哈弗曼树HT存在。 操作结果： 在HT[1...i-1]选择parent为0且weight最小的两个节点，其 序号分别为s1,s2。 (3) HuffmanCoding(&HT, HC,w, n) 初始条件：无 操作结果：w存放n个字符的权值（均>0）构造哈弗曼树HT，并求出n 个字符的哈弗曼编码HC (4) TransFile(HC,n); 初始条件：哈弗曼树HT存在。 操作结果：将文件进行哈弗曼编码，并将编码存储在文件2.txt中 (5)HuffmanDecoding(HT,n); 初始条件：哈弗曼树HT存在。 操作结果：将哈弗曼编码的文件进行哈弗曼解码，并将解码存储在3.txt 中 2.本程序包含三个模块：

(1)主程序模块； (2)创建二叉树模块； (3)遍历二叉树模块； 三、详细设计 1.元素类型，结点类型和指针类型： typedef struct BiTNode{ char data;//数据域 struct BiTNode *lchild,*rchild;//左孩子右孩子指针 }BiTNode,*BiTree; 2.每个模块的分析： 主程序模块： int main() {

HuffmanTree HT;//定义哈弗曼树HT HuffmanCode HC;

printf(\对文件1.txt进行统计结果如下：\\n\ CountFre();

HuffmanCoding(&HT,HC,w,k);

printf(\经过哈弗曼编码后的文件存储在文件2.txt中,解码后的文件存储在文 件3.txt中\\n\ return 0; } 3. 统计字符模块 int CountFre() {//统计字符和每个字符出现的次数 FILE* fp;

fp=fopen(\ char c;

int i,fre[128]={0};//fre数组用以保存字符出现次数 if(fp==NULL) printf(\异常处理 while(!feof(fp))//判断是否到文件末尾 { fread(&c,1,1,fp);//依次读取文件字符 if(c!='\\n') fre[c]+=1; } printf(\ 字符 权数\\n\ for(i=0,k=1;i<128;i++) if(fre[i]!=0) {//忽略次数为0的字符 printf(\第%d个字符为: \ printf(\ %d\\n\ w[k]=fre[i];data[k]=i;//添加新的字符表 k++;

}

k--;//k为字符种类的个数 fclose(fp);//关闭文件 return 0; }//CountFre 4.编码和解码模块 int TransFile(HuffmanCode HC,int n) {//对文件进行哈弗曼编码 int i; char c;

FILE* fp1,*fp2;//定义文件指针变量 fp1=fopen(\ fp2=fopen(\ if(fp1==NULL) printf(\异常处理 while(!feof(fp1))//判断是否到文件末尾 { fread(&c,1,1,fp1);//依次读取文件字符 if(feof(fp1)) break; if(c=='\\n')//c为换行号则直接将c读入到文件中 fputc(c,fp2); for(i=1;i<=n;i++) {

if(c==data[i]&&c!='\\n')

fprintf(fp2,\将字符对应的哈弗曼编码写入到文件中 } }

fclose(fp1);//关闭文件 fclose(fp2);//关闭文件 return 0; }//TransFile int HuffmanDecoding(HuffmanTree HT[],int n) {//对经哈弗曼编码的文件进行哈弗曼解码 FILE *fp3,*fp4; int i,s1,m; char c; m=2*n-1;

fp3=fopen(\ fp4=fopen(\

if(fp3==NULL) printf(\ while(!feof(fp3)) {

s1=m;

while(s1>n)

{//当s1<=n时，则意味着访问到叶子节点 fread(&c,1,1,fp3); if(feof(fp3)) break;

if(c=='0') s1=HT[s1].lchild;//如果c为0，则访问HT[s1]的左孩子 if(c=='1') s1=HT[s1].rchild;//如果c为1，则访问HT[s1]的右孩子 if(c=='\\n') fputc(c,fp4); if(s1<=n&&feof(fp3))

fprintf(fp4,\ }

if(feof(fp3)) break; //将解码后的字符读入到文件中 }

fclose(fp3);fclose(fp4); return 0; } int HuffmanCoding(HuffmanTree HT[],HuffmanCode HC,int *w,int n) {//w存放n个字符的权值（均>0）构造哈弗曼树HT，并求出n个字符的哈 弗曼编码HC int i,m,s1,s2,f,c,start; char *cd;

if(n<=1) return 0;//异常处理 m=2*n-1;

HT=(HuffmanTree *)malloc((m+1)*sizeof(HTNode));//0号单元未用 for(i=1;i<=m;++i)

{//对哈弗曼树进行初始化 HT[i].lchild =0; HT[i].rchild =0; HT[i].parent =0;

if (i<=n)HT[i].weight=w[i]; else HT[i].weight=0; }

for(i=n+1;i<=m;i++) {//建哈弗曼树

Select(HT,i-1,s1,s2);

//在HT[1...i-1]选择parent为0且weight最小的两个节点，其序号分别为s1,s2。 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((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)); //为第i个字符编码分配空间

strcpy(HC[i],&cd[start]);//从cd复制编码串到HC

printf(\的哈弗曼编码：\输出第i个字符 printf(\输出第i个字符的哈弗曼编码 }

TransFile(HC,n);

HuffmanDecoding(HT,n); //调用函数 free(cd); } int Select(HuffmanTree HT[],int n,int &x1,int &x2)

{//在HT[1...i-1]选择parent为0且weight最小的两个节点，其序号分别为x1,x2。 int i;

int m1=9999, m2=9999;//相关变量赋初值

for (i=1;i<=n;i++)//找两个最小权的无父结点的结点 {//扫描

if (HT[i].weight

m2=m1; x2=x1; m1=HT[i].weight; x1=i; } else if(HT[i].weight

m2=HT[i].weight; x2=i; } }

return 0; }//Select 4.函数调用关系： main函数 {

CountFre();

HuffmanCoding(&HT,HC,w,k); } int HuffmanCoding(HuffmanTree HT[],HuffmanCode HC,int *w,int n) { Select(HT,i-1,s1,s2); TransFile(HC,n);

HuffmanDecoding(HT,n); }

本文来源：https://www.bwwdw.com/article/ozr2.html