第一章 绪论

1.1 什么是数据结构

  数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

1.2 基本概念和术语

数据:对客观事物的符号表达,在计算机科学中指能输入到计算机中并被计算机程序处理的符号总称。是计算机加工的“原料”。

数据元素:是数据的基本单位,在计算机程序中通常作为一个整体来考虑和处理。

数据项:数据的不可分割的最小单位。

有时,一个数据元素可由若干个数据项组成。一本书的书目信息为一个数据元素),其中的每一项(如书名、作者名)为一个数据项。

数据对象:性质相同的数据元素的集合,是数据的一个子集。

数据结构的一种简单解释:相互之间存在一种或多种特定关系的数据元素的集合。基本结构可分为:(1)集合:结构中的元素除“存在于同一集合”外无其他关系(2)线性结构:结构中的元素之间存在一对一关系(3)树状结构:结构中的元素之间存在一对多关系(4)图状结构:结构中的元素存在多对多关系。形式定义为一个二元组:Data Structure = ( D , S ),D为数据元素的有限集,S为D上关系的有限集。

存储结构:数据结构在计算机上的表示,又称映像。

数据元素之间的关系在计算机中有两种不同的表示方式:顺序映像非顺序映像。对应两种不同的存储结构:顺序存储结构和链式存储结构。两种方式的特点分别为:顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,非顺序映像借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

数据类型即一个值的集合和定义在这个值集上的一组操作的总称,明显或隐含地规定了在程序执行期间变量或者表达式所有可能取值的范围以及在这些值上允许进行的操作。可分为:原子类型和结构类型。

抽象数据类型:由一个值域和定义在该值域上的一组操作组成。可分为:原子类型、固定聚合类型和可变聚合类型。抽象数据类型可用三元组(D , S , P)表示,定义为:

ADT 数据类型数据名 {

   数据对象:<数据对象的定义>

   数据关系:<数据关系的定义>

   基本操作:<基本操作的定义>

} ADT 抽象数据类型名

1.3 抽象数据类型的表示与实现

抽象数据类型可通过固有数据类型来表示和实现,即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作。

1.4 算法和算法分析

算法是指对于特定问题求解步骤的一种描述,是指令的有限序列。具有有穷性、确定性、可行性、输入、输出的性质。算法设计时应考虑达到目标索要有的正确性可读性健壮性、以及效率低存储量需求。

算法时间度量: $$ T(n) = O(f(n)) $$ 算法时间复杂度考虑的只是对于问题规模 n 的增长率,在难以精确计算基本操作次数或语句频度的情况下,只需求出它关于 n 的增长率或阶