数据结构——绪论

重要的数据结构思想

程序 = 数据结构 + 算法

基本概念

程序设计的实质即为计算机处理问题编制一组“指令集"，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。
- 具体来说，是非数值计算问题的数学模型。数据结构研究这个数学模型及其上的操作在计算机中如何表示
- 数据结构是程序设计的基础
术语

数据数据元素数据项关键字数据对象数据结构逻辑结构物理结构

是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。

指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。

是性质相同的数据元素的集合。是数据的一个子集。例：整数数据对象是集合 ${0, ±1, ±2, ±3,……}$ 。

是相互之间存在一种或多种特定关系的（带结构的）数据元素的集合。被形式地定义为 $DataStructures = (D,S)$ ，其中，D是数据元素的有限集，S是D上关系的有限集。

数据之间的相互关系称为逻辑结构。

集合结构线性结构树形结构网（图）状结构

结构中的数据元素除了同属于一种类型外，别无其它关系

结构中的数据元素之间存在一对一的关系

结构中的数据元素之间存在一对多的关系

结构中的数据元素之间存在多对多的关系

数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。

顺序映象链式映象索引散列

以存储位置的相邻表示后继关系

以附加信息（指针）表示后继关系

为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表

选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲突
抽象数据类型（ADT）
- 一个数学模型以及定义在此数学模型上的一组操作
- 两个重要特性：数据抽象和数据封装
ADT的形式描述

抽象数据类型的形式描述为： $ADT = (D,S,P)$ ，其中D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集

算法

算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作
算法的特性
有穷性确定性可行性具有输入和输出
一个算法必须总是在执行有穷步骤之后结束，且每一步都在有穷时间内完成。

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

一个算法是可行的，即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
- 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
- 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个好的算法，应该具有的特质
1. 正确性
2. 可读性
3. 健壮性
4. 高效率、低存储
时间复杂度
- 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用 $T(n)$ 表示，若有某个辅助函数 $f(n)$ ，使得当n趋近于无穷大时， $T(n)/f(n)$ 的极限值为不等于零的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作
\[ T(n) = O(f(n)) \]
Text Only
```
称 $T(n)$ 为算法的（渐近）时间复杂度
```
- 如何确定复杂度：分析“主要原操作”的次数
  - 算法的执行时间与所有原操作的执行次数之和成正比
- 常见复杂度排序：“常对幂指阶”
\[ O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) \]
空间复杂度
- 通常情况下，算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为
\[ S(n) = O(g(n)) \]

Info

使用递归算法时，空间复杂度往往与递归调用深度相关

原地工作算法

若算法的空间复杂度为常量级，则称该算法为原地工作的算法

数据结构——绪论

基本概念

算法

评论