02.数据结构与算法.md

# 问题与简答

## 数据结构与算法篇

### 1. 概述

#### 解决问题的效率

解决问题方法的效率，跟`数据的组织方式`有关，跟`空间的利用效率`有关，也跟`算法的巧妙程度`有关

#### 抽象数据类型

`抽象数据类型`(Abstract Data Type，ADT)是一种对"数据类型"的描述，这种描述是"抽象"的

数据类型描述内容：一是`数据对象集`，二是`与数据集合相关联的操作集`

#### 算法定义

算法是一个`有限指令集`，它接受一些输入，产生输出，并在一定的有限步骤之后终止

#### 算法复杂度

- 空间复杂度 S(n)：根据算法写成的程序在执行时占用存储单元的长度
- 时间复杂度 T(n)：根据算法写成的程序在执行时耗时时间的长度

#### 分析算法效率

- 最坏情况的复杂度 T<sub>worst</sub>(n)
- 平均复杂度 T<sub>avg</sub>(n)

拓展阅读 [《数据结构与算法概述》](./02.数据结构与算法/01.数据结构与算法概述.md)

### 2. 实现基础

数据结构的处理方法是从这些具体应用中`抽象`出共性的数据组织与操作方式，进而采用某种具体的程序设计语言`实现`相应的数据存储与操作

#### 数据存储基础

- 数组

数组是最基本的构造类型，它是一组相同类型数据的有序集合

- 结构

结构类型是一种允许把一些数据分量聚合成一个整体的数据类型，它能够把有内在联系的不同类型的数据统一成一个整体，使它们相互关联

- 链表

链表是一种常见而重要的基础数据结构，也是实现复杂数据结构的重要手段

#### 流程控制基础

程序设计语言除了能够表达各种各样的数据外，还必须提供一种手段来表达数据处理的过程，即`程序的控制过程`

按照结构化程序设计的观点，任何程序都可以将程序模块通过三种基本的控制结构进行组合来实现。这三种基本的控制结构是`顺序`、`分支`和`循环`

拓展阅读 [《数据结构实现基础》](./02.数据结构与算法/02.数据结构实现基础.md)

### 3. 线性结构

#### 线性表

线性表(Linear List)是由同一类型的数据元素构成的有序序列的线性结构

操作集：初始化、指定查找、查找、插入、删除、求表长

实现方式：顺序存储、链式存储

#### 堆栈

堆栈(Stack)可以认为是具有一定约束的线性表，插入和删除操作都作用在一个称为栈顶(Top)的端点位置

操作集：生成栈、判断是否满、压栈、判断是否空、出栈

实现方式：顺序存储、链式存储

#### 队列

队列(Queue)是一个有序线性表，队列的插入和删除操作分别是在线性表的两个不同的端点进行

操作集：生成队列、判断是否满、压入队列、判断是否为空，移除队列

实现方式：顺序存储、链式存储

### 4. 树

树(Tree)是一种十分重要且广泛应用的非线性数据结构

#### 二叉树

五种基本形态：空二叉树、只有根节点的二叉树、只有根节点和左子树T<sub>L</sub>的二叉树、只有根节点和右子树T<sub>R</sub>的二叉树、具有根节点、左子树T<sub>L</sub>和右子树T<sub>R</sub>的二叉树

其它二叉树：斜二叉树、满二叉树、完美二叉树

实现方式：顺序存储、链式存储

操作集：创建二叉树、判断是否为空、遍历(先序遍历、中序遍历、后序遍历、层序遍历)

#### 二叉搜索树

二叉搜索树(Binary Search Tree)是一种对排序和查找都很有用的特殊二叉树

定义：左子树 < 根节点 < 右子树

实现方式：一般用链表实现

操作集：创建二叉树、判断是否为空、遍历、查找、查找最小元素、查找最大元素、插入、删除

时间复杂度：最好 O(logN) 最差 O(N)

#### 平衡二叉树

平衡二叉树(Balanced Binary Tree)又称为 AVL 树，AVL 树的插入、删除、查找操作均可在O(logN)时间内完成

定义：任一结点的左、右子树均为 AVL 树；根节点左、右子树高度差的绝对值不超过1

平衡二叉树的调整：单旋调整、双旋调整

#### 树的应用

堆及其操作、哈夫曼树、集合及其运算

### 5. 散列查找

