ZEROCATH

身无长物江湖远,胸有沟壑天地宽

0%

数据结构笔记(复习版)

For final exam only.

绪论

  • 数据元素:数据的基本单位
  • 数据项:数据的不可分割的最小单位
  • 数据对象:性质/类型相同的数据元素组成的集合
  • 算法:有穷,确定,可行,输入输出
  • 算法设计:正确,可读,健壮,高效率,低存储量
  • 算法复杂度
    • 时间频度f(n):算法中原操作的执行次数
    • 时间复杂度:T(n)=O(f(n))
      • 表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同
      • 本质是求f(n)的同阶无穷大
    • 空间复杂度:存储本身,输入输出,临时占用

      线性表

      由元素组成的有限序列
  • 顺序存储寻址
  • 双向链表
  • 多项式链表表示

    栈与队列

    只在表尾进行插入、删除操作的线性表;后进先出
  • 顺序栈:top指向栈顶元素的上一空位置
  • 链式栈:top指向栈顶,新进站的:首结点,同样先出栈
  • 应用
    • 数制转换
    • 表达式:括号匹配/求值

      队列

  • 一端插入元素,另一端删除元素
  • 顺序队列假溢出的解决

  • 基本操作
    • strcat(s,t):st
    • strcmp(s1,s2): s1=s2:0,s1s2:负整数,s1s2:正整数
    • strstr(s1,s2):若s2是s1的子串,则指向s2在s1中第1次出现时的第1个字符的位置;否则返回NULL
    • Replace(s,t,v):用v代替主串s中出现的所有与t相等的不重叠的子串
    • StrInsert(s,i,t):将t插入s中第i个字符之前
  • 单链表表示
    • 存储密度:串值所占存储位/实际分配存储位
  • 匹配模式——字串定位
    • 朴素匹配
    • O(m+n),O((n-m+1)*m)

      KMP

  • O(n+m)

    数组与广义表

    数组

    元素是同类型元素或同类型的定长线性表
  • 顺序:以行序为主序
  • 逆序:以列序为主序

矩阵压缩存储

  • 将下三角矩阵存储至意味数组中的下标转换
  • 稀疏矩阵的压缩
  • 十字链表储存稀疏矩阵

    广义表

    元素可以是同类型的元素或广义表。相同类型的数据的有限,有序的组合。数据元素或广义表组成的有限序列
  • 树型结构
    树型结构
  • 链式存储
    • 多项式运算

      一些概念

  • 结点的度:结点的子树数目
  • 树的度:树中各结点的度的最大值。n度树
  • 广义表,eg.A(B(C,D),E,F(G))

    二叉树

  • 第i层最多2^(i-1)个结点
  • 深度k,最多2^k-1个结点
  • 叶子数=度为2的结点数目+1
  • 顺序编号的满二叉树
    • i的左小孩:2i,右小孩2i+1,双亲:i/2向下取整,层号log2(i)向下取整
  • 线索二叉树
  • 表达式二叉树:前序——前缀/波兰式,后序——后缀/逆波兰式
  • 树与二叉树的转换

    哈夫曼树

  • 路径长度:路径上分枝的数目
  • 树的路径长度PL(T):树的根到其余的每个结点的路径长度之和
    • 完全二叉树:PL(T)min
  • 带权路径长度WPL(T):每个叶子的权值与其到根的距离乘积之和
  • 构造哈夫曼树
  • 哈夫曼码

    乱七八糟的概念

  • (强)连通分量:极大(强)连通子图
  • 生成树:图的极小连通子图
  • 有向树:仅有一个顶点的入度为0,其余顶点的入度均为1

    存储结构

  • 数组/邻接矩阵
  • 邻接表
  • 十字链表
  • 邻接多重表
    邻接多重表

    遍历

  • DFS
    • 生成树/森林
  • BFS
    • 生成树/森林

最小生成树

各边的权之和最小的生成树

  • MST性质:设G=(V,E)是连通图,T=(U,TE)是正在构造的最小生成树;若边(u,v)是G中所有一端在U中,一端在V中的具有最小值的一条边,则必存在一颗包含边(u,v)的最小生成树。
    邻接多重表
  • Prime算法

对n个顶点的连通网,先选一个顶点,再根据MST性质,每次增加相连的权值最小的边和顶点,直至得到最小生成树

  • Kruskal算法

将边按递增次序排列以供选择

  • 网的最小生成树

删除权最大的边,以不破坏连通性为标准,保留n-1条

