数据结构综合实验报告.doc

华北科技学院计算机学院综合性实验报告实 验 报 告 课程名称 数据结构B 实验学期 2018 至 2019 学年 第 一 学期学生所在系部 年级 专业班级 学生姓名 学号 2017 任课教师 实验成绩 计算机学院制数据结构课程综合性实验报告开课实验室： 软件工程实验室 2018年 11 月 23日实验题目用赫夫曼编码实现文件压缩一、实验目的1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。二、设备与环境微型计算机、Windows 系列操作系统 、Visual C+6.0软件三、实验内容1、 实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。2、实验要求a、用C语言编程实现上述实验内容中的结构定义和算法。b、要有main()函数，并且在main()函数中使用检测数据调用上述算法。3、最后结果输出。要求：输出格式要界面直观、清晰大方、格式规范。四、实验方法或步骤1、实验的预备知识（1）构造Hufffman树的方法Hufffman算法构造Huffman树步骤：I.根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj。II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。（3）二叉树的存储结构 typedef struct node datatype data; struct node *lchild, *rchild;BtTree2、设计思想（1）实现的Haffman树的结构及创建算法，有两点说明：a) 这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b) 由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1，整个Haffman树的需要的结点数为2m-1。编码部分（2）压缩过程的实现：压缩过程的流程是清晰而简单的：1创建Haffman树2打开需压缩文件3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出4文件压缩结束。其中，步骤1和步骤3是压缩过程的关键。步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建。统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率；或者是创建前即做好统计。本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出，这是本压缩程序中最关键的部分。这里涉及“转换”和“输出”两个关键步骤：“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode;创建由该结构体结点所组成的，长度为128的一维数组codeList128且codeList中的下标和asciiCode满足下面的顺序存放关系：codeListi.asciiCode=i;这样的话，查找某个字符inChar的haffman编码的工作便变得相当轻松了,如下：sHaffCode=codeListinChar.haffCode;数组codeList128的创建可以采用某种遍历方式下的按找到的字符进行置数的方式，十分的方便。/*Code2:codeList的创建算法,采用前序遍历的方式进行创建.*/void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList)if(inTree-htrootIndex.llinkIndex=-1&inTree-htrootIndex.rlinkIndex=-1)inListinTree-htrootI.haffCode=youBiao;inListinTree-htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree-htrootIndex.llinkIndex,youBiaohtrootIndex.rlinkIndex,(youBiao1)|0x01,sDepth+1,inList);“输出”部分是最重要的部分，也是最易出错的部分。这里，涉及到C语言的位操作,要求这个算法能处理好以下几个问题：1)每个字符所对应的haffCode的比特位长度由523位不等长，不可少输，多输，输错任何一位，后一个字符的haffCode要紧跟在前一个字符的haffCode后面。2)最后一个字符要能合理的结束。这主要是为解压缩考虑的，比如，在最后一个要输出的haffCode的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个比特位是要用无效的haffCode加以填充的。否则，如果填充的haffCode亦为某个ascii字符的haffCode时，那么在解压缩时，则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现，这显然是不正确的，应在程序中加以处理。编码部分的流程如图3-1所示：图3- 1#include #include #include #include struct head unsigned char b; /记录字符在数组中的位置 long count; /字符出现频率（权值） long parent,lch,rch; /定义哈夫曼树指针变量 char bits256; /定义存储哈夫曼编码的数组header512,tmp;/*压缩*/void compress() char filename255,outputfile255,buf512; unsigned char c; long i,j,m,n,f; long min1,pt1,flength,length1,length2; double div; FILE *ifp,*ofp; /printf(t请您输入需要压缩的文件：); /gets(filename);strcpy(filename,yuan.txt); ifp=fopen(filename,rb); if(ifp=NULL) printf(nt文件打开失败!nn); return; /printf(t请您输入压缩后的文件名：); /gets(outputfile); strcpy(outputfile,yuanys.txt); /ofp=fopen(strcat(outputfile,.hub),wb); ofp=fopen(outputfile,wb); if(ofp=NULL) printf(nt压缩文件失败!nn); return; flength=0; while(!feof(ifp) fread(&c,1,1,ifp); headerc.count+; /字符重复出现频率+1 flength+; /字符出现原文件长度+1 flength-; length1=flength; /原文件长度用作求压缩率的分母 headerc.count-; for(i=0;i512;i+) if(headeri.count!=0) headeri.b=(unsigned char)i; /*将每个哈夫曼码值及其对应的ASCII码存放在一维数组headeri中， 且编码表中的下标和ASCII码满足顺序存放关系*/ else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化 for(i=0;i256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树 for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i; /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1. m=2*n-1; for(i=n;im;i+) /构建哈夫曼树 min1=999999999; /预设的最大权值，即结点出现的最大次数 for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; /依据parent域值（结点层数）确定树中结点之间的关系 headeri.lch=pt1; /计算左分支权值大小 min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; /计算右分支权值大小 headerpt1.parent=i; for(i=0;in;i+) /哈夫曼无重复前缀编码 f=i; headeri.bits0=0; /根结点编码0 while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.lch=j) /置左分支编码0 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); /依次存储连接“0”“1”编码 headeri.bits0=0; else /置右分支编码1 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; fseek(ifp,0,SEEK_SET); /从文件开始位置向前移动0字节，即定位到文件开始位置 fwrite(&flength,sizeof(int),1,ofp); /*用来将数据写入文件流中，参数flength指向欲写入的数据地址， 总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/ fseek(ofp,8,SEEK_SET); buf0=0; /定义缓冲区,它的二进制表示00000000 f=0; pt1=8; /*假设原文件第一个字符是A，8位2进制为01000001，编码后为0110识别编码第一个0， 那么我们就可以将其左移一位，看起来没什么变化。下一个是1，应该|1，结果00000001 同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符， 根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符， 如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/ while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /对哈夫曼编码位操作进行压缩存储 for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /对哈夫曼编码位操作进行压缩存储 strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /若存储的位数不是8的倍数，则补0 for(f=j%8;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) c=0; for(j=0;j8;j+) /字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接 if(headeri.bitsj=1) c=(c1)|1; /|1不改变原位置上的“0”“1”值 else c=c1; strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接 fwrite(&c,1,1,ofp); length2=pt1-; div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率 fclose(ifp); fclose(ofp); printf(nt压缩文件成功!n); printf(t压缩率为 %f%nn,div*100); /*解压缩*/void uncompress() char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; /printf(t请您输入需要解压缩的文件：); /gets(filename); strcpy(filename,yuanys.txt); /ifp=fopen(strcat(filename,.hub),rb); ifp=fopen(filename,rb); if(ifp=NULL) printf(nt文件打开失败!n); return; /printf(t请您输入解压缩后的文件名：); /gets(outputfile);strcpy(outputfile,yuanjy.txt); ofp=fopen(outputfile,wb); if(ofp=NULL) printf(nt解压缩文件失败!n); return; fread(&flength,sizeof(long),1,ifp); /读取原文件长度，对文件进行定位 fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i0) m=p/8+1; else m=p/8; for(j=0;jf;l-) strcat(headeri.bits,0); strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) /根据哈夫曼编码的长短，对结点进行排序 for(j=i+1;jstrlen(headerj.bits) tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(headern-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0; while(1) /通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储 while(strlen(bx)f;l-) /在单字节内对相应位置补0 strcat(bx,0); strcat(bx,buf); for(i=0;in;i+) if(memcmp(headeri.bits,bx,headeri.count)=0) break; strcpy(bx,bx+headeri.count); /*从压缩文件中的按位存储还原到按字节存储字符，字符位置不改变*/ c=headeri.b; fwrite(&c,1,1,ofp); m+; /统计解压缩后文件的长度 if(m=flength) break; /flength是原文件长度 fclose(ifp); fclose(ofp); printf(nt解压缩文件成功!n)