<commit_before>---
layout:     post
title:      DS-学习笔记-上
subtitle:   数据结构（C++语言版）
date:       2018-07-31
author:     IdiotLeo
header-img: img/beach_real_2.jpg
catalog: true
tags:
    - 数据结构
    - DS
---

# Overview

记录学习数据结构的知识结构（上）

# 第三章 列表

##### 3.1 从向量到列表


[**列表**] 结构尽管也要求各元素在逻辑上具有线性次序，但对其物理地址却未做任何限制——几位“动态存储”策略。

##### 3.2 接口


[**节点内部**] T data; ListNode(T) pred; ListNode(T) succ;

##### 3.3 列表


[**头、尾节点**] 私有的头节点（header）和尾节点（trailer）始终存在，对外不可见。对外部可见的节点如果存在则第一个和最后一个称为首节点（first node）和末节点（last node）

外部不可见的节点叫做哨兵节点。

[**秩到位置的转换**] 重载操作符“[]”。

[**查找**] 时间复杂度O(n)，线性正比于查找区间的宽度。

[**插入**] 具有特定的操作顺序（顺序不可颠倒）。

[**删除**] 具有特定的操作顺序（顺序不可颠倒）。

[**析构**] 反复删除首节点。

[**唯一化**] 需要O（n）步迭代，每次迭代中find（）操作所需的时间线性正比于查找区间宽度，即当前节点的秩。

时间复杂度：1 + 2 + 3 + ···· + n = O（n^2）

##### 3.4 有序列表


大小次序与逻辑次序完全一致。

[**唯一化**] 两个指针p q分别指向每一对相邻的节点。时间复杂度：O（n）。

[**查找**] 顺序查找。原因：在动态存储策略中，节点的物理地址与逻辑次序毫无关系，故无法像有序向量那样自如地应用减而治之。

##### 3.5 排序器


[**插入排序**] 特点：在任何时刻，前缀总是已经有序。不断地插入。时间复杂度（取决于每一步的查找、删除、插入操作）：O（n^2）。

[**选择排序**] 特点：任何时刻，后缀总是已经有序。在前缀中找最大的插入后缀首节点。时间复杂度：O（n^2）。

[**归并排序**] 归并时间复杂度：O（m + n）。分治时间复杂度O（logn）。总时间复杂度：O（nlogn）。

# 第四章 栈与队列

##### 4.1 栈


[**盲端**] 不能进行操作的一端。栈底。

##### 4.2 栈与递归


递归算法所需空间量，主要决定于最大递归深度。

[**函数调用栈**] 基本单位帧。栈底必然是main（）占的一帧。

[**运行树**] 任意时刻的所有活跃函数实例，在调用栈中自底到顶，对应于运行树从根节点到最活跃函数实例的一条调用路径。

##### 4.3 栈的典型应用


[**逆序输出**] 逆序计算输出的。eg.**进制转换**。各数位由低到高逐位算出，但引入栈就可逆序输出，由高到低。

[**递归嵌套**] 自相似性。

**1、栈混洗**。随机的出栈或入栈操作。只要满足“任意前缀中的push不少于pop”这一限制，则该序列也必然对应于某个栈混洗。

**2、括号匹配**。<递归实现> 一般的，任何一个表达式S可以转化为：S = S0 + "(" + S1 + ")" + S2 + S3。其中S0和S3不含括号，且S1中左右括号数目相等，则S匹配当且仅当S1和S2匹配。采用分治策略：将表达式分为S0、S1、S2，递归的判断S1、S2是否匹配。时间复杂度：O（n^2）<迭代算法> 左右括号对应于push、pop操作，只需扫描一遍表达式，对所有括号进行栈操作即可。（也可推广至不同种类括号并存的场合）

[**延迟缓冲**] 在一些应用问题中，输入可以分解为多个单元并通过迭代依次扫描处理，但过程中的各步计算往往滞后于扫描的进度，需要待到必要的信息已完整到一定程度后才能做出判断并实施计算。这种场合可以使用栈结构扮演数据缓冲区的角色。

**表达式求值**。仅仅根据表达式的某一前缀，并不能完全确定其中各运算符可否执行以及执行的次序；只有在已获得足够多的信息后才可决定哪些运算符可以执行。<不同优先级的处置> 三种情况（高、等、低）。栈顶的优先级必然是当前栈最高的。可用来构造逆波兰表达式。

[**逆波兰表达式**] 操作符紧邻于对应的（最后一个）操作数之后。后缀表达式。<手工转换> 加足够细致的括号，将各运算符后移，使之紧邻于其对应的右括号的右侧。

##### 4.4 试探回溯法


[**剪枝**] 利用问题本身具有的某些规律尽可能多、尽可能早的排除搜索空间中的候选解。技巧在于根据某些局部特征，以候选解子集为单位批量的删除。

