第1章 绪论
1.1 数据结构的研究内容
1.2 基本概念和术语
1.2.1 数据、数据元素、数据项和数据对象
- 数据:是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称
- 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理
- 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位
- 数据对象:是性质相同的数据元素的集合,是数据的一个子集
1.2.2 数据结构
逻辑结构
从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的
有两个要素:数据元素和关系
举例:
- 集合结构
- 线性结构
- 树结构
- 图结构或网状结构
几种逻辑结构层次图:
存储结构
在计算机中的存储表示称为数据的存储结构,也称为物理结构
举例:
- 顺序存储结构
- 链式存储结构
1.2.3 数据类型和抽象数据类型
- 数据类型:是一个值的集合和定义在这个值的集合和定义在整个值集上的总称
- 抽象数据类型:一般指由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称,具体包括三部分:数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.4.1 算法的定义和特性
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
1.4.2 评价算法优劣的基本标准
- 确定性
- 可读性
- 健壮性
- 高效性
1.4.3 算法的时间复杂度
\[T(n)=O(f(n))\]除特别指明外,时间复杂度均指最坏情况下的时间复杂度
1.4.4 算法的空间复杂度
\[S(n)=O(f(n))\]1.5 小结
本章介绍了数据结构的基本概念和术语,以及算法和算法时间复杂度的分析方法。