第一章 概论
引言
数据结构，Data structure：是指一组相互之间存在一种或多张特定关系的数据的 组织方式 和它们在计算机内的 存储方式，以及定义在该组数据上的一组 操作。
计算机解决访问的步骤：
- 建立数学模型；
- 设计算法；
- 编程实现算法；
数据结构主要研究：
- 数据（计算机加工对象）的逻辑结构；
- 实现各种基本操作的算法；
基本概念和术语
术语
数据，Data：所有被计算机存储、处理的对象。
数据元素，Data Element：数据的基本单位，是运算的基本单位。常常又简称为元素。
数据项，Data Item：数据元素常常还可分为若干个数据项，数据的不可分割的最小识别单位。
数据的逻辑结构
逻辑结构，Logical Structure：指数据元素之间的结构关系。与数据元素本身的形式、内容、相对位置、个数 无关。
逻辑结构的 种类：
- 集合：任意两个结点之间都没有领接关系，组织形式松散；
- 线性结构：结点按逻辑关系依次排列形成一条“锁链”；
- 树形结构：具有 分支、层次 的特性，上层的结点可以和下层的多个结点相领接，但下层的结点只能和上层的一个结点相领接；
- 图结构：任何两个结点都可以相领接，最复杂；
数据的存储结构
物理结构，存储结构，Physical Structure：指数据结构在机内的表示，数据的逻辑结构在计算中的实现。
存储结构的 主要部分：
- 存储结点（每个存储结点存放一个数据元素）；
- 数据元素之间关联关系的表示；
存储结构的 种类：
- 顺序存储方式：指所有存储结点存放在 一个连续的存储区里，利用结点在存储器中的相对位置来表示元素之间的 逻辑 关系；
- 链式存储方式：指每个存储结点除了包含有一个数据元素之外，还包含 指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的 逻辑 关系；
- 索引存储方式：借助索引表的 索引指示 各存储结点的存储位置；
- 散列存储方式：用 散列函数 指示各结点的存储位置；
链式存储方式适合 频繁地插入和删除操作。
数据元素之间的关联方式 主要 采用：顺序存储方式 + 链式存储方式。
运算
运算：是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。
线性表、栈和队列 中的元素具有相同的逻辑结构（即：线性结构），但有不同的运算集，它们是不同的数据结构。
算法及描述
算法 规定了求解给定类型问题所需的 处理步骤 及 执行顺序，是给定类型问题能在 有限时间 内被机械的求解。
算法必须使用某种语言描述：
- 程序；
- 介于自然语言和程序设计语言的伪代码；
- 非形式算法（自然语言）；
- 框图（N-S图）；
评价算法好坏的因素包括以下几个方面：
- 正确性：能正确地实现预定的功能，满足具体问题的需要；
- 易读性：易于阅读、理解和交流，便于调试、修改和扩充；
- 健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果；
- 时空性：指该算法的时间效能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量；
算法分析
解决同一问题的算法可以有多种。我们希望从中选出最优的算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。
通常考虑两个度量：
- 时间复杂度：算法运行时需要的总步数，通常是问题规模的函数；
- 空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数。
时间复杂度
时间复杂度 = 最坏情况时间复杂度 + 平均情况时间复杂度
如果确定算法的计算量：
- 算法的 最坏 情况时间复杂度：以算法在 所有输入下的计算量的最大值 作为算法的计算量；
- 算法的 平均 情况时间复杂度：以算法在 虽有输入下的计算量的加权平均值 作为算法的计算量；
此算法的最坏情况时间复杂度和平均时间复杂度均为n的函数：
T(n) 与 的数量级相同，称此算法的时间复杂度量级为
，记作：
。
一般我们将 称作 时间复杂度。
常见的时间复杂度 按数量级递增 排序依次为：
-
；
-
；
-
；
-
；
-
；
-
；
-
；
我们将时间复杂度记为输入数据规模n的函数，若求解问题需要执行 次操作，则记作
。
空间复杂度
空间复杂度式对一个算法在运行过程中 临时占用存储空间大小的量度。
一个算法在执行期间所需要的存储空间量包括以下部分：
- 程序代码所占用的空间；
- 输入数据所占用的空间；
- 辅助变量所占用的空间；
估算算法空间复杂度式，一般只分析 辅助变量 所占用的空间。