拓扑排序

  • DAG图:无环的有向图
  • AOV网:顶点表示活动,弧表示活动之间的优先关系的DAG图
  • 拓扑排序
    有向图全部顶点的保持了原有向图中各顶点间相对次序的线性序列
  • 算法思想:
    • 在有向图中选一个入度为0的顶点
    • 从图中删除该顶点及所有以之为尾的弧

      关键路径

  • AOE网
    • 带权的无环有向图,顶点表示事件,弧表示活动,权值表示活动持续时间
    • 估算完成时间:开始点,完成点
    • 关键路径:从开始点到完成点的最长路径长度
    • ve(vi):事件vi的最早发生时间
    • vl(vi):事件vi的最迟发生时间
    • e(ai):活动ai的最早开始时间,与其上一事件的最早发生时间对应
    • vl(vi):事件vi允许的最迟开始时间=完成点vn的最早发生时间-vi~vn的最长路径长度
  • 关键路径算法步骤
    • 从开始点v1出发,令ve(1)=0,按拓朴排序序列求其它各顶点的最早发生时间ve(k)=max{ve(j)+dut(<j,k>)}(vj为以顶点vk为弧头的所有弧的弧尾对应的顶点集合)
    • 从完成点vn出发,令vl(n)=ve(n),按逆拓朴排序序列求其它各顶点的最迟发生时间Vl(j)=min{vl(k)-dut(<j,k>)}(vk为以顶点vj为弧尾的所有弧的弧头对应的顶点集合)
    • 求每一项活动ai(vj,vk):e(i)=ve(vj)l(i)=vl(vk)-dut(ai)

最短路径

  • Dijkstra

以每一个顶点为源点,重复执行Dijkstra算法n次,即可求出每一对顶点之间的最短路径。

  • Floyd

假设求Vi到Vj的最短路径,如果从Vi到Vj有弧,则存在一条长度为arcs[i][j]的路径,该路径不一定是最短路径,尚需进行n次试探。

查找

  • 平均查找长度ASL:查找时比较关键字次数的平均值

    静态

    不插入/删除元素
  • 顺序查找
    • 有监视哨:ASL=(n+1)/2
    • 无监视哨:ASL=n/2
  • 折半/二分查找(有序表)
    • 判定树
    • ASL:成功/失败(根据判定树)
    • O(log2(n))
  • 分块查找
    • ASL:ASL(索引表)+ASL(块内)
    • 顺序查找
      • 最佳分块:s=√n,b=√n,ASL(min)=√n+1

        动态

        在查找时同时插入查找表中不存在的数据元素
  • 二叉排序/查找树
    • 任一结点大于其非空左子树的所有结点,而小于其非空右子树的所有结点
    • 中序遍历的结点序列递增有序
    • 删除结点
      • 叶结点:双亲结点指针置空
      • 只有一个子树:用子树结点替换被删除结点
      • 左右子树都存在:
        • 在右子树中找中序下第一个结点填补
    • 查找性能
      • 最好:满二叉树:ASL=(n+1)/n*logx(n+1)-1
      • 最坏:单枝树:ASL=(n+1)/2
      • 平均:O(log2(n))
  • 平衡二叉树
    • 平衡因子:结点的左右子树深度之差
    • AVL树:任意结点平衡因子绝对值<=1
    • 平衡化处理
      • 左单旋转
        左单旋转
      • 右单旋转
        右单旋转
      • 先左后右
        先左后右
        先左后右
      • 先右后左
        先右后左
        先右后左

(平衡)二叉(排序)树
树的比较

哈希

存储数据元素时,利用一个Hash函数根据数据元素的关键字计算出该数据元素的存储位置,查找时,也是根据给定的数据元素的关键字计算出该数据元素可能存储位置

哈希表也称为散列表,其数据元素的存储一般是不连续的。 通过Hash函数计算出的地址称为哈希地址或散列地址

排序

  • 插入排序
    • 稳定,O(n^2)
  • 折半/二分插入排序
    • high<low,low为插入点
  • 希尔排序
    • 不稳定
  • 冒泡排序
    • 稳定的
  • 快速排序
    首先在r[1..n]中,确定一个r[i],经过比较和移动,将r[i]放到”中间”某个位置上,使得r[i]左边所有记录的关键字小于等于r[i].key,r[i]右边所有记录的关键字大于等于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。
    用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。
    • O(nlog2(n))
    • 不稳定
  • 选择排序
    • 比较次数均为n(n-1)/2
    • O(n^2)
    • 不稳定
  • 归并排序
    • 稳定的

      堆排序

  • 堆:(a1,a2,…n):ai>=a2i,ai>=a2i+1
  • 按顺序排列成完全二叉树
  • ai:树根值,a2i:左子树根值,a2i+1:右子树根值
  • 调整堆:将根与其左右子树的最大值交换,对其左右子树分别做相同操作
  • 创建堆:1.从下往上逐步调整堆至建成初始顶堆 2.从序号最大的结点开始将结点逐个与根节点交换后从根节点开始调整堆
  • 最坏:O(nlogn)

基数排序

  • n个数字,每个数字有效位为d,范围r
  • 时间复杂度O(d*(n+rd))

比较

  • 时间

    • O(nlog2n):快速排序、堆排序和归并排序,其中快速排序目前被认为是最快的一种排序方法。后两者之比较,在 n 值较大的情况下,归并排序较堆排序更快。
    • O(n2):插入排序、冒泡排序和选择排序,其中以插入排序最为常用,特别是对于已按关键字基本有序排列的记录序列尤为如此。选择排序过程中记录移动次数最少。
    • O(n):基数排序
  • 空间

    • O(1):所有的简单排序方法(包括:插入、冒泡和选择排序)和堆排序
    • O(log2(n)):快速排序
    • O(n):基数排序,归并排序