线性表-数据结构第2章

什么是静态链表：用数组的方式实现的链表、每个数据元素 4B，每个游标4B（每个结点共 8B）设起始地址为 addr。

第二章 线性表 数据结构 王道考研系列

• 定义（Linear List）
  • 值得注意的特性
    • 数据元素同类型、有限、有序
  • 重要的术语
    • n为表长、当n=0时为空表
    • 表头a₁、表尾aₙ
      • 注意：位序从1开始数组下标从0开始
    • 前驱、后继
      • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
    • 数据元素的位序aᵢ（从1开始）
  • “逻辑结构”
    • a₁→ a₂→ a₃→ a₄→ a₅
• 基本操作
  • InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
  • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
  • ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
  • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
  • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
  • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
  • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
  • 其他值得注意的点
    • ①对数据的操作（记忆思路） —— 创销、增删改查
    • ②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)
    • ③实际开发中，可根据实际需求定义其他的基本操作
    • ④函数名和参数的形式、命名都可改变
      • 函数命名要有可读性
    • 什么时候要传入参数的引用“&”
      • 对参数修改结果需要“带回来”
  • 从无到有
  • 增、删（"改"）
  • （“改”
  • 判空、判长、打印输出（还可以自己根据实际需求增加其它基本操作）
• 线性表的实现
  • 顺序存储
    • 顺序表
  • 链式存储
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表（借助数组实现）
    • 借助数组实现
  • 线性表的应用
