综合实验报告格式--哈弗曼树--数据结构

1、华北科技学院 用哈夫曼编码实现文件压缩实验报告用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构B 实验学期 2014 至 2014 学年 第 1 学期学生所在系部 计算机系 年级 2010 专业班级 网络B10-3 学生姓名 学号 任课教师 实验成绩 一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows 系列操作系统 、Visual

2、 C+6.0软件四、实验内容：根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、概要设计： 在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。哈夫曼编码即是这样一个过程。用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫曼编码时，使哈夫曼树的左孩子上的

3、分支编码为0，右孩子上的分支编码为1。然后对文件进行压缩。压缩过程用到了文件的读写。六、详细设计：头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。定义第二个结构体，其中包含结构体数组和树根的编号。定义指针，使其指向第二个结构体。接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。将程序所用到的函数包含在头文件里。哈夫曼树的构造：在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编

4、号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。接着为哈夫曼树分配空间，然后调用asserF函数对条件进行判断，看是否满足构造哈夫曼树的条件。对含有m个字符的结点构造哈夫曼树时，将产生(2m-1)个结点。为了便于程序进行，先利用循环结构对每个结点里的左右孩子及双亲编号进行初始化，然后将m个字符中的数据从0位开始依次存入各个结点中，用pht->hti.ww=wi实现字符权值的存储， 用pht->hti. info=i实现字符数据的存储；剩下结点的权值全赋值为-1。构造哈夫曼树是这个程序的核心，也是文件是否能压缩成功的关键。从结点中选择权值最小的结点的编号分别赋给fi

5、rstMinIndex和secondMinIndex，权值也进行相应赋值，将两结点的权值相加后放到未放元素的结点处m+i；将这两个权值最小的结点的双亲编号都替换为m+i,而m+i处的左孩子放第一小的结点的编号，右孩子放第二小的结点的编号。然后从产生的m+i个结点中再找权值最小的两个，重复上述操作，直到所有的结点构成一棵树。文件在对字符进行哈夫曼编码时用到了位的运算，并且使用了递归的算法。统计权值：在统计权值时定义了两个数组，一个是字符型的数组，用于输入数据时的使用，另一个是结构体类型的数组，其中包括字符域和权值域，用于统计权值时使用。首先输入数据，并将数据存储在字符类型的数组中，然后从第一个字

6、符开始，使第一个数组中的数据与第二个数组中的字符进行比较，若相等，则字符相应的权值加1，若不相等，则将字符放入第二个数组中未放字符的数据域，权值加1。直到将第一个数组中的所有字符遍历完为止。（假设两数组分别为s1和s2，s1中含3n个字符，s2中含n个字符；s2定义如下所示 ）Struct tongji Char data; Int w;主函数：程序在运行的时候运用了文件的读写。和大多数程序一样，这个程序在最开始对所需的变量进行了定义，包括哈夫曼数组，输入文件名数组，输出文件名数组，指向文件的指针等。首先根据条件判断文件是否已打开，若没有打开则输出please enter your file

7、address.n。若打开则将argv赋给inputFileName和outputFileName，然后计算文件名的长度；将.rer连接到outputFileName的后面，以此来区分程序运行前后的文件。assertF函数的流程图：由主函数传来condition和 errorMsg的值 Condition的值为真？ F T输出errorMsg的值Abort( )统计权值流程图：向s1中输入数据当i<3nS1i=s2j.data? T FS2j.w+S2j+1.data=s1iS2j+1.w+I+哈夫曼树构造流程图：定义指针变量及整型变量分配空间 分配成功？ F T输出errorMsg的值

8、当I<2*m-1为结点的左右孩子及双亲赋值 I<m T F将结点的权值域及数据域进行赋值将权值位标记为-1i+当i<m-1当j<m+i 所指结点权值小于最小权值的值且双亲域值为-1 F T 比第二最小 权值小 T F将该结点的值赋到minFirst相应的位置将该结点的值赋到secondMin相应的位置J+将权值最小和第二小的双亲域赋值为m+i对结点M+i的相应的各位置进行赋值打开文件流程图： Argc<=1F T对inputFileName和outputFileName进行赋值输出please enter your file address将.rer连接到outp

9、utFileName后，并使inputFileName和outputFileName成为完整的字符串 打开文件成功 F T输出file path not found输出File open success七、测试结果及分析：总结体会：经过一年的学习，终于可以接触一点儿比较正式的程序，感觉真的很好。相对以前的程序，这次的程序不但在理解上有点儿难度，在程序上的运行上和以前也不同，这次是在DOS环境下运行的，而以前只是直接在程序里边进行运行。刚开始觉得很不可思议。但后来发现程序只是被分开，然后再被组装到一块儿，相对于以前的程序，更有利于多人同时编写。这个程序是对文件进行压缩，和实际生活很接近，因此这个

