数据结构知识导图

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储、组织数据的方式。以下梳理了数据结构的基本概念和术语、线性结构、数组和广义表、树形结构、内部排序、查找、图状或网状结构。

数据结构

• 基本概念和术语
  • 数据
    • 基本单位
      • 数据元素
        • 由数据项组成
    • 不可分割的最小单位
      • 数据项
  • 结构
    • 逻辑结构
      • 数据元素之间的逻辑关系
    • 物理结构
      • 在计算机中存储结构
  • 算法
    • 指令的有序序列
    • 有穷性、确定性、可行性
• 线性结构
  • 线性表
    • 实现
      • 顺序表
        • 试用于随机存取等操作
        • 插入/删除：O(n)
          • 插入移动次数：n/2
          • 删除移动次数
            • (n-1)/2
        • 求表长/取第i个数据元素：O(1)
      • 链表
        • 线性链表/单链表
          • 非随机存取的存储结构
          • 插入：s->next=p->next;p->next=s;删除：p->next=p->next->next;复杂度O(n)
        • 静态链表
          • 用一维数组表示，用游标cur来代替指针，第0分量看成头节点
        • 双向链表
          • 结点有两个指针域
          • 删除/插入：O(n)
        • 循环链表
          • 表中最后一个节点的指针域指向头节点
    • 应用
      • 一元多项式的表示和相加
  • 栈和队列
    • 栈
      • 后进后出（仅在表尾进行插删除操作）
        • 实现
          • 顺序栈(Page46、47)
            • 非空栈中的栈顶指针始终在栈顶元素的下一个位置上
            • 插入/删除：top+-1;
          • 链栈
          • 共享栈
        • 应用
          • 数值转换
          • 括号匹配检验
          • 行编译程序
          • 迷宫求解
          • 表达式求值
            • 操作数、运算符、界限符
          • 实现递归
    • 队列
      • 先进先出（在表的一端进行插入，在另一端进行删除操作
        • 实现
          • 链队列
            • 头指针和尾指针
              • 队列为空：头指针和尾指针均指向头节点
          • 循环队列
            • front\rear,非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置
            • 判断满/空
              • 空
                • Q.fornt==Q.rear
              • 满
                • Q。front==(Q.rear+1)%MAxSize
    • 双端队列
  • 串
    • 由字符组成的有限序列
      • 空串or空格串
    • 子串
      • 串中任意连续个字符组成的子序列
      • 数目S=(1+n)n/2+1
    • 实现
      • 定长顺序存储
      • 堆分配存储表示
      • 串的块链存储表示
    • 模式匹配算法
      • 主串S,模式串T
      • 朴素模式匹配算法
        • O((n-m+1)*n)
      • KMP算法
        • next[]数组的计算
          • 三种情况
          • 注意和原串数组下标有些错位，因为next[0]=0
        • nextval[]数组的计算
          • 当next[j]=k;pj=pk时，next[j]=next[k];
        • 算法时间复杂度
          • O(n*m),接近于O(n+m)
        • 特点
          • 指示主串的指针不需回溯
    • 串操作应用
• 数组和广义表
  • 数组
    • 只有存取元素和修改元素值的操作，一般不做插入/删除操作
    • 实现
      • 顺序存储
    • 矩阵的压缩存储
      • 特殊矩阵
        • n阶对称矩阵
          • 存储下三角/上三角(Page95-96)
          • 下三角
            • i>=j:i(i-1)/2+j-1
        • 对角矩阵
      • 稀疏矩阵
        • 三元组顺序表
          • 转置运算
            • 将矩阵的行列值互换
            • 将每个三元组中的i和j相互调换
            • 重排三元组之间的次序
        • 行逻辑链接的顺序表
        • 十字链表
  • 广义表
    • 定义
      • 表头：第一个元素
      • 原子a和子表A
      • 表尾：其余元素组成的表
      • 区分：()与(())
      • 任何一个非空列表，其表头可能是原子/列表，其表尾必然是列表
      • 求广义表的深度
        • 括弧的重数
    • 实现
      • 链式存储结构
        • 表结点
          • 标志域、指示表头/表尾的指针域
        • 原子结点
          • 标志域和值域