[**八皇后问题**] 问题描述：nxn棋盘中放n个皇后，使他们互不冲突。由鸽巢原理知，在n行n列的棋盘上至多能放置n个皇后。反之，n个皇后在nxn棋盘上的可行棋局通常也存在。用栈记录，回溯，试探。

[**迷宫寻径**] 除了记录位置，格点还需要记录其所在的状态。属于当前路径的格点，还需记录其前驱和后继。用栈实现路径由正确方向回溯。

##### 4.5 队列


队头允许取元素，队尾允许插入元素。

##### 4.6 队列应用

[**循环分配器**]  [**银行服务模拟**]

# 第五章

##### 5.1 二叉树及其表示


[**深度与层次**] 约定根节点位于第0层。

[**度数或度**] v的孩子总数。

[**祖先、后代与子树**] 父亲、孩子、叶节点、内部节点。

[**高度**] 所有节点深度的最大值。规定，仅含单个节点的树高度为0，空树高度为-1。

[**真二叉树**] 不含一度节点的二叉树。

[**有序多叉树 = 二叉树**] 增加一项约束条件：同一节点的所有孩子之间必须具有某一线性次序。

##### 5.2 编码树


[**前缀无歧义性**] 为了消除歧义性，任意两个原始字符所对应的二进制编码串相互都不能是前缀。

[**二叉编码树**] 向左（右）对应于0（1）。

[**PFC编码树**] 只要所有字符都对应于叶节点，歧义现象即自然消除。其解码过程可以在二进制编码串的接受过程中实时进行，而不必等到所有比特位都到达之后才开始，因此这类算法属于在线算法。PFC编码方案如何得出？

##### 5.3 二叉树的实现


[**成员变量**] 根据不同的需求，可以考虑要不要加入某些成员变量，比如depth和size等，利用这些变量固然可以加速静态的查询或搜索，但未保持这些变量的时效性，在所属二叉树发生结构性调整之后，这些成员变量都要动态的更新。比如，在二叉树结构改变频繁以至于动态操作多于静态操作的场合，舍弃深度、子树规模等变量，转而在实际需要时再直接计算这些指标，应是更为明智的选择。

[**高度更新**] 二叉树任一节点的高度，都等于其孩子节点的最大高度加一。一旦有节点加入或离开二叉树，则更新其所有祖先的高度。

[**子树接入**]  [**子树删除**]   [**子树分离**]  复杂度 ：常数

##### 5.4 遍历


无论是递归版遍历还是迭代版遍历算法都只需渐进的线性时间。

[**递归版遍历**]

[**迭代版先序遍历**] 先序遍历可分解为两段：沿最左侧通路自顶而下访问的各节点，以及自底向上遍历的对应右子树。{思考一下}

[**迭代版中序遍历**] 利用辅助栈记录和保存沿途经过的各个节点，一遍确定自底向上各段遍历子序列最终在宏观上的拼接次序。

[**迭代版后序遍历**] 借助辅助栈。

[**层次遍历**] 利用辅助队列，访问该节点时，放入子节点。

高度为h的满二叉树由2^(h+1)-1个节点组成，其中叶节点总是恰好比内部节点多一个。

##### 5.5 Huffman编码


# 第六章 图

##### 6.1 概述


[**简单图**] 不含任何自环的图。

[**简单通路**] 沿途顶点互异的通路。

[**DAG**] 有向无环图，不含任何环路的有向图。

[**欧拉环路**] 经过图中**各边**一次且恰好一次的环路。

[**哈密尔顿环路**] 经过图中**各顶点**一次且恰好一次的环路。

##### 6.3 邻接矩阵

##### 6.4 邻接表

尽管邻接表访问单条边的效率不高，却十分擅长于以批量方式，处理同一顶点的所有关联边。

##### 6.6 广度优先搜索BFS


[**实现**] 利用辅助队列。

[**BFS森林**] 各次BFS（）调用所得的BFS树构成BFS森林。

[**复杂度**] O（n + e）。

[**应用**] 连通域分解、最短路径问题。

##### 6.7 深度优先搜索DFS


[**DFS森林**] 选用不同的起始基点，生成的DFS树（森林）也可能各异。

[**复杂度**] O（n + e）。

[**应用**] 迷宫起点和终点的可达性。

##### 6.8 拓扑排序

[**拓扑排序**] 每个顶点都不可能通过边指向在此序列中的前驱顶点。

拓扑排序未必存在。但不含环路的有向图一定存在拓扑排序。

用栈记录拓扑排序的顶点。<commit_msg>Update 2018-07-31-DS-学习笔记-上.md<commit_after>---
layout:     post
title:      DS-学习笔记-上
subtitle:   数据结构（C++语言版）
date:       2018-07-31
author:     IdiotLeo
header-img: img/beach_real_2.jpg
catalog: true
tags:
    - 数据结构
    - DS
