一、线性表的定义和基本操作
1）定义
线性表：零个或多个数据元素的有序排列。
除第一个元素外，每个元素有且只有一个直接前驱元素；除最后一个元素外，每个元素有且只有一个直接后继元素。
2）基本操作
- InitList：初始化
- ListEmpty：判空
- ClearList：清空
- GetElem：取值
- LocateElem：定位
- Listlnsert：插入
- ListDelete：删除
- ListLength：长度
二、线性表的实现
1 顺序存储
1）定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
2）存储结构
一维数组，存取时间性能为O(1)，随机存取结构
- 存储空间的起始位置：数组 data 的存储位置
- 线性表的最大容量：数组长度 MaxSize
- 线性表的当前长度 : length
3）主要操作
- 取值O(1)：返回数组中指定下标的值。下标超限抛异常
- 插入O(n)：从最后一个元素到插入位置元素依次后移，插入，表长+1。位置或长度有问题抛异常或扩容。
- 删除O(n)：从删除位置到最后元素依次前移，表长-1。删除位置不合理抛异常。
4）优缺点
优点
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的”碎片”
2 链式存储
2.1 单链表
1）定义
不考虑相邻，哪有空就存哪，让每个元素知道它下一个元素的位置
2）存储结构
链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
- 单链表：每个结点中只包含一个指针域，n 个结点链结成一个链表
- 结点：数据元素的存储映像，由数据域和指针域组成
- 数据域：存储数据元素信息的域
- 指针域：存储直接后继位置的域
- 头指针：（必要元素）指向链表中第一个结点的存储位置
- 头结点：（可选元素）为方便操作，可在第一个结点前附设一个头结点。
- 头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。
- 有了头节点，对第一结点前插入和删除第一结点，与其他结点的操作就统一了
- 线性链表的最后一个结点指针为“空”
3）主要操作
- 读取O(n)：从第一个节点遍历
- 插入、删除：遍历查找第i个元素O(n)，改变指针，插入和删除O(1)
- 若不知道位置，与顺序存储结构没有优势。知道位置后，优势很大
- 对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显
- 整表创建：动态生成链表。从空表起，依次建立元素结点，插入链表。
- 头插法：新结点插入到头结点与前一新元素之间。
- 尾插法：记录尾结点，新结点插在终端结点后面
- 整表删除：便利每个节点，在内存中将它释放
4）单链表与顺序存储优缺点
- 时间性能
- 查找
- 顺序：o(1)
- 单链表：O(n)
- 插入和删除
- 顺序：平均移动一半元素，O(n)
- 单链表：找出位置后，O(1)
- 查找
- 空间性能
- 顺序：需预分配，大了浪费，小了溢出
- 单链表：无需分配不受限
- 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
- 若需要频繁插入和删除时，宜采用单链表结构。
- 元素个数变化较大或未知时，最好用单链表。
- 如长度确定，顺序存储结构效率会高很多。
2.2 静态链表
1）定义
针对没有指针的语言，用数组来代替指针描述链表，被称为静态链表。
2）存储结构
游标实现法：数组的元素都是由两个数据域组成， data 和 cur
- 数据域data ：用来存放数据元素
- 游标 cur ：相当于单链表中的 next 指针，存放该元素的后继在数组中的下标
- 第一个元素：存放备用链表的第一个结点的下标
- 最后一个元素：存放第一个有数值的元素的下标
3）主要操作
将可用空间链成备用链表
- 插入
- 模拟空间分配：从备用链表上取第一个结点作为待插入的新结点
- 删除
- 模拟空间释放：将删除位置加入备用链表第一位
4）静态链表优缺点
- 插入和删除操作时 ，只需要修改游标。
- 没有解决连镇存储分配带来的表长难以确定的问题
- 失去了顺序存储结构随机存取的特性
2.3 循环链表
1）定义
循环链表：将单链表中终端结点的指针端由空指针改为指向头结点，这种头尾相接的单链表称为单循环链表，简称循环链表。
2）差异
循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next 是否为空，现在则是 p -> next 不等于头结点，则循环未结束。
3）尾指针
如用尾指针替代头指针，则查找开始结点和终端结点都很方便。
2.4 双向链表
1）定义
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
2）主要操作
在插入和删除时，需要更改两个指针变量。顺序很重要，千万不能写反了。
- 插入
- 先搞定插入结点的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。
- 删除
- 将前结点的后继指向后结点，将后结点的前驱指向前结点
3 线性表的应用
队列和堆栈