带头节点循环单链表【详细解析+完整代码】-爱代码爱编程
文章目录
前言
循环单链表在单链表的基础上进行改进。思考一下，普通单链表从表头遍历到表尾，时间复杂度为o(n)，如果我想从表尾找到表头呢？时间复杂度也还是o(n)。怎么快速从表尾找到表头，于是引入了循环链表。整个链表形成闭环，表尾找到表头，时间复杂度为o(1)。
循环单链表定义
循环单链表是首尾相连的一种单链表，即将最后一个结点的空指针改为指向头结点或第一个结点的形成一个环型，最后一个结点称为尾指针:tail。判断单链表为空的条件是 head->next == NULL，而判断循环单链表为空的条件是 head->next == head。访问第一个结点即tail->next->next（带头结点的情况）。
循环对比非循环
优势
对单向链表中任一个节点的访问都需要从头结点开始；而对单向循环链表从任意节点出发都能遍历整个列表，极大的增强了其灵活性。
修改
-
判断是否为空：
单向链表：如果头结点指向空，那么为空链表
单向循环链表：如果头结点指向自身，那么为空链表 -
判断是否为尾结点
单向链表：指向空的节点为尾结点
单向循环链表：指向头结点的节点为尾结点
循环单链表操作
循环链表的插入，删除算法与单链表基本一直，所不同的是若操作在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。
初始化
申请一个头结点，头结点的next指针指向自己达到循环的性质。
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
L->next = L;
return true;
}
建立链表
头插法
循环和非循环单链表的头插法是一样的，不用修改代码。
LinkList List_HeadInsert(LinkList& L) {
InitList(L);
LNode* HeadNode = L;
LNode* NewNode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) {
NewNode = (LNode*)malloc(sizeof(LNode));
NewNode->data = x;
NewNode->next = HeadNode->next;
HeadNode->next = NewNode;
scanf_s("%d", &x);
}
return L;
}
尾插法
循环单链表的尾插法是一样的，只用修改非循环单链表的一句代码。就是尾指针的指向，以前指向NULL，现在指向头结点。
LinkList List_TailInsert(LinkList& L) {
InitList(L);
LNode* NewNode, * TailNode = L;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) {
NewNode = (LNode*)malloc(sizeof(LNode));
NewNode->data = x;
TailNode->next = NewNode;
TailNode = NewNode;
scanf_s("%d", &x);
}
TailNode->next = L;
return L;
}
打印链表
循环单链表相当于一个环，遍历的话就是进入死循环，所以找到遍历一圈的条件，跳出循环即可。
void PrintList(LinkList L) {
LNode* p = L->next;
if (p == L) {
printf("空链表\n");
}
else {
printf("遍历链表:");
while (p!=L) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
链表长度
也就是遍历链表，记录结点数量。
int Length(LinkList L) {
LNode* p = L->next;
int len = 0;
while (p!=L) {
p = p->next;
len++;
}
return len;
}
查找操作
循环单链表查找操作和单链表一致
按值查找
LNode* LocateElem(LinkList L, int x) {
LNode* p = L->next;
while (p!=L && p->data != x) {
p = p->next;
}
return p;
}
按位查找
LNode* GetElem(LinkList L, int i) {
LNode* p = L;
int j = 0;
if (i<0 || i>Length(L)) {
printf("输入不合法\n");
return NULL;
}
while (j < i){
p = p->next;
j++;
}
return p;
}
插入操作
插入操作也是和单链表一样。将值为x的新结点插入到单链表L的第i个位置上。从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后利用前插操作，令新结点s的指针域指向p的后继结点，再令结点p的指针域指向新结点s。
bool Insert(LinkList& L, int i, int x) {
if (i < 1 || i>Length(L)) {
printf("输入不合法\n");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
删除操作
删除结点
将单链表的第 i 个结点删除。先检查删除位置的合法性，然后从头开始遍历，找到i的前驱结点p，被删除结点为s，修改p的指针域，将其指向s的下一个结点，最后再释放结点s的存储空间。
bool Delete(LinkList& L, int i)
{
if (i < 1 || i>Length(L)) {
printf("输入不合法\n");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* q = p->next;
p->next = q->next;
free(q);
return true;
}
销毁链表
重复删除第一个结点，直到删完剩下头结点，最后释放头结点。
void DestoryList(LinkList& L) {
while (L->next !=L)
{
Delete(L, 1);
L = L->next;
}
free(L);
printf("链表已销毁\n");
}
判空
这就是与单链表不同之处，L -> next == NULL 修改为 L -> next == L
bool IsEmpty(LinkList& L)
{
if (L->next == L) return true;
else return false;
}
判尾
循环单链表把整个链表连成一个环，表尾和表头相连接，如果结点next指针指向头结点便是表尾
bool IsTail(LinkList& L,LNode *p)
{
if (p->next == L) return true;
else return false;
}
完整代码及实列
完整代码
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
L->next = L;
return true;
}
LinkList List_HeadInsert(LinkList& L) { //逆序创建链表
InitList(L); //初始化链表
LNode* HeadNode = L;
LNode* NewNode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) { //输入0表示结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
NewNode->next = HeadNode->next; //头插核心
HeadNode->next = NewNode;
scanf_s("%d", &x);
}
return L;
}
LinkList List_TailInsert(LinkList& L) { //顺序创建链表
InitList(L);
LNode* NewNode, * TailNode = L;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) { //输入0结束
NewNode = (LNode*)malloc(sizeof(LNode)); //创建新结点
NewNode->data = x;
TailNode->next = NewNode; //尾插核心
TailNode = NewNode;
scanf_s("%d", &x);
}
TailNode->next = L; //尾指针指向NULL
return L;
}
//遍历操作
void PrintList(LinkList L) {
LNode* p = L->next;
if (p == L) {
printf("空链表\n");
}
else {
printf("遍历链表:");
while (p!=L) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int Length(LinkList L) {
LNode* p = L->next;
int len = 0;
while (p!=L) {
p = p->next;
len++;
}
return len;
}
LNode* LocateElem(LinkList L, int x) {
LNode* p = L->next;
while (p!=L && p->data != x) {
p = p->next;
}
return p;
}
LNode* GetElem(LinkList L, int i) {
LNode* p = L;
int j = 0;
if (i<0 || i>Length(L)) {
printf("输入不合法\n");
return NULL;
}
while (j < i)
{
p = p->next;
j++;
}
return p;
}
//将x插入到单链表L的第i个位置上
bool Insert(LinkList& L, int i, int x) {
if (i < 1 || i>Length(L)) {
printf("输入不合法\n");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
bool Delete(LinkList& L, int i)
{
if (i < 1 || i>Length(L)) {
printf("输入不合法\n");
return false;
}
LNode* p = GetElem(L, i - 1);
LNode* q = p->next;
p->next = q->next;
free(q);
return true;
}
void DestoryList(LinkList& L) {
while (L->next !=L)
{
Delete(L, 1);
L = L->next;
}
free(L);
printf("链表已销毁\n");
}
bool IsEmpty(LinkList& L)
{
if (L->next == L) return true;
else return false;
}
bool IsTail(LinkList& L,LNode *p)
{
if (p->next == L) return true;
else return false;
}
int main()
{
LinkList L;
InitList(L);
printf("头插建立链表\n");
List_HeadInsert(L);
PrintList(L);
printf("插入99到第2位\n");
Insert(L, 2, 99);
PrintList(L);
printf("删除第1位\n");
Delete(L, 1);
PrintList(L);
printf("\n\n尾插建立链表\n");
List_TailInsert(L);
PrintList(L);
printf("插入99到第1位\n");
Insert(L, 1, 99);
PrintList(L);
printf("删除第1位\n");
Delete(L, 1);
PrintList(L);
}
测试结果
头插建立链表
输入链表元素（以0结束）：
1 2 3 4 5 6 7 0
遍历链表:7 6 5 4 3 2 1
插入99到第2位
遍历链表:7 99 6 5 4 3 2 1
删除第1位
遍历链表:99 6 5 4 3 2 1
尾插建立链表
输入链表元素（以0结束）:
1 2 3 4 5 6 7 0
遍历链表:1 2 3 4 5 6 7
插入99到第1位
遍历链表:99 1 2 3 4 5 6 7
删除第1位
遍历链表:1 2 3 4 5 6 7