有时在解决具体问题时，需要我们对链表的结构进行稍微地调整。比如，可以把链表的两头连接，使其成为了一个环状链表，通常称为循环链表。
和它名字的表意一样，只需要将表中最后一个节点的指针指向首元节点，链表就能成环儿，如图所示。
单向循环链表.png
需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元节点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。
以下是自己手敲的C语言单向循环链表
如果有不对的地方，欢迎指正，谢谢～
1、初始化链表方法
/*
1、初始化单向循环链表
判断是否第一次创建链表，分2种情况:
① YES->创建一个新节点,并使得新节点的next 指向自身; (*L)->next = (*L);
② NO-> 找链表尾节点,将尾节点的next = 新节点. 新节点的next = (*L);
注意：这里需要每次记录尾节点，方便插入数据
*/
Status InitList(LinkList *list){
LinkList tempNode,lastNode = NULL;
int scanfData;
printf("请输入要插入的数据(输入比1小的数退出输入)：");
while (1) {
scanf("%d",&scanfData);
if (scanfData < 1) {
break;
}
//创建一个节点
tempNode = malloc(sizeof(Node));
if (tempNode == NULL) {
return ERROR;
}
tempNode->data = scanfData;
if (*list == NULL) {
//首元节点插入
*list = tempNode;
tempNode->next = tempNode;
}
else {
//尾节点插入
tempNode->next = lastNode->next;
lastNode->next = tempNode;
}
//记录尾节点
lastNode = tempNode;
}
return OK;
}
2、遍历链表方法
/*
2、遍历链表
循环链表的遍历最好用do while语句，因为需要先做一次p = p->next，判断p->next等于首元节点的时候就是找到尾节点了
*/
void ListTraverse(LinkList list){
printf("遍历链表：");
LinkList p = list;
if (!p) {
printf("这是一个空链表");
}
else {
do {
printf("%d ",p->data);
p = p->next;
} while (p != list);
}
printf("\n");
}
3、链表插入节点方法
插入数据分两种情况：
-
1、插入位置在首元节点
插入在首元节点.png
-
2、插入位置不在首元节点，这按普通链表插入方式操作即可
插入非首元节点.png
/*
3、链表插入数据
初始条件:链表表List已存在,0≤i≤ListLength(List);
操作结果：在List中第i个位置之后插入新的数据元素data（i以0开始）
1.插入位置在首元节点
(1) 创建新节点,并判断是否创建成功,成功则赋值,否则返回ERROR;
(2) 判断是否空链表，是则直接插入，并赋值*list。不是则找到链表的尾节点;
(3) 让新节点的next 指向首元节点;
(4) 尾节点的next 指向新节点;
(5) 让头指针指向新节点.
2.如果插入的位置在其他位置;
(1) 创建新节点,并判断是否创建成功,成功则赋值,否则返回ERROR;
(2) 先找到插入的位置,如果超过链表长度,则自动插入队尾;
(3) 通过locaNode找到要插入位置的前一个节点;
(4) 新节点的next 指向locaNode原来的next位置, 然后让locaNode->next = 新节点.
*/
Status ListInsert(LinkList *list, int index, ElemType data){
LinkList p = malloc(sizeof(Node));
if (p == NULL) {
return ERROR;
}
p->data = data;
if (index == 0) {
//插入的是首元节点
if (*list == NULL) {
p->next = p;
}
else {
//找到尾节点
LinkList lastNode = *list;
while (lastNode->next != *list) {
lastNode = lastNode->next;
}
p->next = lastNode->next;
lastNode->next = p;
}
*list = p;
}
else {
LinkList locaNode = *list;
for (int i = 1; i < index && locaNode->next != *list; i++) {
locaNode = locaNode->next;
}
//插入数据
p->next = locaNode->next;
locaNode->next = p;
}
return OK;
}
4、链表删除节点方法
删除数据分两种情况：
- 1、删除首元节点
- 2、删除非首元节点
/*
4、循环链表删除元素
初始条件：链表L已存在，1≤i≤ListLength(List)
操作结果：删除List的第i个数据元素（i以0为起始位置）
1.删除首元节点
(1) 判断是否只有一个节点，是则直接删除;
(2) 找到链表的尾节点，使得尾节点next 指首元节点的下一个节点;
(3) 把新节点做为首元节点,然后释放原来的首元节点;
2.删除非首元节点
(1) 找到删除节点前一个节点previousNode，和当前节点locaNode
(2) 使得previousNode->next 指向locaNode->next
(3) 释放需要删除的节点locaNode
*/
Status ListDelete(LinkList *list, int index){
if (*list == NULL) {
return ERROR;
}
if (index == 0) {
//删除首元节点
if ((*list)->next == *list) {
(*list)->next = NULL;
free(*list);
*list = NULL;
}
//1、找到尾节点
LinkList lastNode;
for (lastNode = *list; lastNode->next != *list; lastNode = lastNode->next);
LinkList p = *list;
lastNode->next = p->next;
*list = p->next;
free(p);
}
else {
LinkList previousNode = *list;
int I;
for (i = 1; i < index && previousNode->next != *list; i++) {
previousNode = previousNode->next;
}
if (i == index) {
LinkList locaNode = previousNode->next;
previousNode->next = locaNode->next;
free(locaNode);
}
else {
return ERROR;
}
}
return OK;
}
5、链表取值方法
//5、单链表取值
/*
初始条件: 顺序线性表List已存在,1≤i≤ListLength(List);
操作结果：用data返回List中第i个数据元素的值
*/
Status GetElem(LinkList list, int index, ElemType *data){
LinkList p = list;
int i = 0;
//当尾节点指向首元节点就会直接跳出循环
while (p && i < index && p->next != list) {
p = p->next;
I++;
}
if (i != index || !p) {
return ERROR;
}
*data = p->data;
return OK;
}
6、清空单向循环链表方法
//6、清空链表
/* 初始条件：顺序线性表List已存在。操作结果：将List重置为空表 */
void ClearList(LinkList *list){
LinkList p,q;
for (p = *list; p->next != *list; p = p->next);
p->next = NULL;
p = *list;
while (p) {
q = p->next;
free(p);
p = q;
}
*list = NULL;
}
7、类定义和main方法
#define OK 1
#define ERROR 0
#define S_TRUE 1
#define S_FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
int main(int argc, const char * argv[]) {
//初始化
LinkList list;
printf("初始化链表\n");
InitList(&list);
//遍历数据
ListTraverse(list);
//插入数据
int insertIndex;
ElemType insertData;
while (1) {
printf("输入要插入的位置和数据用空格隔开(数据小于1则结束输入)：");
scanf("%d %d",&insertIndex,&insertData);
if (insertData < 1) {
break;
}
ListInsert(&list, insertIndex, insertData);
printf("插入数据后 ");
ListTraverse(list);
}
//删除数据
ListDelete(&list, 3);
printf("删除第3个元素：\n");
ListTraverse(list);
//取出数据
ElemType data;
GetElem(list, 3, &data);
printf("取出第3个数：%d\n",data);
// //清空链表
ClearList(&list);
printf("清空链表\n");
ListTraverse(list);
printf("\n");
return 0;
}
根据此代码实现的约瑟夫环地址：https://www.jianshu.com/p/d8b65de0ef1f
网友评论