《数据结构》第二章-线性表

《数据结构》第二章-线性表知识梳理，包括它的定义和基本操作、顺序表示、链式表示三部分内容。

线性表

• 定义和基本操作
  • 定义
    • 线性表是具有相同数据类型的n个数据元素的有限序列
    • • a1为表头元素
      • an为表为元素
      • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
  • 特点
    • PS：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。
    • 表中元素的个数有限
    • 表中元素具有逻辑上的顺序性，表中元素有其先后次序
    • 表中元素都是数据元素，每个元素都是单个元素
    • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
    • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容
  • 线性表的基本操作
    • InitList(&)：初始化表。构造一个空的线性表
    • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数
    • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
    • GetElem(L,i)：按位查找操作。获取表中第i个位置的元素的值
    • ListInsert (&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
    • ListDelete(&L,i,&e):删除操作。删除表工中第i个位置的元素，并用e返回删除元素的值
    • PrintList(L)：输出操作。按前后顺序输出线性表工的所有元素值
    • Empty(L)：判空操作。若工为空表，则返回true，否则返回false
    • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间
• 顺序表示
  • 定义
    • 线性表的顺序存储，是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
    • 特点
      • 随机访问
        • 通过首地址和元素序号可在时间O(1)内找到指定的元素
        • 存储密度高，每个结点只存数据元素
        • 表中的元素的逻辑顺序与其物理顺序相同，所以插入和删除操作需要移动大量元素
  • 基本操作
    • （1） 插入
      • 时间复杂度: O(n)
    • （2） 删除
      • 时间复杂度: O(n)
    • （3） 按值查找（顺序查找）
      • 时间复杂度: O(n)
• 链式表示
  • 单链表的定义
    • 通过一组任意的存储单元来存储线性表中的数据元素
    • 对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针
    • 在单链表第一个结点之前附加一个结点，称为头结点，其数据域不设任何信息，指针指向线性表的第一个元素结点
  • 单链表的基本操作
    • 采用头插法建立单链表
      • 生成的链表中的结点次序和输入数据的顺序不一致
      • 时间复杂度：O(n)
    • 采用尾插法建立单链表
      • 引入尾指针r，始终指向当前链表的尾结点
      • 时间复杂度：O(n)
    • 按序号查找结点值
      • 时间复杂度：O(n)
    • 按值查找表结点
      • 时间复杂度：O(n)
    • 插入结点操作
      • 时间复杂度
        • 在给定结点后插入：O(1)
        • 否则，O(n)
      • 前插操作
        • 设待插入结点为s，将其插到结点p的前面：可先s插入到p的后面，再将p->data和s->data交换，时间复杂度仅为O(1)
    • 删除结点操作
      • • 时间复杂度：O(1)
      • 扩展做法：为了删除结点p，可先将其后继节点的值赋予自身，再将后继结点删除，时间复杂度仅为O(1)
    • 求表长操作
      • 时间复杂度：O(n)
  • 双链表
    • 单链表访问前驱结点的时间复杂度为O(n)，为此引入双链表，每个结点有两个指针prior和next，分别指向其前驱和后继结点
    • 插入操作
    • 删除操作
  • 循环链表
    • 循环单链表
      • 表中最后一个结点的指针不是NULL，而是指向头结点
      • 其余与单链表相同
    • 循环双链表
      • 头结点的prior指针指向表尾结点；当链表为空表时，其头结点的prior域和next域都等于L
  • 静态链表
    • 利用数组来描述线性表的链式存储结构
    • 指针是结点的相对地址（数组下标），又称游标
    • 以next==-1作为结束的标志
  • 顺序表和链表的比较
    • 存取（读写）方式
      • 顺序表：可以顺序存取，也可由随机存取
      • 链表：只能从表头顺序存取元素
    • 逻辑结构与物理结构
    • 查找、插入和删除元素操作
    • 空间分配
      • 顺序存储在静态存储分配时难以扩充；动态存储分配又会降低操作效率