1.1 数据结构的基本概念
1.1.1 基本概念和术语
1. 数据(Data)
- 数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
- 数据是计算机程序加工的原料
- 数据包括数值型数据(如整数、实数)和非数值型数据(如文字、图)
2. 数据元素(Data Element)
- 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
- 一个数据元素由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位
- 如果一个数据项由更多的细分的属性组成，则这个数据项称为组合项
3. 数据对象(Data Object)
- 数据对象是性质相同的数据元素的集合，是数据的一个子集。
- 例如，学生基本信息表中的学生记录所构成的集合是一个数据对象，其中学生记录都具有相同的性质。
4. 数据类型
- 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
- 值的集合：规定了属于该数据类型的数据可以取什么值
- 定义在此集合上的一组操作：规定了数据该数据类型的数据可以进行什么操作
- 原子类型：其值不可再分的数据类型。
- 结构类型：其值可以再分解为若干成分（分量）的数据类型。
- 分量之间具有一定的逻辑关系
- 抽象数据类型（ADT）：抽象数据组织及与之相关的操作。
- 抽象数据类型表示数据的逻辑结构与运算的定义，不涉及具体的实现
5. 数据结构
- 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
- 数据元素相互之间的关系称为结构(Structure)。
- 数据结构是描述数据元素之间的关系
- 数据结构强调数据元素之间的关系，而数据对象，只要数据元素的性质相同即可属于同一个数据对象
- 数据结构包括三方面的内容：
- 逻辑结构
- 存储结构
- 数据的运算
- 一个数据对象中的数据元素的关系可以采用不同的数据结构表示，不同的数据对象可以使用相同的数据结构表示数据元素的关系
6. 数据、数据对象、数据元素、数据项之间的关系
- 数据 > 数据对象 > 数据元素 > 数据项
7. 数据元素与数据对象
- 数据元素
- 数据元素是组成数据的基本单位
- 数据元素与数据的关系：集合的个体
- 数据对象
- 数据对象是性质相同的数据元素组成的集合
- 数据对象与数据的关系：集合的子集
1.1.2 数据结构三要素
- 数据结构的三要素为：
- 数据的逻辑结构
- 数据的存储结构
- 数据的运算
1. 数据的逻辑结构
- 数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。
- 数据的逻辑结构与数据的存储无关，是独立于计算机的。
- 数据的逻辑结构分为线性结构和非线性结构，其中非线性结构又可分为：集合、树形结构、图状结构或网状结构
- 线性结构：结构中的数据元素之间只存在一对一的关系
- 除了第一个元素，所有元素都有一个唯一前驱；除了最后一个元素，所有元素都有一个唯一后继
- 集合：结构中的数据元素之间除“同属一个集合”外，别无其他关系
- 树形结构：结构中的数据元素之间存在一对多的关系
- 图状结构或网状结构：结构中的数据元素之间存在多对多的关系
2. 数据的存储结构
- 数据存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。
- 数据的存储结构包括数据元素的表示和数据元素之间关系的表示。
- 数据的存储结构是用计算机语言实现的逻辑结构，依赖于计算机语言
- 数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储
1）顺序存储
- 顺序存储就是把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
2）链式存储
- 链式存储不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
3）索引存储
- 索引存储是在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是
(关键字，地址)。
4）散列存储
- 散列存储是根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash) 存储。
在上述四种数据的存储结构中，顺序存储的数据元素是相邻存放的，链式存储、索引存储以及散列存储的数据元素可以离散存放。
采用不同的存储结构会影响存储空间分配的方便程度，也会影响数据运算的速度
3. 数据的运算
- 施加在数据上的运算包括运算的定义和实现。
- 运算的定义是针对逻辑结构的，指出运算的功能
- 针对于某种逻辑结构，结合实际需求定义基本运算
- 运算的实现是针对存储结构的，指出运算的具体操作步骤。
- 采用不同的存储，运算的具体操作步骤不同
1.2 算法和算法评价
程序 = 数据结构 + 算法，数据结构是要处理的信息，算法是处理信息的步骤
1.2.1 算法的基本概念
- 算法是对特定问题求解方法和步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或多个操作
- 算法的5个重要特性：
- 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
- 算法必须是有穷的，程序可以是无穷的（程序可以一直运行）
- 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
- 算法的求解步骤必须是明确的、无歧义的
- 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定的数据对象的集合。
- 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
- 算法的五个重要特性，只要有其中一个不满足，就不为算法
- 设计算法追求的目标:
- 正确性：算法应能够正确地解决求解问题。
- 可读性：算法应具有良好的可读性，以帮助人们理解。
- 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
- 高效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间
1.2.2 算法效率的度量
- 算法效率的度量是通过时间复杂度和空间复杂度来描述的。
1. 时间复杂度
- 时间复杂度用于评价一个算法的时间开销，评价算法时间开销的方法有，事后统计法和事前分析法
- 一个语句的频度是指该语句在算法中被重复执行的次数。
- 算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。
- 在计算算法时间复杂度时，可用忽略所有低次幂项和最高次幂的系数
- 算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。
- 顺序执行的代码只会影响常数项，对于O(f(n))，f(n)的常数项可以忽略，所以顺序执行的代码可以不用考虑
- 计算时间复杂度只需挑循环中的一个基本操作分析其执行次数于n的关系即可（对于O(f(n))，f(n)最高次项前的系数可以忽略），如果有多层嵌套循环，只需关注最深层循环中的基本操作分析其执行次数于n的关系即可
- 算法的时间复杂度记为：T(n) = O(f(n))
- O的含义是T(n)的数量级
- 算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质(如输入数据元素的初始状态)。
- 三种时间复杂度：
- 最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
- 平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
- 最好时间复杂度是指在最好情况下，算法的时间复杂度。
- 一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
2. 空间复杂度
- 算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)= O(g(n))
- 一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
- 由于一个程序和输入的数据所占空间只取决于问题本身，和算法无关，所以只需分析除输入和程序之外的额外空间。
- 算法原地工作是指算法所需的辅助空间为常量，即O(1)。
- 算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能导致占用较多的存储空间，即可能使空间复杂度变大；反之亦然