10、程序使我更加感觉到学好程序对生活帮助的巨大作用。该程序的核心是对结点进行哈夫曼编码，这听起来或许有点难度，但通过课上的学习，这个很容易做到，即利用循环，找权值最小的结点，构造新结点，将其构造成二叉树即可，然后进行二进制编码，并存储。这次的程序对于我最大的挑战，应该算是对于以前没有学的自学。从上小学开始，一切的学习都是老师教哪儿就看哪儿，不教的就很少去理会，即使看也只是粗略的很不详细的看，基本不会掌握很多有用的知识。可是这次实验用到的文件的运行和位运算，都是以前很少涉及的，因此要看懂程序就得自己学习，这和以前的学习有很大的不同，但更接近了大学的学习方式，很值得在以后的学习中继续运用。这应该才是学

11、习的目的，会自己学习而不是一味的靠别人学习。刚看到程序，看到有好多不认识的函数，心里感到很烦，尤其看到打印出来的那么多函数，当时真有点而泄气了。后来发现已经有好多同学开始着手综合实验，就觉得若再不做可能就只能在仓促中做，这样一学期的学习岂不是要再仓促中画上句号？这不是我想要的，因此无论如何也要把程序弄好。最初我在图书馆找了点儿对文件进行处理的程序，但是发现只有哈夫曼编码，没有压缩，后来就放弃了；在网上看到的程序都只是在C+里运行，有关文件的运算很少，所以到后来就直接用了老师的代码。看程序之前，我先把有关文件的内容看了下，发现和文件有关的函数名和以前学的函数在命名上很相似，而且都能见名知意，有了

12、以前学习的基础，有关文件这一章的内容看起来就简单多了。像这个是打开文件的fopen(inputFileName,"rb")一个语句，和字符串的复制和链接很相似，只不过这个是先输入文件名，后面是文件的打开方式；fscanf(keyFile,"%d,",&wListi);这一句是对文件进行字符的输入，语句格式为先输入文件名，然后字符类型，最后是存放的地址。这些都是文件的基本操作，简单，方便。对结点进行哈夫曼编码时，在我所看过的程序里，编码的过程都是一样的，所说语句会有所不同，但思路都是一样的，均是对结点进行赋初值，为下面的操作提供方便。然后对已有的字

13、符结点赋值，构造哈夫曼树。这些虽然简单，却是很重要的东西。统计权值，我自己感觉是用两个数组进行统计的程序更容易接受，而且在程序里加入这个函数，增加了程序的可运用性，可以自己进行文件的输入，再运用函数统计权值，进而构造哈夫曼树，实现文件压缩。不必只拘泥于一个文件，更能深刻体会文件压缩的过程。在看程序时，不但看了老师的程序，同时也看了些同学找得关于文件压缩的程序，发现程序中对函数的运用有好多，以前我一直比较排斥用函数写程序，因为在看主程序时看到陌生的函数心里很反感，有时形参和实参所用的字符不一致时还要分辨哪个字符代表哪儿个参数，看得多了就感觉都晕了。可是看过一些比较长的程序后才发现，调用函数编写程

14、序其实很简单，只要搞懂了每个程序的作用是什么，对每个函数都了如指掌，在看程序时就会发现程序的脉络很清晰，主函数就是将每个函数放到一起的一次运用。将函数要用到的变量定义好后，再调用函数，就可以将一个有特殊功能的函数编写出来。以前曾听说，在开发软件编写程序时，都是先对程序分块，好多人一块儿编写，而对程序进行划分，这需要有很丰富的编写程序的经验。这次我真正体会到了这句话的意思，只有丰富的编写程序的经验，才能对程序进行正确有效的划分，才不至于在分别编写程序时出现很多关系比较密切的程序被分开的现象。编程是一件需要长期实践以此来增长经验的过程，如果只是上课的时候学一点儿书本上得知识就想把编程学好，这是远远

15、不够的，还必须多看书，多动手，在看别人的程序时，自己也要有自己的想法，并将其付诸行动才行。而课外书则是必不可少的，在大学的这段时间应充分利用好课外时间，多读书，多思考，开充实自己。八、教师评语：教 师 评 价评定项目ABCD评定项目ABCD算法正确界面美观，布局合理程序结构合理操作熟练语法、语义正确解析完整实验结果正确文字流畅报告规范题解正确其他：评价教师签名：年 月 日Code.c文件#include "ECBTree.h"#include <stdio.h>#include <stdlib.h>#include <string.h>#

16、define LENGTH 128#define DEBUG 1#define REARPOS 80char dotTxt=".txt"char dotRer=".rer"int getBinLen(unsigned long inData);void main(int argc,char* argv)long wListLENGTH; HaffCode haffListLENGTH;PHtTree myHtTree;/file data.char inputFileNameLENGTH,outputFileNameLENGTH;FILE* inputF

