0x01 绪论

一、数据结构的基本概念

1.1 数据项、数据元素、数据

• 数据项：构成数据元素的最小单位（e.g. 一个学生的年龄）
• 数据元素：数据的基本单位，通常作为一个整体进行考虑和处理（e.g.一个学生的所有个人信息）
• 数据对象：具有相同性质的数据元素的集合，是数据的子集
• 数据：描述客观事物属性的，数+字符+所有能输入到计算机并被计算机识别与处理的符号
• 数据结构：相互之间存在一种或多种特定关系的数据元素的集合
• 数据类型：值的集合+定义在此集合上的一组操作的总称（类似于代数结构）
• 原子类型：值不可再分，如bool类型、int类型
• 结构类型：值可以分解为若干分量的类型。如结构体中每一个属性就是一个分量。
• 抽象数据类型ADT：抽象数据组织及与之相关的操作。定义一个ADT，就是定义一种数据结构。

1.2 数据结构的三要素

• 逻辑结构

• 集合结构

• 线性结构（一对一）：唯一前驱、唯一后继
• 树形结构（一对多）

• 图状结构（多对多）

• 数据运算：查找、插入、删除等

• 数据运算的定义：针对逻辑结构

• 数据运算的实现：针对存储结构

• 物理结构（存储结构）

• 顺序存储：逻辑上相邻=物理上相邻，存储时需要寻找一大片连续的空间

• 链式存储：逻辑上相邻≠物理上相邻，物理上离散，通过指针反映逻辑关系
• 索引存储：建立索引表，（关键字，地址）；物理上离散
• 散列存储：根据元素关键字直接计算出元素的存储地址

顺序存储以外的三种存储方式均为非顺序存储

二、算法的基本概念

2.1 什么是算法

• 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中的一条指令表示一个或多个操作

2.2 算法的特性

• 有穷性：一个算法必须在执行有穷步后结束
• 确定性：算法中的每条指令必须有确切的含义，对于相同的输入必须有相同的输出
• 可行性：算法中的每个操作都可以通过已经实现的基本运算执行有限次来实现
• 输入：有零个或多个输入
• 输出：有一个或多个输出，且输出是与输入有某种特定关系的量

2.3 设计算法的目标

• 正确性：要正确地解决求解问题
• 可读性：帮助人们理解
• 健壮性：输入非法数据时，算法能适当地做出反应或进行处理
• 高效率与低存储量需求：省时省内存，时间复杂度、空间复杂度低

2.4 时间复杂度

• 加法规则： $$ O(f(n))+O(g(n))=O(max(f(n),g(n))) $$

• 乘法规则 $$ O(f(n))\times O(g(n))=O(f(n)\times g(n)) $$

• 代码分析：

• 嵌套循环：只关注最深层循环循环了几次

• 执行时间与输入有关的：计算各种情况的输入出现的概率，计算各情况下的时间复杂度，求个平均

• 时间复杂度取的是一个上界，最坏时间复杂度

2.5 空间复杂度

• 与问题规模$n$相关的数组声明
• 函数递归调用
• 计算一次函数调用中新声明了多少局部变量
• 计算递归调用的深度