• 树形结构
  • 树
    • 结点
      • 终端结点/叶子
      • 分支结点
    • 基本术语
      • 结点的度
        • 结点拥有的子树数
      • 孩子、双亲、兄弟、堂兄弟
      • 深度
      • 有序树、无序树
    • 存储结构
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟表示法/二叉链表表示法
        • 右指针指向兄弟
    • 树和森林的遍历
      • 树
        • 先根遍历
        • 后根遍历
        • 以二叉链表做为树的存储结构时，先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历实现
      • 森林
        • 森林的先序
          • 对应二叉树的先序遍历
        • 森林的中序
          • 二叉树的中序遍历
  • 二叉树
    • 定义
      • 每个结点至多只有两棵子树（不存在度大于2的结点），子树次序不能颠倒，有左右之分
      • 5种基本形态
    • 性质
      • 在二叉树第i层上至多有2^(i-1)个结点
      • 深度为k的二叉树至多有2^k-1个结点
      • 任何一棵二叉树，叶子结点数为n0，度为2的结点数为n2，则n0=n2+1
      • 完全二叉树
        • 具有n个结点的完全二叉树的深度为ëlognû+1
        • 特点
        • 对任意结点
      • 满二叉树
        • 深度为k且有2^k-1个结点
    • 存储结构
      • 顺序存储结构
      • 链式存储结构
        • 在含有n个结点的二叉链表中有n+1个空链域
        • 子主题
    • 应用
      • 遍历二叉树
        • 前序遍历
          • VLR
        • 中序遍历
          • LVR
        • 后序遍历
          • LRV
        • 已知前序遍历+中序遍历，求后序遍历
          • 前序遍历第一个结点为根结点，中序遍历可断开左右分段
        • 已知后序遍历+中序遍历，求前序遍历
          • 后序遍历最后一个结点是根节点
        • 在二叉树结点的先序、中序、后序遍历中，所有叶子节点的先后顺序相同
        • 前序遍历和中序遍历，得到唯一的一棵二叉树
      • 线索二叉树
        • 作用
          • 加快查找结点的前驱或后继的速度
        • 前序和后序线索化后，空链域为1； 中序线索化后，空链域为2
    • 最优二叉树/赫夫曼树
      • 路径长度
        • 路径上的分支数目
      • 树的带权路径长度
        • WPL=åwl
      • 构造
        • page145
      • 赫夫曼编码
        • 前缀编码
          • 二叉树
      • 赫夫曼树的结点个数一定是奇数
  • 森林与二叉树的转换
    • 子主题
    • 一棵树可转换成唯一的一棵没有右子树的二叉树
  • 树的计数
    • n个结点的不相似的二叉树有--棵Page154
    • 具有n个结点有不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同
• 内部排序
  • 判断排序方法是否稳定
  • 待排序记录存放在计算机随机存储器中进行的排序
  • 插入排序
    • 直接插入排序
      • 正序时比较次数达n-1，逆序时比较次数为1/2n(n-1)
      • 时间复杂度O(n*n)
      • 是稳定的排序
    • 折半插入排序
      • 时间复杂度为O(n*n)
    • 2-路插入排序
      • 需要n个记录的辅助空间
    • 表插入排序
      • 以修改指针代替移动记录
      • 结果进行重排
        • 先互换，再修改指针域
      • 时间复杂度仍为O(n*n)
    • 希尔排序
      • 先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
      • 将相隔某个“增量”的记录组成一个子序列
      • 时间复杂度比直接插入低
      • 应使增量序列中的值没有除1以外的公因子，并且最后一个增量值必须等于1
      • 是不稳定的排序算法
  • 快速排序
    • 起泡排序
      • 一趟排序：将第一个记录和第二个记录比较，再将第二个与第三个记录比较
      • 若初始为正序序列，则只需进行一趟排序，若初始为逆序序列，则需进行n-1趟排序
      • 时间复杂度O(n*n)
      • 是稳定的排序算法
    • 快速排序
      • 枢轴
      • O(nlogn)
      • 若初始记录按关键字有序或基本有序时，快速排序将退化为起泡排序，时间复杂度为O(n*n)
      • 空间复杂度
        • 需要一个栈来实现递归，最大深度可降为O(logn)
      • 是不稳定的排序算法
  • 选择排序
    • 简单选择排序
      • 关键字的比较次数为n(n-1)/2
        • 不受记录的初始排列影响
      • 时间复杂度O(n*n)
      • 是一种不稳定的排序
    • 树形选择排序
      • 首先对n个记录的关键字进行两两比较，在其中én/2ù个较小者之间再两两比较，直至选出最小/大的
      • 可用一棵有n个叶子结点的完全二叉树表示
      • O(nlogn)
    • 堆排序
      • 堆
        • 若看成完全二叉树，则完全二叉树额所有非终端结点的值均不大/小于其左、右孩子结点的值
        • 小顶堆、大顶堆
      • 一个记录大小供交换用的辅助空间，每个待排序的记录仅占有一个存储空间
      • 对n较大的文件比较有效
      • 最坏情况下，时间复杂度O(nlogn)
      • 空间复杂度O(1)
      • 是不稳定的排序方法
  • 归并排序
    • 时间复杂度O(nlogn)
    • 空间复杂度O(n)
    • 是稳定的排序方法
  • 基数排序
    • MSD与LSD
    • 多关键字排序
