②线性表

24自用408数据结构，线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，n＝0为空表。

线性表

• 线性表的基本定义和操作
  • 定义
    • 线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，n＝0为空表。
    • 特点
      • 1| 表中元素的个数有限
      • 2| 表中元素具有逻辑上的顺序性
      • 3| 表中元素都是数据元素，每个元素都是单个元素
      • 4| 表中元素的数据类型都相同，即每个元素占着相同大小的存储空间
      • 5| 表中元素具有抽象性，只讨论逻辑间关系，而不考虑元素内容
    • 注意
      • 线性表是一种逻辑结构，表示一对一的相邻关系
      • 顺序表和链表是指存储结构
      • 位序(第几个)从1开始
      • 数组下标从0开始
  • 基本操作
    • InitList(&L):初始化表
    • Length(L):求表长
    • LocateElem(L,e):按值查找操作
    • GetElem(L,i):按位查找
    • ListInsert(&L,I,e):插入操作
    • ListDelete(&L,I,&e):删除操作
    • PrintList(L):顺序输出表中内容
    • Empty(L):判空操作
    • DestroyList(&L):销毁操作
• 线性表的顺序表示
  • 定义
    • 线性表的顺序存储又叫顺序表
    • 是用一组地址连续的存储单元依次存储线性表中的数据元素，从而逻辑上相邻的两个元素，物理位置上也相邻
    • 一维数组空间分配
      • 静态分配
        • 数组的大小和空间事先已经固定，一旦空间占满，再加入新元素将会产生溢出，进而程序崩溃
      • 动态分配
        • 存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另开辟一块更大的存储空间，用以替换原来的存储空间
        • L.data＝(ElemType*)malloc(sizeof(ElemType)*InitSize);
        • 动态分配并不是链式存储，它同样属于顺序存储，物理结构没有发生变化，依然支持随机存取
    • 注意特点
      • 随机访问。即通过首地址和元素序号可在时间O(1)内找到指定元素
        • LOC(A)+(i-1)×sizeof(ElemType) i为第i个，是位序
      • 存储密度高。每个结点只存储数据元素
      • 逻辑上相邻物理上也相邻，所以插入和删除需要移动大量元素，拓展容量不方便
  • 基本操作实现
    • 插入操作
      • 因为表中元素物理位置相邻，所以在位置i上插入元素，需要将第i个元素及之后的元素后移
      • 注意
        • 判断i的范围是否有效，1＜i＜L.length+1
        • 判断存储空间是否已满，L.length＜Maxsize
        • 插入后，线性表长度+1
      • 实际情况
        • 最好情况:在表尾插入，时间复杂度为O(1)
        • 最坏情况:在表头插入，时间复杂度为O(n)
        • 平均情况
          • 平均移动次数为
            • 
              • 
      • 时间复杂度为O(n)
    • 删除操作
      • 将第i个位置之后的元素前移
      • 注意
        • 判断i的范围是否有效，1＜i＜L.length+1
        • 删除后，线性表长度-1
      • 实际情况
        • 最好情况 :在表尾删除，时间复杂度为O(1)
        • 最坏情况:在表头删除，时间复杂度为O(n)
        • 平均情况
          • 平均移动次数为
            • 
              • 
      • 时间复杂度为O(n)
    • 按值查找
      • 查找第一个元素值等于e的元素，返回其位序
      • 注意
        • 下标为i的元素值为e，返回其位序i+1
      • 实际情况
        • 最好情况 :在表头找到，时间复杂度为O(1)
        • 最坏情况:在表尾找到，时间复杂度为O(n)
        • 平均情况
          • 平均移动次数为
            • 
              • 
      • 时间复杂度为O(n)
• 线性表的链式表示
  • 单链表
    • 定义
      • 线性表的链式存储称为单链表。使用一组任意的存储单元来存储数据元素
      • 非随机存取
      • 只能从头开始遍历
      • 引入头节点两个优点
        • 方便操作
        • 判空
    • 基本操作实现
      • 建立
        • 头插法
          • 将新结点插入到当前链表的表头
          • 时间复杂度：O(1) 空间复杂度：O(n)
          • 采用头插法建立链表时，读入的数据的顺序与链表中的元素是相反的 用于链表逆置
        • 尾插法
          • 将新结点插入到当前链表的表尾
          • 需设置表尾指针始终指向表尾
          • 时间复杂度：O(1) 空间复杂度：O(n)
      • 查找
        • 按序号查找
        • 按值查找
      • 插入
        • 
        • 时间复杂度：O(n)
      • 删除
        • 先找到删除结点，更改前驱指针
      • 插入和删除的优化:填充法
  • 双链表
    • 定义
      • 有两个指针prior和next分别指向前驱和后继
    • 插入
      • 
    • 删除
      • 
  • 循环链表
    • 循环单链表
      • 表中最后一个结点的指针不是null，而改为头结点
      • 可以从任何一个结点遍历整个链表
      • 判空：尾结点指针＝头结点指针
    • 循环双链表
      • 尾结点rear指向头结点，头结点的prior指针指向表尾
      • 判空：头结点rear和prior相等
  • 静态链表
    • 指针是结点的相对位置，又称游标
    • 需要连续的存储空间
    • 以next＝＝-1结束
    • 插入，删除方便，不支持随机存取
    • 不适合低级语言，适合定长文件