哈弗曼实验报告.doc

华北科技学院计算机系综合性实验报告华北科技学院计算机系综合性实验实 验 报 告 课程名称 数据结构 实验学期 2009 至 2010 学年 第 二 学期学生所在系部 计算机系 年级 2008级 专业班级 信管B081 学生姓名 XX 学号 任课教师 实验成绩 计算机系制 数据结构 课程综合性实验报告开课实验室：基础一 2010 年 6 月 22日实验题目用哈弗曼编码实现文件压缩一、实验目的1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理二、设备与环境微型计算机、Windows 系列操作系统 、Visual C+6.0软件三、实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。四、实验结果及分析1.主要结构图主函数 统计字符，得出统计出的字符的权值n编码解码退出根据权值进行建立哈夫曼树输出哈夫曼树输出编码压缩编码生成二进制文件解压生成新的文本文档2、主要函数功能 FileRead(int count,char s,char filename)压缩文档存在。对该文档进行读取，求其所有出现的字符和字符的权值。CreateHuffmanTree(HTree T,int N,int count,char s)以求得该文档的字符和权值。建立Huffman树。HuffmanCoding(HTree T,HCode H,int N,char s)求各个字符的Huffman编码。FilePrint(HTree T,HCode H,int N)求得Huffman编码以及 各节点的权值。将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中。FileWrite(HCode H,int N,char filename)求得Huffman编码以及 各节点的权值。将文档翻译成Huffman编码以字符形式存放在File.txt中。FileConvert(void)File.txt存在。将字符形式的Huffman编码翻译成二进制形式，每首季8比特就通过位操作合并成一个字节写入文件code.txt中，最后不足8 位时将最后的几位存放在Tail.txt中。FileRead(HTree T,HCode H)压缩生成的HuffmanCode.txt、Char.txt、Weight.txt存在。读取字符及其权值和其Huffman编码。FileExtract(void)压缩结果文件Code.txt和tail.txt存在。将code.txt和tail.txt中的字符写成编码的二进制字符形式，写进file00.txt。FileTrans(HTree T,HCode H,int N)已生成File00,txt并已求得各个字符的Huffman编码，Huffman树已建立。：将Huffman编码翻译成原文件，写入translated.txt。还需要包含调用若干库文件：stdio.h, malloc.h, string.h。3、 实验步骤进入主界面输出编码运行完毕处理结果如下：该文本文件保存的是测试文件中出现的字符以及相应的权值字母对应的权值，保存在Weight.txt测试文件pp.txt编码压缩以后保存在code文本文件里对应字符哈夫曼编码压缩文件根据huffman编码解压后的结果保存在Translated File.txt里面4、 主要思想生成Huffman树函数选取字符中权值最小的两个节点建树，将权值相加放在根节点中，将原节点删除，新节点放入数组。递归进行上述操作直到数组中只有一个节点为止。 算法如下： 2、建立哈夫曼树 构造哈夫曼数时，首先将n个权值的叶子结点存放到数组huffTree2*num的前n个分量中，然后不断的将两棵子树合并为一棵子树，并将新子树的根结点顺序存放到数组huffTree2*num的前n个分量的后面。设n个叶子的权值保存在数组cntn中，哈夫曼树的存储主要是利用数组存储伪代码描述为: 1. 数组哈夫曼树HuffmanTree初始化，所有元素结点的双亲、左右孩子都置为0； 2. 数组哈夫曼树HuffmanTree的前n个元素的权值给定权值cntn； 3. 进行n-1次合并 c.1、在二叉树集合中选取两个权值最小的根结点，其下标分别为i1和i2； c.2、将二叉树i1和i2合并为一棵新的二叉树对每个叶子结点进行编码： a.1初始化编码深度为0，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，深度加1，继续向上查找，这时该双亲结点已变成孩子结点，循环知道双亲结点为空，求出每一个叶子结点的深度。 a.2将编码初始结点初始化为深度+1，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，初始结点-1，如果此孩子为双亲的左孩子，则置为0，否则置为1，循环知道双亲结点为空。编码完毕压缩部分： 主要思想为： 对字符窜编码的解码是将编码窜从左到右逐为判别，直到确定一个字符。这可以用生成哈夫曼的逆过程实现。从根结点开始，根据每一位的值是0还是1确定选择左分支还是右分支，直到到达一个叶子结点，然后再从根结点出发，开始下一个字符的翻译。如根据上面的（a）哈夫曼编码树对生成的(b)字符编码表进行解码，从根结点开始，由于第一位是1，所以选择右分支，下一位又是1，又选择右分支，到达叶子结点对应的字符a。再从根结点出发，下一位是0，选择左分支，再下一位是1，则选择右分支，再下一结点为0，选择左分支，到达叶子结点对应的字符c，同理，知道所有的字符都被解出 伪代码如下： 创建新的文本文档 b、 读取压缩的二进制文件： 按照编码的先后顺序进行读取编码，当文件没结束时，读取编码，从根结点开始，如果此结点有子结点，如果读取的编码为0并且是根结点的左孩子，则将此左孩子置为根结点，如果读取的编码为1并且是根结点的右孩子，则将此右孩子置为根结点，否则的话说明已经有一个字符和编码对应了,输出，再从根结点开始，重复上述过程，知道读取的文件为空，解码完毕。 c、 关闭文件源代码#include#include#include#define MAX_SIZE 1000000#define n 150#define m 2*n-1 /-Huffman树存储结构-typedef struct char ch; int weight; int lchild,rchild,parent;HuffmanTree;typedef HuffmanTree HTreem; /-Huffman编码存储结构-typedef struct int start; char ch; char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;/-读文件-int FileRead(int count,char s,char filename) int i=0,N=0,k=0,tempn; char c; FILE *rf; rf=fopen(filename,r); if (rf=NULL) printf(cannot open filen); exit(0); for (i=0;in;i+) tempi=0; counti=0; while (!feof(rf) c=fgetc(rf); k=c; tempk+; i+; fclose(rf); for (i=0;in;i+) if (tempi!=0) sN=i; countN=tempi; N+; return N;/FileRead/-生成哈弗曼树函数-void CreateHuffmanTree(HTree T,int N,int count,char s) int i,j,p1=0,p2=0,l1,l2; for (i=0;i2*N-1;i+) Ti.lchild=0; Ti.rchild=0; Ti.parent=0; for (i=0;iN;i+) Ti.weight=counti; for (i=N;i2*N-1;i+) l1=l2=1000000; for (j=0;ji;j+) if (Tj.parent=0) if (Tj.weightl1) l1=Tj.weight, p1=j; for (j=0;ji;j+) if (Tj.parent=0) if (Tj.weightl2)&(j!=p1) l2=Tj.weight,p2=j; Tp1.parent=i; Tp2.parent=i; Ti.lchild=p1; Ti.rchild=p2; Ti.weight=Tp1.weight+Tp2.weight; T2*N-2.parent=0;/ CreateHuffmanTree/-求Huffman编码函数-void HuffmanCoding(HTree T,HCode H,int N,char s)int c,p,i,start;char cdn+1;cdN+1=0;for (i=0;iN;i+) Hi.ch=si; start=N; c=i; p=Tc.parent; while (p) if (Tp.lchild=c) cd-start=0; else cd-start=1; c=p; p=Tp.parent; Hi.start=start; strcpy(Hi.bits,cd); / HuffmanCoding/-输出解压信息函数-void FilePrint(HTree T,HCode H,int N)int i,j=0;FILE *rf,*fp,*rp;rf=fopen(HuffmanCode.txt,w);fp=fopen(Char.txt,w);rp=fopen(Weight.txt,w);while (jN) for (i=Hj.start;iN;i+) fprintf(rf,%c,Hj.bitsi); fprintf(rf,n); j+; for (i=0;iN;i+) fputc(Hi.ch,fp);for (i=0;iN;i+) fprintf(rp,%dn,Ti.weight);fclose(rf);fclose(fp);fclose(rp);/ FilePrint/-翻译成Huffman编码函数-void FileWrite(HCode H,int N,char filename)int i,k,p=0;char c;FILE *rf,*fp;rf=fopen(filename,r);fp=fopen(File.txt,w);if (rf=NULL) printf( cannot open filenn ); exit(0);while (!feof(rf) c=fgetc(rf); for (i=0;iN;i+) if (Hi.ch=c) for (k=Hi.start;kN;k+) fputc(Hi.bitsk,fp),p+; if (p=8) fprintf(fp, ); p=0; fclose(rf);fclose(fp);/ FileWrite/-压缩函数-void FileConvert(void)int i=0,k=0,temp=0,l;char st10;FILE *rf,*fp,*rp;rf=fopen(File.txt,r);fp=fopen(Code.txt,wb);rp=fopen(Tail.txt,w);if (rf=NULL) printf( cannot open filenn ); exit(0); while (!feof(rf) sti=fgetc(rf); switch(sti) case0: k=2*k+0; i+;break; case1: k=2*k+1; i+;break; case : fwrite(&k,1,1,fp); temp+; k=0; i=0;break; default: fprintf(rp,%d ,temp); for (k=0;ki;k+) fprintf(rp,%c,stk);break; fclose(rf);fclose(fp);fclose(rp);l=remove(File.txt);/ FileConvert/-读取解压信息函数-int JYFileRead(HTree T,HCode H) int i=0,j=0,N=0; char c,*p; char strMAX_SIZE; FILE *rf,*fp,*rp; rf=fopen(Char.txt,r); fp=fopen(HuffmanCode.txt,r); rp=fopen(Weight.txt,r); if (rf=NULL) printf(cannot open filen); exit(0); if (fp=NULL) printf(cannot open filen); exit(0); if (rp=NULL) printf(cannot open filen); exit(0); while (!feof(rf) HN.ch=fgetc(rf); TN.ch=HN.ch; N+; while (!feof(fp) c=fgetc(fp); switch(c) casen: i+; j=0;break; default: Hi.bitsj=c; j+; Hi.bitsj=0;break; for (i=0;iN;i+) Ti.weight=0; i=0; j=0; while (!feof(rp) c=fgetc(rp); switch(c) casen: for (p=str;*p!=0;p+) Ti.weight=Ti.weight*10+*p-48; i+; j=0;break; default: strj=c; j+; strj=0;break; fclose(rf); fclose(fp); fclose(rp); return N-1;/JYFileRead/-翻译为二进制文档函数-/将Code.txt重新翻译成二进制，在以字符形式输入到File00.txt中，再将Tail.txt中的最后编码复制到File.txt的最后。int FileExtract(void) int i,j=0,k=0,t,temp=0; unsigned char c; char s8; FILE *rf,*fp,*rp; rf=fopen(Tail.txt,r); fp=fopen(File00.txt,w); rp=fopen(File00.txt,a); if (rf=NULL) printf(cannot open filen); exit(0); fscanf(rf,%d %s,&temp,s); fclose(rf); rf=fopen(Code.txt,rb); if (rf=NULL) printf(cannot open filen); exit(0); while (j=0;i-) t=c; t=i; t&=1; if (k=0&t=1) k=1; if (k=1) fprintf(fp,%d,t); fprintf(fp, ); fclose(rf); fclose(fp); for (i=0;si!=0;i+) fprintf(rp,%c,si); fclose(rf); fclose(rp); return temp;/ FileExtract/-翻译为Huffman编译文档函数 -/读取二进制文档，从根节点开始找叶子节点，遇到1找左节点，遇到0找右节点，直到为叶子节点为止，/输出叶子节点的字符，最后删除中间文件File00.txt。float FileTrans(HTree T,HCode H,int N) int i=2*N-2,l; float temp=0.0; char c; FILE *rf,*fp; rf=fopen(File00.txt,r); fp=fopen(Translated File.txt,w); if (rf=NULL) printf(cannot open filen); exit(0); while(!feof(rf) c=fgetc(rf);if (Ti.lchild|Ti.rchild) if (c=0) i=Ti.lchild; else if (c=1) i=Ti.rchild; else fputc(Ti.ch,fp); temp+; i=2*N-2; if (c=0) i=Ti.lchild; else if (c=1) i=Ti.rchild; fclose(rf); fclose(fp); l=remove(File00.txt); return temp;/ FileTrans/*输出HuffmanTree存储结构*void print1(HTree HT,int N )printf(初始状态为n);int x; for(x=1;x=N;x+) HTx.parent=0;HTx.lchild=0;HTx.rchild=0;printf(%11d %dt %dt %dn,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild);printf(-n); void print2(HTree HT,int N)printf(末状态为n);int k;for(k=1;k=2*N-1;k+) printf( %dt %dt %dt %dn,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild);printf(-n); /-void main()HTree T;HCode H;int N,M,a;int countn;int temp01;float temp02;char sn,filename10;printf(n);printf(Input Filenamen);scanf(%s,filename);N=FileRead(count,s,filename);CreateHuffmanTree(T,N,count,s);HuffmanCoding(T,H,N,s);printf(n);abc:printf(-n);printf( 1.哈弗曼存储结构n);printf( 2.压缩n);printf( 3.解压n);printf( 4.退出n);printf(-n);printf(请输入选项（04）：);scanf(%d,&a);getchar();switch(a) case 1:system(cls);print1(T, N );print2(T, N );goto abc;break;case 2:system(cls);printf(CharacterIn Char.txtn); printf(CharacterWeight In Weight.txtn); FilePrint(T,H,N); printf(Huffman Code In HuffmanCode.txtn); FileWrite(H,N,filename); FileConvert(); printf(Code File In Code.txtn); printf(Tail File In Tail.txtn)