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

* * 数据结构课程设计 陈正铭 教学目的与要求 《数据结构》课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 通过这次课程设计，要求掌握数据结构的逻辑特性和物理表示，数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 数据结构基本原理简要复习 1．数据元素之间的四种基本逻辑结构： 非线性，线性，树，图 2．数据物理表示（存储方法）： 顺序存储，链式存储，索引存储，散列存储 3．算法的特征： 有穷性，可行性，确定性，正确性 算法设计的要求： 可读性，健壮性，高效性 4．算法的时间复杂度、空间复杂度及分析： O（1），O（n），O（logn），O（n2） 5．典型的几种数据结构： 顺序表，链表， 顺序栈，链栈，循环队列，链队列， 字符串， 多维数组， 二叉链表树，二叉顺序树， 邻接矩阵图，邻接表图， 散列表 设计题目 基于哈夫曼树的文件压缩/解压程序 （《数据结构课程设计案例精编》P329） 该参考教材同学们可自行借阅或在网上购买（一般8折），也可联系出版社市场部集体定购（清华大学出版社市场部电话：010转分机号220）），可能有更大折扣。 该参考教材内容丰富，尤其是C++语言 STL方面的内容，对日后从事开发设计工作的同学有较大参考作用。但教材价格较贵，零售价45元，因此本学期没为大家指定定购，大家可按需购买，但建议购买。 STL（Standard Template Library，标准模板库）概述 STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组。 STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。 STL提供了大量的模板类和函数，可以在OOP和常规编程中使用。所有的STL的大约50个算法都是完全通用的，而且不依赖于任何特定的数据类型。 STL示例——排序算法 （1）自行写排序算法与调用； （2）调用标准C++函数qsort()完成排序； （3）部分使用STL特性； （4）完全使用STL特性。 设计要求 基于哈夫曼树的文件压缩/解压程序 基本要求：实现一个基于哈夫曼树的文件压缩程序和文件解压程序。要求压缩程序读入源文件，分析每种字符的频度，然后建立相应的哈夫曼树，再求出相应哈夫曼编码，根据编码对源文件进行压缩，得到源文件对应的压缩文件。解压程序读入压缩文件，根据相应的哈夫曼编码解压还原 ，得到对应的源文件。 选做内容：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。 （参考教材的本题目设计指导部分的扫描页） 程序建议使用c＋＋语言完成，建议开发工具为Microsoft Visusl C++ 2005 Express（可在微软网站免费下载）。 设计报告撰写指导 1、 需求分析 以无歧义的陈述说明所选设计题目的任务，强调的是程序要做什么？明确规定：输入的形式和输出、值的范围；输出的形式；程序所能达到的功能；测试的数据：包括正确的输入和错误的输入及其相应的输出结果； 2、 概要设计 问题解决的思路概述；说明程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次（调用）关系。 3、 详细设计 实现概要设计中定义所有数据类型，对每个操作只需要写出伪代码算法，画出函数的调用关系图。 4、 调试分析报告 调试过程中遇到的问题并且是如何解决的以及对设计实现的回顾讨论和分析算法的时空分析（包括基本操作和主要算法的时空复杂度的分析）和改进设想经验和体会等 5、 用户使用说明 向用户说明如何使用你编写的程序，详细列出每一步的操作步骤。 6、 测试结果 列出测试结果，包括输入的数据和相应的输出数据。这里的测试数据应该完整和严格，最好多于需求分析中所列的测试项。 7、 附录（电子版文档必须要，打印版该部分可不打印） 应附上带详细注释的可读性好的源程序