数据结构笔记-线性表部分。
线性表定义
- 线性表（linear list）：是多个数据元素的有限序列。
- 线性表中元素个数n为线性表长度，n=0时为空表。
- 线性表有唯一的首/尾元素，首元素无前驱元素，尾元素无后继元素。
- 线性表中的数据元素可以有多个数据项，但除首尾元素外，每个数据元素前/后有且只有唯一一个数据元素前驱/后继。
线性表的基本操作：
- Init（L）初始化线性表为空
- Destroy (L) 这是一个将L变为空表的方法（释放内存）
- Clear（L）清除所有元素
- IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
- Length（L） 返回表L的长度，即表中元素个数
- Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
- Prior（L，i） 取i的前驱元素
- Next（L，i） 取i的后继元素
- Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
- Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
- Delete（L，p） 从表L中删除位置p处的元素
- Traverse（L, visit）遍历所有元素调用visit()
线性表的顺序存储（顺序表）
- 顺序表中的数据元素在内存中按顺序连续存储（例如数组）。
- 表中相邻元素的物理地址是相邻的。
- 显然，顺序表可以通过索引存取第i个元素 L.elem[i-1] ，因此操作6.7.8对应时间复杂度O(1)。
- 连续存放虽然允许索引，但在中间插入/删除需要将插入元素位置之前/之后的所有元素向前/向后移动，因此对N个元素的线性表，操作10,11的平均时间为移动N/2个元素所需要的时间，时间复杂度O(N)。
线性链表
- 顺序表中的数据元素在内存中任意位置存储。
- 表中相邻元素的物理地址可以相邻，也可以不相邻。
- 链表中的结点（Node）由数据域（数据元素）和指针域（指向相邻结点的指针）组成，通过结点中指向相邻元素的指针可获取相邻元素。
- 头结点：指向链表第一个结点，头结点指针域NULL表示链表长度n=0。头结点数据域可以空，也可以存长度等附加信息。
单链表
- 单链表：指针域只有一个指针（指向下一个元素）的链表。
- 由于单链表结点指针指向下一个元素，获取后继元素只要一步，Next（L，i）时间复杂度O(1)。
- 由于元素任意分布在内存空间中，无法使用索引，查找第i个元素只能从第一项开始遍历，平均查找N/2次，因此 Get（L，i）和 Prior（L，i）对应时间复杂度O(N)。
- 对于单链表，在A,B之间插入X，需要让X->B,A->X, 插入只需两步，但找到A平均需要N/2次，时间复杂度O(N)。
- 对于单链表，在A,X,B之间删除X，需要让A->B, 即先让 A的指针 = X的指针，再释放X的内存，删除只需两步，但找到A平均需要N/2次，时间复杂度O(N)。
- 特别的，如果没有特殊标记Length的单链表，获取长度需要遍历全部结点，时间复杂度O(N)。
静态链表
在数组中，一个分量表示数据元素，一个分量表示游标。
- 静态链表：指针域使用数组的游标，游标顺序即为链表中元素顺序。
循环链表
- 循环链表：表中最后一个结点指针指向头结点。
- 头结点指针域等于头本身的指针表示链表长度n=0。
- 其他操作同单链表。
双向链表
- 双向链表：指针域有两个指针，一个指向前驱，一个指向后继。
- 由于双向链表结点指针指向相邻元素，获取前驱/后继元素只要一步，Next（L，i）和 Prior（L，i）时间复杂度O(1)。
- 由于元素任意分布在内存空间中，无法使用索引，查找第i个元素只能从第一项开始遍历，平均查找N/2次，因此 Get（L，i）对应时间复杂度O(N)。
- 特别的，如果没有特殊标记Length的双向链表，获取长度需要遍历全部结点，时间复杂度O(N)。