• 查找
  • 查找表
    • 关键字
      • 主关键字、副关键字
    • 性能分析
      • 平均查找长度ASL
    • 静态查找表
      • 查找元素存在性、检索属性
      • 顺序表的查找
        • 顺序查找（可设置哨兵）
          • 在等概率情况下ASL=(n+1)/2
      • 有序表的查找
        • 折半查找
          • 适用于采用顺序存储结构的有序表（对线性链表无法有效地查找
          • 性能分析
            • 近似ASL=log(n+1)-1
      • 索引顺序表的查找
        • 索引表
          • 表有序或者分块有序
          • 确定块的查找可以顺序/折半查找，块中只能顺序查找
        • 性能分析
          • 表长为n,每一块的记录个数为s,则ASL=log(n/s+1)+s/2
          • 与n、s都有关，可能效率不如折半查找
    • 动态查找表
      • 查找过程中进行插入/删除操作
      • 二叉排序树
        • 性质
          • 左子树若不为空，左子树上所有结点的值均小于它的根节点的值
          • 右子树若不为空，右子树上所有结点的值均大于它的根节点的值
          • 它的左、右子树也分别为二叉排序树
        • 中序遍历一棵二叉排序树可得到一个关键字的有序序列
        • 插入
          • 新插入的结点一定是新添加的叶子结点
        • 删除
          • 三种情况
        • 查找
          • 子主题
        • 平衡二叉树AVL
          • 性质
            • 左子树和右子树均为平衡二叉树，且左右子树深度之差的绝对值不超过1.
          • 平衡因子
            • 左子树深度-右子树深度
            • AVL树只能为1、0、-1
          • 平衡树的生成（调整规律）
            • 单向右旋平衡处理
            • 单向左旋平衡处理
            • 双向旋转（先左后右）平衡处理
            • 先右后左平衡处理
          • 查找性能分析
            • 时间复杂度O(logn)
      • B-树和B+树
        • B-树
          • m阶B-树特性
            • 树中每个结点至多有m棵子树
            • 若根节点不为叶子结点，则至少有两棵子树
            • 除根之外的所有非终端结点至少有ém/2ù棵子树
            • 所有的非终端结点中包含信息数据
              • (n,A0,K1,A1,....Kn,An)
              • Ki关键字，Ki<K(i+1)
                • 个数范围
              • Ai指向子树根结点的指针，A(i-1)所指子树中所有结点的关键字均小于Ki,An所指子树中所有结点的关键字均大于Kn
            • 所有的叶子节点都出现在同一层次上，并且不带信息。
          • 查找分析
            • Page240-241
          • 插入
            • 溢出
              • 分裂，向上移
          • 删除
            • 下溢
              • 合并
        • B+树
          • 特性
            • 有n棵子树的结点包含有n个关键字
            • 其他
          • 查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。即无论查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
          • 插入和删除仅在叶子结点进行
      • 键树
        • 度³2的树，树中每个结点中只含有组成关键字的符号
    • 哈希表
      • 对应关系：哈希函数
      • 定义
        • 哈希表、散列、哈希/散列地址Page253
      • 构造方法
        • 直接定址法
          • 关键字/关键字的线性函数值
        • 数字分析法
          • 取关键字的若干数位组成哈希地址
        • 平方取中法
          • 取关键字平方的中间几位为哈希地址
        • 折叠法
          • 分割，再叠加
        • 除数留余法
          • p选择质数或者不包含小于20的质因数的合数
        • 随机数法
      • 处理冲突的方法
        • 开放定址法
          • di增量序列
            • di=1,2,3,...
              • 线性探测再散列
                • 易发生二次聚集
                • S»1/2(1+1/(1-a))
            • di=1*1,2*2,...
              • 二次探测再散列
            • di=伪随机数序列
              • 伪随机探测再散列
        • 再哈希法
        • 链地址法
        • 建立公共溢出区
      • 查找
        • 装填因子
          • a=表中填入的记录数/哈希表的长度
          • 平均查找长度依赖于装填因子
          • 见Page261
