数据结构_2线性表

参考王道计算机考研《数据结构》课程，自主进行知识点归纳总结，掌握上述术知识要点，轻松高分通过考试！

线性表

• 定义
  • 特点
    • 有序、数据元素同类型、有限
  • 重要术语
    • 前驱、后继
      • 反映数据元素之间一对一的关系
    • 位序
      • 数据元素在线性表(逻辑结构)中的位置(从1开始)
      • 用数组实现线性表时需注意审题（数组下标从0开始）
    • 随机存取(直接访问)
      • 直接可对第N个数据操作
      • 存取第n个元素不需要访问前n-1个元素(数组)
        • 根据起始地址加上元素的序号就可以很方便地访问任一个元素
    • 顺序存取
      • 存取第n个数据，必须先访问前n-1个元素（链表）
    • 顺序存储
      • 逻辑上相邻的元素物理位置上也相邻
• 基本操作
  • 主要
    • 创销、增删改查
  • 其他
    • 判空、判长、打印输出
      • 还可以根据实际需求增加其他操作
  • 注意
    • 函数命令要有可读性
    • 理解什么时候要传入参数为指针的指针（需要带回返回值）
• 单链表
  • 定义
    • 用"链式存储"（存储结构）实现了"线性结构"(逻辑结构)
    • 一个结点存储一个数据元素
    • 各结点间的先后关系用一个指针表示
  • 数据对象的定义
    • LNode，LinkList
      • LNode * 强调是一个结点 LinkList 强调是一个链表
  • 基本操作
    • 初始化
      • 不带头结点（写代码不方便）
        • 头结点不存放数据，只是为了操作方便
      • 带头结点（写代码方便）
    • 空链表的判断
      • 不带头结点
        • L == NULL
      • 带头结点
        • L->next == NULL
    • 插入
      • 按位序插入（注意审题）
        • 带头结点
        • 不带头结点
      • 指定结点的后插操作
      • 制定结点的前插操作
    • 删除
      • 按位序删除
      • 指定结点的删除
        • 有坑：指定结点是最后一个结点时，需要特殊处理(只能从表头开始依次寻找p的前驱，时间复杂度O(n))
    • 查找
      • 按位查找
      • 按值查找
      • 求单链表长度
      • 重点
        • 时间复杂度O(n)
        • 边界条件的处理
• 双链表
  • 初始化
    • 头结点的prior(永远指向NULL)和next都指向NULL
  • 基本操作
    • 插入(后插)
      • 注意新插入结点、前驱结点、后继结点的指针修改
      • 边界条件：新插入结点在最后一个位置，需要特殊处理
    • 删除（后删）
      • 注意删除结点的前驱结点、后继结点的指针修改
      • 边界条件：被删除结点在最后一个位置，需要特殊处理
    • 遍历
      • 给定结点开始,后向(前向)遍历实现(循环终止条件(跳过头结点?))
      • 链表不具备随机存取特性，查找操作只能通过顺序遍历实现
• 循环链表
  • 循环单链表
    • 空表
      • 
    • 非空表
      • 
  • 循环双链表
    • 空表
      • 
    • 非空表
      • 
  • 代码问题
    • 如何判空
    • 如何判断结点p是否是表尾/表头结点（后向/前向遍历的实现核心）
    • 如何在表头、表中、表尾插入/删除一个结点（边界条件）
• 总结
  • 顺序表OR链表
    • 
    • 顺序表
      • 表长可预估、查询（搜索）操作较多
    • 链表
      • 表长难以预估、经常要增加/删除元素
    • 注意
      • 增删操作两者均为O(n)
        • 顺序表
          • 开销主要来源于移动元素
        • 链表
          • 开销主要来源于查找元素
        • 查找元素时间代价比移动数据元素(数据元素很大,移动代价高)好
  • 顺序表OR链表哪个更好？
    • 逻辑结构
      • 二者都是线性结构，都属于线性表
    • 存储结构不同
      • 顺序表（顺序存储）
        • 优缺点
        • 特点
      • 链表（链式存储）
        • 优缺点
        • 特点
    • 基本操作的实现（分情况讨论）
      • 初始化
      • 插入数据元素
      • 删除数据元素
      • 查找数据元素
      • 由于采用不同的存储结构，因此基本实现效率也不同
• 静态链表（少考）
  • 用数组的方式实现链表
  • 优点
    • 增、删操作不需要移动大量元素(修改游标即可)
  • 缺点
    • 不能随机存取(只能从头结点开始依次往后查找)
    • 容量固定不可变
  • 适用场景
    • 不支持指针的低级语言（利用单链表的思想）
    • 数据元素数量固定不变的场景（如操作系统的文件分配表FAT）
• 顺序表
  • 存储与逻辑
    • 存储结构
      • 逻辑上相邻的数据元素在物理位置上也相邻
    • 逻辑关系
      • 元素之间的逻辑关系由存储单元的邻接关系体现
  • 实现方式
    • 静态分配
      • 实现方法
        • 静态数组（普通数组）
      • 大小一旦确定就无法改变
    • 动态分配
      • 实现方法
        • 动态数组（ 动态分配的存储空间，利用指针对其操作）
      • 核心函数
        • L.data = (ElemType *)malloc(sizeof(ElemType)*size);
      • 动态
        • 顺序表存满时，可再用malloc动态扩展顺序表的最大容量
        • 需要将数据元素复制到新的存储区域，并用free函数释放原区域
  • 基本操作
    • 插入
      • ListInsert(&L,i,e)
        • 将元素e插入到L的第i个位置（位序）
      • 实现
        • 元素的移动
          • 插入位置后的元素都要后移（从最后开始）
        • 时间复杂度P16
          • 最好O(1)、最坏O(n)、平均O(n)
    • 删除
      • ListDelete(&l,i,&e)
        • 将L的第i个元素删除，并用e返回
      • 实现
        • 元素的移动
          • 删除位置后的元素都要前移（从删除位置开始）
        • 时间复杂度P17
          • 最好O(1)、最坏O(n)、平均O(n)
    • 查找
      • 按位查找
        • GetElem(L,i)
          • 理解：获取表L中第i个位置(位序)的元素的值
          • 方法：用数组下标即可得到第i个元素L.data[i-1]
          • 区分
        • 时间复杂度
          • 最好/最坏/平均时间复杂度都是O(1)
      • 按值查找
        • LocateElem(L,e)
          • 理解：在顺序表L中查找第一个元素值等于e的元素，并返回其位序
          • 方法：从第一个元素开始依次往后检索
        • 时间复杂度
          • 最好O(1)：目标元素在第一个位置
          • 最坏O(n):目标元素在最后一个位置
          • 平均O(n)：目标元素在每个位置的概率相同（求数学期望）
    • 代码要点
      • 代码中注意位序i和数组下表的区别
      • 算法要有健壮性，判断i的合法性
        • 表满、比表头小、比表尾大
      • 移动元素从表尾元素开始？从靠前的位置开始？
      • 理解函数什么时候需要传入变量的指针
        • 变量的值需要带回的时候，则需要传入变量的指针
  • 特点
    • 随机访问
      • O(1)时间内找到第i个元素
        • 数据元素是连续存储的，所以只要知道起始元素的位置，其他位置的元素很容易获得 代码实现 data[i-1](静态动态都一样)
    • 存储密度高
      • 数据元素存储在连续的物理位置
      • 每个结点只存储数据元素
    • 扩展容量不方便(需要移动整个表的元素到新的表)
    • 插入删除操作不方便