1. 创建循环链表
单向链表
循环链表
循环链表的创建实际就是单向链表的尾节点指向头结点，最终形成一个环。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
/*线性结构使用顺序表的方式存储*/
//链表结构设计
typedef struct Node {
ElemType data;
struct Node *next;
} Node, *LinkList;
Status CreateList(LinkList *L) {
ElemType elem;
LinkList tail = NULL;
while (1) {
scanf("%d", &elem); // 输入数据
if (elem == 0) break; // 输入0时结束
if (*L == NULL) { // 表是空的时候
*L = (LinkList)malloc(sizeof(Node)); // 创建表头
if (*L == NULL) return ERROR; // 没创建出来报错
(*L)->data = elem; // 存入数据
tail = *L; // 尾节点，方便后续添加
} else { // 表不为空
tail->next = (LinkList)malloc(sizeof(Node)); // 创建新节点
if (!tail->next) return ERROR; // 没创建出来报错
tail->next->data = elem; // 存入数据
tail = tail->next; // 之前的尾节点指向新节点
}
}
tail->next = *L; // 形成环
return OK;
}
2. 输出所有节点
Status ListTraverse(LinkList L)
{
LinkList p = L; // 临时变量指向头节点
do {
printf("%4d ", p->data); // 打印临时节点的数据
p = p->next; // 临时节点变为下一个节点
} while (p != L); // 又回到表头，停止循环
printf("\n");
return OK;
}
3. 节点的插入与删除
其实不管是单向链表还是循环链表，增删操作核心都是找到前一个节点。
因为都是单向的，需要前一个节点的指向来获取插入位置的下一个节点。
3.1 插入
循环链表的插入
插入步骤：
- 创建新节点
- 找到前一个节点
- 新节点指向前一个节点的后一个节点 ①
- 前一个节点指向新节点 ②
- 如果在头结点插入，还需要修改头结点的指向
Status ListInsert(LinkList *L, int loc, ElemType elem) {
if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
LinkList tmp = (LinkList)malloc(sizeof(Node)); // 1.创建新节点
if (!tmp) return ERROR; // 没创建出来报错
tmp->data = elem; // 存入数据
LinkList target = *L; // 不管loc是多少，都是从头开始找
if (loc == 1) {
for (; target->next != *L; target = target->next); // 2.找到头结点的前一个节点(尾节点)
*L = tmp; // 5.头结点变为新节点
} else {
int idx = 1;
for (; target->next != *L && idx != loc - 1; target = target->next, ++idx); // 2.找到loc结点的前一个节点
if (target->next == *L && idx != loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
}
tmp->next = target->next; // 3.新节点指向前一个节点的下一个节点
target->next = tmp; // 4.前一个节点指向新节点
return OK;
}
3.2 删除
循环链表的删除
插入步骤：
- 找到前一个节点
- 临时指针指向被删除节点
- 前一个节点指向被删除节点的后一个节点 ①
- 释放被删除节点 ②
- 如果在头结点删除，还需要修改头结点的指向下一个节点
Status ListDelete(LinkList *L, int loc, ElemType *elem) {
if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
LinkList tmp, target = *L; // 不管loc是多少，都是从头开始找
if (loc == 1) {
if ((*L)->next == *L) { // 如果只有1个节点
free(*L);
*L = NULL;
return OK;
};
for (; target->next != *L; target = target->next); // 1.找到头结点的前一个节点(尾节点)
*L = (*L)->next; // 5.头节点变为头节点的下一个节点
} else {
int idx = 1;
for (; target->next != *L && idx != loc - 1; target = target->next, ++idx); // 1.找到loc结点的前一个节点
if (target->next == *L && idx != loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
}
tmp = target->next; // 2.tmp指向当前节点
target->next = tmp->next; // 3.前一个节点指向当前节点的下一个节点
*elem = tmp->data; // 获取被删除数据
free(tmp); // 4.释放被删除节点
return OK;
}
4. 查找元素并返回位置
和单向链表差不多，主要区别就是结束的判断。
-
单向链表结束的标志是尾节点的下一个节点为
NULL - 循环链表结束的标志是尾节点的下一个节点为头节点
int LocateElem(LinkList L, ElemType elem)
{
if (L == NULL) return NOT_FOUND; // 空表
int i = 1;
LinkList p = L; // 从表头开始找
do {
if (p->data == elem) return i; // 找到直接返回
i++;
p = p->next;
} while (p != L); // 只找一圈
return NOT_FOUND;
}
5. 约瑟夫环(杀人游戏算法)
已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
5.1 问题分析
很明显这是一个环，我们需要用循环链表解决。
要解决问题有几个阶段：
- 创建循环链表
- 找到开始的序号
- 开始执行报数，直到只剩一个人
用到的循环链表知识：
- 循环链表的创建
- 循环链表元素的查找
- 循环链表的节点的删除
5.2 代码实现
Status josephKill(int n, int start, int m)
{
if (n <= 0 || start < 1 || m < 1 || start > n)
return ERROR;
// 1.创建循环链表
LinkList head = (LinkList)malloc(sizeof(Node));
head->data = 1;
if (head == NULL) return ERROR;
LinkList target = head;
for (int i = 2; i <= n; i++) {
target->next = (LinkList)malloc(sizeof(Node));
if (target->next == NULL) return ERROR;
target->next->data = i;
target = target->next;
}
target->next = head;
// 2.找到开始序号的人
target = head;
do {
if (target->data == start) break; // 找到对应的序号
target = target->next;
} while (target != head);
if (target == head && target->data != start) return ERROR; // 找了一圈，没有找到对应序号
// 3.循环到只剩一个人
int i;
LinkList tmp = NULL;
while (target->next != target) {
for (i = 1; i < m; i++) {
tmp = target; // 记录前一个节点，方便删除和释放
target = target->next; // 向后移动一个节点
}
tmp->next = target->next; // 前一个节点指向当前节点的下一个节点
printf("%d was killed.\n", target->data);
free(target); // 释放被删除节点
// 从下一个节点开始
target = tmp->next;
}
printf("%d survived!\n", target->data);
return OK;
}
int main(int argc, const char * argv[]) {
josephKill(5, 3, 2);
}
//输出
4 was killed.
1 was killed.
3 was killed.
2 was killed.
5 survived!
Program ended with exit code: 0
6. 循环链表的逆序
因为是单向链表：
- 断开节点前需要引用下一个节点，要不然就找不到了。
- 单向链表没法直接找到前一个节点，所以需要一个额外的引用。
Status ListReverse(LinkList *L) {
if (L == NULL) return ERROR; // 空表
LinkList prev, current, next;
prev = *L;
current = prev->next;
next = current->next;
while (current != *L) { // 当current为头结点时结束，再移动就找不到尾节点了
current->next = prev; // 指针反向
// 依次移动节点
prev = current;
current = next;
next = next->next;
}
current->next = prev; // current为头结点，但还没有反向，所以先反向
*L = prev; // 头结点逆序后应为原来的尾节点
return OK;
}
7. 循环链表倒数第k个数
核心思想是两个指针，保证2个指针间隔为 k，后面的指针到头的时候，另一个指针指向倒数第 k 个数。
// 循环链表倒数第k个元素
Status ListLocateKBackwards(LinkList L, int k, ElemType *elem) {
if (L == NULL) return ERROR; // 空表
LinkList target, tmp;
target = L;
tmp = L->next;
// 移动tmp使得两个指针间隔k
int i = 1;
for (; i < k && tmp != L; tmp = tmp->next, i++);
if (tmp == L && i < k) return ERROR;
// tmp走到头的时候，倒数第k个节点被target指针指向
do {
target = target->next;
tmp = tmp->next;
} while (tmp != L);
*elem = target->data;
return OK;
}
网友评论