1.单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据。链表中的数据是以节点来表示的，每个节点由元素和指针构成，元素就是存储数据的存储单元，指针就是连接每个元素的地址数据。在单链表中指针只指向他的后继节点。
2.单链表的实现
2.1 定义一些辅助元素
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
2.2 设计单链表的节点
节点.png
由上图可知一个单链表的节点由元素(数据域)和指针（指针域）两个部分组成，元素存储数据，指针存储该节点指向的下一个节点的地址数据。
实现代码：
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
2.3 设计一个单链表
单链表.png
带头结点的单链表
一个单链表的基本结构可以由上图所示。在设计单链表的时候我们可以给单链表初始化一个头结点，头结点不存储数据，可以存储一些辅助信息，例如链表的长度。头结点的指针域可以指向首元节点，在后续的链表增删的时候会很方便，不用修改首指针所指向的地址。便于空表和非空表的处理。
初始化单链表的代码实现：
/// 初始化一个带头结点的单链表
/// @param L 单链表
Status InitLinkList(LinkList *L){
// 分配内存
*L = (LinkList)malloc(sizeof(Node));
// 分配失败，报错
if (*L==NULL) { return ERROR; }
// 头结点指针置空
(*L)->next = NULL;
return OK;
}
2.4 遍历打印单链表
代码实现：
void PrintLinkList(LinkList L){
LinkList p = L->next;
// 判断一下首元节点是否有值，有值在遍历打印
if (p == NULL) { return; }
while (p) {
printf("该节点的值是：%d\n",p->data);
p = p->next;
}
}
2.5 指定位置插入新节点
由于我们引入了头结点的概念，所以插入变的相对简单，不用在插入第一个位置的时候修改链表起始位置的指针。
插入新节点.png
核心算法：
- 1.找到要插入位置的前一个节点
- 2.将新节点的next指向前一个节点的next
- 3.将前一个节点的next指向新节点
实现代码：
/// 在指定位置插入新节点
/// @param L 单链表
/// @param location 位置
/// @param e 新节点的数据
Status InsertLinkList(LinkList *L, int location, ElemType e){
//取出头节点的指针
LinkList p = *L;
// 记录位置的中间变量
int j = 1;
// 如果指针一直有值就可以继续寻找，直到找到要插入的位置的前一个节点
while (p && j<location) {
p = p->next;
j++;
}
// p为NULL或者位置的值大于要插入的位置则直接报错
if (!p || j>location) { return ERROR; }
// 创建要插入的节点
LinkList new = (LinkList)malloc(sizeof(Node));
new->data = e;
new->next = p->next;
// 前一个位置的next指向新的
p->next = new;
return OK;
}
2.6 根据指定位置获取元素
这个查找没什么难的，由于我们引入了头结点，遍历可以从1开始，找到要找的位置返回该节点的值即可。相关容错处理在代码中可见。
实现代码：
/// 根据指定位置获取元素
/// @param L 链表
/// @param location 位置
/// @param e 取到的值
Status GetElemFromList(LinkList L, int location, ElemType *e) {
// 初始化一些临时变量
LinkList p = L->next;
int j = 1;
// 查找要取值得位置
while (p && j<location) {
p = p->next;
j++;
}
// 没取到或者位置不合法就报错
if (!p || j>location) { return ERROR; }
// 返回取到的值
*e = p->data;
return OK;
}
2.7 根据指定位置删除节点
由于引入了头结点的概念，我们从头结点开始就是可能待删除节点的前驱，一直遍历查找到前一个几点。
删除指定位置的节点.png
核心算法：
- 1.找到待删除位置的前一个节点
- 2.将前一个节点的next指向待删除节点的next
- 3.释放待删除节点的内存
实现代码：
/// 删除指定位置的节点
/// @param L 链表
/// @param location 位置
/// @param e 返回删除的数据
Status DeleteLinkList(LinkList *L, int location, ElemType *e){
// 初始化一些辅助变量
LinkList p = (*L);
LinkList q;
// 要找要删除节点的前一个节点，所以从0开始，如果要删除首元节点的时候，其实他的前一个节点是头结点（辅助节点）
int j = 0;
// 查找要删除节点的前一个节点
while (p->next && j<(location-1)) {
p = p->next;
j++;
}
// 没找到要删除的节点，或者位置非法就报错
if (!p->next && j>(location-1)) { return ERROR; }
// 临时存放要删除的节点
q = p->next;
// 要删除的前一个节点的next指向要删除节点的next
p->next = q->next;
// 返回删除的数据
*e = q->data;
// 释放节点内存
free(q);
return OK;
}
2.8 清空链表
清空主要是把链表恢复到初始状态，删除所有的除去头节点的节点，并把头结点的next置为NULL。
/// 清空单链表
/// @param L 单链表
Status ClearLinkList(LinkList *L){
// 找到第一个节点
LinkList p = (*L)->next;
// 头结点的next置空
(*L)->next = NULL;
// 辅助节点
LinkList q;
// 循环遍历清空
while (p) {
q = p;
p = p->next;
free(q);
}
return OK;
}
2.9 单链表头插法
头插法，顾名思义，就是一直在最前面插入数据，所以如果一组有序的数据插入完成后就是倒序的。
核心算法：
- 1.将新节点的next指向头结点的next
- 2.将头结点的next指向新节点
实现代码：
/// 创建单链表，头插法
/// @param L 链表
/// @param n 初始长度
void CreateLinkListHeader(LinkList *L, int n) {
// 分配内存
*L = (LinkList)malloc(sizeof(Node));
// 头结点指针置空
(*L)->next = NULL;
LinkList p;
for (int i = 1; i<=n; i++) {
// 创建新节点
p = (LinkList)malloc(sizeof(Node));
// 新节点赋值
p->data = i;
//新节点的next指向头结点的next
p->next = (*L)->next;
// 头结点的next指向新节点
(*L)->next = p;
}
}
2.9 单链表尾插法
跟头插法一样，尾插法就是将新数据一直插入到单链表的尾部，所以如果一组有序的数据插入完成后就是正序的。
核心算法：
- 1.开辟一个辅助节点，不断存储新的尾节点初始化为头结点
- 2.将辅助节点的next指向新节点
- 3.将新节点赋值给辅助节点
实现代码：
/// 尾插法
/// @param L 链表
/// @param n 长度
void CreateLinkListTail(LinkList *L, int n) {
// 分配内存
*L = (LinkList)malloc(sizeof(Node));
// 头结点指针置空
(*L)->next = NULL;
LinkList p,r;
r = *L;
for (int i = 1; i<=n; i++) {
// 创建新节点
p = (LinkList)malloc(sizeof(Node));
// 新节点赋值
p->data = i;
// 新节点的next为NULL
p->next = NULL;
// 辅助节点的next指向新节点
r->next = p;
// 将新节点赋值给辅助节点
r = p;
}
}