---

# Overview

记录学习数据结构的知识结构（上）

# 第三章 列表

##### 3.1 从向量到列表


[**列表**] 结构尽管也要求各元素在逻辑上具有线性次序，但对其物理地址却未做任何限制——几位“动态存储”策略。

##### 3.2 接口


[**节点内部**] T data; ListNode(T) pred; ListNode(T) succ;

##### 3.3 列表


[**头、尾节点**] 私有的头节点（header）和尾节点（trailer）始终存在，对外不可见。对外部可见的节点如果存在则第一个和最后一个称为首节点（first node）和末节点（last node）

外部不可见的节点叫做哨兵节点。

[**秩到位置的转换**] 重载操作符“[]”。

[**查找**] 时间复杂度O(n)，线性正比于查找区间的宽度。

[**插入**] 具有特定的操作顺序（顺序不可颠倒）。

[**删除**] 具有特定的操作顺序（顺序不可颠倒）。

[**析构**] 反复删除首节点。

[**唯一化**] 需要O（n）步迭代，每次迭代中find（）操作所需的时间线性正比于查找区间宽度，即当前节点的秩。

时间复杂度：1 + 2 + 3 + ···· + n = O（n^2）

##### 3.4 有序列表


大小次序与逻辑次序完全一致。

[**唯一化**] 两个指针p q分别指向每一对相邻的节点。时间复杂度：O（n）。

[**查找**] 顺序查找。原因：在动态存储策略中，节点的物理地址与逻辑次序毫无关系，故无法像有序向量那样自如地应用减而治之。

##### 3.5 排序器


[**插入排序**] 特点：在任何时刻，前缀总是已经有序。不断地插入。时间复杂度（取决于每一步的查找、删除、插入操作）：O（n^2）。

[**选择排序**] 特点：任何时刻，后缀总是已经有序。在前缀中找最大的插入后缀首节点。时间复杂度：O（n^2）。

[**归并排序**] 归并时间复杂度：O（m + n）。分治时间复杂度O（logn）。总时间复杂度：O（nlogn）。

# 第四章 栈与队列

##### 4.1 栈


[**盲端**] 不能进行操作的一端。栈底。

##### 4.2 栈与递归


递归算法所需空间量，主要决定于最大递归深度。

[**函数调用栈**] 基本单位帧。栈底必然是main（）占的一帧。

[**运行树**] 任意时刻的所有活跃函数实例，在调用栈中自底到顶，对应于运行树从根节点到最活跃函数实例的一条调用路径。

##### 4.3 栈的典型应用


[**逆序输出**] 逆序计算输出的。eg.**进制转换**。各数位由低到高逐位算出，但引入栈就可逆序输出，由高到低。

[**递归嵌套**] 自相似性。

**1、栈混洗**。随机的出栈或入栈操作。只要满足“任意前缀中的push不少于pop”这一限制，则该序列也必然对应于某个栈混洗。

**2、括号匹配**。<递归实现> 一般的，任何一个表达式S可以转化为：S = S0 + "(" + S1 + ")" + S2 + S3。其中S0和S3不含括号，且S1中左右括号数目相等，则S匹配当且仅当S1和S2匹配。采用分治策略：将表达式分为S0、S1、S2，递归的判断S1、S2是否匹配。时间复杂度：O（n^2）<迭代算法> 左右括号对应于push、pop操作，只需扫描一遍表达式，对所有括号进行栈操作即可。（也可推广至不同种类括号并存的场合）

[**延迟缓冲**] 在一些应用问题中，输入可以分解为多个单元并通过迭代依次扫描处理，但过程中的各步计算往往滞后于扫描的进度，需要待到必要的信息已完整到一定程度后才能做出判断并实施计算。这种场合可以使用栈结构扮演数据缓冲区的角色。

**表达式求值**。仅仅根据表达式的某一前缀，并不能完全确定其中各运算符可否执行以及执行的次序；只有在已获得足够多的信息后才可决定哪些运算符可以执行。<不同优先级的处置> 三种情况（高、等、低）。栈顶的优先级必然是当前栈最高的。可用来构造逆波兰表达式。

[**逆波兰表达式**] 操作符紧邻于对应的（最后一个）操作数之后。后缀表达式。<手工转换> 加足够细致的括号，将各运算符后移，使之紧邻于其对应的右括号的右侧。

##### 4.4 试探回溯法


[**剪枝**] 利用问题本身具有的某些规律尽可能多、尽可能早的排除搜索空间中的候选解。技巧在于根据某些局部特征，以候选解子集为单位批量的删除。

