1. 线性表
1.1 线性表的定义
线性表是有零个或多个数据元素组成的有序数列。 线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。
1.2 线性表的特性
- 集合中必存在唯一的一个“第一元素”；
- 集合中必存在唯一的一个 “最后元素” ；
- 除了第一个元素之外，均有唯一的前驱。
- 除了最后一个元素之外，均有唯一的后继；
1.3 线性表的物理存储结构：
- 顺序存储结构：数据元素逻辑相邻，物理存储地址也相邻。
- 链式存储结构：数据元素不连续的，需要指针域链接。
2. 顺序存储结构
2.1 顺序存储定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。线性表里的每一个数据元素逻辑相邻，物理存储地址也相邻.
2.2 顺序存储结构方式
- 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
- 线性表的中最大存储容量，数组的长度MaxSize。
- 线性表的当前长度:length。
注意，数组的长度与线性表的当前长度需要区分一下：数组长度是存放线性表的存储空间的长度，存储空间分配完一般是不变的。线性表长度是线性表中元素数据的个数，随着线性表插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该小于等于数组的长度。
顺序存储结构的初始化
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct {
ElemType *data;
int length;
} sqlist;
// 初始化
Statue InitList (sqlist *L) {
L -> data = malloc(sizeof(ElemType));
if (!L -> data) return ERROR;
L ->length = 0;
return OK;
}
顺序存储结构的取值
Status GetElem(Sqlist L,int i, ElemType *e) {
if (i<1 || i > L.length) return ERROR; // 判断i值是否合理, 若不合理,返回ERROR
*e = L.data[i-1]; // data[i-1]单元存储第i个数据元素.
return OK;
}
顺序存储结构的插入
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
Status ListInsert(Sqlist *L,int i,ElemType e) {
if ((i<1) || (i>L->length+1)) return ERROR; // 1.i值不合法判断
if (L->length == MAXSIZE) return ERROR; // 2.存储空间已满
// 插入数据不在表尾,则先移动出空余位置
if(i <= L->length){
for(int j = L->length-1; j>=i-1;j--){
L->data[j+1] = L->data[j]; // 3.从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
}
}
L->data[i-1] = e; // 4.将新元素e 放入第i个位置上
++L->length; // 5.长度+1
return OK;
}
顺序存储结构的删除
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果: 删除L的第i个数据元素,L的长度减1
*/
Status ListDelete(Sqlist *L,int i) {
if(L->length == 0) return ERROR; // 1.线性表为空
if((i<1) || (i>L->length)) return ERROR; // 2.i值不合法判断
for(int j = i; j < L->length;j++) {
L->data[j-1] = L->data[j]; // 3.从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
}
L->length --; // 表长度-1;
return OK;
}
顺序存储结构的清空
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L) {
L->length=0;
return OK;
}
顺序存储结构的复杂度
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。
2.3 顺序存储结构的优缺点
优点:
- 无须为表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点:
- 插入和删除需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”
3. 链式存储结构
3.1 链式存储结构定义
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些元素可以存在内存未被占用的任意位置。
在顺序结构中，每个元素数据只需要存储数据元素信息就可以了。在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
- 节点（Node）：线性表的链式存储，每个数据元素是不连续的，每个数据元素除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
- 首元节点：链表存储结构中的第一个结点叫首元节点。线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。
- 首指针：链表存储结构中的第一个结点的存储位置叫首指针。
- 头结点：为了更加方便地对链表进行操作，会在首元节点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域指向首元结点。
- 单链表：n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,….,an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
3.2 单链表存储结构方式
单链表的初始化
#define MAXSIZE 20 /* 存储空间初始分配量 */
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
// 定义结点
typedef struct Node {
ElemType data; // 数据域
struct Node *next; // 指针域
} Node;
typedef struct Node *LinkList;
// 初始化单链表线性表
Status InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node)); // 1.产生头结点,并使用L指向此头结点
if(*L == NULL) return ERROR; // 2.存储空间分配失败
(*L)->next = NULL; // 3.将头结点的指针域置空
return OK;
}
单链表的读取
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L) {
LinkList p=L->next;
while(p) {
printf("%d\n",p->data);
p=p->next;
}
return OK;
}
单链表的插入元素
在单链表L的第i个位置之后插入新的数据元素e，L的长度加1;
- 找到第i个位置的节点p
- 创建插入的节点s，并给节点s的数据域赋值e
- 将节点p的后继结点赋值给节点s的后继（此时有两个指针指向s的后继，如果步骤3和步骤4顺序调换，s的后继会没有指针指向，丢失在链表中）
- 将节点s赋值给节点p的后继
// 单链表插入元素
/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
*/
Status ListInsert(LinkList *L, int i, ElemType e) {
int j;
LinkList p,s;
p = *L;
j = 1;
while (p && j<i) { // 1.寻找第i个结点
p = p->next;
++j;
}
if (!p || j>i) return ERROR; // 第i个元素不存在
s = (LinkList)malloc(sizeof(Node)); // 2.生成新结点s
s->data = e; // 将e赋值给s的数值域
s->next = p->next; // 3.将p的后继结点赋值给s的后继
p->next = s; // 4.将s赋值给p的后继
return OK;
}
单链表的删除删除元素
设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向他的后继结点。
删除L的第i个数据元素，L的长度减1
- 寻找第i-1个结点p
- 用指针q指向删除节点（这时有两个指针指向删除节点，防止删除节点丢失在链表中）
- 将删除节点的后继赋值给p的后继
- free节点q，释放内存;
/*
初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
操作结果：删除L的第i个数据元素，L的长度减1
*/
Status ListDelete(LinkList *L,int i){
int j;
LinkList p,q;
p = (*L)->next;
j = 1;
while (p->next && j<(i-1)) { // 1.寻找第i-1个结点p
p = p->next;
++j;
}
if (!(p->next) || (j>i-1)) return ERROR;
q = p->next; // 2.用指针q指向删除节点
p->next = q->next; // 3.将删除节点的后继赋值给p的后继
free(q); // 4.free节点q;
return OK;
}
单链表的整表创建
头插法建立单链表
//随机产生n个元素的值，建立带表头结点的单链表线性表L(头插法)
void CreateListHead(LinkList *L,int n) {
LinkList p;
int i;
srand(time(0));//初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;//先建立一个带头结点的单链表
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizoef(Node));//生成新的结点
p->data = rand() % 100 + 1;//随机生成100以内的数字
p->next = (*L)->next;
(*L)->next = p; //插入到表头
}
}
尾插法建立单链表
//随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L,int n) {
LinkList p,r;
int i;
srand(time(0));//初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));//为整个线性表
r = *L;//r为指向尾部的结点
for(i = 0;i < n;i++)
{
p = (Node *)malloc(sizeof(Node));//生成新结点
p->data = rand() % 100 + 1;//随机生成100以内的数字
r->next = p;//将表尾终端结点的指针指向新结点
r = p; //就那个当前新结点定义为表尾终端结点
}
r->next = NULL;//表示当前链表结束
}
不管是头插法还是尾插法：都是先处理要插入的结点（要插入的的结点需要一个指针域指向，防止丢失），再更新新结点的指针域next的指向，最后更新首元结点的指向或者表尾终端结点的指向
