计算机考研数据结构复习总结.pdfVIP

1 1 第11章 概述 1 1 11．概念和术语 数据：是能输入到计算机中并能被计算机程序处理的符号的总称。 数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。 一个数据元素可由若干数据项组成。 数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。 数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。 数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。 数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。 数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。 抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。 算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。 2 2 22．逻辑结构的四种基本形态 根据数据元素之间关系的不同特征，通常有下列四类基本结构： 1 1 （11）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。 2 2 （22）线性结构：结构中的数据元素之间存在一个对一个的关系。 3 3 （33）树型结构：结构中的数据元素之间存在一个对多个的关系。 4 4 （44）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。 3 3 33．数据存储结构的基本组织方式 数据存储结构有顺序和链式两种方式。 1 1 （11）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻 辑关系，常用高级编程语言中的“一维数组”来描述或实现。 2 2 （22）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系， 通常用链表来实现。 在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。 1 1 （11）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把 一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。 2 2 （22）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一 个存储地址之间尽量达到一一对应的目的。这样，查找时同样可大大提高效率。 4 4 44．数据结构的研究内容 数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的 定义和实现。 5 5 55．算法的五个重要特征 1 1 （11）有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。 2 2 （22）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。 3 3 （33）可行性：每一个操作步骤都必须在有限的时间内完成。 4 4 （44）输入：一个算法可以有一个或多个输入，也可以没有输入。 5 5 （55）输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。 6 6 66．算法的评价标准 1 1 （11）正确性。 2 2 （22）易读性。 3 3 （33）高效性。 4 4 （44）可维护性。 7 7 77．算法分析的目的 算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所 需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进 行比较。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度分析作为重点。 8 8 88．算法的时间复杂度分析 1 1 （11）算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。 2 2 （22）算法运行时间的分析规则 T n n T n n 通常把一个程序的运行时间定义为一个TT（nn），其中nn是该程序输入数据的规模，而不是某一个 T(n) T(n) 具体的输入。TT((nn))的单位是不确定的，一