数据结构

数据结构思维导图如下，供大家参考借鉴。

数据结构

• 线性表
• 树
  • 线索二叉树
  • 哈夫曼树
• 图
  • 1. 基本概念
    • I. 完全图
      • 无向完全图
        • 任意两点之间都有一条边，整个图有n(n-1)/2条边。
      • 有向完全图
        • 任意一个顶点到其余点之间均有一条弧，即有n(n-1)条弧。
    • II. 连通图
      • 若无向图G中任意两点之间存在路径，则称G为连通图。
      • n个顶点无向连通图最少有n-1条边。
    • III. 强连通图
      • 若有向图中任意两点之间可以互相到达，则称为强连通图。
  • 2. 最小生成树
  • 3. 最短路径
    • Dijkstra算法
      • 计算某一顶点到其余各顶点的最短路径
      • 时间复杂度
        • O(n²)（邻接矩阵、邻接表）
• 排序
  • 1. 插入排序
    • I. 直接插入排序
    • II. 希尔排序
      • O(nlog2n)
  • 2. 交换排序
    • I. 冒泡排序
    • II. 快速排序
      • O(nlog2n)
  • 3. 选择排序
    • I. 直接选择排序
    • II. 堆排序
      • O(nlog2n)
  • 4. 基数排序
  • 5. 归并排序
    • O(nlog2n)
  • 6. 外部排序
  • 排序知识点小结
    • 时间复杂度
      • 快希nlog2n归堆
    • 空间复杂度
    • 稳定性
      • 情绪不稳定，快希选堆好朋友聊天
• 查找
• 数组与广义表
• 栈和队列