哈夫曼的文件压缩解压程序

1数据结构课程设计陈正铭2教学目的与要求《数据结构》课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。通过这次课程设计，要求掌握数据结构的逻辑特性和物理表示，数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。3数据结构基本原理简要复习1．数据元素之间的四种基本逻辑结构：非线性，线性，树，图2．数据物理表示（存储方法）：顺序存储，链式存储，索引存储，散列存储3．算法的特征：有穷性，可行性，确定性，正确性算法设计的要求：可读性，健壮性，高效性44．算法的时间复杂度、空间复杂度及分析：O（1），O（n），O（logn），O（n2）5．典型的几种数据结构：顺序表，链表，顺序栈，链栈，循环队列，链队列，字符串，多维数组，二叉链表树，二叉顺序树，邻接矩阵图，邻接表图，散列表5设计题目基于哈夫曼树的文件压缩/解压程序（《数据结构课程设计案例精编》P329）该参考教材同学们可自行借阅或在网上购买（一般8折），也可联系出版社市场部集体定购（清华大学出版社市场部电话：[phone]（转分机号220）），可能有更大折扣。该参考教材内容丰富，尤其是C++语言STL方面的内容，对日后从事开发设计工作的同学有较大参考作用。但教材价格较贵，零售价45元，因此本学期没为大家指定定购，大家可按需购买，但建议购买。6STL（StandardTemplateLibrary，标准模板库）概述STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组。STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。STL提供了大量的模板类和函数，可以在OOP和常规编程中使用。所有的STL的大约50个算法都是完全通用的，而且不依赖于任何特定的数据类型。7STL组成三个基本的STL组件：1）迭代器，提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。2）容器，是一种数据结构，如list，vector，和deques，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。3）算法，是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。8STL总结尽管很多程序员仍然在使用标准C与C++函数，使用标准C函数确实方便(如使用sprintf()进行格式化输出)。但是C与C++函数不使用异常机制来报告错误，也不适合处理新的数据类型。而且标准C与C++函数经常使用内存分配技术，没有经验的程序员很容易写出bug来。.STL的最主要的两个特点：数据结构和算法的分离，非面向对象本质。访问对象是通过象指针一样的迭代器实现的；容器是象链表，矢量之类的数据结构，并按模板方式提供；算法是函数模板，用于操作容器中的数据。由于STL以模板为基础，所以能用于任何数据类型和结构。9STL示例——排序算法（1）自行写排序算法与调用；（2）调用标准C++函数qsort()完成排序；（3）部分使用STL特性；（4）完全使用STL特性。10设计要求基于哈夫曼树的文件压缩/解压程序基本要求：实现一个基于哈夫曼树的文件压缩程序和文件解压程序。要求压缩程序读入源文件，分析每种字符的频度，然后建立相应的哈夫曼树，再求出相应哈夫曼编码，根据编码对源文件进行压缩，得到源文件对应的压缩文件。解压程序读入压缩文件，根据相应的哈夫曼编码解压还原，得到对应的源文件。选做内容：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。（参考教材的本题目设计指导部分的扫描页）程序建议使用c＋＋语言完成，建议开发工具为MicrosoftVisuslC++2005Express（可在微软网站免费下载）。11设计报告撰写指导1、需求分析以无歧义的陈述说明所选设计题目的任务，强调的是程序要做什么？明确规定：输入的形式和输出、值的范围；输出的形式；程序所能达到的功能；测试的数据：包括正确的输入和错误的输入及其相应的输出结果；2、概要设计问题解决的思路概述；说明程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次（调用）关系。123、详细设计实现概要设计中定义所有数据类型，对每个操作只需要写出伪代码算法，画出函数的调用关系图。4、调试分析报告调试过程中遇到的问题并且是如何解决的以及对设计实现的回顾讨论和分析算法的时空分析（包括基本操作和主要算法的时空复杂度的分析）和改进设想经验和体会等135、用户使用说明向用户说明如何使用你编写的程序，详细列出每一步的操作步骤。6、测试结果列出测试结果，包括输入的数据和相应的输出数据。这里的测试数据应该完整和严格，最好多于需求分析中所列的测试项。7、附录（电子版文档必须要，打印版该部分可不打印）应附上带详细注释的可读性好的源程序。数据结构课程设计报告－示例文档14时间安排时间内容地点备注第1周复习数据结构相关原理，明确题目要求、确定数据结构与设计方案课室第2~8周编写程序，准备测试数据实验室或宿舍在实验室或宿舍完成编写程序任务第9周上机演示，回答教师提问，按格式撰写课程设计报告实验室课程设计报告应严格按照上述设计报告撰写要求撰写；最后将报告用A4纸打印装订；第10周以班为单位上交课程设计的资料光盘（内含每个同学的课程设计的源程序、编译后可直接运行的目标程序与课程设计报告的电子文档），课程设计报告打印稿2009年11月16日前交齐全部课程资料，逾期者以缺考处理，课程成绩0分。15考核方式与成绩程序：30％课程设计报告：70％2009年11月16日前以班为单位交齐全部课程考核资料（光盘和课程设计打印稿），逾期者以缺考处理，课程成绩0分。166.8哈夫曼树与哈夫曼编码最优树的定义如何构造最优树前缀编码17树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：一、最优树的定义1827975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895419根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;二、如何构造最优树(1)(赫夫曼算法)以二叉树为例:20在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(2)21从F中删去这两棵树，同时加入刚生成的新树;重复(2)和(3)两步，直至F中只含一棵树为止。(3)(4)229例如:已知权值W={5,6,2,9,7}56275276976713952723671395279527166713290000111100011011011124指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。三、前缀编码利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。25练习题有一份电文中共使用八种字符，频率依次为：A(0.04)，B(0.3)，C(0.08)，D(0.09)，E(0.13)，F(0.22)，G(0.03)，H(0.11)，请构造相应的哈夫曼树（要求树中所有结点的左右孩子权值必须左大右小），求出每个字符的哈夫曼编码。26解：设左子树编码为0，右子树编码为1，则A,B,C,D,E,F,G,H字符的哈夫曼编码为：A：01010B：00C：0100D：111E：011F：10G：01011H：11027电文中共使用八种字符，如果按一般方法对其进行编码，则最少需要3位码长，如：A(000)，B(001)，C(010)，D(011)，E(100)，F(101)，G(110)，H(111)，假设电文中共100个字符，按其出现频率则该电文的码长为：3*100＝300。若按哈夫曼编码A：01010（5位）B：00（2位）C：0100（4位）D：111（3位）E：011（3位）F：10（2位）G：01011（5位）H：110（3位），按其出现频率则该电文的码长（即带权路径长度WPL）为：4*5+30*2+8*4+9*3+13*3+22*2+3*5+11*3＝270，明显的压缩了30位码长。28程序设计思路文件由若干个字节组成，一个字节有8bits，故有28=256种字节构成形式，对应字节码为0-255。按此256种字节出现频率可构造haffman树进行重新编码，编码后每字节的新编码平均长度将=8bits，将每个字节对应了压缩编码写到新文件中，从而达到压缩文件的目的。