首页data structure

# 绪论

# 数据结构的定义

  • 数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
  • 数据元素是数据的基本单位（例如，A 班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理
  • 数据项是具有独立含义的数据最小单位，也称为成员或域
  • 数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。
  • 数据结构是指所涉及的数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。
  • 数据元素之间的逻辑关系 => 数据的逻辑结构
  • 数据元素及其关系在计算机存储器中的存储方式 => 数据的存储结构（或物理结构）
  • 施加在该数据上的操作 => 数据运算

# 算法及其描述

  • 有穷性
  • 确定性
  • 可行性
  • 输入性
  • 输出性

# 算法时间性能分析

  • 求和定理
  • 求积定理

# 算法存储空间分析

  • 在对算法进行存储空间分析时，只考察临时变量所占空间

# 线性表

# 顺序表

  • 插入元素移动的平均次数为∑i=0npi(n−i)=1n+1×n(n+1)2=n2\sum\limits_{i=0}^n p_i (n-i)=\frac{1}{n+1}\times \frac{n(n+1)}{2}=\frac{n}{2}
  • 删除元素移动的平均次数为∑i=0n−1pi(n−i−1)=1n×n(n−1)2=n−12\sum\limits_{i=0}^{n-1} p_i (n-i-1)=\frac{1}{n}\times \frac{n(n-1)}{2}=\frac{n-1}{2}

# 链表

  • 插入 s->next = p->next; p->next = s;
  • 删除 q = p->next; p->next = q->next; delete q;
  • 头插法建表 s->next = head->next; head->next = s;

# 栈和队列

# 栈

  • 判断准则：输入序列为1,2,…,n,(p1,p2,…,pn)1,2,…,n,(p_1,p_2,…,p_n) 是1,2,…,n1,2,…,n 的一种排列，利用一个栈得到输出序列(p1,p2,…,pn)(p_1,p_2,…,p_n) 的充分必要条件是不存在这样的i、j、ki、j、k 满足i<j<ki<j<k 的同时也满足pj<pk<pip_j<p_k<p_i。
  • 1∼n1\sim n 共产生1n+1C2nn\frac{1}{n+1} C_{2n}^n 种合法出栈序列

# 队列

# 顺序队列

  • 队空条件： front == rear
  • 队满（上溢出）条件： rear == MaxSize - 1

# 循环队列

  • 元素出队： front = (front + 1) ％ MaxSize
  • 元素 e 进队： rear = (rear + 1) ％ MaxSize
  • 队空条件： front == rear
  • 队满条件： (rear + 1) % MaxSize == front

# 链队

  • 队空条件： front = rear = NULL

# 数组

# 数组的存储结构

# 一维数组

  • LOC(ai)=LOC(a0)+i×k    (1≤i<n)LOC(a_i)=LOC(a_0)+i×k \ \ \ \ (1≤i<n)

# 二维数组

  • 行优先：LOC(aij)=LOC(a00)+(i×n+j)×kLOC(a_{ij})=LOC(a_{00}) + (i×n + j)×k
  • 列优先：LOC(aij)=LOC(a00)+(j×m+i)×kLOC(a_{ij})=LOC(a_{00}) + (j×m + i)×k

