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

线性表的定义

• 线性表是具有相同数据类型的n个()数据元素的有限序列
• 为表长
• 用命名，则表示为，注意从1开始
• 特点
  • 元素有限
  • 逻辑上有顺序性（注：这里指先后次序而不是物理的顺序存储）
  • 表中元素为数据元素，类型相同，存储空间大小相同
  • 不考虑存储结构，属于逻辑结构

线性表的顺序表示

定义

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

线性表的链式表示

定义

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

头结点和头指针

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

头插法和尾插法

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

其他链表

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

顺序表和链表的比较

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