[**八皇后问题**] 问题描述：nxn棋盘中放n个皇后，使他们互不冲突。由鸽巢原理知，在n行n列的棋盘上至多能放置n个皇后。反之，n个皇后在nxn棋盘上的可行棋局通常也存在。用栈记录，回溯，试探。

[**迷宫寻径**] 除了记录位置，格点还需要记录其所在的状态。属于当前路径的格点，还需记录其前驱和后继。用栈实现路径由正确方向回溯。

##### 4.5 队列


队头允许取元素，队尾允许插入元素。

##### 4.6 队列应用

[**循环分配器**]  [**银行服务模拟**]

# 第五章

##### 5.1 二叉树及其表示


[**深度与层次**] 约定根节点位于第0层。

[**度数或度**] v的孩子总数。

[**祖先、后代与子树**] 父亲、孩子、叶节点、内部节点。

[**高度**] 所有节点深度的最大值。规定，仅含单个节点的树高度为0，空树高度为-1。

[**真二叉树**] 不含一度节点的二叉树。

[**有序多叉树 = 二叉树**] 增加一项约束条件：同一节点的所有孩子之间必须具有某一线性次序。

##### 5.2 编码树


[**前缀无歧义性**] 为了消除歧义性，任意两个原始字符所对应的二进制编码串相互都不能是前缀。

[**二叉编码树**] 向左（右）对应于0（1）。

[**PFC编码树**] 只要所有字符都对应于叶节点，歧义现象即自然消除。其解码过程可以在二进制编码串的接受过程中实时进行，而不必等到所有比特位都到达之后才开始，因此这类算法属于在线算法。PFC编码方案如何得出？

##### 5.3 二叉树的实现


[**成员变量**] 根据不同的需求，可以考虑要不要加入某些成员变量，比如depth和size等，利用这些变量固然可以加速静态的查询或搜索，但未保持这些变量的时效性，在所属二叉树发生结构性调整之后，这些成员变量都要动态的更新。比如，在二叉树结构改变频繁以至于动态操作多于静态操作的场合，舍弃深度、子树规模等变量，转而在实际需要时再直接计算这些指标，应是更为明智的选择。

[**高度更新**] 二叉树任一节点的高度，都等于其孩子节点的最大高度加一。一旦有节点加入或离开二叉树，则更新其所有祖先的高度。

[**子树接入**]  [**子树删除**]   [**子树分离**]  复杂度 ：常数

##### 5.4 遍历


无论是递归版遍历还是迭代版遍历算法都只需渐进的线性时间。

[**递归版遍历**]

[**迭代版先序遍历**] 先序遍历可分解为两段：沿最左侧通路自顶而下访问的各节点，以及自底向上遍历的对应右子树。{思考一下}

[**迭代版中序遍历**] 利用辅助栈记录和保存沿途经过的各个节点，一遍确定自底向上各段遍历子序列最终在宏观上的拼接次序。

[**迭代版后序遍历**] 借助辅助栈。

[**层次遍历**] 利用辅助队列，访问该节点时，放入子节点。

高度为h的满二叉树由2^(h+1)-1个节点组成，其中叶节点总是恰好比内部节点多一个。

##### 5.5 Huffman编码


# 第六章 图

##### 6.1 概述


[**简单图**] 不含任何自环的图。

[**简单通路**] 沿途顶点互异的通路。简单环路亦可推广。

[**DAG**] 有向无环图，不含任何环路的有向图。（Directed Acyclic graph）

[**欧拉环路**] 经过图中**各边**一次且恰好一次的环路。

[**哈密尔顿环路**] 经过图中**各顶点**一次且恰好一次的环路。

##### 6.3 邻接矩阵

##### 6.4 邻接表

尽管邻接表访问单条边的效率不高，却十分擅长于以批量方式，处理同一顶点的所有关联边。

[**邻接表示方法的优缺点**]

##### 6.6 广度优先搜索BFS


[**实现**] 利用辅助队列。

[**BFS森林**] 各次BFS（）调用所得的BFS树构成BFS森林。

[**复杂度**] O（n + e）。

[**应用**] 连通域分解、最短路径问题。

##### 6.7 深度优先搜索DFS


[**DFS森林**] 选用不同的起始基点，生成的DFS树（森林）也可能各异。

[**复杂度**] O（n + e）。

[**应用**] 迷宫起点和终点的可达性。

##### 6.8 拓扑排序

[**拓扑排序**] 每个顶点都不可能通过边指向在此序列中的前驱顶点。

拓扑排序未必存在。但不含环路的有向图一定存在拓扑排序。

用栈记录拓扑排序的顶点。
{'fraction_non_alphanumeric': 0.21524496393931858, 'fraction_numerical': 0.021885103208157175, 'mean_word_length': 7.723427331887201, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3092391', 'n_tokens_mistral': 7352, 'n_tokens_neox': 8561, 'n_words': 445}