数据结构课程设计基于哈夫曼的文件压缩解压程序.pptVIP

数据结构课程设计 陈正铭 教学目的与要求 《数据结构》课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 通过这次课程设计，要求掌握数据结构的逻辑特性和物理表示，数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 数据结构基本原理简要复习 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组成 三个基本的STL组件： 1）迭代器，提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。 2）容器，是一种数据结构，如list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。 3）?算法，是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来有哪些信誉好的足球投注网站一个list中的对象。函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。 STL总结 尽管很多程序员仍然在使用标准C与C++函数，使用标准C函数确实方便(如使用sprintf()进行格式化输出)。但是C与C++函数不使用异常机制来报告错误，也不适合处理新的数据类型。而且标准C与C++函数经常使用内存分配技术，没有经验的程序员很容易写出bug来。. STL的最主要的两个特点：数据结构和算法的分离，非面向对象本质。访问对象是通过象指针一样的迭代器实现的；容器是象链表，矢量之类的数据结构，并按模板方式提供；算法是函数模板，用于操作容器中的数据。由于STL以模板为基础，所以能用于任何数据类型和结构。 STL示例——排序算法 （1）自行写排序算法与调用； （2）调用标准C++函数qsort()完成排序； （3）部分使用STL特性； （4）完全使用STL特性。 设计要求 基于哈夫曼树的文件压缩/解压程序 基本要求：实现一个基于哈夫曼树的文件压缩程序和文件解压程序。要求压缩程序读入源文件，分析每种字符的频度，然后建立相应的哈夫曼树，再求出相应哈夫曼编码，根据编码对源文件进行压缩，得到源文件对应的压缩文件。解压程序读入压缩文件，根据相应的哈夫曼编码解压还原 ，得到对应的源文件。 选做内容：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。 （参考教材的本题目设计指导部分的扫描页） 程序建议使用c＋＋