842数据结构

数据结构

1. 绪论

• 斐波那契数列时间复杂度
  • 递归方法用差分方程求，时间复杂度n方
  • 非递归时间复杂度n

2. 线性表

• 随机存取：已知首元素地址和位序，O(1)时间内直接得到目标地址（顺序表）

• 顺序表可以顺序存取和随机存取，链表只能从表头顺序存取元素

• 头指针和头结点的区分：不管带不带头结点，头指针都始终指向链表第一个结点，而头结点是带头结点链表的第一个结点

• 链表的定义

  typedef struct LNode{
      int data;
      LNode *next;
  }LNode, *LinkList;
  
  // 树的链表定义
  typedef struct BiTNode{
      int data;
      struct BiTNode *lchild, *rchild;
  }BiTNode, *BiTree;

3. 栈和队列

• 都属于线性表

• 栈和队列的定义

  #define MaxSize 50
  typedef struct{
      int data[MaxSize];
      int top;
  } SqStack;
  
  // 队列顺序存储
  typedef struct{
      int data[MaxSize];
      int front, rear;
  } SqQueue;
  
  // 队列链式存储
  typedef struct LinkNode{
      int data;
      struct LinkNode *next;
  } LinkNode;
  typedef struct{
      LinkNode *front, *rear;
  } LinkQueue;

• 栈的top初始值-1，队列的front指向头元素，rear指向队尾元素下一位置(循环队列一般空一个位置，用来区分队列空和队列满的判别条件)

• 应用题

  • 栈：括号匹配 表达式求值

• 特殊矩阵压缩

  • 上三角 or 下三角 除了存三角区域的元素，还要存另外半三角的常量一次
  • 三对角矩阵：非零元素都在三角区域内，第一行和最后一行只有两个非零数，其余行是三个

• 稀疏矩阵

  • 三元组（行、列、值）
  • 十字链表

4. 树

• 树的度数（边数）等于节点数减一

• 二叉树：叶子结点个数等于度为2的结点数加一 N0 = N2 + 1

• 含有N个结点的二叉链表中含有N+1空链域（线索二叉树）

• 先后序不能确定唯一二叉树

• 线索二叉树，有两个标志位，ltag = 1 表示 lchild 是结点左前驱

• 顺序存储法要存所有结点

• 王道：先序序列abcd的不同二叉树个数相当于以abcd入栈的出栈序列：用亚特兰数 1/(n+1)Cn 2n

• 先序中序后序递归遍历中，栈的作用

  • 递归算法的话，只是visit的位置不同
  • 先序和中序用栈非递归，都是先遍历左子树入栈，后出栈一个遍历右子树，先序是先访问再入栈，中序是先入栈，弹出再访问

• 树的存储结构

  • 双亲表示法（顺序存储结构，除了数据还有双亲下标）
  • 孩子表示法（类似邻接表，结点有孩子链）
  • 孩子兄弟表示法（又叫二叉树表示法）

• 树和森林的遍历

  • 树的遍历（因为不是二叉树，不分为左右子树，只分根和子树）
    • 先根遍历：与对应二叉树的先序序列相同
    • 后根遍历：与对应二叉树的中序序列相同
    • 层次遍历：和二叉树层次遍历思想相同
  • 森林的遍历
    • 先序遍历：访问第一颗树的根 先序遍历第一棵树的子树森林 先序遍历剩余
    • 中序遍历：中序遍历第一颗树 访问根结点 中序遍历剩余
  • 记忆方式：不用二叉树的后序遍历

• 并查集：一种集合，用树的形式

• 二叉搜索树要满足中序遍历是有序的，不是简单的左结点小右结点大

• 王道：三叉树计算带权路径：用0构造完全三叉树

5. 图

• 概念
  • 简单图：不存在重复边，不存在顶点到自身的边。
  • 完全图（简单完全图）：任意两个顶点之间都存在边
  • 子图：顶点是子集，边集也是子集
  • 连通图：任意两个顶点都是连通的
  • 连通分量：无向图的极大连通子图是连通分量
  • 强连通：对应有向图的连通
  • 生成树：包含全部顶点的极小连通子图
  • 简单路径：顶点不重复出现的路径
• 邻接矩阵：一维数组存顶点，二维数组存边
• 邻接表：两种结点（顶点表结点、边表结点）
  • 顶点表结点（一个数组）：值和边表指针
  • 边表结点：值和下一个边的指针
