数据结构-线性表

这是一篇关于数据结构-线性表思维导图，包含线性表、栈和队列都是运算受限的线性表等。

线性结构

• 线性表
  • 定义：是逻辑结构，具有相同数据类型的n个数据元素的有限序列
  • 顺序存储
    • 顺序表（逻辑顺序和物理顺序相同）
      • 特点
        • 随机访问，查找方便
        • 存储密度高
        • 增删麻烦
        • 扩容麻烦（malloc会增加时间复杂度）
      • 实现方式
        • 静态分配
          • 定义一个定长数组，系统自动回收空间
        • 动态分配
          • 使用malloc、free函数（成对出现）
      • 基本操作
        • 插入
          • 最好O(1)，最坏O(n)，平均O(n)
        • 删除
          • 最好O(1)，最坏O(n)，平均O(n)
        • 查找
          • 按位查找
            • 最好/最坏/平均O(1)
          • 按值查找
            • 最好O(1)，最坏O(n)，平均O(n)
        • 主要的时间开销是来自移动元素
  • 链式存储
    • 链表（逻辑顺序和物理顺序不用相同）
      • 特点
        • 存储密度低
        • 插入删除方便
        • 存储灵活
      • 单链表
        • 建立（插入）
          • 头插法建立
            • O(n)
          • 尾插法建立
            • O(n)
        • 查找
          • 按值查找
            • O(n)
          • 按位查找
            • O(n)
        • 删除
          • O(n)
        • 求表长
          • 添加一个计数器即可
            • O(n)
      • 双链表
        • 插入
          • O(1)
        • 删除
          • O(1)
        • 不用像单链表一直遍历下去，可以直接找到前驱指针将其修改
        • 查找
          • O(n)
      • 循环链表
        • 循环单链表
          • 将头节点L指向尾部，这样在尾部操作的时间复杂度是O(n)
        • 循环双链表
      • 静态链表
        • 用数组实现的链表，游标表示数组下标
      • 主要的时间开销是来自移动元素，所以在处理实际问题中，链表插入/删除的效率高于顺序表
• 栈和队列都是运算受限的线性表
  • 栈
  • 队列