[TOC]
-
This is a datastructure learning notebook
-
Ref: \
-
os
Ubuntu 16.04 LTS
-
compiler
g++ version 9.4.0
- Use cmake version 3.22 to build this project
- git clone
$ git clone [email protected]:DC-Jade/TinyDataStructure.git- build && run
$ cmake ./ && make && ./bin/main.o/* k >> 3 refers to the index of k in array */
/* k & 0x07 equal to k % 8 */
/* 1 << (k & 0x07) refers to index in a char(8 bits) */
void Set(int k) { Expand(k); _M[k >> 3] |= (1 << (k & 0x07)); }
void Clear(int k) { Expand(k); _M[k >> 3] &= ~(1 << (k & 0x07)); }
bool Test(int k) { Expand(k); return _M[k >> 3] & (1 << (k & 0x07)); }-
程序设计是对确定的问题，选择一种合适的数据结构，加上合适的算法
-
程序设计= 数据结构 + 算法
-
数据结构管理存在一种或多种关系数据元素的容器
-
本质
-
解决数据和数据关系的存储和实现
-
关系的存储
-
顺序存储
顺序表SeqList
数组实现顺序存储
-
链接存储
单链表SingleLinkList
线性结构的链接实现
一个指针，指向后继节点
-
哈希存储
-
索引存储
-
-
-
def
不可分割的最小单位
-
example
人的年龄
-
def
又称记录，是组成数据的、有一定意义的基本单位，通常作为整体处理
-
构成
数据项
-
example
一个人
-
def
- 性质相同的数据元素的集合
-
example
- 一群人
-
def
存在一种或多种关系的数据元素的集合
基于某种特定语言，实现ADT的一套算法
-
结构
数据（元素）之间的关系
-
集合结构
数据元素同属一个集合，但没有相互关系
-
线性结构
一对一
-
树形结构
一对多
-
图形结构
多对多
-
作用
面向问题
-
def
数据的逻辑结构在计算机中的存储形式
-
顺序存储结构
地址必须连续
-
链接存储结构
地址可以不连续
指针表示地址
-
作用
面向计算机，存储数据和逻辑关系到内存
-
def
性质相同的值的集合以及在该集合上一些操作的总称
-
本质
数据类型按照值的不同进行划分。高级语言中每个表达式（变量等）都有各自的取值范围，类型用于说明表达式的取值范围和能够进行的操作
-
分类（Clang）
原子类型 - 不可分割的基本类型, 包含整型，字符型
结构类型 - 原子类型复合而成。 包含类类型 - 如vector， Union
-
抽象
提取数据本质特征，忽略非本质的细节，是一种思考问题的方式
-
def
一个数学模型和定义在该数学模型上的一组操作，没有代码实现
-
分类
-
内置的数据类型
-
类类型，即自定义的数据类型
-
-
构成
-
数据成员(data member)
-
成员函数/接口(function member)
-
-
作用
-
实现接口和实现的分离
-
程序设计中的问题分解，抽象和信息隐藏
-
大问题分解为小问题，建立计算机能处理的数据模型，把每个功能模块的实现细节作为一个独立单元，使具体实现过程隐藏
-
-
顺序存储结构
存取（存入或取出）时间复杂度$$O(1)$$，该特点的数据结构称为随机存取结构
内置数据类型，内存的一块连续空间, 大小不可更改
数组的抽象和泛化
-
特点
相对数组，元素不限于基本类型
call by rank, 寻秩访问
-
data member
Rank _size
int _capacity
T *_elem
-
interface
-
size()
-
get(rank r)
-
put(rank r, T &e)
用e替换秩为r的元素
-
insert(rank r, T &e)
-
remove(rank r)
-
find(T &e)
所有向量查找
查找失败返回-1
成功返回r
-
disordered()
返回逆序对的数目
-
sort()
-
search(T &e)
有序向量查找
返回不大于e的最大元素的秩r
最小元素大于e时候，返回-1
-
deduplicate()
所有向量去重复
-
uniquify()
有序向量去重复
-
traverse()
访问所有元素
-
-
def
零个或多个数据元素的有限序列
-
特点
-
序列
有顺序的数据元素的集合
-
-
表示
$a_1a1a_1a1, ..., a_{i-1}ai−1a_{i-1}ai−1, a_{i}aia_{i}ai, a_{i+1}ai+1a_{i+1}ai+1,..., a_nana_nan$
-
构成
-
长度n
元素个数n称为线性表的长度
n>=0
n= 0，称为空表
-
$索引i$ $i是元素a_iaia_iai在线性表的位序$ -
直接前驱元素
$i > 1 ,a_iaia_iai只有唯一一个直接前驱元素$ $a_{i-1} ai−1a_{i-1} ai−1是a_iaia_iai直接前驱元素$ -
直接后继元素
$i < n ,a_iaia_iai只有唯一一个直接后继元素$ $a_{i+1} ai+1a_{i+1} ai+1是a_iaia_iai直接后继元素$
-
-
def
线性表的特殊形式，后进先出的线性表
-
特点
后进先出（LIFO）
只能表尾插入删除
-
构成
栈顶top - 进行插入删除的一端
栈底bottom
-
def
线性表的特殊形式，先进先出的线性表
-
特点
先进先出（FIFO）
队头删除
队尾插入
-
构成
队头（front）
队尾（rear）
-
def
n个节点（node）的有限集
-
本质
列表的列表
半线性结构
前驱节点存在, 后继节点不一定存在
按层次组织数据的关系
-
特点
-
有且仅有唯一的根节点(root)
-
n=0，空树
-
n>1时，其余节点分为m（m>0）个互不相交的有限集T1，T2，...,Tm，其中每一个集合本身是一个树，称为根的子树(subtree)
-
-
节点vertex
数据元素和若干指向其子树的分支
所有节点由叶子节点和分支节点构成
-
度(degree)
节点的孩子节点数目
-
叶节点(leaf)
度为0, 没有后继的节点
-
分支节点
度不为0的节点，即除叶子节点以外的节点
-
父节点(parent)
孩子节点的上层节点
-
孩子节点(child)
节点的子树的根
-
兄弟节点(sibling)
父节点的孩子节点互称兄弟节点
-
层次(level)
即节点深度 + 1
根节点是第一层
根的孩子节点是第二层
以此类推
-
深度(depth)
节点到根节点的边的个数
-
高度(height)
所有叶子节点到子树根节点的深度的最大值
-
节点高度
节点对应子树的高度
-
路径
节点到节点之间的边构成
长度是路径之间的边的个数
-
连通图
所有节点之间都存在路径的树
-
无环图
不含环路的连通图
所有节点到根节点都存在唯一路径
双亲表示法
孩子表示法
孩子兄弟表示法
双亲+孩子表示法
-
分类
-
有序树
子树从左到右不可互换 ，即子树有序
-
无序树
子树左右顺序可互换，即子树无序
-
-
森林(forest)
- 互不相交的树的集合
-
表示方法
-
父亲-孩子表示法
-
长子-兄弟表示法
只记录长子和兄弟节点
-
-
特点
-
每个节点最多两棵子树
-
左右子树有顺序，不可互换
-
只有一棵子树，必须区分左右子树
-
-
分类
-
空二叉树
-
只有根节点
-
只有左子树
-
只有右子树
-
左右子树都有
-
-
左斜树
只有左子树
-
右斜树
只有右子树
- 节点的度都是偶数$(0 || 2)$，即不含度为1的节点
-
完全二叉树的特例，即所有叶节点都在最底层的完全二叉树
-
所有分支节点都有左右子树
-
所有叶节点在同一层
-
性质
-
叶节点出现在最底部的两层，并且最底层叶节点均处于次底层叶节点的左侧
-
二叉树的第i层上至多有$2^{i-1}2i−12^{i-1}2i−1个节点（i≥1）$
-
深度为k的二叉树至多有$2^k - 12k−12^k - 12k−1个节点$
-
-
存储结构
-
顺序存储
-
二叉链表
两个指针域（左右节点）
-
-
定义
按照某种次序，所有节点有且只有一次访问
-
分类
按照父节点V的访问顺序定义，默认从左往右
-
中序遍历(inorder)
LVR - left -> root -> right, V在中间被访问
-
后序遍历(postorder)
LRV - left -> right -> root, V在最后被访问
-
前(先)序遍历(preorder)
VLR - root -> left -> right, V第一个被访问
-
特点
深度优先，即先访问左子树的所有左子树节点
先自上而下访问左子树（左侧链）的左节点，后自下而上访问右子树
-
步骤
-
访问父亲节点
-
依次检查右孩子和左孩子, 右孩子入栈
-
左孩子作为父节点迭代
-
访问
-
-
-
本质
一般意义的树
-
有序树(ordered tree)
即同一节点孩子之间需有存在某一线性次序的多叉树，等价于二叉树
-
二叉树表示
-
前提
有根; 有序
-
方法
长子-兄弟表示
-
-
重构
-
条件
本质，需要根据两个序列，判断序列的左右子树，从而重构
-
一般树
-
条件
（先序/后序）+中序
-
-
-
def
由顶点(V)、有穷非空集合和顶点之间的边(E)的集合组成
相对树结构，顶点之间的关系限定更少
-
邻接关系
顶点与顶点之间的关系
-
关联关系
顶点和边之间的关系
-
分类
-
无向图（undirected graph）
顶点之间的关系没有次序，则顶点之间的边称为无向边，仅有无向边构成图是无向图
-
有向图（Directed graph）
顶点之间存在次序，边是有向边，仅有有向边构成的图
-
-
简单路径
不含重复节点的路径
-
路径
含有重复节点的路径
-
有向无环图
-
欧拉环路
-
哈密尔顿环路
-
表示
-
G(V，E)
-
V(vertex)，图G顶点的集合
-
E(edge)，图G边的集合
-
-
顶点(vertex)
-
边(Edge)
-
有向边（或弧Arc）
弧头(tail)
弧尾(head)
$(v_i , v_jvi,vjv_i , v_jvi,vj)$ -
无向边
$(v_{i} ,v_jvi,vjv_{i} ,v_jvi,vj)$
-
-
顶点(vertex)
-
邻接矩阵(adjacency matrix)
-
无向图
对称矩阵
-
有向图
-
无权图
01表示
-
有权图（网络）
权重值表示
-
-
一维数组
-
-
边(edge)
邻接表（adjacency list）
-
概念
-
权（weight）
与图的边或弧相关的数
表示从顶点到顶点的距离
-
连通
顶点之间存在路径
-
环
路径的起始点和终点是同一个顶点
-
度
无向图顶点的边数是度
-
入度
进入有向图顶点的边数
-
出度
离开有向图顶点的边数
-
网络
由带权重的边组成的图
-
-
def
从某一顶点出发，所有顶点遍历一次
本质是将图转化成树tree进行遍历
-
广度优先遍历（breadth first search，BFS）
-
即图的层次遍历，构建支撑树Spanning Tree
-
步骤
-
访问顶点s
-
访问s的邻接顶点
-
迭代
-
-
最短路径
-
-
深度优先遍历（depth first search，DFS）
-
即树的深度遍历，构建支撑树
-
步骤
-
访问顶点s
-
访问s未被访问的任一邻居
-
循环1-2步
-
-
-
最小生成树(minimum cost spanning tree)
-
权重和最小的生成树
-
克鲁斯卡尔(Kruskal)算法
以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树
-
迪杰斯特拉(Dijkstra)算法
一个按路径长度递增的次序产生最短路径的算法”
-
弗洛伊德(Floyd)算法
-
-
def
字符序列
-
元素
字符
-
结构
-
特点
-
def
解决问题的一系列步骤
有限的指令
-
输入
-
输出
-
有穷性 - 有限时间可完成
-
确定性 - 每个命令明确作用，不出现二义性，即无歧义
-
可行性 - 机器能够在有限次数内完成
-
算法设计
-
正确性
语义正确，得到正确结果
处理非法输入，得到合适结果
通过复杂的测试
-
可读性 - 必要的注释
-
鲁棒性（健壮性）- 处理输入数据不合法的情况，抛出常见错误，输入错误等
-
高效率 - 低T(n)
-
低存储 - 低S(n)
-
-
正确性 - 不变性+单调性
-
复杂度
-
分类
-
时间复杂度$T(n)$ - 默认复杂度是$T(n)$， 正相关于基本操作的执行次数
-
空间复杂度$S(n)$ - 存储空间需求
-
-
估计方法
-
事后统计 - benchmark
-
事前统计 - 时间复杂度估计算法时间效率，渐进分析
-
大$O$记法 - 即估计时间上限，算法最差情况
常数加法$O(1)$
线性复杂度$O(n)$
含n多项式$O(n^k)$，保留最高次幂k，省略多项式的常数系数
顺序
$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(e^n)<O(n!)<O(n^n)$ -
大$\Omega$记法 - 即估计时间下界，算法最好情况
-
$大\Theta记法$ - 即估计平均时间，算法平均情况
-
-
-
级数
-
算术级数
末项高出一阶
$1+ 2 + ... + n < n + n + ... + n = n^21+2+...+n<n+n+...+n = n21+ 2 + ... + n < n + n + ... + n = n^21+2+...+n<n+n+...+n=n2$ -
调和级数 logn
不收敛，但是长度有限
$1 + 1/2 + ... + 1/n = O(logn)1+1/2+...+1/n=O(logn)1 + 1/2 + ... + 1/n = O(logn)1+1/2+...+1/n=O(logn)$ -
对数级数nlogn
$log1 + log 2 + ... + logn = log(n!) < log(n^n) = nlognlog1+log2+...+logn=log(n!)<log(nn)=nlognlog1 + log 2 + ... + logn = log(n!) < log(n^n) = nlognlog1+log2+...+logn=log(n!)<log(nn)=nlogn$ -
幂方级数
比幂次高出一阶
$1^2 + 2^2 + ... + n^2 = n(n+1)(n+2)/6 = O(n^3)12+22+...+n2=n(n+1)(n+2)/6=O(n3)1^2 + 2^2 + ... + n^2 = n(n+1)(n+2)/6 = O(n^3)12+22+...+n2=n(n+1)(n+2)/6=O(n3)$ -
几何级数
与末项同阶
$ 2^0 + 2^1 + ... + 2^n = O(2^n)20+21+...+2n=O(2n)2^0 + 2^1 + ... + 2^n = O(2^n)20+21+...+2n=O(2n)$
$2^0 + 2^1 + ... + 2^{log2n} = O(n)20+21+...+2log2n=O(n)2^0 + 2^1 + ... + 2^{log2n} = O(n)20+21+...+2log2n=O(n)$ -
收敛级数O(1)O(1)O(1)O(1)
-
-
-
增
-
删
-
查
-
无序查找find
-
有序查找search
-
二分查找binSearch
-
复杂度 -
$O(logN)$ -
步骤
T &e，Rank lo， Rank hi
Rank mid = （lo + hi ）>> 1
分为三个区间 [lo,mid), [mid], (mid,hi);
-
-
Fib查找fibSearch
-
复杂度 -
$O(logN)$ -
$fib(n) = n (n < 2); fib(n) = fib(n-1) + fib(n-2)$ -
类似二分查找
-
区别：mid换成fib分割点，使左侧更深，右侧更浅，总体更均衡
-
-
插值查找
-
mid 根据概率随机抽取
-
-
-
-
-
改
-
排序
-
向量排序- 接口
- Rank lo， Rank hi
- 接口
-
冒泡排序bubbleSort
-
复杂度 -
$O(n^2)$ -
步骤
-
遍历lo hi
-
调用bubble
- 比较一对元素
- 是否逆序对
- 交换为顺序对
-
记录是否交换（没有交换，提前终止）
-
扫描交换
-
-
-
归并排序mergeSort
-
复杂度 -
$O(nlogn)$ -
步骤
- 一分为二
- 子序列递归分解
- 合并
-
特点
- 不稳定
-
-
选择排序selectionSort
-
复杂度 -
$O(n^2)$ -
步骤
分为Unsort(prefix) + Sort(suffix)
-
特点
稳定; 输入不敏感
-
范围
向量; 列表
-
-
插入排序insertionSort
-
步骤
分为Sort(prefix) + Unsort(suffix)
-
逆序对inversion
-
复杂度 -
$O(I + n)= O(I) + O(n)$ I是整个list的逆序对总数，算法复杂度取决于逆序对总数I和序列长度n
最快$O(n)$,即I = 0
最慢$O(n^2)$, 即$I = （n-1 + n -2 + ... + 1） = n *（n-1） / 2$
-
特点
输入敏感; 稳定
-
范围
列表; 向量
-
链表排序 -
-
遍历
-
深度优先遍历(deepth fisrt search, dfs)
中序遍历 - left -> root -> right
后序遍历 - left -> right -> root
-
广度优先遍历(breadth first search, bfs)
先序遍历 - root -> left -> right
-
- 迭代iteration
-
减治
-
步骤
-
分解为两个子问题
一个是基（或平凡）
另一个规模缩小
-
求解子问题
-
合并子问题
-
- 递归recursion
-
本质
top-down，即自顶向下
-
步骤
处理递归基
分解子问题
-
策略
减而治之
分而治之
-
分析
-
递归跟踪recursive trace
线性递归linear recursive
-
递推方程
-
$T(n) = T(n- 1 ) + O(1)$ $T(n) -n = T(n - 1) - (n - 1) = ... = T(1) - 1 = T(0) $ $T(n) = T(0) + n = n + O(1) = O(n)$ -
$T(0) = O(1)$
-
-
-
特点
- 所有递归都可以由迭代实现
- 动态规划(dynamic programming, DP)
-
本质
-
一种算法思想，先拆分问题，将大问题拆分成性质相同的子问题，求解子问题
-
bottom-up，或table-fill，自底向上，也可以通过top-down
-
-
fib递归
-
递归存在大量的重复计算，造成低效
-
自上而下
-
-
fib迭代（动态规划）
- 自下而上
-
LCS（longest common subsequence）
-
cache
-
临时内存，减少IO
-
cache会存一个元素临近的page，而非一个元素，会减少IO
-