线性表

这是一个线性表的思维导图，从顺序表示、链式表示这两点展开阐述，总结全面，希望整理的内容对你有帮助哦！

2. 线性表

• 顺序表示
  • 逻辑结构：线性结构
  • 存储结构：顺序存储
    • 静态分配
    • 动态分配
    • 静态和动态的区别首先在于存储类型的描述不同，初始动态分配语句为：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
  • 基本操作的实现
    • 插入操作
      • 注意要先判断输入的i是否有效和存储空间是否有空余，元素后移和插入完成后，不要忘了将表长length加1
        • i表示的是第几个元素，与数组下标是有区别的，i等于数组下标加1
    • 删除操作
      • 同样要注意判断输入的i是否有效，删除和前移完成后，不要忘了将表长length减1
    • 按值查找
    • 按位查找
    • 最好时间复杂度都是O(1)，最坏时间复杂度都是O(n)，平均时间复杂度都是O(n)
• 链式表示
  • 逻辑结构：线性结构
  • 存储结构：链式存储
    • 单链表
      • 结点类型描述
    • 双链表
      • 结点类型描述
    • 循环链表
      • 结点类型描述
        • 循环单链表
        • 循环双链表
    • 静态链表
      • 结点类型描述
  • 基本操作的实现
    • 单链表
      • 带头结点
        • 建立单链表
          • 头插法
            • 注意插入的时候指针赋值的顺序（先瞻前后顾后）
          • 尾插法
            • 加入一个尾指针，每次插入操作的结束都要将插入结点指针赋给尾指针
        • 按序查找
        • 按值查找
        • 插入结点
          • 后插
            • 先通过按序查找GetElem(L，i-1)查找到插入位置的前一个结点，然后再进行结点指针赋值
          • 前插
            • 先直接进行后插操作，然后再更改前后的数据（偷天换日）
        • 删除结点
          • 删除最后一个结点时，需要将其前驱结点的指针指向NULL
          • 删除第i个结点
            • 先通过按序查找GetElem(L，i-1)查找到插入位置的前一个结点，通过结点指针赋值进行逻辑上的删除后在进行物理结构上的删除
          • 删除某个给定的结点
            • 可转化为：交换该结点和后继结点的值，然后删除后继结点（省去了查找前驱结点的时间）
        • 求表长
          • 遍历链表
      • 不带头结点
    • 双链表
      • 插入操作
        • 注意结点指针赋值的顺序
      • 删除操作
        • 瞻前顾后原则，别忘了释放结被删除的结点指针空间
    • 循环链表
      • 循环单链表
        • 若设立的尾指针为r，那么r->next就是头指针
      • 循环双链表
    • 静态链表
      • 指针与其他链表的指针不同，这里的指针存放的地址为下一个元素的数组下标，这样的指针又称为游标
• 逻辑结构为线性结构，可以用顺序存储结构或链式存储结构来实现