《综合实验报告格式--哈弗曼树--数据结构》由会员分享，可在线阅读，更多相关《综合实验报告格式--哈弗曼树--数据结构（18页珍藏版）》请在金锄头文库上搜索。
1、华北科技学院 用哈夫曼编码实现文件压缩实验报告用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构 B 实验学期 2014 至 2014 学年 第 1 学期学生所在系部 计算机系 年级 2010 专业班级 网络 B10-3 学生姓名 学号 任课教师 实验成绩 华北科技学院 用哈夫曼编码实现文件压缩实验报告一、 实验题目 ：用哈夫曼编码实现文件压缩二、 实验目的 ：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握 Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用 Huffman树及 Huffman编码，掌握实现文件压缩的一般原理。三、 实验设备与
2、环境 ：微型计算机、Windows 系列操作系统 、Visual 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 实现字
5、符数据的存储；剩下结点的权值全赋值为-1。构造哈夫曼树是这个程序的核心，也是文件是否能压缩成功的关键。从结点中选择权值最小的结点的编号分别赋给 firstMinIndex 和 secondMinIndex，权值也进行相应赋值，将两结点的权值相加后放到未放元素的结点处 m+i；将这两个权值最小的结点的双亲编号都替换为 m+i,而 m+i 处的左孩子放第一小的结点的编号，右孩子放第二小的结点的编号。然后从产生的 m+i 个结点中再找权值最小的两个，重复上述操作，直到所有的结点构成一棵树。文件在对字符进行哈夫曼编码时用到了位的运算，并且使用了递归的算法。统计权值：在统计权值时定义了两个数组，一个是字
6、符型的数组，用于输入数据时的使用，另一个是结构体类型的数组，其中包括字符域和权值域，用于统计权值时使用。首先输入数据，并将数据存储在字符类型的数组中，然后从第一个字符开始，使第一个数组中的数据与第二个数组中的字符进行比较，若相等，则字符相应的权值加 1，若不相等，则将字符放入第二个数组中未放字符的数据域，权值加 1。直到将第一个数组中的所有字符遍历完为止。 （假设两数组分别为 s1和 s2， s1 中含 3n 个字符，s2 中含 n 个字符；s2 定义如下所示 ）Struct tongjiChar data;Int w;主函数：程序在运行的时候运用了文件的读写。和大多数程序一样，这个程序在最开
7、始对所需的变量进行了定义，包括哈夫曼数组，输入文件名数组，输出文件名数组，指向文件的指针等。首先根据条件判断文件是否已打开，若没有打开则输出 please enter your file address.n。若打开则将 argv 赋给 inputFileName 和 outputFileName，然后计算文件名的长度；将.rer 连接到 outputFileName 的后面，以此来区分程序运行前后的文件。华北科技学院 用哈夫曼编码实现文件压缩实验报告assertF 函数的流程图：由主函数传来 condition 和 errorMsg 的值Condition 的值为真？FT输出 errorMsg
8、 的值 Abort( )统计权值流程图：向 s1 中输入数据当 i#include #include #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,outp
9、utFileNameLENGTH;FILE* inputFile,* outputFile,* keyFile;int fileNameLen;华北科技学院 用哈夫曼编码实现文件压缩实验报告/binary opeartion data.char inData,outputData;unsigned long curCode,tmpBinData;int curLen,realLen,curIndex;int i;int count;unsigned long rearCode;/*rear data consult*/int rearCodeLen;/open the files.if (ar
10、gc-keyFile not founded-rootIndex,0x000000,0,haffList);fprintf(stdout,haffCode List:rn);for(i=0;i(rearCodeLen-1-i)/* the consult below will make error happen!outputDataShould be a ascii file.curCode=haffListinData.haffCode;curLen=haffListinData.haffCodeLen;realLen=getBinLen(curCode);i=curLen-realLen;
11、curIndex=0;if(i0)outputData(curLen-curIndex-1)outputData#include 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 appl
12、y failuren);/*Initialize the tree array*/for(i=0;ihti.llinkIndex=-1;pht-hti.rlinkIndex=-1;pht-hti.parentIndex=-1;if(ihti.ww=wi;pht-hti.info=(char)i;else pht-hti.ww=-1;for(i=0;ihtj.wwhtj.parentIndex=-1)/trans minFirst info to minSecond infosecondMinIndex=firstMinIndex;secondMinW=firstMinW;/set new fi
13、rst min node.firstMinIndex=j;firstMinW=pht-htj.ww;else if(pht-htj.wwhtj.parentIndex=-1)/*update second node info*/secondMinW=pht-htj.ww;secondMinIndex=j;华北科技学院 用哈夫曼编码实现文件压缩实验报告/Construct a new node. m+i is current new nodes indexpht-htfirstMinIndex.parentIndex=m+i;pht-htsecondMinIndex.parentIndex=m+
14、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,HaffCode* inList)if(inTree-htrootIndex.llinkIndex=-1&inTree-htrootIndex.rlinkIndex=-1)inListinTree-htrootIndex.info.haffCode=youBiao;inListinTree-htrootIndex.info