# 对称矩阵的压缩存储

  • k={i(i+1)2+ji≥j时(下三角+主对角线的元素)j(j+1)2+i当i<j时(aij=aji)k=\begin{cases}\frac{i(i+1)}{2}+j &i≥j时(下三角+主对角线的元素) \\ \frac{j(j+1)}{2}+i &当i<j时(a_{ij}=a_{ji})\end{cases}

# 稀疏矩阵的三元组表示

  • 行号、列号、元素值

# 递归

# 递归算法转换为非递归算法

# 迭代转换法

  • 尾递归和单向递归是两种特殊类型的递归，可以采用迭代转换法将它们转换为非递归算法，即将其递归结构用循环结构来替代。
  • 尾递归是递归调用语句只有一个，而且是处于算法的最后
  • 单向递归是指执行过程总是朝着一个方向进行的，递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，参数相互之间无关

# 用栈模拟转换法

  • 不能采用迭代转换法的递归算法执行中往往涉及回溯，可以采用栈来保存暂时不能执行的子问题，或者使用栈保存中间结果，称为用栈模拟转换法

    void nonrecursive(si)	//非递归算法框架
    {  将大问题状态si进栈;
       while (栈不为空)
       {  退栈一个元素s;
          if (s可以直接解决)
             直接求该问题解;
          else
          {  根据递归过程将s转换为若干个相似子问题的状态sj;
             将每个sj进栈;
          }
       }
    }

# 树和二叉树

# 树的基本术语

  • 结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度
  • 树的度：树中所有结点的度的最大值称之为树的度
  • 分支结点：度大于 0 的结点称为分支结点或非终端结点。度为 1 的结点称为单分支结点，度为 2 的结点称为双分支结点，依次类推
  • 叶子结点：度为零的结点称为叶子结点或终端结点
  • 结点层次：树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次
  • 树的高度：树中结点的最大层次称为树的高度或深度

# 树的性质

  • 树中的结点数等于所有结点的度数加 1
  • 度为 m 的树中第 i 层上至多有mi−1m^{i-1} 个结点，这里应有 i≥1
  • 高度为 h 的 m 次树至多有mh−1m−1\frac{m^h-1}{m-1} 个结点
  • 具有 n 个结点的 m 次树的最小高度为log⁡m[n(m−1)+1]\log_m[n(m-1)+1]

# 二叉树的定义

  • 在含 n 个结点的二叉树中，所有结点的度小于等于 2，通常用n0n_0 表示叶子结点个数，n1n_1 表示单分支结点个数，n2n_2 表示双分支结点个数

# 满二叉树

  • 即一棵高度为 h 且有2h−12^{h}-1 个结点的二叉树称为满二叉树，只有度为 0 和度为 2 的结点，
  • 含 n 个结点的满二叉树的高度为log⁡2(n+1)\log_2(n+1)，叶子结点个数为⌊n/2⌋+1\lfloor n/2\rfloor +1，度为 2 的结点个数为⌊n/2⌋\lfloor n/2 \rfloor

# 完全二叉树的特点

  • 叶子结点只可能出现在最下面两层中
  • 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上
  • 如果有度为 1 的结点，只可能有一个，且该结点只有左孩子而无右孩子
  • 按层序编号后，一旦出现某结点（其编号为 i）为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点
  • 具有 n 个（n＞0）结点的完全二叉树的高度为⌊log⁡2(n+1)⌋\lfloor \log_2(n+1)\rfloor 或⌊log⁡2n⌋+1\lfloor\log_2n\rfloor+1

# 二叉树性质

  • 非空二叉树上叶结点数等于双分支结点数加 1。即n0=n2+1n_0=n_2+1
  • 非空二叉树上第 i 层上至多有2i−12^{i-1} 个结点，(i≥1)。
  • 高度为 h 的二叉树至多有2h−12^{h}-1 个结点（h≥1）
  • n1n_1 只能是 0 或 1，当 n 为偶数时，n1=1n_1=1，当 n 为奇数时，n1=0n_1=0

# 哈夫曼树

  • WPL=∑i=1n0wi×liWPL=\sum\limits_{i=1}^{n_0}w_i\times l_i
  • 哈夫曼树中没有单分支结点
  • 对于具有n0n_0 个叶子结点的哈夫曼树，共有2n0−12n_0-1 个结点

# 哈夫曼编码

  • 规定哈夫曼树中的左分支为 0，右分支为 1
  • 从根结点到每个叶子结点所经过的分支对应的 0 和 1 组成的序列便为该结点对应字符的编码

# 树 / 森林与二叉树的转换及还原

# 一棵树到二叉树的转换

  • 加线：在各兄弟结点之间加一连线，将其隐含的 “兄－弟” 关系以 “双亲－右孩子” 关系显示表示出来
  • 抹线：对任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的 “双亲－孩子” 关系
  • 调整：以树的根结点作为二叉树的根结点，将树根与其最左子树之间的 “双亲－孩子” 关系改为 “双亲－左孩子” 关系，且将各结点按层次排列，形成二叉树
# 特点
  • 根结点只有左子树而没有右子树
  • 左分支不变（左分支为最左孩子），兄弟变成右分支（右分支实为双亲的兄弟）
  • 树中分支结点个数为 m，则二叉树中无右孩子的结点个数为 m+1

# 一棵由树转换的二叉树还原为树

  • 加线：在各结点的双亲与该结点右链上的每个结点之间加一连线，以 “双亲－孩子” 关系显示表示出来
  • 抹线：抹掉二叉树中所有双亲结点与其右孩子之间的 “双亲－右孩子” 关系
  • 调整：以二叉树的根结点作为树的根结点，将各结点按层次排列，形成树
# 特点
  • 根结点不变
  • 左分支不变（左分支为最左孩子），右分支变成兄弟

# 森林与二叉树的转换及还原

# 森林转换为二叉树

  • 转换：将森林中的每一棵树转换成二叉树，设转换成的二叉树为bt1、bt2、…、btmbt_1、bt_2、…、bt_m
  • 连接：将各棵转换后的二叉树的根结点相连
  • 调整：以bt1bt_1 的根结点作为整个二叉树的根结点，将bt2bt_2 的根结点作为bt1bt_1 的根结点的右孩子，将bt3bt_3 的根结点作为bt2bt_2 的根结点的右孩子，…，如此这样得到一棵二叉树，即为该森林转换得到的二叉树

# 二叉树还原为森林

  • 抹线：抹掉二叉树根结点右链上所有结点之间的 “双亲－右孩子” 关系，分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为bt1、bt2、…、btmbt_1、bt_2、…、bt_m
  • 转换：分别将bt1、bt2、…、btmbt_1、bt_2、…、bt_m 二叉树各自还原成一棵树
  • 调整：将转换好的树构成森林

# 图

# 图的存储结构

# 邻接矩阵

# 邻接表

  • 对图中每个顶点 i 建立一个单链表，将顶点 i 的所有邻接点链起来
  • 每个单链表上添加一个表头结点（表示顶点信息）。并将所有表头结点构成一个数组，下标为 i 的元素表示顶点 i 的表头结点
# 特点
  • 邻接表表示不唯一
  • 对于有 n 个顶点和 e 条边的无向图，其邻接表有 n 个表头结点和 2e 个边结点；对于有 n 个顶点和 e 条边的有向图，其邻接表有 n 个表头结点和 e 个边结点
  • 用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为O(m)O(m)

# 查找

# 查找的基本概念

  • 静态查找表是只作查找操作的查找表，主要操作有查询某个 “特定的” 数据元素是否在查找表中，检索某个 “特定的” 数据元素及其属性
  • 动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

# 顺序查找

  • ASL成功=∑i=0n−1pici=1n∑i=0n−1(i+1)=1n×n(n+1)2=n+12ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{i=0}^{n-1}(i+1)=\frac{1}{n}\times\frac{n(n+1)}{2}=\frac{n+1}{2}
  • ASL不成功=∑i=0n−1qin=nASL_{不成功}=\sum\limits_{i=0}^{n-1}q_in=n
  • ASL=ASL成功+ASL不成功    (p+q=1)ASL=ASL_{成功}+ASL_{不成功}\ \ \ \ (p+q=1)

# 折半查找

  • ASL成功=∑i=0n−1pi×level(ki)ASL_{成功}=\sum\limits_{i=0}^{n-1}p_i\times level(k_i)
  • ASL不成功=∑i=−1n−1qi×(level(ui)−1)ASL_{不成功}=\sum\limits_{i=-1}^{n-1}q_i\times (level(u_i)-1)
  • 满二叉树：ASL成功=∑i=0n−1pici=1n∑j=1h2j−1×j=n+1nlog⁡2(n+1)≈log⁡2(n+1)−1ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{j=1}^h2^{j-1}\times j=\frac{n+1}{n}\log_2(n+1)\approx\log_2(n+1)-1

# 索引存储结构和分块查找

# 过程

  • 查找索引表（有序）：可以顺序查找块，也可以二分查找块。
  • 查找数据块（无序）：只能顺序查找块中元素。

# 性能（若有 n 个元素，每块中有 s 个元素（块数b=⌈n/s⌉b=\lceil n/s \rceil））

  • 折半：ASLblk=ASLbn+ASLsq=log⁡2(b+1)−1+s+12≈log⁡2(ns+1)+s2ASL_{blk}=ASL_{bn}+ASL_{sq}=\log_2(b+1)-1+\frac{s+1}{2}\approx \log_2(\frac{n}{s}+1)+\frac{s}{2}
  • 顺序：ASLblk‘=ASLbn+ASLsq=b+12+s+12=12(ns+s)+1ASL^`_{blk}=ASL_{bn}+ASL_{sq}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1

# 二叉排序树

  • 查找序列（k1，k2，…，knk_1，k_2，…，k_n）的查找树画法是，每一层只有一个结点，首先 k1 为根结点，再依次画出其他结点，若ki+1<kik_{i+1}<k_i，则ki+1k_{i+1} 的结点作为kik_i 结点的左孩子，否则作为右孩子

# 哈希表

  • 对于两个不同的关键字kik_i 和kjk_j（i≠ji≠j）出现h(ki)=h(kj)h(k_i)=h(k_j)，这种现象称为哈希冲突，同义词冲突

# 构造方法

  • 直接定址法 h(k)=k+ch(k)=k+c
  • 除留余数法 h(k)=k%ph(k)=k\%p
  • 数字分析法

# 哈希冲突解决方法

  • 装填因子 α 是指哈希表中已存入的元素数 n 与哈希地址空间大小 m 的比值，即α=nmα=\frac{n}{m}
# 开放定址法
  • 线性探测法d0=h(k), di=(di−1+1)%m    (1≤i≤m−1)d_0=h(k),\ d_i=(d_{i-1}+1)\% m \ \ \ \ (1≤i≤m-1)
  • 平方探测法d0=h(k), di=(d0±i2)%m    (1≤i≤m−1)d_0=h(k),\ d_i=(d_0±i^2)\% m\ \ \ \ (1≤i≤m-1)
# 拉链法

# 排序

# 希尔排序（不稳定）

  • d=n/2
  • 将排序序列分为 d 个组，在各组内进行直接插入排序
  • 递减 d=d/2，重复② ，直到 d=0 为止

# 快速排序（不稳定）

  • 每趟使表的第 1 个元素放入适当位置（归位），将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为 0 或 1（递归出口）

# 堆排序（不稳定）

  • 大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字
  • 最小关键字的元素一定是某个叶子结点
  • 堆排序的关键是构造堆，这里采用筛选算法建堆
  • 自顶向下筛选：从根结点 R [low] 开始向下依次查找较大的孩子结点
  • 所有筛选的时间复杂度为O(log⁡2n)O(\log_2n)

# 自底向上的二路归并排序

# 平衡归并

  • 有清晰的趟数（同一趟产生的归并段优先归并）
  • 归并树高度h=⌊log⁡2n⌋+1h=\lfloor \log_2n\rfloor+1
  • 归并的趟数h−1h-1