/TinyDataStructure

Primary LanguageC++MIT LicenseMIT

[TOC]

TinyDataStructure

Intrucduction

Supported

  • os

    Ubuntu 16.04 LTS

  • compiler

    g++ version 9.4.0

Required

  • Use cmake version 3.22 to build this project

Run test

  1. git clone
$ git clone git@github.com:DC-Jade/TinyDataStructure.git
  1. build && run
$ cmake ./ && make && ./bin/main.o

BitMap

/* 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)); }

核心问题

  • 程序设计是对确定的问题，选择一种合适的数据结构，加上合适的算法

  • 程序设计= 数据结构 + 算法

  • 数据结构管理存在一种或多种关系数据元素的容器

  • 本质

    • 解决数据和数据关系的存储和实现

    • 关系的存储

      1. 顺序存储

        顺序表SeqList

        数组实现顺序存储

      2. 链接存储

        单链表SingleLinkList

        线性结构的链接实现

        一个指针，指向后继节点

      3. 哈希存储

      4. 索引存储

数据相关概念

数据项

  • def

    不可分割的最小单位

  • example

    人的年龄

数据元素

  • def

    又称记录，是组成数据的、有一定意义的基本单位，通常作为整体处理

  • 构成

    数据项

  • example

    一个人

数据对象

  • def

    • 性质相同的数据元素的集合

  • example

    • 一群人

数据结构

  • def

    存在一种或多种关系的数据元素的集合

    基于某种特定语言，实现ADT的一套算法

  • 结构

    数据（元素）之间的关系

逻辑结构

  1. 集合结构

    数据元素同属一个集合，但没有相互关系

  2. 线性结构

    一对一

  3. 树形结构

    一对多

  4. 图形结构

    多对多

  • 作用

    面向问题

物理/存储结构

  • def

    数据的逻辑结构在计算机中的存储形式

  1. 顺序存储结构

    地址必须连续

  2. 链接存储结构

    地址可以不连续

    指针表示地址

  • 作用

    面向计算机，存储数据和逻辑关系到内存

数据类型（或者数据）

  • def

    性质相同的值的集合以及在该集合上一些操作的总称

  • 本质

    数据类型按照值的不同进行划分。高级语言中每个表达式（变量等）都有各自的取值范围，类型用于说明表达式的取值范围和能够进行的操作

  • 分类（Clang）

    原子类型 - 不可分割的基本类型, 包含整型，字符型

    结构类型 - 原子类型复合而成。 包含类类型 - 如vector， Union

抽象数据类型(abstract data type, ADT)

  • 抽象

    提取数据本质特征，忽略非本质的细节，是一种思考问题的方式

  • def

    一个数学模型和定义在该数学模型上的一组操作，没有代码实现

  • 分类

    1. 内置的数据类型

    2. 类类型，即自定义的数据类型

  • 构成

    1. 数据成员(data member)

    2. 成员函数/接口(function member)

  • 作用

    1. 实现接口和实现的分离

    2. 程序设计中的问题分解，抽象和信息隐藏

    3. 大问题分解为小问题，建立计算机能处理的数据模型，把每个功能模块的实现细节作为一个独立单元，使具体实现过程隐藏

线性结构sequence

  • 顺序存储结构

    存取（存入或取出）时间复杂度$$O(1)$$，该特点的数据结构称为随机存取结构

数组(array)

内置数据类型，内存的一块连续空间, 大小不可更改

向量(vector)

数组的抽象和泛化

  • 特点

    相对数组，元素不限于基本类型

    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()

      访问所有元素

线性表(list)

  • 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 &gt; 1 ,a_iaia_iai只有唯一一个直接前驱元素$

      $a_{i-1} ai−1a_{i-1} ai−1是a_iaia_iai直接前驱元素$

    • 直接后继元素

      $i &lt; n ,a_iaia_iai只有唯一一个直接后继元素$

      $a_{i+1} ai+1a_{i+1} ai+1是a_iaia_iai直接后继元素$

栈(stack)

  • def

    线性表的特殊形式，后进先出的线性表

  • 特点

    后进先出（LIFO）

    只能表尾插入删除

  • 构成

    栈顶top - 进行插入删除的一端

    栈底bottom

队列(queue)

  • def

    线性表的特殊形式，先进先出的线性表

  • 特点

    先进先出（FIFO）

    队头删除

    队尾插入

  • 构成

    队头（front）

    队尾（rear）

位图Bitmap

非线性结构

树(tree)

  • 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)

    • 互不相交的树的集合

  • 表示方法

    • 父亲-孩子表示法

    • 长子-兄弟表示法

      只记录长子和兄弟节点

二叉树(binary tree)

  • 特点

    • 每个节点最多两棵子树

    • 左右子树有顺序，不可互换

    • 只有一棵子树，必须区分左右子树

  • 分类

    • 空二叉树

    • 只有根节点

    • 只有左子树

    • 只有右子树

    • 左右子树都有

斜树

  • 左斜树

    只有左子树

  • 右斜树

    只有右子树

真二叉树(proper binary tree)
  • 节点的度都是偶数$(0 || 2)$，即不含度为1的节点
满二叉树

  • 完全二叉树的特例，即所有叶节点都在最底层的完全二叉树

  • 所有分支节点都有左右子树

  • 所有叶节点在同一层

完全二叉树

  • 性质

    • 叶节点出现在最底部的两层，并且最底层叶节点均处于次底层叶节点的左侧

    • 二叉树的第i层上至多有$2^{i-1}2i−12^{i-1}2i−1个节点（i≥1）$

    • 深度为k的二叉树至多有$2^k - 12k−12^k - 12k−1个节点$

  • 存储结构

    • 顺序存储

    • 二叉链表

      两个指针域（左右节点）

遍历(traversal)

  • 定义

    按照某种次序，所有节点有且只有一次访问

  • 分类

    按照父节点V的访问顺序定义，默认从左往右

深度优先遍历(deepth fisrt search, dfs)

  1. 中序遍历(inorder)

    LVR - left -> root -> right, V在中间被访问

  2. 后序遍历(postorder)

    LRV - left -> right -> root, V在最后被访问

  3. 前(先)序遍历(preorder)

    VLR - root -> left -> right, V第一个被访问

    • 特点

      深度优先，即先访问左子树的所有左子树节点

      先自上而下访问左子树（左侧链）的左节点，后自下而上访问右子树

    • 步骤

      1. 访问父亲节点

      2. 依次检查右孩子和左孩子, 右孩子入栈

      3. 左孩子作为父节点迭代

      4. 访问

广度优先遍历(breadth first search, bfs), 层次遍历

多叉树(multiple tree)

  • 本质

    一般意义的树

  • 有序树(ordered tree)

即同一节点孩子之间需有存在某一线性次序的多叉树，等价于二叉树

  • 二叉树表示

    • 前提

      有根; 有序

    • 方法

      长子-兄弟表示

  • 重构

    • 条件

      本质，需要根据两个序列，判断序列的左右子树，从而重构

    • 一般树

      • 条件

        （先序/后序）+中序

图(graph)

  • def

    由顶点(V)、有穷非空集合和顶点之间的边(E)的集合组成

    相对树结构，顶点之间的关系限定更少

  • 邻接关系

    顶点与顶点之间的关系

  • 关联关系

    顶点和边之间的关系

  • 分类

    • 无向图（undirected graph）

      顶点之间的关系没有次序，则顶点之间的边称为无向边，仅有无向边构成图是无向图

    • 有向图（Directed graph）

      顶点之间存在次序，边是有向边，仅有有向边构成的图

  • 简单路径

    不含重复节点的路径

  • 路径

    含有重复节点的路径

  • 有向无环图

  • 欧拉环路

  • 哈密尔顿环路

  • 表示

    • G(V，E)

    • V(vertex)，图G顶点的集合

    • E(edge)，图G边的集合

逻辑结构

  • 顶点(vertex)

  • 边(Edge)

    1. 有向边（或弧Arc）

      弧头(tail)

      弧尾(head)

      $(v_i , v_jvi,vjv_i , v_jvi,vj)$

    2. 无向边

      $(v_{i} ,v_jvi,vjv_{i} ,v_jvi,vj)$

存储结构

  • 顶点(vertex)

    1. 邻接矩阵(adjacency matrix)

      • 无向图

        对称矩阵

      • 有向图

      • 无权图

        01表示

      • 有权图（网络）

        权重值表示

    2. 一维数组

  • 边(edge)

    邻接表（adjacency list）

  • 概念

    • 权（weight）

      与图的边或弧相关的数

      表示从顶点到顶点的距离

    • 连通

      顶点之间存在路径

    • 环

      路径的起始点和终点是同一个顶点

    • 度

      无向图顶点的边数是度

    • 入度

      进入有向图顶点的边数

    • 出度

      离开有向图顶点的边数

    • 网络

      由带权重的边组成的图

图遍历(Traversing Graph)

  • def

    从某一顶点出发，所有顶点遍历一次

    本质是将图转化成树tree进行遍历

  • 广度优先遍历（breadth first search，BFS）

    • 即图的层次遍历，构建支撑树Spanning Tree

    • 步骤

      1. 访问顶点s

      2. 访问s的邻接顶点

      3. 迭代

    • 最短路径

  • 深度优先遍历（depth first search，DFS）

    • 即树的深度遍历，构建支撑树

    • 步骤

      1. 访问顶点s

      2. 访问s未被访问的任一邻居

      3. 循环1-2步

  • 最小生成树(minimum cost spanning tree)

    • 权重和最小的生成树

    • 克鲁斯卡尔(Kruskal)算法

      以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树

    • 迪杰斯特拉(Dijkstra)算法

      一个按路径长度递增的次序产生最短路径的算法”

    • 弗洛伊德(Floyd)算法

串(string)

  • def

    字符序列

  • 元素

    字符

  • 结构

  • 特点

算法

  • def

    解决问题的一系列步骤

    有限的指令

五大特点

  1. 输入

  2. 输出

  3. 有穷性 - 有限时间可完成

  4. 确定性 - 每个命令明确作用，不出现二义性，即无歧义

  5. 可行性 - 机器能够在有限次数内完成

  6. 算法设计

    • 正确性

      语义正确，得到正确结果

      处理非法输入，得到合适结果

      通过复杂的测试

    • 可读性 - 必要的注释

    • 鲁棒性（健壮性）- 处理输入数据不合法的情况，抛出常见错误，输入错误等

    • 高效率 - 低T(n)

    • 低存储 - 低S(n)

算法分析

  • 正确性 - 不变性+单调性

  • 复杂度

    • 分类

      1. 时间复杂度$T(n)$ - 默认复杂度是$T(n)$， 正相关于基本操作的执行次数

      2. 空间复杂度$S(n)$ - 存储空间需求

    • 估计方法

      1. 事后统计 - benchmark

      2. 事前统计 - 时间复杂度估计算法时间效率，渐进分析

        • 大$O$记法 - 即估计时间上限，算法最差情况

          常数加法$O(1)$

          线性复杂度$O(n)$

          含n多项式$O(n^k)$，保留最高次幂k，省略多项式的常数系数

          顺序

          $O(1) &lt; O(logn) &lt; O(n) &lt; O(nlogn) &lt; O(n^2) &lt; O(n^3) &lt; O(e^n)&lt;O(n!)&lt;O(n^n)$

        • 大$\Omega$记法 - 即估计时间下界，算法最好情况

        • $大\Theta记法$ - 即估计平均时间，算法平均情况

    • 级数

      1. 算术级数

        末项高出一阶

        $1+ 2 + ... + n &lt; n + n + ... + n = n^21+2+...+n&lt;n+n+...+n = n21+ 2 + ... + n &lt; n + n + ... + n = n^21+2+...+n&lt;n+n+...+n=n2$

      2. 调和级数 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)$

      3. 对数级数nlogn

        $log1 + log 2 + ... + logn = log(n!) &lt; log(n^n) = nlognlog1+log2+...+logn=log(n!)&lt;log(nn)=nlognlog1 + log 2 + ... + logn = log(n!) &lt; log(n^n) = nlognlog1+log2+...+logn=log(n!)&lt;log(nn)=nlogn$

      4. 幂方级数

        比幂次高出一阶

        $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)$

      5. 几何级数

        与末项同阶

        $ 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)$

      6. 收敛级数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 &lt; 2); fib(n) = fib(n-1) + fib(n-2)$

        • 类似二分查找

        • 区别：mid换成fib分割点，使左侧更深，右侧更浅，总体更均衡

      • 插值查找

        • mid 根据概率随机抽取

        • img

  • 改

  • 排序

    • 向量排序

      • 接口
        • Rank lo， Rank hi

    • 冒泡排序bubbleSort

      • 复杂度 - $O(n^2)$

      • 步骤

        1. 遍历lo hi

        2. 调用bubble

          1. 比较一对元素
          2. 是否逆序对
          3. 交换为顺序对

        3. 记录是否交换（没有交换，提前终止）

        4. 扫描交换

    • 归并排序mergeSort

      • 复杂度 - $O(nlogn)$

      • 步骤

        1. 一分为二
        2. 子序列递归分解
        3. 合并

      • 特点

        • 不稳定

    • 选择排序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

算法**

  1. 迭代iteration

  • 减治

  • 步骤

    1. 分解为两个子问题

      一个是基（或平凡）

      另一个规模缩小

    2. 求解子问题

    3. 合并子问题

  1. 递归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)$

  • 特点

    • 所有递归都可以由迭代实现
  1. 动态规划(dynamic programming, DP)

  • 本质

    • 一种算法**，先拆分问题，将大问题拆分成性质相同的子问题，求解子问题

    • bottom-up，或table-fill，自底向上，也可以通过top-down

  • fib递归

    • 递归存在大量的重复计算，造成低效

    • 自上而下

  • fib迭代（动态规划）

    • 自下而上

  • LCS（longest common subsequence）

  • cache

    • 临时内存，减少IO

    • cache会存一个元素临近的page，而非一个元素，会减少IO