0%

【知识总结】 第二章-线性表

线性表的定义

  • 线性表是具有相同数据类型的n个(\(n\geq 0\))数据元素的有限序列
  • \(n\)为表长
  • \(L\)命名,则表示为\(L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)\),注意从1开始
  • 特点
    • 元素有限
    • 逻辑上有顺序性(注:这里指先后次序而不是物理的顺序存储
    • 表中元素为数据元素,类型相同,存储空间大小相同
    • 不考虑存储结构,属于逻辑结构

线性表的顺序表示

定义

  • 线性表的顺序存储称作顺序表
  • 线性表位序从1开始,数组下标从0开始
  • 特点:逻辑结构和物理结构相同(插入删除要移动大量元素),可随机存取、存储密度高

线性表的链式表示

定义

  • 线性表的链式存储称作单链表
  • 优点:不需要大量连续存储单元、插入删除不需要移动大量元素
  • 缺点:不能随机存取,引入额外指针空间开销

头结点和头指针

  • 不管是否有头结点,头指针都指向链表第一个结点
  • 头结点是带头结点链表的第一个结点,但不存储信息
  • 引入头结点的好处
    • 统一链表第一个数据结点和其他位置结点的操作
    • 对空表和非空表的处理进行了统一
  • 头结点指针为NULL,则链表为空

头插法和尾插法

  • 头插法,操作简单,但数据顺序和输入顺序相反
  • 尾插法,额外增加一个尾指针
  • 复杂度都是\(O(n)\)

其他链表

  • 双链表:每个结点中有前驱指针和后继指针(带头空表判断:头结点指针为NULL)
  • 循环单链表:在单链表的基础上,表尾结点指针指向头结点(带头空表判断:头结点后继为头结点)
  • 循环双链表:在双链表的基础上,表尾结点后继指向头结点,头结点前驱指向表尾结点(带头空表判断:头结点前驱和后继指针都指向头结点)
  • 静态链表:借助数组描述线性表的链式存储结构
    • 数据域:存储数据
    • 指针域:存储结点的相对地址(数组下标,游标),从0开始
    • 指针的NULL用-1表示
    • 增删操作不需要移动元素,只需要修改指针。

顺序表和链表的比较

  • 存取方式
    • 顺序表可以随机存储
    • 链表只能顺序存储
  • 逻辑结构和物理结构
    • 顺序表逻辑相邻的元素在物理存储上相邻
    • 链表通过指针表示元素的逻辑关系
  • 按值查找
    • 顺序表有序时可以折半查找
    • 链表不能折半查找
  • 按序号查找
    • 顺序表\(O(1)\)
    • 链表\(O(n)\)
  • 插入和删除
    • 顺序表平均要移动半个表长的元素
    • 链表只需要对应指针域
  • 存储密度
    • 顺序表较大
    • 链表需要额外的指针域
  • 空间分配
    • 顺序表静态分配容易内存溢出或空间大量闲置;动态分配需要移动大量元素,且要求内存有大量连续空间
    • 链表在需要时申请分配空间,操作灵活,空间利用高效。