线性表是具有相同数据类型的n个数据元素的有限序列。一般表示为：L=(a1, a2, ..., an)
- 除了第一个元素外，每个元素有且仅有一个前驱；第一个元素只有后继，没有前驱。
- 除最后一个元素外，每个元素有且仅有一个后继；最后一个元素只有前驱，没有后继。
- InitList(&L): 初始化表。构造一个空的线性表
- Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数
- LocateElem(L, e): 按值查找操作
- GetElem(L, i): 按位查找
- ListInsert(&L, i, e): 插入操作
- ListDelete(&L,i, &e): 删除操作
- PrintList(L): 输出操作
- Empty(L): 判空操作
- DestroyList(&L): 销毁操作
线性表的顺序存储又称为顺序表。存储类型描述为：
#define MaxSize 50 // 定义线性表的最大长度
typedef struct {
ElemType data[MaxSize]; // 顺序表的元素
int length; // 顺序表当前长度
} SqList; // 顺序表的类型定义一维数组可以是静态分配的，也可以是动态分配的。静态分配时，由于数组的大小和空间是事先已经固定的，所以一旦空间占满，再加入新的数据会导致溢出。动态分配时若数据空间占满，可以另外开辟一个更大的存储空间替换原有存储空间。
#define InitSize 100 // 表长度的初始定义
typedef struct {
ElemType *data; // 指示动态分配数组的指针
int MaxSize, length; // 数组的最大容量和当前个数
} SeqList; // 动态分配数组顺序表的类型定义C的初始态分配语句为：
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);C++的初始态分配语句为：
L.data = new ElemType[InitSize];特点：
- 随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
- 存储密度高，每个结点只存储数据元素。
- 逻辑上相邻的数据元素在物理上也相邻，所以插入和删除操作需要移动大量元素。
时间复杂度：O(n)
bool ListInsert(SqList &L, int i, ElemType e) {
// 将元素e插入到顺序表L的第i个位置
if (i < 1 || L > L.length + 1) {
return false;
}
if (L.length >= MaxSize) {
return false;
}
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}时间复杂度：O(n)
bool ListDelete (SqList &L, int i, ElemType &e) {
// 删除顺序表L中第i个元素，并将删除的值用引用变量e返回
if (i < 1 || i > L.length) {
return false;
}
e = L.data[i - 1];
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j];
}
L.length--;
return true;
}时间复杂度：O(n)
int LocateElem (SqList L, ElemType e) {
// 查找顺序表中值为e的元素，并返回元素位序，否则0
int i = 0;
for (i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1;
}
}
return 0;
}线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点，除了自身信息外还需要存放一个指向其后继的指针。
typedef struct LNode { // 定义单链表结点类型
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;单链表是非随机存取的存储结构，即不能直接查找到表中某个特定的结点。
通常使用头指针来标识一个单链表，若为NULL，则表示空链表。有时附加一个结点作为头结点，头结点指向的下一个结点才是数据结点，若指向为NULL，则带头结点的单链表为空。引入头结点的优点：
- 由于开始结点的位置存放在头结点的指针域中，所以在链表的第一个位置上的操作和表中其他位置上的操作一致。
- 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表统一处理。
生成的新结点插入到当前链表的表头，所以读入顺序与表顺序是相反的，插入结点时间复杂度O(1)，长度为n的单链表创建时间复杂度为O(n):
LinkList CreateList1 (LinkList &L) {
// 从表尾到表头建立单链表L，每次均在头结点之后插入元素
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
whild (x != 999) {
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}由于头插法的逆序问题，所以可以通过增加一个尾指针r来实现尾插法，时间复杂如与头插法相同：
LinkList CreateList2 (LinkList &L) {
// 正向创建单链表
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L;
scanf("%d", &x);
while (x != 999) {
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
// s->next = NULL;
r->next = s;
r = s;
}
r->next = NULL;
return L;
}时间复杂度为O(n)：
LNode *GetElem (LinkList L, int i) {
// 获取带头结点的单链表第i个位置的结点指针
int j = 1;
LNode *p = L->next;
if (i == 0) {
return L;
}
if (i < 1) {
return NULL;
}
while (p && j < i) {
p = p->next;
j++;
}
return p;
}时间复杂度O(n)：
LNode *LocateElem (LinkList, L, ElemType e) {
// 返回值域为e的结点指针
LNode *p = L->next;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}将值为x的新结点s插入到指定位置i的单链表中，也就是在第i-1个位置后插入新的结点。查找时间复杂度为O(n)，插入时间复杂度为O(1):
- p = GetElem(L, i - 1);
- s->next = p->next;
- p->next = s;
上述方法属于前插法，还有一种为后插法，即在第i个位置后插入新的结点，然后将第i位置和第i+1位置结点中的值进行交换，但需要额外的中间变量。
找到第i-1个位置的结点指针，然后删除其后一个位置的结点即为删除第i个位置的结点，时间复杂度为O(n)。
遍历单链表，计算不含头结点在内的结点数量。
单个结点同时存在两个指针，一个指向前驱，一个指向后继：
typedef struct DNode {
ElemType data;
struct DNode *prior, *next;
} DNode, *DLinkList;在双链表中p所指的结点之后插入结点*s：
- s->next = p->next;
- p->next->prior = s;
- s->prior = p;
- p->next = s;