《数据结构教程》1 绪论

1,119 阅读3分钟

数据结构是具有结构的数据元素的集合。

Data-Structure = (D, R)

其中,D 是 数据元素 的有限集合,R 是 D 上 关系 的集合。

数据结构所研究的主要内容:

  1. 数据元素之间固有的客观联系(逻辑结构)
  2. 数据在计算机内部的存储方法(存储结构)
  3. 在数据的各种结构(逻辑的和物理的)的基础上如何对数据实施有效的操作或处理(算法)

结构

结构是指数据元素之间的关系或者联系。结构分为两类:逻辑结构存储结构。算法的设计取决于逻辑结构,算法的实现依赖于存储结构。

逻辑结构

逻辑结构指数据元素在客观世界中具有的逻辑关系。一般分为 线性结构非线性结构

线性结构:数据元素之间的逻辑关系是一对一的。除了第一个数据元素和最后一个数据元素之外,其他数据元素有且只有一个直接前驱元素,有且仅有一个直接后继元素。

非线性结构:数据元素之间的逻辑关系是一对多、多对一、多对多等关系。

存储结构

存储结构指具有逻辑结构的数据再计算机存储器中的存储方式(存储映像)。通常有顺序存储结构、链式存储结构、索引结构和散列结构等。

二者关系

数据的逻辑结构面向所解决的问题,反映了数据内部的构成方式;而数据的存储结构面向计算机,目标是将数据及其逻辑关系存储到计算的存储器中。一般情况下,一种逻辑结构可以采用多种存储结构来存储。

数据的逻辑结构设计可以独立于数据的存储结构,这是因为数据的逻辑结构设计是在数据的分析阶段进行的,而存储结构是在设计阶段进行的。反之,存储结构不能独立于逻辑结构,这是因为数据的存储结构是逻辑结构在计算机存储中的映像。(2018 年选择题真题)

算法

所谓 正确的算法 是指,当输入一组合理的数据时,能够在优先的运行时间内得到正确的结果;对于不合理的数据输入,能够给出警告提示信息。

算法分析

算法分析的 前提 是算法是正确的;目的 是分析算法的效率,以求改进算法;主要任务 是分析算法的执行时间与问题规模之间的关系。

衡量算法质量优劣的基本标准有:正确性、易读性、健壮性、可移植性、时空效率。

计算算法的时间复杂度属于 事前分析估算 的方法。