冀教网 - 河北教师网站 - 专注于冀教版课本资源

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 5|回复: 0

数据结构复习笔记

[复制链接]

4万

主题

4万

帖子

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
124631
发表于 2020-5-24 01:19 | 显示全部楼层 |阅读模式
数据结构

简单地梳理一下数据结构课程的主要内容
目录

绪论


  • 数据结构三要素

    • 逻辑结构

      • 线性结构:一般线性结构、栈、队列、数组、广义表
      • 非线性结构:集合、树形结构、图状结构

    • 存储(物理)结构

      • 顺序存储
      • 链式存储
      • 索引存储
      • 散列存储

    • 数据的运算

  • 算法评估

    • 时间复杂度:基本运算的频度
    • 空间复杂度

线性表


  • 顺序存储:顺序表
  • 链式存储:

    • 单链表(指针)
    • 双链表(指针)
    • 循环链表(指针)
    • 静态链表(借助数组实现)

顺序表


  • 定义
  • 基本操作

    • 插入:平均移动 n/2 复杂度O(n)
    • 删除:好1 坏n 平均 (n-1)/2
    • 查找:平均 (n+1)/2

  • 常考问题:

    • 就地逆置
    • 扫描的同时移动
    • 两表归并
    • 二分查找
    • 分区间反转

链表


  • 定义:空间分配、头结点
  • 基本单链表

    • 建表:头插法、尾插法
    • 插入、删除
    • 查找:按序号,按值

  • 双链表:前后双指针
  • 循环链表:头尾相连
  • 静态链表 数组,每个元素包含当前值和下一个元素下标
栈和队列


  • 操作受限线性表

    • 栈:顺序栈、链栈、共享栈
    • 队列:循环队列、链式队列、双端队列

  • 推广:

    • 一维数组
    • 多维数组:压缩存储、稀疏矩阵
    • 广义表




  • 定义:栈顶、栈底、空栈
  • 基本操作:初始化、判空、进出、取顶、销毁
  • 顺序栈:数组、栈顶指针
  • 共享栈:仅两个栈顶指针相邻时满,降低上溢发生的概率
  • 链栈:不存在上溢
队列


  • 定义:队头、队尾
  • 基本操作:初始化、判空、出入、读队头
  • 具体实现

    • 顺序存储:假溢出
    • 循环队列:顺序+取模
    • 链式存储
    • 双端队列:输入受限、输出受限 两端可以X仅一端可以Y

栈和队列应用


  • 括号匹配
  • 表达式求值:前缀 中缀 后缀转换
  • 递归
  • 合法序列
  • 回文 字符串中心对称
  • 判空 满 top=0 or -1两种情况
  • 括号匹配
  • 层次遍历
数组、矩阵


  • 数组:行优先、列优先
  • 压损存储:

    • 对称矩阵
    • 三角矩阵
    • 三对角矩阵
    • 稀疏矩阵:三元组




  • 定义:字符组成的有限序列
  • 存储:定长、堆分配、块链存储
  • 基本操作:赋值、复制、判空、比较、连接....
  • 模式匹配:

    • 暴力匹配法
    • KMP算法 next数组求解

树和二叉树

树的基本概念


  • 根节点,前驱节点,后继结点,
  • 双亲结点,孩子结点,子孙节点,祖先结点,
  • 分支节点,叶子结点
  • 层次,深度,高度
  • 有序树,无序树(左右结点有无区分)
  • 路径,路径长度,带权路径长度(所有节点)
  • 森林
  • 性质

    • 结点数(n) = 结点的度数(i x ni) + 1
    • 度为m的树i层上最多 m^(i-1)个结点
    • 高度为h的m叉树至多有(m^h -1)/(m-1)个结点

二叉树


  • 定义
  • 特殊的二叉树

    • 满二叉树:树中每层含最多结点
    • 完全二叉树:i森林:先转成二叉树森林,再转树森林

  • 树和森林的遍历



      • 先根遍历  该树对应的二叉树先序遍历
      • 后根遍历  该树对应的二叉树层次遍历

    • 森林

      • 先序遍历
      • 中序遍历


树的应用


  • 并查集,操作:并,查,初始化,常用双亲表示法+数组
  • 二叉排序树

    • 定义, 中序遍历为递增有序序列
    • 查找,取决于树形
    • 插入,构造,删除

  • 平衡二叉树

    • 定义
    • 插入,调整 LL,RR,LR,RL
    • 查找,平均logn

  • 哈夫曼树、哈夫曼编码

    • 树的带权路径长度 = 所有叶节点带权路径长度之和
    • 使得 ↑ 最小的树
    • 构造:小的相结合
    • 二进制编码:树根开始左0 右1,前缀编码




  • 定义,顶点集V,边集E
  • 有向图、无向图
  • 简单图,多重图:重复边,回到自身的边
  • 完全图:任意两个结点之间存在边

    • n顶点无向 n(n-1)/2
    • 有向 n(n-1)

  • 子图
  • 连通图,连通分量
  • 强连通图,强连通分量: 有向图
  • 生成树,生成森林:包含所有顶点的极小连通子图;多个子图组成森林
  • 顶点的度,入度,出度
  • 边的权
  • 稠密图,稀疏图
  • 路径,路径长,贿赂
