数据结构第6章实验哈弗曼解析.docVIP

数据结构 实验报告 第六章 实验名称： 文件压缩 实验类型： 综合性实验 班级： 学号： 姓名： 实验日期：2014年6月14日 问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。 根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。 数据结构设计 在实验中数据结构设为： typedef struct { char data; //存放字符 unsigned int weight;//权重 unsigned int parent,lchild,rchild;//左孩子标号，右孩子标号 }HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树 typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表 算法设计 程序分为以下几个部分： 统计数据文件里字符以及出现的次数 int *w; //存放每个字符的频数 int i; //用于各种计数 //*********************************************************** //统计1.txt中文件字符以及频数 ifstream fin(d:\\1.txt,ios::in);//从1.txt中读取字符 if(!fin) { coutFile open error!\n; return 0; } int tongji[256]; int aa; //字符对应的ascii char cc;//用来读取文件里的字符 for(int ii=0;ii256;ii++)//初始化 { tongji[ii]=0; } while((cc=fin.get())!=EOF)//从文件读取字符，并建立字符统计数组 { aa=int(cc); tongji[aa]++; } fin.close();//关闭文件 //************************************** //用于建立哈弗曼树的统计变量 unsigned int n=0; for(int ii=0;ii256;ii++) { if(tongji[ii]!=0) { n++; } } unsigned int pinshu[n];//每个字符的频数 char zifu[n];//文件中出现的字符 int n1=0;//范围从0--n-1，用于出现过字符的赋值 for(int ii=0;ii256;ii++) { if(tongji[ii]!=0) { pinshu[n1]=tongji[ii]; zifu[n1]=char(ii); ++n1; } } 依据字符出现的频率建立哈弗曼树 void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char zi[]) { // w存放n个字符的权值(均0),zi[]存放n字符，6构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i=n;++i,++p,++w,++zi) //初始化哈弗曼树 { (*p).weight=*w; (*p).data=*zi; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i=m;++i,++p) //非叶子节点的父亲为0