线性表（Linear List）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用$n$表示，$n≥0$。当$n=0$时，表示线性表是一个空表。
设序列中第$i$个元素为$a_i (1≤i≤n)$（$i$表示逻辑序号）。线性表$L$可以表示为：
$$
L=(a_1,a_2,…a_i,a_{i+1},…,a_n)
$$
其中$a_1$为第一个元素，又称做表头元素，$a_2$为第二个元素，$a_n$为最后一个元素，又称做表尾元素。例如，以下的线性表：
$$
(1,4,3,2,8,10)
$$
$1$为表头元素，$10$为表尾元素。
线性表$L$中的元素是与位置有关的，即第$i$个元素$a_i$处在第$i-1$个元素$a_$的后面和第$i+1$个元素$a_{i+1}$的前面。这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。
顺序表
顺序表是线性表的顺序存储结构，把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。
假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof(ElemType)，整个线性表所占用存储空间的大小为:
n * sizeof(ElemType) // n表示线性表的长度。
类型定义
#define ElemType int // 元素类型
#define MaxSize 10 // 最大长度
typedef struct
{
ElemType data[MaxSize]; // data用于存放元素
int length; // 顺序表的实际元素个数
} SqList; // 顺序表结构体类型
由于C/C++中数组的下标从$0$开始，线性表的第$i$个元素$a_i$存放在顺序表的第$i-1$个位置上。
将$a_i$在逻辑序列中的位置称为逻辑序号，而在顺序表中的位置称为物理序号（指数组下标）。
基本运算
初始化顺序表
// 初始化顺序表
void initList(SqList *&L)
{
L = (SqList *) malloc(sizeof(SqList));
L->length = 0;
}
初始化非空顺序表
// 根据数组拷贝建立非空顺序表
void createList(SqList *&L, ElemType a[], int n)
{
if (a == NULL || n < 0 || n >= MaxSize) return;
L = (SqList *) malloc(sizeof(SqList));
for (int i = 0; i < n; ++i)
{
L->data[i] = a[i];
}
L->length = n;
}
销毁顺序表
// 销毁顺序表
void destroyList(SqList *&L)
{
free(L);
}
遍历顺序表
平均时间复杂度为$O(n)$。
// 打印顺序表
void printList(SqList *L)
{
printf("[");
for (int i = 0; i < L->length; ++i)
{
if (i == L->length - 1) printf("%d", L->data[i]);
else printf("%d, ", L->data[i]);
}
printf("]");
}
查找元素
平均时间复杂度为$O(1)$。
// 获取第i个元素, 将元素值存入e中
bool getElem(SqList *L, int i, ElemType &e)
{
if (L == NULL || i < 1 || i > L->length) return false;
e = L->data[i - 1];
return true;
}
按元素值查找
平均时间复杂度为$O(n)$。
// 按元素值查找, 返回逻辑序号
int locateElem(SqList *L, ElemType e)
{
if (L == NULL) return 0;
int i = 0;
while (i < L->length && L->data[i] != e) i++;
if (i >= L->length) return 0; // 找不到就返回0
else return i + 1;
}
插入元素
该运算在顺序表$L$的第$i$（$i$是逻辑序号，$1≤i≤n+1$）个位置上插入新的元素$e$。如果$i$值不正确，则显示相应错误信息；否则将顺序表原来第$i$个元素及以后元素均后移一个位置，移动方向从右向左，如下图所示，腾出一个空位置插入新元素，最后顺序表长度增$1$。
// 在第i个位置上插入元素e
bool insertElem(SqList *&L, ElemType e, int i)
{
if (L == NULL || i < 1 || i > L->length) return false;
i--; // 将逻辑序号转换成物理序号
for (int j = L->length; j > i; --j)
{
L->data[j] = L->data[j - 1];
}
L->data[i] = e;
L->length++;
return true;
}
对于本算法来说，元素移动的次数不仅与表长L->length = n有关，而且与插入位置$i$有关：
- 当$i=n+1$时，移动次数为$0$。
- 当$i=1$时，移动次数为$n$，达到最大值。
删除算法最好的时间复杂度为$O(1)$，最坏时间复杂度为$O(n)$。
平均情况分析：
在插入元素$a_i$时，若为等概率情况，则$p_i = \frac{1}{n+1}$。
此时需要将$a_i～a_n$的元素均后移一个位置，共移动$n-i+1$个元素。
所以在长度为$n$的线性表中插入一个元素时所需移动元素的平均次数为：
$$
\sum_{n+1} p_(n-i+1)=\sum_{n+1} \frac{1}{n+1}(n-i+1)=\frac{2}
$$
因此插入算法的平均时间复杂度为$O(n)$。
删除元素
该运算删除顺序表L的第$i$**（ $i$是逻辑序号，1≤i≤n）**个元素。如果$i$值不正确，则显示相应错误信息；否则将线性表第$i$个元素以后元素均向前移动一个位置，移动方向为从左向右，如下图所示，这样覆盖了原来的第$i$个元素，达到删除该元素的目的，最后顺序表长度减$1$。
// 删除第i个位置上的元素
bool deleteElem(SqList *&L, int i)
{
if (L == NULL || i < 1 || i > L->length + 1) return false;
i--; // 将逻辑序号转换成物理序号
for (int j = i; j < L->length; ++j)
{
L->data[j] = L->data[j + 1]; // 元素前移
}
L->length--;
return true;
}
对于本算法来说，元素移动的次数也与表长$n$和删除元素的位置$i$有关：
- 当$i=n$时，移动次数为$0$。
- 当$i=1$时，移动次数为$n-1$。
删除算法最好的时间复杂度为$O(1)$，最坏时间复杂度为$O(n)$。
平均情况分析：
在删除元素$a_i$时，若为等概率情况，则$p_i = \frac{1}$。
此时需要将$a_{i+1}～a_n$的元素均前移一个位置，共移动$n-i$个元素。
所以在长度为$n$的线性表中删除一个元素时所需移动元素的平均次数为：
$$
\sum_p_(n-i)=\sum_ \frac{1}(n-i)=\frac{2}
$$
因此删除算法的平均时间复杂度为$O(n)$。
单链表
链表是线性表的链式存储结构，在每个结点中除包含有数据域外，还含有一个指针域，用以指向其后继结点，这样构成的链接表称为线性单向链接表，简称单链表。
类型定义
在单链表中，假定每个结点的类型用LinkNode表示，它应包括存储元素的数据域，这里用data表示，其类型用通用类型标识符ElemType表示，还包括存储后继元素位置的指针域，这里用next表示。
typedef int ElemType; // 数据类型
typedef struct LNode // 定义单链表节点类型
{
ElemType data; // 数据域
struct LNode *next; // 指针域, 指向后继节点
} LinkNode; // 单链表节点的类型
基本运算
初始化单链表
该运算建立一个空的单链表，即创建一个头结点。
// 初始化单链表
void initList(LinkNode *&L)
{
L = (LinkNode *) malloc(sizeof(LinkNode));
L->next = NULL; // 创建头结点
}
初始化非空单链表
非空单链表可以通过一个含有$n$个数据的数组来建立单链表，常用方法有如下两种:
头插法
该方法从一个空表开始，依次读取数组$a$中的元素，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上（即头结点之后），直到结束为止。
// 利用头插法根据数组拷贝建立非空单链表
void createListL(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s;
L = (LinkNode *) malloc(sizeof(LinkNode)); // 创建头结点
L->next = NULL; // 其next域置为NULL
for (int i = 0; i < n; i++) // 循环建立数据节点
{
s = (LinkNode *) malloc(sizeof(LinkNode));
s->data = a[i]; // 创建数据结点s
s->next = L->next; // 将结点s插在原首结点之前, 头结点之后
L->next = s;
}
}
尾插法
该方法从一个空表开始，依次读取数组$a$中的元素，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾后，直到结束为止。
为此，必须增加一个尾指针$r$，使其始终指向当前链表的尾结点。
// 利用尾插法根据数组拷贝建立非空单链表
void createListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *) malloc(sizeof(LinkNode)); // 创建头结点
r = L; // r始终指向尾结点, 开始时指向头结点
for (int i = 0; i < n; i++) // 循环建立数据结点
{
s = (LinkNode *) malloc(sizeof(LinkNode));
s->data = a[i]; // 创建数据结点s
r->next = s; // 将结点s插入到结点r之后
r = s;
}
r->next = NULL; // 尾结点next域置为NULL
}
销毁单链表
释放单链表$L$占用的内存空间。即逐一释放全部结点的空间。平均时间复杂度为$O(n)$。
// 销毁单链表
void destroyList(LinkNode *&L)
{
LinkNode *pre = L, *p = L->next; // pre指向*p的前驱结点
while (p != NULL) // 扫描单链表L
{
free(pre); // 释放*pre结点
pre = p; // pre, p同步后移一个结点
p = pre->next;
}
free(pre); // 循环结束时, p为NULL, pre指向的是尾结点, 释放它
}
判断是否为空表
// 判断是否为空表
bool isEmpty(LinkNode *L)
{
return L->next == NULL; // 若单链表L没有数据结点, 则返回真, 否则返回假
}
求单链表的长度
平均时间复杂度为$O(n)$。
// 求单链表的长度
int getLength(LinkNode *L)
{
int n = 0;
LinkNode *p = L; // p指向头结点, n置为0(即头结点的序号为0)
while (p->next != NULL)
{
p = p->next;
n++;
}
return n; // 循环结束, p指向尾结点, 序号n为单链表中数据结点的个数
}
遍历单链表
平均时间复杂度为$O(n)$。
// 打印单链表
void printList(LinkNode *L)
{
printf("[");
LinkNode *p = L->next; // p指向开始结点
while (p != NULL) // p不为NULL, 输出p结点的data域
{
printf("%d ", p->data);
p = p->next; // p指向下一个结点
}
printf("]");
}
查找元素
在单链表$L$中从头开始遍历到第$i$个结点，若存在第$i$个数据结点，则将其数据域的值赋给变量$e$。平均时间复杂度为$O(n)$。
// 获取第i个元素, 将元素值存入e中
bool getElem(LinkNode *L, int i, ElemType &e)
{
if (i <= 0) return false; // 保证逻辑序号大于0
LinkNode *p = L; // p指向头结点
int j = 0; // j置为0(即头结点的序号为0)
while (j < i && p != NULL) // 找第i个结点
{
p = p->next;
j++;
}
if (p == NULL) return false; // 不存在第i个数据结点, 返回false
e = p->data; // 存在第i个数据结点, 返回true
return true;
}
按元素值查找
在单链表$L$中从头开始找第$1$个值域与$e$相等的结点，若存在这样的结点，则返回逻辑序号，否则返回$0$。平均时间复杂度为$O(n)$。
// 按元素值查找, 返回逻辑序号
int locateElem(LinkNode *L, ElemType e)
{
int i = 1;
LinkNode *p = L;
while (p != NULL && p->data != e)
{
p = p->next;
i++;
}
return p == NULL ? 0 : i;
}
插入元素
先在单链表$L$中找到第$i-1$个结点$p$，若存在这样的结点，将其值为$e$结点$s$的下一个结点指向第$i$个节点，并将结点$s$插入到$p$的后面。插入到表头的时间复杂度为$O(1)$，插入到表尾的时间复杂度为$O(n)$。
// 在第i个位置上插入元素e
bool insertElem(LinkNode *&L, int i, ElemType e)
{
if (i <= 0) return false; // 保证逻辑序号大于0
int j = 0;
LinkNode *p = L, *s; // p指向头结点, j置为0
while (j < i - 1 && p != NULL) // 查找第i-1个结点
{
p = p->next;
j++;
}
if (p == NULL) return false; // 未找到第i-1个结点, 返回false
// 找到第i-1个结点p, 创建新结点s
s = (LinkNode *) malloc(sizeof(LinkNode));
s->data = e; // 将新结点s其data域置为e
s->next = p->next; // 将s之后的结点指向p之后的结点
p->next = s; // 将s插入到p之后, 完成新结点s的插入
return true;
}
删除元素
先在单链表$L$中找到第$i-1$个结点$p$，若存在这样的结点，且也存在后继结点，则删除该后继结点。删除指定位置结点的平均时间复杂度为$O(n)$。
// 删除第i个位置上的元素
bool deleteElem(LinkNode *&L, int i, ElemType &e)
{
if (i <= 0) return false; // 保证逻辑序号大于0
int j = 0;
LinkNode *p = L, *q; // p指向头结点, j置为0
while (j < i - 1 && p != NULL) // 查找第i-1个结点
{
p = p->next;
j++;
}
if (p == NULL) return false; // 未找到第i-1个结点, 返回false
// 找到第i-1个结点p
q = p->next; // q指向第i个结点
if (q == NULL) return false; // 若不存在第i个结点, 返回false
e = q->data;
// 将p指向的下一个结点替换成q的下一个结点, 从而删除q结点
p->next = q->next;
free(q); // 释放q结点
return true; // 成功删除第i个结点, 返回true
}