存储结构


  • 邻接矩阵:

    • 顶点表,边表(邻接矩阵) N*N
    • 适合存储稠密图

  • 邻接表法:

    • 顶点表:data,firstarc  第一个出边
    • 边表:adjvex, nextarc  邻接点,下一边
    • 适合存储稀疏图

  • 十字链表法

    • 有向图适用
    • 顶点结点  出边链,入边链
    • 弧结点 头,尾,下一指同头的弧,下一条指同尾的弧

  • 邻接多重表

    • 无向图
    • 与十字链表类似  顶点结点仅1个边链

遍历


  • 深度优先搜索 DFS

    • 递归 栈空间 O(V)
    • 邻接表 O(E + V)
    • 邻接矩阵 O(V^2) 查早每个顶点的邻接结点
    • 类似二叉树先序遍历

  • 广度优先搜索 BFS

    • 辅助队列 空间 O(V)最坏
    • 邻接表 O(V + E)
    • 邻接矩阵 O(V^2)

  • 图的遍历与连通性

    • 无向图:连通则一次遍历到所有点
    • 有向图:仅能判断是否强连通

应用


  • 最小生成树

    • 权值之和最小,不唯一
    • Prim:选顶点开始,依次添加距离S集合最近的S外结点  类似dijkstra; 适合稠密图 O(V^2)
    • Kruskal:依次选不构成回路的最小边,添加进集合S;适合稀疏图 O(ElogE)

  • 最短路径

    • Dijkstra:

      • 单源最短路径
      • 依次添加距离源点最近的结点,更新源点到其他各点的最短长度
      • path数组记录前驱节点用于溯源
      • 稀疏图 O(V^2)

    • Floyd:

      • 计算各顶点间的最短路径;
      • 方阵序列,依次在路径中加入新点,更新各点距离
      • 用辅助矩阵path记录路径
      • 稠密图 O(V^3) 比V次dijkstra高效 加上的额外因子小


  • 关键路径

    • AOE网
    • 关键路径、关键活动  (减少这些时间可加快整体速度)
    • 事件V 最早最迟发生时间
    • 活动E 最早最迟开始时间

  • 拓扑排序

    • 有向无环图 DAG图
    • AOV网  顶点活动 边关系 先后关系
    • 拓扑排序产生序列依次消解
    • 可判断是否有环

查找

评价指标:平均查找长度ASL 成功和失败
线性结构


  • 顺序查找

    • 哨兵
    • 成功 (n+1)/2, 失败 n + 1
    • 有序时,可降低失败的平均查找长度 n/2 + n/(n+1)

  • 折半查找

    • 有序顺序表
    • low,high,mid
    • 成功 log(n+1) - 1
    • 失败看具体情况计算ASL

  • 分块查找

    • 顺序查找+折半查找
    • 块间有序,块内无序
    • n 分 b块 每块s
    • s = √n 时候中最高效

树形结构(略)


  • B树
  • B+树
散列结构


  • 散列函数,散列表
  • 散列函数构造

    • 直接定址法
    • 除留余数法
    • 数字分析法
    • 平方取余法
    • 折叠法

  • 冲突处理

    • 开放定址法:线性探测、平方探测法、再散列法
    • 拉链法

  • 性能分析 装填因子:记录数/散列表长度
排序


  • 排序的稳定性:相等大的元素排序后的相对位置变化与否
  • 衡量标准:时空复杂度
算法描述


  • 内部排序

    • 插入排序

      • 直接插入:有序|无序 两个区域,无序区域元素直接插入有序区域,边判断边移动
      • 折半插入:在直接插入的基础上通过折半查找插入位置,找到位置后统一移动元素
      • 希尔排序:用步长将表分为几个子表,在子表内直接插入排序,缩小步长继续排序 e.g. 步长 n/2, n/2/2

    • 交换排序

      • 冒泡排序:从后往前,两两比较交换,一趟排序没有交换即完成。
      • 快速排序:划分操作(左右比较向中移动找枢轴),一次确定一个元素的最终位置,左右递归排序。时间效率与是否平均划分有关。

    • 选择排序

      • 简单选择排序:每一趟排序选取一个无序区域最小元素和无序区第一个元素交换
      • 堆排序:大根堆小根堆,

        • 建堆 从最后一个有孩子的结点开始向上调整O(n)
        • 删除 头尾交换,向下调整
        • 插入 插入末端向上调整
        • 排序 建堆 进行n-1次删除操作 O(n) + (n-1) * O(logn) O(nlogn)


    • 归并排序:由小到大前后两个子表归并
    • 基数排序:多次分配、收集

  • 外部排序:多路归并排序
排序算法的比较

算法名时间复杂度空间复杂度稳定性表的条件备注直接插入排序好O(n); 坏,平均O(n^2)O(1)稳定希尔排序O(n^3/2)O(1)不稳定仅顺序存储冒泡排序好O(n); 坏,平均O(n^2)O(1)稳定有序子序列全局有序快速排序坏O(n^2); 好,平均O(nlogn)O(logn)不稳定皆可,实现有差异坏:基本有序简单选择排序O(n^2)O(1)不稳定堆排序O(nlogn)O(1)不稳定归并排序O(nlogn)O(n)稳定基数排序O(d+r)O(r)稳定d:分配数 r:队列数
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|冀教网 - 河北教师网站 - 专注于冀教版课本资源  

GMT+8, 2020-5-31 23:43 , Processed in 0.304195 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表