• 图状/网状结构
  • 基本术语
    • 顶点
    • 弧（有向图）
      • 弧尾
        • 弧的初始点
      • 弧头
        • 弧的终端点
    • 边（无向图）
    • 无向图
      • eÎ[1,1/2*n(n-1)]
    • 有向图
      • eÎ[0，n(n-1)]
    • 完全图、有向完全图
      • e分别取上面的最大值
    • 稀疏图
    • 子图
    • 邻接点、依附、相关联
    • 度
      • 和顶点v相关联边的数目TD(v)
      • 出度
      • 入度
    • 回路或环
    • 简单路径
      • 顶点不重复出现的路径
    • 连通
      • 连通图
        • 图中任意两个顶点间都连通
      • 连通分量
        • 无向图中的极大连通子图
      • 强连通图
        • 有向图中，每两点间都可以相互到达
      • 强连通分量
        • 有向图的极大连通子图
      • 一个连通图的生成树是一个极小连通子图
    • 网
      • 带权的图
  • 存储结构
    • 数组表示法
      • 对于无向图，顶点Vi的度是邻接矩阵中第i行/列的元素之和
      • 对于有向图，第i行元素的和是顶点Vi的出度OD(Vi),第j列元素的和是顶点Vj的入度ID(Vj)
    • 邻接表
      • 每个顶点建立一个单链表
      • 若无向图有n个顶点，e条边，则邻接表需要n个头结点和2e个表结点
      • 为方便计算有向图中顶点的入度，可以建立一个有向图的逆邻接表
    • 十字链表
    • 邻接多重表
  • 图的遍历
    • 深度优先搜索(DFS)
      • 类似于树的先根遍历
      • 时间复杂度
        • 当用邻接表存储图时，O(n+e)
      • 利用递归/栈来实现
    • 广度优先搜索(BFS)
      • 类似于树的按层次遍历
      • 利用队列
      • 时间复杂度
        • 和DFS相同
  • 图的连通性问题
    • 无向图
      • 对无向连通图遍历时，仅需从图中任意一点出发，进行DFS/BFS，便可访问到所有顶点。对非连通图则需从多个顶点进行搜索
      • 生成树
        • 深度/广度优先生成树
    • 有向图
      • 利用DFS求有向图的强连通分量
      • 最小生成树
        • Prim算法
          • 时间复杂度O(n*n)
            • 试用于求边稠密的网
        • Kruskal算法
          • 时间复杂度O(eloge)
            • 试用于求边稀疏的网
    • 关节点和重连通分量
      • 关节点
        • 若删去该顶点及其关联的边后，将一个连通分量分割成两个以上的连通分量
        • 两类关节点的特性
      • 重连通图
        • 没有关节点的连通图
      • 利用深度优先搜索可以求得关节点，并由此判断图是否重连通
      • 连通度k
        • 在该连通图上至少删去k个顶点才能破坏连通性
    • 有向无环图
      • 拓扑排序
        • 由某个集合上的一个偏序得到集合上的一个全序
        • AOV网
          • 顶点表示活动，弧表示活动间的优先关系的有向图
        • 如何进行拓扑排序
          • 在有向图中选一个没有前驱的顶点且输出
          • 从图中删除该顶点和所有以它为尾的弧
          • 重复以上两步，直至全部顶点均已输出，或者当前不存在无前驱的顶点为止。后一种情况说明有向图中有环。
          • 也可利用DFS,按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列
      • AOE网
        • 顶点表示事件，弧表示活动（activity on edge），权表示活动持续的时间
        • 可用来估算工程的完成时间
        • 源点、汇点
        • 关键路径
          • 路径长度最长的路径，即为完成工程的最短时间
          • e(i)
            • 活动ai的最早开始时间
          • l(i)
            • 活动ai最迟必须开始的时间
          • 关键活动
            • e(i)=l(i)
            • 关键路径上的活动都是关键活动（提前完成非关键活动不能并不能加快工程进度）
          • ve(i)
            • 事件的最早发生时间
            • 计算时应从ve(0)向前递推
          • vl(i)
            • 事件的最迟发生时间
            • 计算时从vl(n-1)=ve(n-1)向前后递推
          • 求关键路径的算法
    • 最短路径
      • 从某个源点到其余各顶点的最短路径
        • Dijkstra算法
          • 内容Page187-189
          • 时间复杂度O(n*n)
      • 每一对顶点之间的最短路径
• 关系：e=1/2åTD(v)