循环单链表的一些基本概念
头结点
头结点的定义
头结点是链表中的第一个结点，其数据域一般无意义（有时可存放链表长度等）。
头结点目的
统一链表的操作。使得空表时的操作不用特殊处理，简化了链表的操作。
尾指针
尾指针的定义
尾指针是指向链表尾结点的指针。
尾指针的作用
用来找到整个链表。
减少时间复杂度。链表的插入删除操作一般在表尾进行操作，头指针因为一开始指向头结点，要找到尾结点的时间复杂度为O(n)，而尾指针指向的就是尾结点，所以找到尾结点的时间复杂度为O(1)。
循环单链表的相关声明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
struct Node;
typedef struct Node* PtrToNode;
typedef PtrToNode CircList; // 表示指向链表的指针
typedef PtrToNode Position; // 表示指向结点的指针
typedef int ElemType; // 数据类型
// 结点的定义
typedef struct Node {
ElemType element;
Position next;
}Node;
void InitList(CircList* pprear);
bool IsEmptyList(CircList rear);
Position CreateNode(ElemType elem);
Position GetElem(CircList rear, int pos);
void InsertElem(CircList* pprear, int pos, ElemType elem);
void PushFront(CircList* ppRear, ElemType elem);
void PushBack(CircList* ppRear, ElemType elem);
ElemType DeleteElem(CircList* ppRear, int pos);
ElemType PopFront(CircList* ppRear);
ElemType PopBack(CircList* ppRear);
void ModifyElem(CircList rear, int pos, ElemType elem);
int GetLength(CircList rear);
void ClearList(CircList* ppRear);
// 非通用型
Position FirstSameElem(CircList rear, int elem);
int FirstSameElemPos(CircList rear, int elem);
int RemoveFirstSameElem(CircList* ppRear, ElemType elem);
void HeadInsert(CircList* ppRear);
bool InputInteger(int* elem);
void Print(CircList L);
二级指针
二级指针是指向指针的指针**，用来在函数中改变指针的位置。
在带有尾指针的循环单链表中尾指针始终是指向尾结点的，所以当尾结点发生改变时，如插入，删除等操作改变了尾结点，那么就要传入二级指针移动尾指针。
循环单链表的定义
struct Node; // 先定义结点的结构体，不创建模板
typedef struct Node* PtrToNode;
typedef PtrToNode CircList; // 表示指向链表的指针
typedef PtrToNode Position; // 表示指向结点的指针
typedef int ElemType; // 链表的数据类型
// 结点结构体的定义
typedef struct Node {
ElemType element;
Position next;
}Node;
循环单链表的基本通用操作
1、初始化循环单链表
因为是循环链表，初始化时只有一个头结点，所以尾指针指向的是头结点，头结点指向的还是头结点。
void InitList(CircList* ppRear)
{
(*ppRear) = (CircList)malloc(sizeof(Node)); // 创建头结点并使尾指针指向头结点
assert((*ppRear) != NULL); // 如果头结点创建失败则终止程序
(*ppRear)->next = (*ppRear); // 使头结点的下一个还是头结点，形成循环
}
2、循环单链表是否为空
单独写个函数，为了方便后面做特殊情况判断。
bool IsEmptyList(CircList rear)
{
return rear->next == rear; // 如果头结点的下一个结点还是头结点那么就是空表
}
3、创建新结点
单独写个创建新结点的函数方便以后插入相关的操作使用。
Position CreateNode(ElemType elem)
{
Position node = (Position)malloc(sizeof(Node)); // 创建新结点
if (node == NULL) // 创建失败则提示并终止程序
{
puts("Creation failed.");
exit(EXIT_FAILURE);
}
node->element = elem; // 为新节点赋值
node->next = NULL; // 不知道新节点的下一个位置，所以暂时指向NULL
return node; // 返回新结点地址
}
4、查找指定位置上的元素
查找元素时会有两个错误
1、表为空表
2、查找的位置超出范围
所以要有这两个错误的处理
查找元素时有些特殊情况
1、查找位置为0时，因为pos为0，pos<0与count<pos都不成立，所以会直接返回头结点的位置
2、查找位置为表尾时count=pos，cur为尾结点，然后会跳出while循环，这时就会返回尾结点
（rear为尾结点，尾结点下一个是头结点）
Position GetElem(CircList rear, int pos)
{
if (pos < 0) // 左越界判断
{
puts("Wrong position.");
exit(EXIT_FAILURE);
}
Position cur = rear->next; // 从头结点开始找
int count = 0; // 用来计数
// 右越界判断：如果循环了一遍链表还没找到那就代表位置越界，则终止程序
while (count < pos)
{
cur = cur->next;
count++;
// 当找到头结点时，说明已经循环完一遍链表但还没找到，代表越界了
if (cur == rear->next)
{
puts("Wrong position.");
exit(EXIT_FAILURE);
}
}
return cur; // 返回位置结点
}
5、在指定位置上插入结点
插入结点需要知道插入位置的前驱结点，这样才能将新结点连接上链表，而上面写的查找指定位置的元素函数就能帮我们做到。
void InsertElem(CircList* ppRear, int pos, ElemType elem)
{
Position prec = GetElem((*ppRear), pos - 1); // 查找前驱结点目的是为了将新结点连接上链表
Position newnode = CreateNode(elem); // 创建新结点
newnode->next = prec->next; // 将新节点连接上链表
prec->next = newnode;
if (prec == *ppRear) // 如果新节点的位置是在最后一位那么要移动尾指针指向新节点
(*ppRear) = newnode;
}
6、在首部插入新结点
要注意：如果是空表的情况要移动一次尾指针
void PushFront(CircList* ppRear, ElemType elem)
{
Position newNode = CreateNode(elem); // 创建一个新节点
newNode->next = (*ppRear)->next->next; // 使新节点指向首元结点
(*ppRear)->next->next = newNode; // 使首结点指向新节点，新节点变为新的首元结点
// 对空表插入后只有头结点和第一个结点，此时尾指针指向头结点，这时候需要将尾指针移动到第一个结点上
if ((*ppRear)->next->next == *ppRear)
*ppRear = (*ppRear)->next;
}
7、在尾部插入新结点
每次在尾部插入新结点时都要移动尾指针
void PushBack(CircList* ppRear, ElemType elem)
{
Position newNode = CreateNode(elem); // 创建一个新节点
newNode->next = (*ppRear)->next; // 使新节点指向首元结点
(*ppRear)->next = newNode; // 使尾结点指向新结点
(*ppRear) = newNode; // 移动尾指针
}
8、删除指定位置上的结点
要检查该链表是否为空表和越界问题
注意：当要删除的结点是尾结点的下一个时，GetElem函数不会报错，而是会返回尾结点，所以要做特殊越界处理
ElemType DeleteElem(CircList* ppRear, int pos)
{
if (IsEmptyList(*ppRear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
Position prec = GetElem(*ppRear, pos - 1); // 找到将被删除的结点的前驱节点
// 如果前驱结点为最后一个时GetElem函数不会报错，所以要做特殊处理
if (prec == (*ppRear))
{
puts("Wrong position.");
exit(EXIT_FAILURE);
}
Position cur = prec->next; // 标记要被删除的结点
ElemType elem = cur->element; // 标记要被删除的元素
if (cur == (*ppRear)) // 如果被删除的结点是最后一个时就要移动尾指针指向他
*ppRear = prec;
prec->next = cur->next; // 将前驱结点与被删除结点的后继结点连接在一起
free(cur); // 删除（释放）结点
return elem; // 返回被删除的元素
}
9、从头部删除元素
ElemType PopFront(CircList* ppRear)
{
if (IsEmptyList(*ppRear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
Position cur = (*ppRear)->next->next; // 标记将被删除的首元结点
ElemType elem = cur->element; // 标记将被删除的元素
(*ppRear)->next->next = cur->next; // 将首元结点改为将被删除的结点的后一个
if (cur == (*ppRear)) // 如果链表中只有一个结点，那么要将指针重新指向头结点
*ppRear = (*ppRear)->next;
free(cur); // 删除（释放）结点
return elem; // 返回被删除的元素
}
10、从尾部删除结点
每次删除结点时都要找到尾结点的前驱结点，并且移动尾指针指向它
ElemType PopBack(CircList* ppRear)
{
if (IsEmptyList(*ppRear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
Position prec = (*ppRear)->next;
Position cur = (*ppRear); // 标记将被删除的尾结点
ElemType elem = (*ppRear)->element;
while (prec->next != (*ppRear)) // 找到尾结点的前驱节点
prec = prec->next;
prec->next = (*ppRear)->next; // 将尾结点的前驱结点与头结点连接变为新的尾结点
*ppRear = prec; // 使尾指针指向新的尾结点
free(cur); // 删除（释放）结点
return elem;
}
11、修改特定位置上的元素
要做空表判断
pos为0时的结点为头结点，GetElem函数不会报错，所以要特殊处理
void ModifyElem(CircList rear, int pos, ElemType elem)
{
if (IsEmptyList(rear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
if (pos == 0) // 左越界判断
{
puts("Wrong position.");
exit(EXIT_FAILURE);
}
Position cur = GetElem(rear, pos); // 找到该结点
cur->element = elem; // 修改值
}
12、得到表长
要做空表判断
结点从首元结点开始找，如果找到头结点就代表找完一遍了文章来源：https://www.toymoban.com/news/detail-639391.html
int GetLength(CircList rear)
{
if (IsEmptyList(rear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
Position cur = rear->next->next; // 标记首元结点
int length = 0; // 用来计数
while (cur != rear->next) // 找到头结点时代表找完一遍，结束循环
{
cur = cur->next;
length++;
}
return length;
}
13、清空链表
要做空表判断
借用尾指针找到一个元素，用cur记录这个元素，尾指针指向下一个元素，再释放cur，直到尾指针重新指向头结点
最后使头结点指向头结点形成空表文章来源地址https://www.toymoban.com/news/detail-639391.html
void ClearList(CircList* ppRear)
{
if (IsEmptyList(*ppRear)) // 空表则中断程序
{
puts("The list is empty.");
exit(EXIT_FAILURE);
}
Position head = (*ppRear)->next; // 记录头结点位置
*ppRear = head->next; // 将指针移动到首元结点
// 记录指针指向的结点，让指针指向下一个结点，释放被记录的结点，直到指针指向头结点
while ((*ppRear) != head)
{
Position cur = (*ppRear);
*ppRear = cur->next;
free(cur);
}
(*ppRear)->next = (*ppRear); // 变回只有头结点的循环单链表
}
到了这里，关于带头结点和尾指针的循环单链表（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
