可以看到,单向循环链表的尾结点的指针域会指向首元结点。
一、单项循环链表的初始化
创建一个单向循环链表的逻辑如下:
1,第一次创建的时候,它就是一个指针,还没有开辟任何内存空间
(1)新增一个节点
(2)将新节点的指针域指向节点自身
(3)将新节点设置为链表的首元节点
2,链表中已经存在至少一个节点,此时再向其中新增节点
(1)找到链表的尾结点
(2)新建一个节点
(3)新节点的指针域指向首元结点
(4)将尾结点的指针域指向新节点
代码如下:
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
// 操作的结果状态
typedef enum : int {
Success,
Error,
} Status;
// 给链表分配的初始存储量
#define MAX_SIZE 20
// 定义元素的类型
typedef int ElementType;
// 定义节点
typedef struct Node {
ElementType data; // 数据域
struct Node * next; // 指针域
} Node;
// 定义链表类型
typedef struct Node * LinkedList;
// 1.1,初始化链表
/* 要分两种情况:
* (1),传入的链表为空,那么就新建一个节点,并且让该节点的指针域指向自身
* (2),传入的链表非空,那么就找到尾结点,然后将尾结点的指针域指向新节点,新节点的指针域指向链表首元结点
*/
Status initLinkedList1(LinkedList *list) {
int scanedItem;
printf("请依次输入节点的值,输入0结束");
while (1) { // 该while循环的退出条件是,输入0
scanf("%d", &scanedItem); // 控制台输入数字
if (scanedItem == 0) { // 停止输入,退出循环
break;
}
if (*list == NULL) {// 如果传入的链表是空的
// 新建一个节点
LinkedList node = malloc(sizeof(Node));
if (!node) {
exit(0);
}
node->data = scanedItem;
// 将该节点的指针域指向其自身
node->next = node;
// 将该节点配置为链表的首元结点
*list = node;
} else { // 如果链表非空
// 找到尾结点
LinkedList tailNode;
for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
// 新建一个节点
LinkedList node = malloc(sizeof(Node));
if (!node) {
exit(0);
}
node->data = scanedItem;
// 将新节点的指针域指向首元结点
node->next = *list;
// 将尾结点的指针域指向新节点
tailNode->next = node;
}
}
return Success;
}
上面👆这种初始化链表的方式,每一次都需要通过循环遍历来获取到链表的尾结点。为了优化算法的时间复杂度,我通过一个临时变量来记录链表的尾结点,这样就不需要每次都再循环遍历一遍了。
那么在哪个时机来更新这个临时变量呢,我的想法是,新节点的每一次插入都是放在链表的最后,然后每次插入新节点之后都将这个新节点赋值给临时节点变量,这样的话,这个临时节点变量就会一直都是尾结点了。
代码如下:
// 1.2,初始化链表
/*
1.1那种初始化链表的方式,每一次都需要通过循环遍历找到尾结点,接下来我通过一个临时变量来记录尾结点
思路跟1.1还是一样的,也是分两种情况:
(1)如果链表之前就是空的,那么新增节点,并且将该节点的指针域指向自身,然后将链表指针指向该节点
(2)如果链表已经存在,那么就找到链表的尾结点,然后将尾结点的指针域赋值给新节点的指针域,并且将尾结点的指针域指向新节点
*/
Status initLinkedList2(LinkedList *list) {
printf("请依次输入链表元素值,输入0结束:\n");
int scanedItem;
LinkedList tailNode = NULL; // 通过tailNode记录尾结点,这样就不需要每次都通过循环遍历来查找尾结点了
while (1) { //当输入0的时候,跳出循环
scanf("%d", &scanedItem);
if (scanedItem == 0) {
break;
}
if ((*list) == NULL) { // 如果链表为空
// 新建一个节点,并将该节点的指针域指向其自身
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = scanedItem;
node->next = node;
// 将该节点设置为链表的首元结点
*list = node;
// 给尾结点赋值
tailNode = node;
} else { // 如果链表非空
// 创建一个新的节点,并且将新节点的指针域指向首元结点
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = scanedItem;
node->next = *list;
// 将尾结点的指针域指向新节点
tailNode->next = node;
// 更新尾结点
tailNode = node;
}
}
return Success;
}
二、单项循环链表的打印
代码如下:
// 2,打印链表
Status printLinkedList(LinkedList list){
if (list == NULL) {
printf("当前链表为空\n");
return Error;
}
printf("当前链表元素为:\n");
LinkedList tempNode = list;
do {
printf("%d\n", tempNode->data);
tempNode = tempNode->next;
} while (tempNode != list);
return Success;
}
1,首先要判断一下链表是否为空
2,如果链表中有元素(即非空),则通过一个do-while循环来遍历链表中的元素。
三、向单向循环链表中插入元素
往单项循环链表中插入元素的时候,需要考虑两个方面:
1,插入的位置是首元结点的位置
(1)新增一个节点
(2)找到链表的尾结点,并将尾结点的指针域指向新节点
(3)新节点的指针域指向当前的首元结点
(4)设置链表的首元结点为新节点
2,插入的位置是首元结点后面的位置
(1)找到插入位置的前面一个节点,下面称为前驱结点
(2)创建一个新节点
(3)将新节点的指针域指向前驱结点的后继节点
(4)将前驱结点的后继节点设置为新节点
(5)如果插入的位置超过链表长度,那么就直接将新节点放到链表的最后。
代码如下:
// 3,往循环链表中插入数据
/*
1,如果插入的位置在第一位,那么就将新节点的指针域指向当前的首元结点,然后将新节点设置为首元结点,还要找到尾结点,然后将尾结点的指针域指向新节点
2,如果插入的位置不在第一位,那么就找到插入位置的前驱结点,然后将新节点的指针域指向当前前驱结点的后继节点,然后将前驱节点的指针域指向新节点
3,如果插入的位置超过了链表长度,则自动插入到表尾。
*/
Status insert(LinkedList *list, int index, ElementType element) {
if (index < 1) {
return Error;
}
if (index == 1) {
// 新建节点,并且将新节点的后继节点设置为当前的首元结点
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = element;
node->next = *list;
// 找到尾结点,并且将尾结点的指针域指向新节点
LinkedList tailNode;
for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
tailNode->next = node;
// 将新节点设置为首元结点
*list = node;
} else {
//找到插入位置的上一个节点(如果插入位置超过链表长度,则将新节点放到表尾)
LinkedList previousNode;
int i;
for (previousNode = *list, i = 2; (previousNode->next != *list) && i < index; previousNode = previousNode->next, i++);
//新建节点,并且将新节点的后继节点设置为当前的前驱结点的后继
LinkedList node = malloc(sizeof(Node));
if (!node) {
return Error;
}
node->data = element;
node->next = previousNode->next;
// 将当前的前驱结点的后继节点设置为新节点
previousNode->next = node;
}
return Success;
}
四、删除单项循环链表中的元素
删除的逻辑如下:
1,如果链表是空,则直接报错
2,如果删除的是首元节点
(1)当链表中只有一个节点的时候,直接将链表置空
(2)当链表中有两个以及两个以上的节点的时候
①找到链表的尾结点
②找到待删除节点(即首元结点)
③将尾结点的指针域指向待删除节点的后继节点
④将待删除节点的后继节点设置为链表的首元结点
⑤将待删除节点的内存清空
3,如果删除的是首元结点后面的其他节点
(1)找到待删除节点前面的节点,后面简称前驱结点
(2)根据前驱结点找到待删除节点
(3)将前驱结点的指针域指向待删除节点的后继节点
(4)释放待删除节点的内存
代码如下:
// 4,删除单项循环链表中的元素
Status deleteElement(LinkedList *list, int index) {
//链表中没有节点
if (*list == NULL) {
return Error;
}
if (index == 1) { // 如果删除的是首元结点
// 如果链表中只有一个首元结点了,则直接将链表置空
if ((*list)->next == *list) {
*list = NULL;
return Success;
}
//如果链表中有两个以及两个以上的节点
// 找到待删除的首元结点
LinkedList toDeleteNode = *list;
// 找到链表的尾结点,并且将尾结点的指针域指向原首元结点的下一个节点
LinkedList tailNode;
for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
tailNode->next = toDeleteNode->next;
//将当前首元结点的下一个节点设置为链表的首元结点
*list = toDeleteNode->next;
//释放节点内存
free(toDeleteNode);
} else { // 如果删除的是其他位置
//找到待删除的节点的上一个节点
LinkedList previousNode;
int i;
for (previousNode = *list, i = 2; previousNode->next->next != *list && i < index; previousNode = previousNode->next, i++);
//将前驱结点的next指向待删除节点的next
LinkedList toDeleteNode = previousNode->next;
previousNode->next = toDeleteNode->next;
//释放待删除节点的内存
free(toDeleteNode);
}
return Success;
}
五、查询单项循环链表中的值
查询单项循环链表中的某一个值的坐标,其逻辑还是蛮简单的:
遍历链表中的每一个元素,直到匹配到对应的值为止;
只要匹配到对应的值,或者遍历完一遍就会跳出循环;
需要对链表的最后一项做特殊处理。
代码如下:
// 5,查询循环链表中的值
int findValue(LinkedList list, int value) {
int index = 1;
LinkedList tempNode = list;
// 找寻值为value的节点
while (tempNode->data != value && tempNode->next != list) {
tempNode = tempNode->next;
index++;
}
//对尾结点做特殊处理
if (tempNode->next == list && tempNode->data != value) {
return -1;
}
return index;
}
以上。