数据结构

数据结构是计算机考研学习的一个重点，我从“概述、线性表、树、图、查找、排序”等方面进行了一个重点梳理，不用再害怕数据结构啦。

数据结构

• 概述
  • 数据
    • 元素
    • 数据项
  • 时间复杂度
    • 区别logn，n，n^2,1
  • 空间复杂度
• 线性表
  • 顺序表
  • 链表
  • 受限线性表
    • 栈
      • 应用
        • 中序转后序
        • 后序求值
        • 中序转前序（前序求值）
    • 队列
      • 循环队列的实现
• 树
  • 基础概念
    • 度和节点关系
    • 满二叉树和完全二叉树
  • 树的相关算法
  • 树的线索化
  • 平衡二叉树
  • 赫夫曼树
• 图
  • 图的概念
  • 图的相关算法
  • 最小生成树
    • Prim
    • Kruskal
  • 最短路径
    • 迪杰特斯拉算法
    • 佛洛依德算法
  • 关键路径
• 查找
  • 查找概念
  • 折半查找
    • 判定树
  • b-树
    • 基本概念
      • 节点数为ceil（n/2）-1到n-1
      • 分支数为节点数加一
      • 根节点做少两个分支
  • b+树
    • 基本概念
      • 节点数为ceil（n/2）到n
      • 分支数等于节点数
      • 叶子节点有单链表连接而成
  • hash表
    • 平均查找成功长度
    • 平均查找失败长度
  • kmp
• 排序
  • 待完善
  • 各种排序对比