第二章-线性表(1)

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表

• 定义
  • 逻辑结构
  • 线性表是具有相同数据类型的n（n>0）个数据元素的有限序列，其中n为表长，当n=0时线 性表是一个空表。若用L命名线性表，则其一般表示为 L=(a1, a2, ai,ai+1，…… , an)
    • 位序是从1开始的，数组的下标从0开始
    • ai,是线性表中的 “第i个〞元素线性表中的位序 a1是表头元素；an是表尾元素。 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅 有一个直接后继。
• 基本操作
  • 运算
  • 初始化
  • 销毁
  • 插入
  • 删除
  • “增删”
  • 按值查找
  • 按位查找
  • “改查”
  • “&”符号表示引用，对参数修改的值可以输出。
• 存储/物理结构
  • 顺序表（顺序存储）
    • 定义
      • 顺序表--用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
      • 静态分配
        • 使用静态数组，大小一旦确定就无法改变
          • 例子
      • 动态分配
        • 使用动态数组实现
        • L.data=(ElemType*)malloc(sizeof(ElemType)*size);
        • • 例子
        • 顺序表存满时，可再用malloc动态拓展顺序表的最大容量，需要将数据元素复制到新的存储区域，并用free函数释放原区域。
      • 特点
        • 1.随机访问：可以在O（1）时间内找到第i个元素
        • 2.存储密度高，每个节点只存储数据元素
        • 3.拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
        • 4.插入、删除操作不方便，需要移动大量的元素
    • 基本操作
      • 插入
        • Listlnsert (&L,i,e):插入操作。在表L中的第i个位置（位序）上插入指定元素e。
        • • 基于静态分配
        • 插入操作时间复杂度分析
          • 最好情况：i=n+1，新元素加到表尾，循环0次，最好的时间复杂度=O（1）； 最坏情况：i=1，新元素加到表头，循环n次，最坏的时间复杂度=O（n）； 平均时间复杂度：O（n/2）可化为O（n）
      • 删除
        • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置元素，并用e返回删除元素的值。
        • 删除操作时间复杂度分析
          • 最好情况：i=n，删除表尾元素，循环0次，最好的时间复杂度=O（1）； 最坏情况：i=1，删除表头元素，循环n-1次，最坏的时间复杂度=O（n）； 平均时间复杂度=O（n）
      • 按位查找
        • GetElem(L,i):按位查找操作。获取表L中的第i个位置的元素的值。
          • 用数组下标即可得到第i个元素L.data[i-1]
        • 时间复杂度分析
          • 三种复杂度都是O(1)
            • 由于顺序表中的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素（随机存放的特性）
      • 按值查找
        • LocateElem(L,e):按值查找操作。在表L中查找具体给定关键字值的元素。
          • 在顺序表Ｌ中查找第一个元素值等于e的元素，并返回其位序，从第一个元素开始依次往后检索。
        • C语言中，结构体的比较不可以直接用“==”，需要依次对比各个分量来判断两个结构体是否相等
          • 《数据结构》初试中，手写代码可以直接用“==”，无论ElemType是基本数据类型还是结构类型。
          • 两种结构体比较方法
        • 时间复杂度分析
          • 最好：目标元素在表头，循环1次，最好时间复杂度=O（1） 最坏：目标元素在表尾，循环n次，最坏时间复杂度=O（n） 平均时间复杂度=O（n）
  • 链表（链式存储）
    • 单链表
      • 定义
        • 什么是单链表
        • 用代码定义一个单链表
          • 注意typedef关键字的用法和“LinkList”以及“LNode”
        • 两种实现
          • 带头结点
            • 空表判断：L==NULL。写代码方便
          • 不带头结点
            • 空表判断：L->next==NULL。写代码更方便
      • 基本操作
        • 插入
          • 按位序插入
            • 带头结点
              • ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
                • 找到第i-1个结点将新结点插入其后。
                • 要先让S结点的指针指向a1结点，再让p结点的指针指向S结点，这个顺序不可以错
            • 不带头结点
          • 指定结点的后插操作
            • 封装的好处，代码变得很简洁
          • 指定结点的前插操作
        • 删除
          • 按位序删除
            • ListDelete（&L，i，&e）：删除操作。删除表L中的第i位置的元素，并用e返回删除元素的值。
          • 指定结点的删除
        • 查找
          • 按位查找
            • 注意与“顺序表”对比，单链表不具备“随机访问”的特性，只能依次扫描。
            • GetElem(L,i):按位查找。获取表中第i个位置的元素的值。
              • 判断按位查找操作是否执行成功时，只需要判定一下指针p是否为NULL即可。平均时间复杂度为O（n）
          • 按值查找
            • LocateElem(L,e):按值查找。在表中查找具有给定关键字值的元素。
          • 求单链表的长度
          • 封装的好处：避免重复代码，简介，易维护。
        • 关键
          • 1.三种基本操作的时间复杂度都是O(n) 2.如何写循环扫描各个结点的代码逻辑 3.注意边界条件的处理
      • 建立
        • 核心就是初始化操作、指定结点的后插操作。
        • 头插法
          • 重要应用于链表的逆置
        • 尾插法
          • 注意设置一个指向表尾结点的指针
    • 双链表
      • 初始化
        • 头结点的prior、next、都指向NULL
      • 插入（后插）
        • 注意新插入结点、前驱结点、后继结点的指针修改。边界情况：新插入结点在最后一个位置，需特殊处理。
      • 删除（后删）
        • 注意删除结点的前驱结点、后继结点的指针修改。边界情况：如果被删除结点是最后一个数据结点，需特殊处理。
      • 遍历
        • 从一个给定结点开始，后向遍历、前向遍历的实现（循环的终止条件）。链表不具备随机存取特性，查找操作只能通过顺序遍历实现
    • 循环链表
      • 循环单链表
        • 区别： 单链表：表尾结点的next指针指向NULL，从一个结点出发只能找到后续的各个结点。 循环单链表：表尾结点的next指针指向头结点，从一个结点出发可以找到其他任何一个结点。
      • 循环双链表
        • 区别： 双链表：表头结点的prior指向NULL；表尾结点的next指向NULL。 循环双链表：表头结点的prior指向表尾结点；表尾结点的next指向头结点。
        • 插入
        • 删除
        • 总结
    • 静态链表
      • 什么是静态链表
        • 用数组的方式实现的链表
          • 优点：增、删操作不需要大量移动元素 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变。 适用场景：1.不支持指针的低级语言；2.数据元素数量固定不变的场景。
      • 如何定义一个静态链表
      • 简述基本操作的实现
  • 顺序表与链表的比较
    • 逻辑结构
      • 都属于线性表，都是线性结构。
    • 存储结构
      • 顺序表优点：支持随机存取、存储密度高； 缺点：大片连续空间分配不方便，改变容量不方便。 链表优点：离散的小空间分配方便，改变容量方便。 缺点：不可随机存取，存储密度低。
    • 基本操作
      • 创
      • 销
      • 增、删
      • 查