线性表
一、逻辑结构和基本操作
1. 逻辑结构
- 具有相同数据类型的n个数据元素的有限序列，表长n，n=0为空表
- 表头：第一个元素
- 表尾：最后一个元素
- 除第一个元素外，每个元素有且仅有一个直接前驱
- 除最后一个元素外，每个元素有且仅有一个直接后继
2. 基本操作
initList(&L);
len(L);
locateElem(L, i);
getElem(L, i);
listInsert(&L, i, e);
listDelete(&L, i, &e);
printList(L);
isEmptyList(L);
destroyList(&L);
二、顺序存储结构
1. 定义：又称顺序表，使用一组地址连续的存储单元，依次存储线性表的数据元素，使逻辑上相邻的两个元素物理位置也相邻
- 存储空间的起始位置data[ ]
- 顺序表最大存储容量MaxSize
- 顺序表当前最大长度len
特点 - 随机访存，O(1)时间复杂度访问
- 存储密度高，每个结点只存储数据元素
- 无需花费空间建立数据之间的逻辑关系，由物理位置相邻特性决定
- 逻辑上物理上均相邻，插入删除操作需要移动大量元素
2. 基本操作
（1）插入元素
//插入元素
boolean listInsert(SqList &L, int i, Elemtype e){
if(i < 1 || i L.len + 1)
return -1;
if(L.len = MaxSize)
return -1;
for(int j = L.len; j i; j--)
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.len++;
}
分析
- 最好情况：在表尾插入 (i=n+1)，不需要移动元素，时间复杂度为O(1)
- 最坏情况：在表头插入 (i=1)，元素后移n次，时间复杂度O(n)
- 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n+1}\))，是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n}{2}\)，其时间复杂度为O(n)
（2）删除元素
//删除元素
boolean listDelete(SqList &L, int i, Elemtype e){
if(i < 1 || i L.len + 1)
return -1;
e = L.data[i-1];
for(int j = i; j < L.len; j++)
L.data[j-1] = L.data[j];
L.len--;
return true;
}
分析
- 最好情况：在表尾插入 (i=n)，不需要移动元素，时间复杂度为O(1)
- 最坏情况：在表头插入 (i=1)，元素后移n次，时间复杂度O(n)
- 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n+1}\))，是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n-1}{2}\)，其时间复杂度为O(n)
（3）查找元素
int locateElem(SqList &L, Elemtype e){
int i;
for(i = 0; i < L.len; i++)
if(e == L.data[i])
return i+1;
}
分析
- 最好情况：查找的元素在表头，仅需比较1次，时间复杂度O(1)
- 最坏情况：查找的元素在表尾或不存在，需要比较n次，时间复杂度O(n)
- 平均情况：假设\(P_i\) (\(P_i = \frac{1}{n}\))是在第i个位置上结点的概率，则在长度为n的线性表中插入一个结点所需移动的平均次数为\(\frac{n+1}{2}\)，其时间复杂度为O(n)
链式存储结构
1.创建单链表
（1）头插法
- 为新插入的结点分配内存空间
- 每次都是把插入的新结点放入表头(头结点位置)
- 链表结点的次序与输入的顺序相反
（2）尾插法
- 为新插入的结点分配内存空间
- 每次都是把插入的新结点放入表尾(尾结点位置)
- 链表中的结点顺序与输入顺序一致
2.按值查找结点
- 在链表中从第一个结点出发，顺指针next逐个向下搜索，直到找到第i个结点，否则返回最后一个结点的指针域NULL
3.按序号查找结点
- 从链表第一个结点开始，由前往后按照序号递增定位到相应结点的位置，返回该值，需检查序号是否越界
4.插入
- 插入操作是将值为x的新结点插入到单链表的第i个位置
- 先检查插入位置是否合法
- 找到待插入位置的前驱结点
- 在其后将结点插入
p = getElem(L, i-1)
s-next = p-next;
p-next = s;
5.删除
- 将单链表的第i个结点删除
- 先检查插入位置是否合法
- 找到待删除位置的前驱结点
- 删除其后结点
p = getElem(L, i-1)
q = p-next;
q-next = p-next;
free(q);
双链表
- 双链表有两个指针prior和next，分别指向前驱和后继结点
- 插入操作
s-next = p-next;
p-next-prior = s;
s-prior = p;
p-next = s;
- 删除操作
p-next = q-next;
q-next-prior = p;
free(q);
循环链表
- 循环双链表和循环单链表
- 静态链表使用数组来描述线性表的链式存储结构