【数据结构】循环链表

文章目录

1.概念
2.循环链表的头文件与函数声明
3.函数实现
4.循环链表的源文件与函数实现

1.概念

循环链表：和单链表唯一的区别：尾节点保留着头节点的地址

在这里插入图片描述
循环链表的特点：

1. 尾节点可以找到头节点
2. 头节点不能找到尾节点
3. 如果没有有效数据节点（空链），头节点指向自身

注意，循环链表，for循环去遍历，判断表达式不再是p->next!=NULL,而是p->next!=plist

2.循环链表的头文件与函数声明

#pragma once

typedef int ELEM_TYPE;
//循环链表有效数据节点结构体设计：


typedef struct CNode
{
	ELEM_TYPE data;//数据域
	struct CNode* next;//指针域
}CNode, *PCNode;


//有关循环链表的操作函数：

//初始化
void Init_clist(struct CNode* plist);

//购买节点
struct CNode* BugNode(ELEM_TYPE val);

//头插
bool Insert_head(PCNode plist, ELEM_TYPE val);

//尾插
bool Insert_tail(PCNode plist, ELEM_TYPE val);

//按位置插  pos=0  头插  
bool Insert_pos(PCNode plist, int pos, ELEM_TYPE val);

//头删
bool Del_head(PCNode plist);

//尾删
bool Del_tail(PCNode plist);

//按位置删  pos=0  头删  
bool Del_pos(PCNode plist, int pos);

//按值删除
bool Del_val(PCNode plist, ELEM_TYPE val);

//查找
struct CNode* Search(PCNode plist, ELEM_TYPE val);

//判空
bool Is_Empty(PCNode plist);
//判满  循环链表也不需要判满

//获取有效元素个数
int Get_length(PCNode plist);

//清空
void Clear(PCNode plist);

//销毁1
void Destroy(PCNode plist);

//销毁2
void Destroy2(PCNode plist);

//打印
void Show(PCNode plist);

3.函数实现

3.1 购买节点

从堆区申请一块内存，返回给指针

//购买节点
struct CNode* BuyNode(ELEM_TYPE val)
{
	//assert
	struct CNode* pnewnode = (struct CNode*)malloc(1 * sizeof(struct CNode));
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return NULL;
	}

	pnewnode->data = val;
	pnewnode->next = NULL;
	return pnewnode;
}

3.2 初始化函数（重点）

使头节点的next域指向自身（单链表是指向NULL）

void Init_clist(struct CNode* plist)
{
	//assert
	//plist->data;   数据域不需要处理
	//plist->next = NULL;//单链表的写法
	plist->next = plist;//循环链表的写法   

}

3.3 判空函数

如果头节点的next域等于自身的话，就代表着链表为NULL；

void Init_clist(struct CNode* plist)
{
	//assert
	//plist->data;   数据域不需要处理
	//plist->next = NULL;//单链表的写法
	plist->next = plist;//循环链表的写法   

}

3.4 获取有效数据个数

利用一个指针 p，从第一个有效数据节点开始遍历，每次遍历计数器+1；
直到 p 等于头指针结束，返回计数器的值

//获取有效元素个数
int Get_length(PCNode plist)
{
	//assert
	int count = 0;
	for(struct CNode *p=plist->next; p!=plist; p=p->next)
	{
		count++;
	}
	return count;
}

3.5 头插函数

直接使用单链表头插法
首先通过 **malloc（）**函数申请一个节点，保存val值
然后把头节点指向的next的地址赋值给 s->next
最后把s 的地址赋值给头节点的next域
在这里插入图片描述

//头插
bool Insert_head(PCNode plist, ELEM_TYPE val)
{
	//assert

	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置  头插不需要特意去找合适的插入位置
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;

	return true;
}

3.6尾插（重点）

首先用指针p遍历循环链表，使p指向尾节点的位置，然后用**buynode（）**函数申请一个节点
此时的 p->next 是头节点
我们把 p->next 赋值给新节点的next域
在这里插入图片描述
然后把s的地址赋值给 p->next 域完成尾插

//尾插
bool Insert_tail(PCNode plist, ELEM_TYPE val)
{
	//assert

	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置
	struct CNode* p;
	for(p=plist; p->next!=plist; p=p->next);//用上面的for循环  让p停留在尾结点
	//此时 p指向尾结点

	//3.插入
	pnewnode->next = p->next;
	p->next =pnewnode;
	return true;
}

3.7 按位置插入

首先判断 pos位置的合法性，pos必须大于等于0 且pos 不能大于链表有效值个数
然后按照单链表方式插入

