数据结构

这是一篇有关数据结构的思维导图，从数组、链表、树、堆、队列等方面进行了概述和分析，需要的，可以收藏。

数据结构

• 数组（Array）
  • 整型数组
  • 字符型数组
  • 浮点型数组
  • 指针数组
  • 结构数组
• 栈（Stack）
  • 后进先出
• 链表（Linked List）
  • 双链表
    • 插入操作
      • s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;
    • 删除操作
      • p->next=q->next;q->next->prior=p;free(q);
  • 循环链表
    • 循环单链表
      • L->next == L;
    • 循环双链表
      • L->next==L;l->prior==L;
  • 静态链表
  • 顺序表与链表的比较
    • 存取方式
      • 单链表
        • 只能顺序存储
      • 顺序表
        • 可以通过计算得到相应的数据元素地址从而达到随机存取
    • 逻辑结构、物理结构
      • 单链表
        • 数据元素存放位置可能相邻可能不相邻
      • 顺序表
        • 一定相邻
    • 基本操作
      • 单链表
        • 插入
          • 修改指针即可
        • 删除
          • 修改结点指针
        • 查找
          • 按值查找
            • 依次遍历，O(n)
          • 按序号查找
            • 依次遍历
      • 顺序表
        • 插入
          • 依次向后移位
        • 删除
          • 依次向前移动
        • 查找
          • 按值查找
            • 依次遍历，O(n)
          • 按序号查找
            • 数组下标直接查找
    • 内存空间
      • 顺序存储
        • 静态分配
          • 预分配空间太大则会造成浪费
          • 预分配空间太小则会造成溢出
        • 动态分配
          • 不会溢出
          • 扩充时需要大量移动元素，操作效率低
      • 链式存储
        • 在需要时分配空间
        • 高校方便
        • 指针要使用额外空间
  • 单链表
  • 顺序表
• 图（Graph）
  • 有向图
    • 图的每条边都规定一个方向
      • 入度
        • 从一个顶点出发的边数
      • 出度
        • 指向一个顶点的边数
  • 无向图
    • 边没有方向的图称为无向图
  • 有权图
    • 图中各边都有各自的权重
  • 无权图
    • 图的边没有权重或者权重都一样
  • 连通图
    • 图中任意两点都是连同的
  • 图的存储
    • 邻接矩阵
    • 邻接表
  • 图的遍历
    • 深度优先搜索
    • 广度优先搜索
• 散列表（Hash）
• 队列（Queue）
• 树（Tree）
• 堆（Heap）
• 最小路径
  • 无权图
    • 寻找边的最小的路径
  • 给定起点
    • 单源最短路径
  • 起点不确定
    • 多源最短路径