符号表(SymbolTable)是名字(Name)-属性(Attribute)对的集合，符号表最核心的操作是查找、插入和删除

操作集：创建符号表、查找指定名字是否存在、获取指定名字对应属性、更改指定名字对应属性、插入新名字及其属性、删除名字及其属性

使用散列技术实现符号表的操作集，符号表也叫做`散列表`(Hash Table，即哈希表)，散列(Hashing)是一种重要的查找方法

散列函数(哈希函数)：在查找数据时，由函数 h 对给定值 key 计算出地址，将 key 与该地址单元中数据对象关键字进行比较，确定查找是否成功。散列法又称为"关键字-地址转换法"

关键字分类：一般把关键字分为`数字型关键字`和`字符串型关键字`

#### 数字型关键字的散列构造

- 直接定址法

h(key) = a x key + b (a、b为常数)

- 除留余数法

h(key) = key mod p

- 数字分析法

h(key) = atoi(key + 7)

#### 字符串型关键字的散列构造

- ASCII 码加和法

h(key) = (Σkey[i]) mode TableSize

#### 冲突处理

- 开放地址法

开放地址法就是一旦产生了冲突，即该地址已经存放了其它数据元素，就去寻找另一个空的散列地址

- 链地址法

链地址法是将所有关键词为同义词的数据对象通过结点链接存储在同一个单链表中

- 影响冲突的因素

散列函数是否均匀、处理冲突的方法、散列表的装填因子 α

### 6. 图

图的结构是任意两个数据对象之前都可能存在某种特定关系的数据结构

### 7. 排序

没有一种排序算法在任何情况下都是最优的，必须根据实际情况选择最优的算法来解决问题

算法稳定性：在一组待排序记录中，如果存在任意两个相等的记录 R 和 S，且在待排序记录中 R 在 S 前，如果在排序后 R 依然在 S 前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的

#### 选择排序

- 简单选择排序

简单选择排序(Simple Selection Sort)是一种直观的排序算法，在未排序的序列中，选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，依次类推，最后形成从小到大的已排序序列

时间复杂度：O(N<sup>2</sup>)

- 堆排序

将无序的序列生成一个最大堆，将堆顶元素与最后一个元素对换位置，将剩下元素生成最大堆，依次进行元素交换并生成最大堆

时间复杂度：O(NlogN)
空间复杂度：O(1)

#### 插入排序

- 简单插入排序

将待排序的一组序列分为已排好序和未排序的两个部分，初始状态时，已排序序列仅包含第一个元素，未排序序列中的元素为除了第一个以外N-1个元素；此后将未排序序列中的元素逐一插入到已排序的序列中。如此往复，经过N-1次插入后，未排序序列中元素个数为0，则排序完成

时间复杂度：O(N<sup>2</sup>) 稳定排序

- 希尔排序

将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开始时设置的"间隔"较大，在每轮排序中将间隔逐步减小，直到"间隔"为1，也就是最后一步是进行简单插入排序

时间复杂度：和增量序列的选取有关 非稳定排序

#### 交换排序

- 冒泡排序

对元素个数为 N 的待排序序列进行排序时，共进行N-1次循环。在第 k 次循环中，对从第1到第N-k个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素，则两者互换位置，否则保持位置不变

时间复杂度：O(N<sup>2</sup>)

- 快速排序

将未排序元素根据一个作为基准的"主元"分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个子序列用类似的方法进行排序

时间复杂度：O(Nlog<sub>2</sub>N)

#### 归并排序

将大小为 N 的序列看成 N 个长度为1的子序列，接下来将相邻子序列两两进行归并操作，形成N/2(+1)个长度为2(或1)的有序子序列；然后再继续进行相邻子序列两两归并操作，如果一直循环，直到剩下1个长度为 N 的序列，则该序列为原序列完成排序后的结果

时间复杂度：O(Nlog<sub>2</sub>N)
空间复杂度：O(N)

#### 基数排序

- 桶排序

如果已知 N 个关键字的取值范围是在 0 到 M-1 之间，而 M 比 N 小的多，则桶排序算法将关键字的每个取值建立一个"桶"，即建立 M 个桶，在扫描 N 个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了

- 基数排序

基数排序是桶排序的一种推广，它所考虑的待排记录包含不止一个关键字

### 8. 补充

### 9. 经典算法题