《用哈夫曼编码实现文件压缩》由会员分享，可在线阅读，更多相关《用哈夫曼编码实现文件压缩（13页珍藏版）》请在金锄头文库上搜索。
1、1用哈夫曼编码实现文件压缩实 验 项 目 指 导 书数据结构实验教学改革课题组2006 年 12 月2一、 实验题目用哈夫曼编码实现文件压缩二、 实验目的1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握 Huffman 树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用 Huffman 树及 Huffman 编码，掌握实现文件压缩的一般原理。三、 实验设备及环境微型计算机、Windows 系列操作系统 、Visual C+6.0 软件四、 实验内容根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Haffman 树，再将各字符对应的哈夫曼编码写入文
2、件中，实现文件压缩。五、 实验要求1、用 C 语言编程实现上述实验内容中的结构定义和算法。2、要有 main()函数，并且在 main()函数中使用检测数据调用上述算法。3、实验完成后撰写实验报告，实验报告的具体格式参见实验报告样例 。4、实验完成后把打印好的实验报告以及电子版的实验报告和源程序一并上交。六、 实验方法或或步骤1、实验的预备知识（1）构造 Hufffman 树的方法Hufffman 算法构造 Huffman 树步骤：I. 根据给定的 n 个权值w1,w2,wn，构造 n 棵只有根结点的二叉树，令起权值为 wj。II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二
3、叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV. 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman 编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造 Huffman 树，然后将树中结点引向其左孩子的分支标“0” ，引向其右孩子的分支标“1” ；每个字符的编码即为从根到每个叶子的路径上得到的 0、1 序列。（3）二叉树的存储结构typedef struct node datatype data;struct node *lchild, *rchild
4、;3BinTree;2、实验步骤（1） 启动 Visual c+6.0，如图 2-1 所示。图 2-1(2)鼠标单击“文件”菜单，选择“New”菜单，如图 2-2 所示。图 2-2（3） 、单击鼠标，在出现的“New”对话框中，选择“Projects”标签下的“Win32 Console Application”选项，如图 2-3 所示。4图 2-3（4） 、在“Project name”中输入工程名称，单击“OK”按钮，如图 2-4 所示。图 2-4（5） 、单击“Finish”按钮，如图 2-5 所示。5图 2-5（6） 、鼠标单击“OK”按钮，完成工程的创建，如图 2-6 所示。图 2-
5、6（7） 、选择“工程” “添加工程” “New”菜单，如图 2-7 所示。6图 2-7（8） 、单击鼠标，在出现的“New” 对话框中，选择“Files”标签，选择“c+ Source File”选项，在“File”框中输入文件名：“code.c”,单击“OK”按钮，如图 2-8 所示。7图 2-8（9） 、输入代码，如图 2-9 所示。图 2-93、设计思想（1）下面给出中实现的 Haffman 树的结构及创建算法，有两点说明：a) 这里的 Haffman 树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b) 由于对于最后生成
6、的 Haffman 树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为 m 个时，内部结点数为 m-1，整个Haffman 树的需要的结点数为 2m-1。/*Code1: Haffman Algorithm*/#define MAXCHAR 30000#define MAXNODE 300#define MAXNUM 150#define InfoType charstruct HtNodeEBTreeType ww;char info;int parentIndex;int llinkIndex;int rlinkIndex;8;struct HtTreestruct H
7、tNode htMAXNODE;int rootIndex;typedef struct HtTree* PHtTree;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 th
8、e 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 first min node.firstMinIndex=
9、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+i;pht-htm+i.ww=firstMinW+secondMinW;pht-htm+i.llin
10、kIndex=firstMinIndex;pht-htm+i.rlinkIndex=secondMinIndex;pht-rootIndex=m+i;return pht;（2）压缩过程的实现：压缩过程的流程是清晰而简单的：1 创建 Haffman 树 2 打开需压缩文件3 将需压缩文件中的每个 ascii 码对应的 haffman 编码按 bit 单位输出4 文件压缩结束。其中，步骤 1 和步骤 3 是压缩过程的关键。a) 步骤 1:这里所要做工作是得到 Haffman 数中各叶子结点字符出现的频率并进行创建。统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件， “实时”的生成各
11、字符的出现频率；或者是创建前即做好统计。本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩 C 语言的源文件，则可事先对多篇 C 语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的 Haffman 树，从而提高压缩效果。10b) 步骤 3: 将需压缩文件中的每个 ascii 码对应的 haffman 编码按 bit 单位输出，这是本压缩程序中最关键的部分。这里涉及“转换”和“输出”两个关键步骤：“转换”部分大可不必去通过遍历 Haffman 树来找到每个字符对应的哈夫曼编码，可以将每个 Haffman 码值及其
12、对应的 ascii 码存放于如下所示的结构体中：typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode;创建由该结构体结点所组成的，长度为 128 的一维数组 codeList128且 codeList 中的下标和 asciiCode 满足下面的顺序存放关系：codeListi.asciiCode=i;这样的话，查找某个字符 inChar 的 haffman 编码的工作便变得相当轻松了,如下：sHaffCode=codeListinChar.haffCode;数组 codeList128的创建可以
13、采用某种遍历方式下的按找到的字符进行置数的方式，十分的方便。/*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-htrootIndex.info.haffCode=youBiao;inListinTree-ht
14、rootIndex.info.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree-htrootIndex.llinkIndex,youBiaohtrootIndex.rlinkIndex,(youBiao(rearCodeLen-1-i)break;/2.search table -Should be a ascii file.curCode=haffListinData.haffCode;curLen=haffListinData.haffCodeLen;realLen=getBinLen(curCode);i=curLen-realLen;curIndex=0;if(i0)outputData(curLen-curIndex-1)outputData=1;13outputData|=(char)tmpBinData;/*-*/curIndex+;count+;fputc(outputData,outputFile);
