data_introduction_0

绪论
- 数据结构（三要素）
  - 逻辑结构
    - 线性结构：线性表、栈、队列
    - 非线性结构：树、图、集合
  - 存储结构（物理结构）
  - 数据的运算
- 五个特征
  - 算法定义
  - 五个特征：有穷性、确定性、可行性、输入、输出
  - 效率的量度
    - 空间复杂度
    - 时间复杂度

整个数据结构可以用上面这一张图来描述。

基本概念

1.数据

数据是信息的载体，是计算机程序加工的原料。

2.数据元素

数据元素是数据的基本单位，通常作为一个整体来考虑。一个数据元素可有若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它是由姓名、学号、性别等数据项组成。

3.数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

4.数据类型

数据类型是一个值的集合和定义子啊此集合上的一组操作的总称。

原子结构：不可再分割的数据类型
结构类型：其值可以再分解为若干个成分的书数据类型
抽象数据结构（ADT）：组织与之相关的操作

5.数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，这些数据元素相互之间的关系称为结构（Structure），数据结构包括三方面内容：逻辑结构、存储结构、数据的运算

数据结构的三要素

1.数据的逻辑结构

数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；图、树、集合是典型的非线性结构。

集合：数据元素之间同属一个集合，其外无他关系。
线性结构：数据元素之间存在一对一的关系
树形结构：数据元素之间存在一对多的关系。
图状结构或网状结构：数据元素之间存在多对多的关系。

2.数据的存储结构

数据的存储结构称为数据结构在计算机中的“映像”，也称为物理结构。主要有顺序存储、链式存储、索引存储和散列存储，下面一一介绍。

顺序存储：

把逻辑上相邻的元素存储在物理位置上也相邻的储存单位中。

优点：可以采用随机存取，每个元素占用最少的存储空间。

缺点：只能使用相邻的一整块存储空间，易产生较多的外部碎片。
链式存储：

对物理位置无特殊要求，借助指示元素存储地址的指针来标识元素之间的逻辑关系。

优点：不会产生碎片现象。

缺点：每个元素因存储指针而占用额外的存储空间，只能实现顺序存储。
索引存储：

在存储元素信息的同时，还建立附加的索引表，表中的每项称为索引项（关键字，地址）。

优点：检索速度快。

缺点：索引表额外占用存储空间。在增删数据元素时也要同时修改索引表，会花费较多欸外的时间。
散列存储：

根据元素的关键字直接计算出元素的存储地址，又称哈希（Hash）存储。

优点：检索、增加和删除节点都很快。

缺点：若散列函数不好，可能会出现元素存储单元冲突问题，解决冲突会增加时间和空间的开销。

3.数据的运算

运算包括运算的定义和实现。

运算的定义：针对逻辑结构，指出运算的功能。

运算的实现：争对存储结构，指出运算都具体操作步骤。

算法和算法评价

算法的基本概念

定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

算法的5个重要特征如下：

有穷性：算法在执行有穷步后结束，且每一步都在有穷时间内完成。
确定性：算法中每条指令都必须有确切的意义。
可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

设计算法的目标：可读性，健壮性，正确性，效率与低存储需求

算法效率的量度

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

时间复杂度

语句的频度：语句在算法中被重复的次数

算法中所有语句的频度之和记为`T(n)`，它是该算法问题规模的函数，算法复杂度就是分析`T(n)`的数量级。算法中基本运算（最深层循环内的语句）的频度与 `T(n)`同数量级，因此通产采用算法中基本运算的频度`f(n)`来分析算法的时间复杂度。因此，算法的时间复杂度记为：
$$
T(n)

O(f(n))
$$

取f(n)中随n增长最快的项，将其系数置为1作为时间复杂度的量度。例如，f(n) = an³ + bn² + cn的时间复杂度为O(n³)

式中，O的含义是T(n)的数量级，定义为存在正常数C和n₀，使得当n≥n₀时，都满足0 ≤ T(n) ≤ Cf(n)。

一般总考虑最坏情况下的时间复杂度以保证算法的运行时间不会比它更长。

空间复杂度

算法的空间复杂度`S(n)`定义为该算法所耗费的存储空间，它是问题规模n的函数。记为：
$$
S(n)

O(g(n))
$$
一个程序在执行时，除了需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析处输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常量，即O(1)。

递归程序的空间复杂度

递归重写一般使用公式递归，来计算时间复杂度。