1.8小结
本章介绍了数据结构的研究对象、基本概念与术语、数据类型和抽象数据类型，以及算法、算法的设计原则、算法效率的衡量方法等。主要内容如下。
（1）数据结构的研究对象
数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构的内容包括3个“层次”的5个“要素”，如表13所示。
（2）基本概念与术语
简单地说，数据就是计算机操作的对象的总称。数据元素是数据的基本单位，它是数据中的一个“个体”。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。数据结构有三个要素：数据元素的集合，数据元素之间关系的集合，定义在其上的操作。
数据的逻辑结构是对数据元素之间的逻辑关系的描述，有集合结构、线性结构、树形结构和图形结构四种。
数据的存储结构是逻辑结构在计算机中的表示和实现，有顺序存储、链式存储、索引存储、哈希存储四种。
（3）数据类型与抽象数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。
（4）算法与算法分析
算法是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法必须满足五个特性：有穷性、确定性、可行性、有输入、有输出。
算法与程序是两个不同的概念。程序不一定满足有穷性，但算法必须满足有穷性；程序中的指令必须是机器可执行的，而算法中的指令则无此限制；算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。
要设计一个“好”的算法，通常应考虑达到以下目标：正确性、可读性、健壮性、高效率与低存储量需求。
衡量算法效率通常有事后统计法和事前分析估算法两种方法。但事后统计法要运行算法，且易掩盖算法本身的优劣，所以衡量算法的效率采用事前分析估算法。算法的渐近时间复杂度记为T(n)= O(f(n))，是问题规模的函数。如果能计算算法中原操作的执行次数，则将其作为时间复杂度，否则将原操作的平均执行次数或最坏情况下原操作的执行次数作为其时间复杂度。
空间复杂度作为算法所需存储空间的量度，记作S(n)=O(g(n))。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
学完本章后，要求清楚数据结构的三个层次、五个要素；掌握数据结构相关的基本概念，包括数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构等；了解抽象数据类型的定义、表示和实现方法；理解算法的定义和特性；掌握算法的时间复杂度分析。