• 十字链表和邻接多重表
• BFS
  • 空间复杂度：顶点队列o(v)
  • 时间复杂度：每个顶点访问一次，访问相邻点时有区别，邻接表访问次数等于e，邻接矩阵每个点都要访问v次。邻接表o(v+e)，邻接矩阵o(v^2)
• DFS
  • 空间复杂度：栈高度为顶点数，o(v)
  • 时间复杂度：与BFS分析一致，都是需要查边
• 最小生成树
  • prim：（p点）选距离最近的点加入集合，适用于边多 o(v^2)
  • kruskal：选最小边，适用于点多
• 最短路径
  • 单源最短Dijkstra算法：dist数组、path数组、集合S（初始为v0）o(v^2)
  • 每对顶点最短路径Floyd算法 o(v^3)
• DAG：有向无环图
  • AOV用点表示活动： 拓扑排序：每次选择没有前驱的点输出，删边
  • AOE用边表示活动： 关键路径：最长路径
    • ve事件最早开始：（从前往后算，最大值）
    • vl事件最晚开始：（从后往前算，最小值）
    • e活动最早开始：起点最早开始时间 ve
    • l活动最晚开始：终点最晚时间减去活动时间 vl-t

6.查找

• 动态查找表：需要动态插入删除的查找表

• 顺序查找

  • 一般：成功（n+1）/2，失败n+1
  • 有序：（画图，判定树）成功不变，失败**(1+2+..+n+n)/n+1**

• 折半查找（有序）

  • 代码（low<=high，low向下取整，high=mid-1，low=mid+1）
  • 所以最后一次查找是low与high相等
  • 判定树找ASL 时间复杂度o（logn）

• 分块查找（索引顺序查找）

  • 块内无序，索引结点（最大值）有序
  • 顺序或折半查找索引，顺序查找块内 ASL = L1 + L2

• 二叉排序树

  • 平衡二叉树o（logn），单支树o（n）
  • 删除：用后继或前驱代替
  • 平衡二叉树：找最近不平衡结点作为a
    • LL：右转 RR：左转
    • LR：左右（先代替左再代替右） RL：右左
  • 平衡二叉树的题目：所有非叶节点平衡因子为1，Cn = Cn-1 + Cn-2 + 1

• B树

  • m叉树：结点至少Ceil(m/2)-1个数，至多m-1
  • 所有叶结点出现在同一层次
  • 插入时分裂：中间位置m/2（上取整）插入父结点
  • 删除：用后继或前继；兄弟够，父亲代替自己，兄弟上去；兄弟不够，父亲下来，和兄弟合并。
  • m叉B树的结点数量
  • 与B+树的不同：B+树可以顺序查找

• 散列表

  • 散列函数：线性直接不会冲突；除留余数（取不大于表长的质数）；平方中间几位；
  • 处理冲突：线性探测（顺序下一个）；平方探测0，1，-1，4，-4；拉链法（同义词存链表）
  • ASL 比较次数（不冲突是1）

• 散列查找

  • 散列表装填因子增大，更容易发生冲突

7.排序

• 上图记忆方法
  • 堆排序、归并排序时间复杂度固定nlogn；直接选择都是n^2
  • 选择排序、希尔排序、快排不稳定
  • 快速排序平均最好都是nlogn，冒泡和直插最好n，平均n^2
  • 快排辅存要nlogn
• 插入排序：将待排序记录插入，前面排好序的子序列
  • 可以折半查找插入位置，再移动之后的元素
  • 希尔排序：取不同步长的数，分组排序
• 交换排序：每次将元素的最终位置找到
  • 快排（内部最快排序算法）：如果区域个数不对称，时间复杂度n^2，递归栈深度n
• 选择排序：每一趟选取最小的元素，作为有序队列的元素。
  • 简单选择：每一趟选最小的，与相应位置交换。移动很少，比较次数固定
  • 堆排序（不断输出堆顶元素）
    • 建立堆：初始顺序放置，之后不断调整非叶子结点
    • 输出元素：堆顶与堆尾元素交换，调整。
    • 插入：放在末端，调整。
• 归并排序和基数排序
  • 归并排序：把单个元素作为子表，n路排序后归并。 eg：对10TB的数据文件进行排序，使用外部排序
  • 基数归并：选10作为基数，个十百千位分别接龙。