抽象数据类型定义
ADT List{
数据对象: D={ai|ai 属于 Elemset,(i=1,2,...n,n>=0)};
数据关系: R={<ai-1,ai>|ai-1,ai属于D,(i=1,2,...,n)};
基本操作
InitList(&L)
操作结果: 构造一个空的线性表L;
DestroyList(&L)
初始条件: 线性表L已经存在;
操作结果: 销毁线性表L;
ClearList(&L)
初始条件: 线性表L已经存在;
操作结果: 将线性表L重置为空表;
ListEmpty(L)
初始条件: 线性表L已经存在;
操作结果: 若线性表L为空表，则返回TURE，否则返回FALSE;
ListLength(L)
初始条件: 线性表L已经存在;
操作结果: 返回线性表L中的数据元素个数;
GetElem(L,i,&e)
初始条件: 线性表L已经存在,i<=i<=ListLength(L);
操作结果: 用e返回线性表L中第i个数据元素的值;
LocateElem(L,e,compare())
初始条件: 线性表L已经存在,compare()是数据元素判定函数;
操作结果: 返回L中第1个与e满足compare()的元素的位序吗，若这样的元素不存在则返回 0;
PriorElem(L,cur_e,&pre_e)
初始条件: 线性表L已经存在;
操作结果: 若cur_e是L的数据元素且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意义;
NextElem(L,cur_e,&next_e)
初始条件: 线性表L已经存在;
操作结果: 若cur_e是L的数据元素且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无意义;
ListInsert(&L,i,e)
初始条件: 线性表L已经存在,i<=i<=ListLength(L)+1;
操作结果: 在L的第i个位置之前插入新的数据元素e,L的长度+1;
ListDelete(&L,i,&e)
初始条件: 线性表L已经存在,i<=i<=ListLength(L);
操作结果: 删除L的第i个数据元素，并用e返回其值，L的长度减一;
ListTraverse(&L,visited())
初始条件: 线性表L已经存在;
操作结果: 依次对线性表中每个元素调用visited();
} ADT List;
单链表、循环链表和双向链表的时间效率比较
| 查找表头结点(首元结点) | 查找表尾结点 | 查找结点 *p 的前驱结点 | |
|---|---|---|---|
| 带头结点的单链表 L | L->next 时间复杂度 O(1) | 从 L->next 依次向后遍历 时间复杂度 O(n) | p->next 无法找到其前驱 |
| 带头结点仅设头指针的循环单链表 L | L->next 时间复杂度 O(1) | 从 L->next 依次向后遍历 时间复杂度 O(n) | p->next 可以找到其前驱 时间复杂度 O(n) |
| 带头结点仅设尾指针 R 的循环单链表 L | R->next 时间复杂度 O(1) | R 时间复杂度 O(1) | p->next 可以找到其前驱 时间复杂度 O(n) |
| 带头结点的双向循环链表 L | L->next 时间复杂度 O(1) | L->prior 时间复杂度 O(1) | p->prior 时间复杂度 O(1) |
顺序表和链表的比较
| 顺序表 | 链表 | |
|---|---|---|
| 存储空间 | 预先分配，会导致空间闲置或溢出现象 | 动态分配，不会出现存储空间闲置或溢出现象 |
| 存储密度 | 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于 1 | 需要借助指针来体现元素间的逻辑关系，存储密度小于 1 |
| 存取元素 | 随机存取，按位置访问元素的时间复杂度为 O(1) | 顺序存取，按位置访问元素时间复杂度为 O(n) |
| 插入、删除 | 平均移动约表中一半元素，时间复杂度为 O(n) | 不需移动元素，确定插入、删除位置后，时间复杂度为 O(1) |
| 适用情况 | 表长变化不大，且能事先确定变化的范围; 很少进行插入或删除操作，经常按元素位置序号访问数据元素 | 长度变化较大 频繁进行插入或删除操作 |