17、ile,* outputFile,* keyFile;int fileNameLen;/binary opeartion data.char inData,outputData;unsignedlong curCode,tmpBinData;int curLen,realLen,curIndex;int i;int count;unsigned long rearCode;/*rear data consult*/int rearCodeLen;/open the files.if (argc<=1)printf("please enter your file address.

18、n");return;else /make up the files' name.strcpy(inputFileName,argv1);strcpy(outputFileName,argv1);fileNameLen=strlen(argv1);/only could zip the file appendix as .*,* have to be 3 char length.outputFileNamefileNameLen-4='0'strcat(outputFileName,dotRer);inputFileNamefileNameLen='0

19、'outputFileNamefileNameLen+4='0'/*inputFile open.*/if(inputFile=fopen(inputFileName,"rb")=NULL)printf("file path not foundn");return;if (DEBUG)printf("input file open successn");/*outpout file open*/assertF(outputFile=fopen(outputFileName,"wb")!=NU

20、LL,"output file error");if (DEBUG)printf("output file open successn");if(keyFile=fopen("KEY.txt","rb")=NULL)printf(">-keyFile not founded-<n");return;for(i=0;i<LENGTH-1;i+)fscanf(keyFile,"%d,",&wListi);fscanf(keyFile,"%d;&

21、quot;,&wListi);myHtTree=haffmanAlgorithm(LENGTH,wList);/step2:for(i=0;i<LENGTH;i+)haffListi.asciiCode=(char)i;preHaffListMake(myHtTree,myHtTree->rootIndex,0x000000,0,haffList);fprintf(stdout,"haffCode List:rn");for(i=0;i<LENGTH-1;i+)fprintf(stdout,"%d,",haffListi.haf

22、fCode);fprintf(stdout,"%drn",haffListi.haffCode);fprintf(stdout,"haffCode List Len:rn");for(i=0;i<LENGTH-1;i+)fprintf(stdout,"%d,",haffListi.haffCodeLen);fprintf(stdout,"%drn",haffListi.haffCodeLen);if(DEBUG)printf("ntest start.n");/starting setti

23、ng.curIndex=curLen=0;rearCode=haffListREARPOS.haffCode;rearCodeLen=haffListREARPOS.haffCodeLen;while(!feof(inputFile)count=0;outputData=0x01;while(count<8)/*-*/if(curIndex=curLen)/1.get data.if(feof(inputFile)break;inData=fgetc(inputFile);if(inData=-1&&feof(inputFile)if(count=0)outputData

24、=-1;else/*the rear output adjust*/for(i=0;i<8-count;i+)outputData<<=1;outputData|=(rearCode>>(rearCodeLen-1-i)&0x01);/*the consult below will make error happen! outputData<<=(8-count);*/break;/2.search table ->Should be a ascii file.curCode=haffListinData.haffCode;curLen=

25、haffListinData.haffCodeLen;realLen=getBinLen(curCode);i=curLen-realLen;curIndex=0;if(i>0)outputData<<=1;/no need to fill bit data.i-;elsetmpBinData=(curCode>>(curLen-curIndex-1)&0x01;outputData<<=1;outputData|=(char)tmpBinData;/*-*/curIndex+;count+;fputc(outputData,outputFil

26、e);if(DEBUG)printf("ntest ends.n");/step3:end of code.fclose(inputFile);fclose(outputFile);getchar();return;int getBinLen(unsigned long inData)int i=0;if( inData=0) return 1;elsewhile(inData!=0)inData/=2;i+;return i;ECBTree.c文件#include "ECBTree.h"#include <stdio.h>#include

27、<stdlib.h>PHtTree haffmanAlgorithm(int m,EBTreeType* w)PHtTree pht;int i,j;int firstMinIndex,secondMinIndex;int firstMinW,secondMinW;pht=(PHtTree)malloc(sizeof(struct HtTree);assertF(pht!=NULL,"in haffman algorithm,mem apply failuren");/*Initialize the tree array*/for(i=0;i<2*m-1;

28、i+)pht->hti.llinkIndex=-1;pht->hti.rlinkIndex=-1;pht->hti.parentIndex=-1;if(i<m)pht->hti.ww=wi;pht->=(char)i;else pht->hti.ww=-1;for(i=0;i<m-1;i+)/new Inner Node Num:m-1firstMinW=MAXCHAR;firstMinIndex=-1; secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;j<m+i;j+)if(pht

29、->htj.ww<firstMinW&&pht->htj.parentIndex=-1)/trans minFirst info to minSecond infosecondMinIndex=firstMinIndex;secondMinW=firstMinW;/set new first min node.firstMinIndex=j;firstMinW=pht->htj.ww;else if(pht->htj.ww<secondMinW&&pht->htj.parentIndex=-1)/*update seco

30、nd node info*/secondMinW=pht->htj.ww;secondMinIndex=j;/Construct a new node. m+i is current new node's indexpht->htfirstMinIndex.parentIndex=m+i;pht->htsecondMinIndex.parentIndex=m+i;pht->htm+i.ww=firstMinW+secondMinW;pht->htm+i.llinkIndex=firstMinIndex;pht->htm+i.rlinkIndex=secondMinIndex;pht->rootIndex=m+i;return pht;/*Invoke:preHaffListMake(myHtTree,myHtTree->rootIndex,0x00,0,myList)*/void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,Haff