//按位置插  pos=0  头插  
bool Insert_pos(PCNode plist, int pos, ELEM_TYPE val)
{
	assert(plist != NULL);//保证循环链表存在
	assert(pos >=0 && pos<=Get_length(plist));


	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置
	struct CNode *p = plist;
	for(int i=0; i<pos; i++)
	{
		p=p->next;
	}
	//此时 p指向待插入位置的前一个节点

	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

3.8 头删

先判空，然后删除链表中第一个有效数据节点
方法如同单链表

//头删
bool Del_head(PCNode plist)
{
	//assert
	//删除需要判空 
	if(Is_Empty(plist))
	{
		return false;
	}

	struct CNode *p = plist->next;
	plist->next = p->next;//plist->next = plist->next->next;
	free(p);

	return true;
}

3.9 尾删（重点）

使用两个指针分别向后跑一个指向最后一个节点，一个指向最后一个节点的前一个节点，有两种方案：
第一种：
先找p，再找q，先让p遍历链表直到 p->next==plist 说明p已经到了尾节点
然后让q遍历链表，直到 q->next == p ，此时q指向的是尾指针的前一个节点
然后使倒数第二个节点的next 指向头指针 plist ，然后释放p（曾经的尾节点）
在这里插入图片描述

//尾删
bool Del_tail(PCNode plist)
{
	//assert plist!=NULL
	if(Is_Empty(plist)) //如果不空，那至少有一个有效数据
	{
		return false;
	}

	//让p和q找到合适的位置：
	/*//第一种方案：先找p，再找q
	struct CNode *p = plist;
	for(p; p->next!=plist; p=p->next);//此时for循环结束，p指向尾结点

	struct CNode *q= plist;
	for(q; q->next!=p; q=q->next);//此时for循环结束，q在p前面
	*/
	//第二种方案：先找q，再直接让p=q->next即可
	struct CNode *q = plist;
	for(q; q->next->next!=plist; q=q->next);//q->  和 q->next->  没有风险，前面排除过了
	//此时for循环结束，q在倒数第二个节点
	struct CNode *p = q->next; 

	//跨越指向，再接着释放待删除节点
	q->next = p->next;//q->next = q->next->next;
	free(p);
	return true;

}

3.10 按位置删除节点

首先判断 pos位置的合法性，pos必须大于等于0 且pos 不能大于链表有效值个数
然后按照单链表方式删除
在这里插入图片描述

//按位置删  pos=0  头删  
bool Del_pos(PCNode plist, int pos)
{
	assert(plist != NULL);
	assert(pos >=0 && pos<Get_length(plist));
	if(Is_Empty(plist))
	{
		return false;
	}

	//让p和q找到合适的位置：
	struct CNode *q = plist;
	for(int i=0; i<pos; i++)
	{
		q = q->next;
	}
	struct CNode *p = q->next; 

	//跨越直线，释放待删除节点
	q->next = p->next;
	free(p);
	return true;
}

3.11 查找

遍历链表，与单链表相同

//查找
struct CNode* Search(PCNode plist, ELEM_TYPE val)
{
	//assert
	for(struct CNode *p=plist->next; p!=plist; p=p->next)
	{
		if(p->data == val)
		{
			return p;
		}
	}

	return NULL;
}

3.12 按值删除

先调用 **Search（）**找到要删除节点的地址
然后删除，与单链表方法相同

//按值删除
bool Del_val(PCNode plist, ELEM_TYPE val)
{
	//assert
	if(Is_Empty(plist))
	{
		return false;
	}


	struct CNode *p = Search(plist, val);
	if(p == NULL)
	{
		return false;
	}
	//此时，如果p不为NULL，代表val值存在，且p现在指向它

	//在让q找到p的前一个节点  
	struct CNode *q = plist;
	for(q; q->next!=p; q=q->next);


	//跨越指向，释放待删除节点
	q->next = p->next;
	free(p);
	return true;
}

3.13 销毁

3.13.1 销毁1

借助头节点进行无限头删，直到头节点的plist->next = plist
类似单链表

void Destroy(PCNode plist)
{
	//assert

	while(plist->next != plist)
	{
		struct CNode *p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = plist;
}

3.13.2 销毁2

提前踢出去头节点，借助两个临时指针
使p指向第一个节点，ps->next = NULL
在这里插入图片描述

当p！=plist的时候使q = p->next; 然后释放p
在这里插入图片描述

然后使 p = q
在这里插入图片描述

此时完成一次循环
再使 p = p->next; free（q）;
在这里插入图片描述

直到 p ==plist 的时候结束循环；此时销毁完成

//销毁2（不借助头结点，有两个临时指针）
void Destroy2(PCNode plist)
{
	//assert plsit!=NULL
	struct CNode *p = plist->next; 
	struct CNode *q = NULL;
	
	plist->next = plist;

	while(p != plist)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

4.循环链表的源文件与函数实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "clist.h"

/*
注意事项：
1.尾可以找到头，但是头不能找到尾
2.如果循环链表是一个空链，头结点的指针域指向自身
3.注意，循环链表，for循环去遍历，判断表达式不再是p->next!=NULL,而是p->next!=plist
*/
/*
for(struct Node* p=plist; p->next!=NULL; p=p->next)//上面for循环用于需要前驱的操作：比如插入删除
for(struct Node* p=plsit->next; p!=NULL; p=p->next)//下面for循环用于不需要前驱的操作：比如查找，找有效值个数，打印
*/

//有关循环链表的操作函数：
//初始化
void Init_clist(struct CNode* plist)
{
	//assert
	//plist->data;   数据域不需要处理
	//plist->next = NULL;//单链表的写法
	plist->next = plist;//循环链表的写法   

}

//购买节点
struct CNode* BuyNode(ELEM_TYPE val)
{
	//assert
	struct CNode* pnewnode = (struct CNode*)malloc(1 * sizeof(struct CNode));
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return NULL;
	}

	pnewnode->data = val;
	pnewnode->next = NULL;
	return pnewnode;
}

//头插
bool Insert_head(PCNode plist, ELEM_TYPE val)
{
	//assert

	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置  头插不需要特意去找合适的插入位置
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;

	return true;
}

//尾插
bool Insert_tail(PCNode plist, ELEM_TYPE val)
{
	//assert

	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置
	struct CNode* p;
	for(p=plist; p->next!=plist; p=p->next);//用上面的for循环  让p停留在尾结点
	//此时 p指向尾结点

	//3.插入
	pnewnode->next = p->next;
	p->next =pnewnode;
	return true;
}

//按位置插  pos=0  头插  
bool Insert_pos(PCNode plist, int pos, ELEM_TYPE val)
{
	assert(plist != NULL);//保证循环链表存在
	assert(pos >=0 && pos<=Get_length(plist));


	//1.购买新节点
	struct CNode *pnewnode = BuyNode(val);
	assert(pnewnode != NULL);
	if(pnewnode == NULL)
	{
		return false;
	}

	//2.找到合适的插入位置
	struct CNode *p = plist;
	for(int i=0; i<pos; i++)
	{
		p=p->next;
	}
	//此时 p指向待插入位置的前一个节点

	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}
//头删
bool Del_head(PCNode plist)
{
	//assert
	//删除需要判空 
	if(Is_Empty(plist))
	{
		return false;
	}

	struct CNode *p = plist->next;
	plist->next = p->next;//plist->next = plist->next->next;
	free(p);

	return true;
}

//尾删
bool Del_tail(PCNode plist)
{
	//assert plist!=NULL
	if(Is_Empty(plist)) //如果不空，那至少有一个有效数据
	{
		return false;
	}

	//让p和q找到合适的位置：
	/*//第一种方案：先找p，再找q
	struct CNode *p = plist;
	for(p; p->next!=plist; p=p->next);//此时for循环结束，p指向尾结点

	struct CNode *q= plist;
	for(q; q->next!=p; q=q->next);//此时for循环结束，q在p前面
	*/
	//第二种方案：先找q，再直接让p=q->next即可
	struct CNode *q = plist;
	for(q; q->next->next!=plist; q=q->next);//q->  和 q->next->  没有风险，前面排除过了
	//此时for循环结束，q在倒数第二个节点
	struct CNode *p = q->next; 

	//跨越指向，再接着释放待删除节点
	q->next = p->next;//q->next = q->next->next;
	free(p);
	return true;

}

//按位置删  pos=0  头删  
bool Del_pos(PCNode plist, int pos)
{
	assert(plist != NULL);
	assert(pos >=0 && pos<Get_length(plist));
	if(Is_Empty(plist))
	{
		return false;
	}

	//让p和q找到合适的位置：
	struct CNode *q = plist;
	for(int i=0; i<pos; i++)
	{
		q = q->next;
	}
	struct CNode *p = q->next; 

	//跨越直线，释放待删除节点
	q->next = p->next;
	free(p);
	return true;
}

//按值删除
bool Del_val(PCNode plist, ELEM_TYPE val)
{
	//assert
	if(Is_Empty(plist))
	{
		return false;
	}


	struct CNode *p = Search(plist, val);
	if(p == NULL)
	{
		return false;
	}
	//此时，如果p不为NULL，代表val值存在，且p现在指向它

	//在让q找到p的前一个节点  
	struct CNode *q = plist;
	for(q; q->next!=p; q=q->next);


	//跨越指向，释放待删除节点
	q->next = p->next;
	free(p);
	return true;
}


//查找
struct CNode* Search(PCNode plist, ELEM_TYPE val)
{
	//assert
	for(struct CNode *p=plist->next; p!=plist; p=p->next)
	{
		if(p->data == val)
		{
			return p;
		}
	}

	return NULL;
}

//判空
bool Is_Empty(PCNode plist)
{
	return plist->next == plist;
}
//判满  循环链表也不需要判满

//获取有效元素个数
int Get_length(PCNode plist)
{
	//assert
	int count = 0;
	for(struct CNode *p=plist->next; p!=plist; p=p->next)
	{
		count++;
	}
	return count;
}

//清空
void Clear(PCNode plist)
{
	Destroy(plist);
}

//销毁1(借助头结点，无限头删)
void Destroy(PCNode plist)
{
	//assert

	while(plist->next != plist)
	{
		struct CNode *p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = plist;
}

//销毁2（不借助头结点，有两个临时指针）
void Destroy2(PCNode plist)
{
	//assert plsit!=NULL
	struct CNode *p = plist->next; 
	struct CNode *q = NULL;
	
	plist->next = plist;

	while(p != plist)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

//打印
void Show(PCNode plist)
{
	//assert
	for(struct CNode *p=plist->next; p!=plist; p=p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");

}