• 链表
  • 单链表
    • 定义
      • 单链表
        • 用链式存储”（存储结构实现了“线性结构"(逻辑结构)）
        • 一个结点存储一个数据元素
        • 各结点间的先后关系用一个指针表示
        • 单链表：表尾结点的next指针指向 NULL
        • 单链表：从一个结点出发只能找到后续的各个结点
      • 用代码定义一个单链表
        • typedef struct LNode{
      • 两种实现
        • 不带头结点
          • 空表判断: L==NULL。写代码不方便
        • 带头结点
          • 空表判断:L->next==NULL。写代码更方便
      • 其他值得注意的点
        • typedef 关键字的用法
        • "LinkList”等价于“LNode *"
    • 基本操作
      • 插入
        • 按位序插入
          • 带头结点
            • 头结点可以看作“第0个”结点
            • 找到第 i-1 个结点，将新结点插入其后
          • 不带头结点
          • 如果不带头结点，则插入、删除第1个元素时，需要更改头指针L
        • 指定结点的后插操作
        • 指定结点的前插操作
          • 时间复杂度为O(1)
      • 删除
        • 按位序删除
          • 头结点可以看作“第0个”结点
          • 找到第 i-1 个结点，将其指针指向第i+1个结点，并释放第i个结点
          • 时间复杂度为O(n)
        • 指定结点的删除
          • 有坑:指定结点是最后一个结点时，需要特殊处理
      • 查找
        • 按位查找
          • 注意与"顺序表"对比
          • 单链表不具备"随机访问"的特性，只能依次扫描
          • 平均时间复杂度：O(n)
        • 按值查找
          • 平均时间复杂度：O(n)
        • 求单链表的长度
          • 时间复杂度：O(n)
        • Key
          • 三种基本操作的时间复杂度都是O(n)
          • 如何写循环扫描各个结点的代码逻辑
          • 注意边界条件的处理
      • 建立
        • 尾插法
          • 初始化单链表
          • 设置变量 length 记录链表长度
          • While 循环 { 每次取一个数据元素 e; ListInsert (L, length+1, e) 插到尾部; length++; }
          • 时间复杂度：O(n)
        • 头插法
          • 头插法建立单链表：
          • 初始化单链表
          • While 循环 { 每次取一个数据元素 e; InsertNextNode (L, e); }
        • 核心就是初始化操作、指定结点的后插操作
  • 双链表
    • 初始化
      • 头结点的prior,next都指向NULL
    • 插入（后插）
      • 注意新插入结点、前驱节点、后继结点的指针修改
      • 边界情况：新插入结点在最后一个位置，需特殊处理
    • 删除（后删）
      • 注意删除结点的前驱结点、后继结点的指针修改
      • 边界情况：如果被删除结点是最后一个数据结点，需特殊处理
    • 遍历
      • 从一个给定结点开始，后向遍历、前向遍历的实现（循环终止条件）
      • 链表不具备随机存取特性，查找操作只能通过顺序遍历实现
  • 循环链表
    • 循环单链表
      • 空表
      • 非空表
    • 循环双链表
      • 空表
      • 非空表
    • 代码问题
      • 如何判空
      • 如何判断结点p是否表尾/表头结点
      • 如何在表头、表中、表尾插入/删除一个结点
  • 静态链表
    • 什么是静态链表
      • 用数组的方式实现的链表
      • 分配一整片连续的内存空间，各个结点集中安置
      • 每个数据元素 4B，每个游标4B（每个结点共 8B）设起始地址为 addr
    • 如何定义一个静态链表
    • 简述基本操作的实现
      • 初始化
        • 把 a[0] 的 next 设为 -1
        • 把其他结点的 next 设为一个特殊值用来表示结点空闲，如 -2
      • 查找
        • 从头结点出发挨个往后遍历结点
      • 插入位序为 i 的结点
        • ①找到一个空的结点，存入数据元素
        • ②从头结点出发找到位序为 i-1 的结点
        • ③修改新结点的 next
        • ④修改 i-1 号结点的 next
      • 删除某个结点
        • ①从头结点出发找到前驱结点
        • ②修改前驱结点的游
        • ③被删除结点 next 设为 -2
    • 优缺点
      • 优点：增、删 操作不需要大量移动元素
      • 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
    • 适用场景：
      • ①不支持指针的低级语言
      • ②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）
• 顺序表
  • 定义（如何用代码实现）
    • 存储结构
      • 逻辑上相邻的数据元素物理上也相邻
  • 实现方式
    • 静态分配
      • 使用“静态数组”实现
      • 给各个数据元素分配连续的存储空间，大小为
      • 大小一旦确定就无法改变
    • 动态分配
      • 使用“动态数组”实现
      • L.data=（Elemtype *）malloc (sizeof(ElemType)*size);
      • 顺序表存满时，可再用malloc动态拓展顺序表的最大容量
      • 需要将数据元素复制到新的存储区域，并用free函数释放原区域
        • 缺点：时间开销大
  • 特点
    • ①随机访问，即可以在 O(1) 时间内找到第 i 个元素。
    • ②存储密度高，每个节点只存储数据元素
    • ③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
    • ④插入、删除操作不方便，需要移动大量元素
  • 基本操作
    • 插入
      • Listinser(&L,i,e)
        • 将元素e插入到L的第i个位置
      • 插入位置之后的元素都要后移
      • 时间复杂度
        • 最好O(1)、最坏O(n)、平均O(n)
    • 删除
      • ListDelete(&L,i,&e)
        • 将L的第i个元素删除，并用e返回
      • 删除位置之后的元素都要前移
      • 时间复杂度
        • 最好O(1)、最坏O(n)、平均O(n)
    • 代码要点
      • 代码中注意位序i和数组下表的区别
      • 算法要有健壮性，注意判断i和注意合法性
      • 移动元素时，从靠前的元素开始？还是从表尾元素开始？
      • 分析代码，理解为什么有的参数需要加“&”引用
        • 如果不加“&”，则被调用函数中处理的是参数数据的复制品
    • 按位查找
      • GetElem(L,i)
        • 获取表L中第i个位置的元素的值
        • 用数组小标可得到第i个元素L.data[i-1]
      • 时间复杂度
        • 最好/最坏/平均时间复杂度都是O(1)
    • 按值查找
      • LocateElem(L,e)
        • 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
        • 从第一个元素开始依次往后检索
      • 时间复杂度
        • 最好O(1)
          • 目标元素在第一个位置
        • 最坏O(n)
          • 目标元素在最后一个人位置
        • 平均O(n)
          • 目标元素在每个位置的概率相同
  • 顺序表
    • 定义（如何用代码实现）
      • 存储结构
        • 逻辑上相邻的数据元素物理上也相邻
    • 实现方式
      • 静态分配
        • 使用“静态数组”实现
        • 给各个数据元素分配连续的存储空间，大小为
        • 大小一旦确定就无法改变
      • 动态分配
        • 使用“动态数组”实现
        • L.data=（Elemtype *）malloc (sizeof(ElemType)*size);
        • 顺序表存满时，可再用malloc动态拓展顺序表的最大容量
        • 需要将数据元素复制到新的存储区域，并用free函数释放原区域
          • 缺点：时间开销大
    • 特点
      • ①随机访问，即可以在 O(1) 时间内找到第 i 个元素。
      • ②存储密度高，每个节点只存储数据元素
      • ③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
      • ④插入、删除操作不方便，需要移动大量元素
    • 基本操作
      • 插入
        • Listinser(&L,i,e)
          • 将元素e插入到L的第i个位置
        • 插入位置之后的元素都要后移
        • 时间复杂度
          • 最好O(1)、最坏O(n)、平均O(n)
      • 删除
        • ListDelete(&L,i,&e)
          • 将L的第i个元素删除，并用e返回
        • 删除位置之后的元素都要前移
        • 时间复杂度
          • 最好O(1)、最坏O(n)、平均O(n)
      • 代码要点
        • 代码中注意位序i和数组下表的区别
        • 算法要有健壮性，注意判断i和注意合法性
        • 移动元素时，从靠前的元素开始？还是从表尾元素开始？
        • 分析代码，理解为什么有的参数需要加“&”引用
          • 如果不加“&”，则被调用函数中处理的是参数数据的复制品
      • 按位查找
        • GetElem(L,i)
          • 获取表L中第i个位置的元素的值
          • 用数组小标可得到第i个元素L.data[i-1]
        • 时间复杂度
          • 最好/最坏/平均时间复杂度都是O(1)
      • 按值查找
        • LocateElem(L,e)
          • 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
          • 从第一个元素开始依次往后检索
        • 时间复杂度
          • 最好O(1)
            • 目标元素在第一个位置
          • 最坏O(n)
            • 目标元素在最后一个人位置
          • 平均O(n)
            • 目标元素在每个位置的概率相同
• 顺序表和链表的比较
  • 逻辑结构
    • 都属于线性表，都是线性结构
  • 物理结构/存储结构
    • 顺序表
      • 优点：支持随机存取、存储密度高
      • 缺点：大片连续空间分配不方便，改变容量不方便
    • 链表
      • 优点：离散的小空间分配方便，改变容量方便
      • 缺点：不可随机存取，存储密度低
  • 数据的运算/基本操作
    • 创
      • 顺序表
        • 需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；
      • 链表
        • 只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展
    • 销
      • 顺序表
        • 修改 Length = 0
      • 链表
        • 依次删除各个结点（free）
          • 静态分配：静态数组
          • 动态分配：动态数组（malloc、free）
    • 增/删
      • 顺序表
        • 插入/删除元素要将后续元素都后移/前移
        • 时间复杂度 O(n)，时间开销主要来自移动元素
        • 若数据元素很大，则移动的时间代价很高
      • 链表
        • 插入/删除元素只需修改指针即可
        • 时间复杂度 O(n)，时间开销主要来自查找目标元素
        • 查找元素的时间代价更低
    • 查
      • 顺序表
        • 按位查找：O(1)
        • 按值查找：O(n)
      • 链表
        • 按位查找：O(n)
        • 按值查找：O(n)
  • 如何抉择？
    • 表长难以预估、经常要增加/删除元素 ——链表
    • 表长可预估、查询（搜索）操作较多 ——顺序表