数据结构复习要点.doc

数据结构复习要点一、 数据结构的内容与要求“数据结构”研究的是如何使用计算机有效地表示数据和处理数据， 这也是计算机科学的核心问题。为此，首先我们需要研究和分析所要处理的数据，数据之间的关系， 也就是数据的逻辑关系或者逻辑结构。在这个过程中，我们往往需要舍弃数据的具体细节，抽取数据的本质内容和联系，使用数学概念来描述数据的逻辑结构。例如，建设城市间的高速通讯网络， 要求建设费用尽可能低，就可以抽象为一个带权图上的最小生成树问题。 有时我们需要将所要处理的数据人为地组织成某种逻辑结构，以便于更有效地处理。例如，将数据按照某种方式排序，或者组织成树状结构以便于信息检索。这是一个抽象的过程， 是解决问题的第一步，也是关键的一步。 抽象的另一个重要意义在于它的广泛的适用性或者重用性：当前问题的解可应用于很多类似结构的问题，或者当前问题可以用已有的方法（程序）来解决。第二，我们需要研究如何实现对于数据的处理或者运算， 即算法的设计。算法为解决某一类问题规定了一个有穷的运算序列。 其中的每一个运算都是有明确定义的（确定性），每一步都是可行的（可行性），并且在有穷步能够给出结果（有穷性）。解决同一个问题的算法可能有多种，因为使用了不同的方法或策略（如排序）， 或者使用了不同的逻辑结构（如线性结构上的查找和树型结构上的查找）， 因此性能也各不相同。衡量一个算法的性能，主要有时间复杂度和空间复杂度两个指标。以上所述的均是概念层上的数据表示和处理。我们把这两者，即数据的逻辑结构与运算统称为抽象数据类型。抽象数据类型是一个重要概念和工具， 它利用数据封装和信息隐蔽技术，实现了抽象数据类型的使用独立于它的实现， 为程序员提供了更有力的编程方法和工具。最后，我们需要考虑数据在计算机中的表示， 即数据的存储结构，以及算法在这种存储结构上的实现。数据的存储结构的选择主要考虑是否有利于算法的实现。例如，长度不确定的线性表上频繁进行插入和删除时用链表存储更好，动态快速查找时使用散列表效果更好等。综上所述， 要使用计算机解决实际问题，必须学会从问题中抽象出数据的逻辑结构， 以及解决问题的算法， 进而选择数据的存储结构，有效地实现解决问题的算法。数据结构课程便是围绕着这些问题展开的。本课程不仅介绍了许多常用的数据结构与算法（如栈、队列、 线性表、 散列表、查找、排序等）的概念及其实现，而且对于同一个ADT的不同实现进行了比较， 如使用连续结构和链式结构的不同特点，相应算法的复杂度的变化等。通过本课程的学习，我们不仅要理解和掌握这些常用的数据结构与算法，而且要掌握选择合适的数据结构与算法解决问题的原理与方法， 在解决实际问题时，能够自觉地使用所学的知识抽象出数据模型，选择合适的存储结构，设计出简洁、有效的算法。二、各章内容提要及要求我们可以把数据结构的内容看成由两大部分构成。第一部分是数据的各种组织形式以及操作的实现。数据的组织形式（逻辑结构）一般按照从简单到复杂划分为：线型结构，树型结构和图形结构。操作的实现往往依赖于数据的存储方式。一般的面向对象语言提供两种基本的存储方法：连续的存储方法，使用数组实现；链式的存储方法，使用指针实现。其它存储方法是这些基本方法的组合。第二部分介绍常用的操作，包括查找和排序。可以说，计算机百分之八十的工作是查找和排序。1 线性结构这部分介绍当所处理的数据可以看成线性序列时，也就是逻辑结构是线性的时候，如何实现它们的存储和处理。 其中有两种线性序列的操作具有特殊性，称为栈和队列， 它们也是我们生活中的货栈和队列的抽象。2 树型结构 这部分介绍具有树型结构的数据如何存储以及如何实现操作。重点是二叉树的存储与操作，这是因为大量的数据可以组织成二叉树来进行处理。3 图形结构 这部分介绍具有更复杂逻辑结构的数据的存储和操作。例如，城市间高速公路网的建设。高速公路网具有图形结构，由于建设费用很高，我们希望建立一个城市间互联，但是建设费用尽可能低的公路网，这便是求最小生成树的问题。又如，一项大型工程的某些任务之间具有先后关系，某些任务可以同时进行，我们希望设计一个工程进度图，要求工期尽可能短， 这便是活动网络图的问题。4 查找查找是常见的一种操作。这部分介绍各种组织数据便于实现查找的方法。 查找方法的选择依赖于数据的组织方式。如，无序的线性表使用顺序查找方法，存储结构可以是顺序的，也可以是非顺序的，即链式结构；有序的线性表使用顺序结构存储，采取折半查找（二分查找）；按照二叉查找树组织的数据使用二叉查找树方法查找（二叉排序树）； 或者使用散列的方法组织的数据使用相应的散列方法查找等。5 排序 排序也是我们常用的一种操作， 而且排序常常是为了便于查找。这部分介绍常用的排序方法，它们的实现以及它们的性能分析。第一章 数据结构概要本章介绍一些基本概念。 数据结构的概念； 逻辑结构的概念，主要类别； 存储结构的概念，主要分类； 数据类型与抽象数据类型的概念； 算法的概念及其特性； 算法设计的主要指标； 算法分析的概念和基本方法。要求：1. 理解每个概念，并且能够使用示例解释说明；2掌握数据的逻辑结构的概念（什么是逻辑结构，举例）和表示（如何表示）；3掌握数据的存储结构的概念和表示（如用图示法和C/C+提供的方法）；4掌握抽象数据类型的概念和表示（如用课本的表示方式或C+的类）；5理解算法设计的目标与要求，能按照基本要求书写算法；6掌握算法分析的基本概念和基本方法，掌握使用大O表示法表示算法的复杂度。第二章 线性表本章介绍线性表的概念，它的不同实现及其特点。1 线性表的概念和它的ADT定义；2 线性表的顺序表示和实现；3 线性表的链式表示和实现（单链表，循环连表和双链表）；4 多项式-线性表的应用。要求：1. 掌握线性表ADT的概念(什么是线性表，其上的基本运算有哪些？)；2. 掌握线性表的顺序结构及其实现；3. 掌握线性表的链式结构及其实现;4 掌握分析复杂度的基本方法；5 能够比较两种实现的特点；掌握选择存储结构的原理（如数据的操作有何特点，数据的总量是否预先确定等）；6 掌握使用线性表解决问题的方法（如集合与多项式的例子）。第三章 栈和队列本章介绍了两个ADT，栈和队列，它们的实现及其应用。1 栈的概念及其ADT定义；2 栈的顺序实现和链式实现；3 栈的应用；4 栈与递归的实现5 队列的ADT定义；6 队列的连续实现，循环队列的实现；7 队列的链表实现；要求： 掌握栈的概念和特点，能够应用栈解决实际问题； 掌握栈的实现方法； 理解栈与递归的关系； 理解递归调用树与递归算法的复杂度的关系； 掌握队列的概念和特点； 掌握队列的实现方法，尤其是循环队列边界情况的处理；第四章 串本章介绍串的概念及其实现。 串的类型定义 串的表示和实现 串的模式匹配算法要求： 掌握串的定义及其特点； 掌握串的两种存储方法：定长顺序存储表示和堆分配存储表示； 掌握串的基本运算的实现； 理解KMP算法的基本思想。 第五章 数组和广义表本章介绍数组和广义表，以及它们的表示和实现。 数组的定义； 数组的顺序表示和实现； 矩阵的压缩存储； 广义表及其存储结构。要求： 掌握数组的顺序存储方法； 掌握特殊矩阵的顺序存储方法； 掌握广义表的基本概念； 掌握广义表的存储结构（能够画出广义表的存储结构图，或者由存储结构图写出广义表）；第六章 二叉树与树第六章 树和二叉树 树的概念二叉树的概念； 二叉树的遍历； 线索二叉树； 树和森林； Huffman树要求： 掌握树的概念，理解树的递归定义； 掌握二叉树的定义，二叉树的性质；完全二叉树的特点； 掌握二叉树的存储结构，特别是二叉链表； 理解线索二叉树的存储方法； 掌握二叉树的各种遍历方法，包括递归和非递归，深度优先和广度优先法； 掌握树的存储结构， 森林与二叉树的转换； 掌握二叉树的应用。第七章 图本章讨论如何实现图的存储以及图上的常见算法。图的基本表示方法有邻接矩阵和邻接表，相应的存储结构是二维数组和邻接表。图上常用的算法包括：拓扑排序，遍历，求最小生成树，最短路径和关键路径等。1图的概念熟悉图的概念和图的术语。如，有向图，无向图，带权图，路经，连通性，结点的入度和出度，度数和边数的关系等。2图的存储结构掌握图的基本存储方法或者表示方法：邻接矩阵和邻接表。 3图的遍历掌握图的深度优先和宽度优先遍历方法和实现。理解在图上如何实现遍历，进一步理解如何根据图的邻接表表示实现遍历。4最小生成树Prim算法和实现掌握求最小生成树的Prim算法，包括Prim算法的思想和算法的实现。5拓扑排序掌握拓扑排序的方法和实现。6关键路径理解关键路径的概念和求关键路径的方法。7最短路径掌握求最短路径的Dijkstra算法和Floyd算法的思想，掌握算法的实现方法。第八章 查找本章介绍常用的几种查找方法。查找方法与所查找的数据的组织方法密切相关。无序的线性表使用顺序查找方法，存储结构可以是顺序的，也可以是非顺序的，即链式结构；有序的线性表使用顺序结构存储，采取折半查找（二分查找）；按照二叉查找树组织的数据使用二叉查找树方法查找（二叉排序树）； 或者使用散列的方法组织的数据使用相应的散列方法查找等。查找主要经过一系列关键字的比较完成。查找的效率使用查找过程中关键字的平均比较次数表示，称之为平均查找长度。平均查找长度分查找成功和查找失败两种情况计算。理解查找的有关概念：关键字，查找表，查找，查找成功，查找失败，静态查找表和动态查找表。掌握顺序查找方法。查找表的数据组织成线性结构，存储结构可以使用顺序结构，也可以使用链式结构。这是一种最简单的查找方法。虽然效率较低，但是，在许多情况下仍然是首选的方法。3掌握折半查找方法。查找表的记录按照关键字有序，并且使用顺序结构存储。折半查找的效率可以通过判定树来计算。理解使用判定树分析折半查找效率的方法。4索引顺序表的查找。当顺序表分块有序时，可以为每个子表建立一个包括子表的最大关键字和子表的开始位置的索引项，这些索引项构成查找表的一个有序索引表，查找问题可以分两步完成：首先在有序的索引表上查找以决定记录可能存在的子表，然后到相应的子表中查找。5掌握二叉查找树的查找方法和性能分析。6掌握平衡二叉查找树（AVL树）的概念，AVL树的插入。7理解B树和B+树的概念，B树的插入和删除方法。8散列是一种查找方法，也是一种存储方法。与其他方法不同的是，散列表的查找效率不依赖于表的大小。要求掌握散列表的概念，构造散列函数的基本原则和方法。掌握散列表的构造方法，查找方法以及删除方法。掌握处理冲突的开地址法和拉链法。第九章 内部排序本章介绍了常用的排序方法。要求掌握每种排序的思想，方法和特点。掌握估算排序效率的方法。 掌握排序的有关概念，如内排序，外排序，稳定性等。 掌握直接插入排序，快速排序，堆排序和归并排序及其各自的特点。 掌握估算最坏情况和平均情况下排序效率的方法。以上是前几章的基本内容和要求。希望同学们能够参照上述内容和要求，自己动手复习和总结一下,特别注意红色字体内容。有问题的同学，请随时发email到. 祝大家通过复习能够进一步掌握课程内容! 同时，欢迎大家对本课程讲授中的不足、今后的改进等提出宝贵意见和建议。谢谢！乔海燕 2006-12-23附：题型举例（1）简答题 什么是算法？ 设计一个好算法应该考虑哪些目标？（2）单项选择例 如下二叉树按中序周游得到的输出序列是（ ）。A BC (a) A B C D E F (b) A B D E C FFED (c) D B E A C F (d) F C A E B D（3）填空例 一棵n个结点的完全二叉树的深度为 。（4）程序阅读填空题例 试填写下列链表插入程序中的空格a、b和cBool ListInsert(List *lp,int i,