第二章线性表
2.1 线性表的定义和基本操作
线性表的定义
线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列，其中 n 为表长，当 n = 0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为 L = (a 1, a 2, … , ai , ai+1, … , an)
ai 是线性表中的 “第 i 个” 元素线性表中的位序
a 1 是表头元素；an 是表尾元素
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
线性表的基本操作
InitList (&L)：初始化表。构造一个空的线性表 L，分配内存空间。
DestroyList (&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。
ListInsert (&L, i, e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e。
ListDelete (&L, i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
LocateElem (L, e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
GetElem (L, i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。
& 表示 C++ 中的引用, 若传入指针型变量且在函数体内要进行改变, 要用到指针变量的引用 (C 中用指针的指针也可以)
2.2 线性表的顺序表示
顺序表的定义
顺序表——用顺序存储的方式实现线性表
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现
顺序表的实现 ：静态分配、动态分配
动态分布语句：
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize)
//malloc函数申请一片连续的存储空间
//free函数释放原来的内存空间
动态分配不是链式存储, 同样属于顺序存储结构, 物理结构没有变化: 随机存取方式, 只是分配的空间大小可以在运行时决定
特点: 随机访问, 存储密度高, 插入和删除需要移动大量元素
顺序表的操作
1. **插入操作** 平均时间复杂度O(n)
2. **删除操作** 平均时间复杂度O(n)
- 查找操作：按值查找、按位查找
2.3 线性表的链式表示
单链表
头指针和头结点的区别：（1）不管带不带头结点, 头指针始终指向链表的第一个结点
（2）头结点是带头结点的链表中的第一个结点, 通常不存储信息
引入头结点的优点：无论链表是否为空, 头指针都指向头结点的非空指针, 空表和非空表处理一致
单链表的操作
建立单链表
核心：初始化操作、指定结点的后插操作
（1）头插法，链表的逆置
（2）尾插法，注意设置一个指向表尾结点的指针
插入结点操作
（1）按位序插入（带头结点）
（2）按为序插入（不带头结点）
（3）指定结点的前插操作: 先找到前一个结点, 时间复杂度为 O (n)
（4） 将前插操作转化为后插操作, 然后交换两个结点的数据, 时间复杂度为 O (1)
删除结点操作
（1）按位序删除（带头结点）
（2）指定结点的删除：先找到前驱节点, 再删除结点, O (n)
查找结点操作
（1）按位查找
（2）按值查找
双链表
循环链表
（1）循环单链表：表尾结点的 next 指针指向头结点
对单链表在表头和表尾操作时: 不设头指针仅设尾指针, 效率更高
可以从任意一个结点开始遍历整个链表
（2）循环双链表：表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点
静态链表
用数组描述链式存储结构, 也有数据域和指针域. 指针是结点的相对地址 (数组下标), 又称游标
插入和删除只需要修改指针, 不需要移动元素
顺序表和链表的比较
-
逻辑结构都属于线性表，都是线性结构
-
存储结构顺序表：顺序存储链表：链式存储
-
基本操作–初始化
-
基本操作–增删
-
基本操作–查
-
如何选择
（1）基于存储的考虑 ：难以估计长度和存储规模时用链表, 但链表的存储密度较低
（2）基于运算的考虑：经常做按序号访问数据元素用顺序表
（3）基于环境的考虑：较稳定选顺序表, 动态性较强选链表