线性表

线性表是最基本、最简单、也是最常用的一种数据结构。下图整理线性表相关思维导图。

第二章 线性表

• 1.线性表的定义和基本操作
  • 定义（Linear List)
    • "逻辑结构"
    • 值得注意的特性
      • 数据元素同类型、有限、有序
    • 重要术语
      • 表长、空表
      • 表头、表尾
      • 前驱、后继
      • 数据元素的位序（从1开始）
        • 用数组实现线性表时需要注意审题
  • 基本操作
    • "运算"
    • 创销、增删改查（所有数据结构适用的记忆思路）
    • 判空、判长、打印输出（还可自己根据实际需求增加其他操作）
    • 其他值得注意的点
      • 理解什么时候要传入参数的引用"&"
      • 函数命名要有可读性
• 2.线性表的顺序表示
  • 定义
    • 存储结构
      • 逻辑上相邻的数据元素物理上也相邻
    • 实现方式
      • 静态分配
        • 使用"静态数组"实现
        • 大小一旦确定就无法改变
      • 动态分配
        • 使用"动态数组"实现
        • L.data = (ElemType *)malloc(sizeof(ElemType) * size);
        • 顺序表满时，可再用malloc动态拓展顺序表的最大容量
        • 需要将数据元素复制到新的存储区域，并用free函数释放原区域
    • 特点
      • 随机访问
        • 能在O（1）时间内找到第i个元素
      • 存储密度高
      • 拓展容量不方便
      • 插入、删除数据元素不方便
  • 基本操作的实现
    • 1.插入
      • ListInsert(&L,i,e)
        • 将元素e插入到L的第i个位置
        • 插入位置之后的元素都要后移
      • 时间复杂度
        • 最好O(1),最坏O(n),平均O(n)
    • 2.删除
      • ListDelete(&L,i,&e)
        • 将L的第i个元素删除，并用e返回
        • 删除位置之后的元素都要前移
      • 时间复杂度
        • 最好O(1),最坏O(n),平均O(n)
    • 代码要点
      • 代码中注意位序ⅰ和数组下标的区别
      • 算法要有健壮性，注意判断ⅰ的合法性
      • 跨考同学注意：移动元素时，从靠前的元素开始？还是从表尾元素开始？
      • 分析代码，理解为什么有的参数需要加“&”引用
    • 3.查找
      • 按位查找
        • GetElem(L,i)
          • 获取表L中第个位置的元素的值
          • 用数组下标即可得到第i个元素L.data[i-1]
        • 时间复杂度
          • 最好/最坏/平均时间复杂度都是O(1)
      • 按值查找
        • LocateElem(L,e)
          • 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
          • 从第一个元素开始依次往后检索
        • 时间复杂度
          • 最好O(1):目标元素在第一个位置
          • 最坏O(n):目标元素在最后一个位置
          • 平均O(n):目标元素在每个位置的概率相同
• 3.线性表的链式表示