单链表基本算法
写在前面
代码语法说明：在C语言语法的基础上使用了C++的 “引用”(&) 特性，后缀名为 .cpp
数据结构
定义单链表的数据结构为：
// 数据结构
typedef struct LNode
{
int data;
struct LNode *next;
} LinkList;
几个算法
- 已知节点 p，在节点 p 之前插入值。一般在单链表中的插入，都是先获取插入位置之前的一个节点，然后在这个节点之后插入新的节点。但这里是说在一个节点的前面插入新的值，所以本质上还是先在这个节点的后面插入一个新节点，然后做的一个操作是：将新节点的值和这个节点的值作交换。以此达到在前面插入的效果。
/* 已知p，在p前插入值
1. p 指向第 idx(idx>=0) 个节点
2. 构建新节点 s，值为 x，要在 p 之前插入节点s
3. 在 p 之后插入 s
4. 交换节点 p 和节点 s 的值即达到效果
*/
void InsertBefore(LinkList *L, int idx, int x) {
// p 指向第 idx 个节点
LinkList *p = L;
for (; idx>=0; idx--) {
p = p->next;
}
// s 为新建节点
LinkList *s = (LinkList *) malloc(sizeof(LinkList));
s->data = x;
// 将 s 插入到 p 之后
s->next = p->next;
p->next = s;
// 交换 p 和 s 的值
int temp = p->data;
p->data = s->data;
s->data = temp;
}
- 已知 p，删除 p 节点的值。和上一个方法同理，本质上还是删除 p 之后的一个节点，但是先把后面节点的值复制到当前节点，然后再删除，这样就达到了删除当前位置值的效果。
/* 已知p，删除p
1. p 指向第 idx(idx>=0) 个节点
2. 要删除p本身
3. 将 p 随后一个节点的值复制到 p 中
4. 删除 p 之后的一个节点
*/
void DeleteInplace(LinkList *L, int idx) {
// p 指向第 idx 个节点
LinkList *p = L;
for (; idx>=0; idx--) {
p = p->next;
}
// 将 p 随后一个节点的值复制到 p 中
p->data = p->next->data;
// 删除 p 随后的一个节点
p->next = p->next->next;
}
- 链表就地逆置1：更换节点指针域方向。将每一个节点的 next 域指向前一个节点，以此达到转置的效果。
/* 链表就地逆置1：更换节点指针域方向
1. 第一个节点（除头节点外）的 next 域置空
2. 每个节点的 next 域指向前一个节点
3. 头节点 next 域指向尾节点
*/
void Reverse1(LinkList *&L) {
LinkList *p = L->next;
LinkList *q = p->next;
LinkList *s;
p->next = NULL; // 第一个节点变尾节点
while (q != NULL) {
s = q->next; // 保留下一个节点地址
q->next = p;
p = q;
q = s;
}
L->next = p; // 头节点接原来的尾节点
}
- 链表就地逆置2：头插法逆置。将每一个节点插入到链表的最前面，以此达到转置的效果。
/* 链表就地逆置2：头插法逆置
1. 第一个节点（除头节点之外）的 next 域置空
2. 每个节点插入到头节点后面
*/
void Reverse2(LinkList *&L) {
LinkList *p = L->next->next; // 第二个节点（除头节点外）
L->next->next = NULL; // 第一个节点（除头节点外）的 next 域名置空
LinkList *s;
while (p != NULL) {
s = p->next; // 保留下一个节点地址
p->next = L->next;
L->next = p;
p = s;
}
}
- 对于递增单链表 L，删除大于等于min，小于等于max之间的节点。
/* 对于递增单链表 L，删除大于等于min，小于等于max之间的节点
1. 找到小于 min 的节点 p
2. 找到大于 max 的节点 q
3. 释放 p->next 至 q(不包含q) 之间的所有节点的空间
4. 令 p->next 指向 q
*/
void delnodes(LinkList *&L, int min, int max) {
LinkList *p = L->next;
while (p->next->data < min) { // 找前边界
p = p->next;
}
LinkList *q = p;
while (q->next->data <= max) { // 找后边界
q = q->next;
}
q = q->next;
LinkList *t = p->next;
while (t != q) { // 释放中间所有节点的空间
LinkList *next = t->next;
free(t);
t = next;
}
p->next = q; // 将 p 的 next 指向 q
}
- 对于递增单链表，删除所有值域重复的节点。
/* 对于递增单链表，删除所有值域重复的节点
1. 发现一个，删除一个的原则
2. 在递增单链表中，重复的值肯定都是紧挨着的
3. p 遍历链表，若 p->next 和 p 的值域相等，则删除 p->next 并释放空间
*/
void dels(LinkList *&L) {
LinkList *p = L->next;
while (p != NULL) {
if (p->next != NULL && p->data == p->next->data) { // 删除值域相同的下一个节点
LinkList *next = p->next->next;
free(p->next);
p->next = next;
}
else p = p->next; // 要加入 else 条件，因为删除下一个节点后，当前节点可能和下下个节点是相同的
}
}
测试代码
#include <stdio.h>
#include <stdlib.h>
// 数据结构
typedef struct LNode
{
int data;
struct LNode *next;
} LinkList;
// tools 功能函数
void Print(LinkList *L, char *s) {
LinkList *p = L->next; // 这是有头节点的链表
printf("%s: ", s);
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
putchar('\n');
}
void CreateListR(LinkList *&L, int data[], int n) {
L = (LinkList *) malloc(sizeof(LinkList)); // 头节点
LinkList *tail = L;
for (int i=0; i<n; i++) {
// 创建新节点
LinkList *p = (LinkList *) malloc(sizeof(LinkList));
p->data = data[i];
p->next = NULL;
// 节点添加到末尾
tail->next = p;
tail = tail->next;
}
}
// 基本算法（开始）
//...
// 基本算法（结束）
int main(void) {
// 初始化链表
// int data[10] = {0,1,2,3,4,5,6,7,8,9};
int data[10] = {0,1,2,2,2,5,6,6,8,9};
LinkList *L;
CreateListR(L, data, 10);
Print(L, "操作前");
// InsertBefore(L, 3, 100);
// DeleteInplace(L, 3);
// Reverse1(L);
// Reverse2(L);
// delnodes(L, 2, 6);
// dels(L);
Print(L, "操作后");
return 0;
}
参考资料
《新编数据结构习题与解析》（李春葆等编著）