数据结构--循环链表

目录

1.为什么要有循环链表

2.定义

3.循环链表和单链表的图示对比

4.循环链表和单链表的代码对比

5.循环链表的操作

1.clist.h

2.clist.cpp

1.初始化plist

2.往plist中头部插入数字val

3.往plist中的尾部插入数字val

4.在plist中查找val值,找到返回该节点地址,失败返回NULL

5.删除plist中的第一个val

6.判断plist是否为空链表(没有数据节点)

7.获取plist长度,数据节点的个数

8.获取plist链表的pos位置的值

9.获取val的前驱

10.获取val的后继

11.输出plist的所有数据

---

1.为什么要有循环链表

在单链表中我们是把结点遍历一遍后就结束了，为了使表处理更加方便灵活，我们希望通过任意一个结点出发都可以找到链表中的其它结点,因此我们引入了循环链表。

2.定义

将单链表中终端结点的指针端由空指针改为头结点，就使整个单链表形成了一个环，这种头尾相接的单链表称为循环链表。

简单理解就是形成一个闭合的环，在环内寻找自己需要的结点。

3.循环链表和单链表的图示对比

单链表：

 循环链表：

4.循环链表和单链表的代码对比

单链表：

typedef struct Node{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型
	struct Node *next; //指针域
}LNode, *LinkList;

循环链表：

typedef struct CNode//循环链表节点
{
	ElemType data;//数据
	struct CNode* next;//后继指针
}CNode ,*CList;

5.循环链表的操作

//带头结点的循环链表,其尾节点的后继为头结点(不是NULL)
//节点的结构和单链表一样

1.clist.h

#pragma once
 
typedef int ElemType;
 
typedef struct CNode//循环链表节点
{
	ElemType data;//数据
	struct CNode* next;//后继指针
}CNode ,*CList;
 
//初始化plist
void InitList(CList plist);
 
//往plist中头部插入数字val
bool Insert_head(CList plist, ElemType val);
 
//往plist中的尾部插入数字val
bool Insert_tail(CList plist, ElemType val);
 
//在plist中查找val值,找到返回该节点地址,失败返回NULL
CNode* Search(CList plist, ElemType val);
 
//删除plist中的第一个val
bool DeleteVal(CList plist, ElemType val);
 
//判断plist是否为空链表(没有数据节点)
bool IsEmpty(CList plist);
 
//获取plist长度,数据节点的个数
int GetLength(CList plist);
 
//获取plist链表的pos位置的值
bool GetElem(CList plist, int pos, int* rtval);//rtval:输出参数
 
//获取val的前驱
CNode* Prior(CList plist, ElemType val);
 
//获取val的后继
CNode* Next(CList plist, ElemType val);
 
//输出plist的所有数据
void Show(CList plist);
 
//清空数据
void Clear(CList plist);
 
//销毁
void Destroy(CList plist);

2.clist.cpp

1.初始化plist

oid InitList(CList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return;
	//数据域不使用
	plist->next = plist;
}

2.往plist中头部插入数字val

这里我们需要思考一下当链表为空时是否适用：这里明确告诉大家不管是否是空链表，这两行代码均可以使用，下面给大家用示意图表示一下；
不是空链：

 是空链：

 

bool Insert_head(CList plist, ElemType val)
{
	//1.动态申请一个新的节点
	CNode* p = (CNode*)malloc(sizeof(CNode));
	assert(p != NULL);
	if (p == NULL)
		return false;
	//2.把数据存放在新节点中
	p->data = val;
 
	//3.把新节点插入在头结点后面
	p->next = plist->next;
	plist->next = p;
 
	return true;
}

3.往plist中的尾部插入数字val

bool Insert_tail(CList plist, ElemType val)
{
	//1.创建新节点并赋值
	CNode* p = (CNode*)malloc(sizeof(CNode));
	assert(p != NULL);
	if (p == NULL)
		return false;
	p->data = val;
 
	//2.找到尾节点
	CNode* q;
	for (q = plist; q->next != plist; q = q->next)
		;
		
	//3.插入新节点.把p插入在q的后面
	p->next = q->next;
	q->next = p;
 
	return true;
}

与单向链表的插入不同，循环单链表插入时只能往表头节点的后面插入，由初始结构可知，想完成插入操作，必须先找到要插入位置的前一个节点，然后修改相应指针即可完成操作。

 

 

4.在plist中查找val值,找到返回该节点地址,失败返回NULL

CNode* Search(CList plist, ElemType val)
{
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		if (p->data == val)
			return p;
	}
	return NULL;
}

5.删除plist中的第一个val

bool DeleteVal(CList plist, ElemType val)
{
	CNode* p = Prior(plist, val);
	if (p == NULL)
		return false;
	CNode* q = p->next;//保存需要删除的节点
	p->next = q->next;//剔除q
	free(q);//释放节点
 
	return true;
}

6.判断plist是否为空链表(没有数据节点)

bool IsEmpty(CList plist)
{
	return plist->next == plist;
}

7.获取plist长度,数据节点的个数

int GetLength(CList plist)
{
	int count = 0;//计数器
	for (CNode* p = plist->next; p != plist; p = p->next)
		count++;
 
	return count;
}

8.获取plist链表的pos位置的值

bool GetElem(CList plist, int pos, int* rtval)//rtval:输出参数
{
	if (pos < 0 || pos >= GetLength(plist))
		return false;
 
	CNode* p = plist->next;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
 
	*rtval = p->data;
	return true;
}

9.获取val的前驱

CNode* Prior(CList plist, ElemType val)
{
	for (CNode* p = plist; p->next != plist; p = p->next)
	{
		if (p->next->data == val)
			return p;
	}
	return NULL;
}

10.获取val的后继

CNode* Next(CList plist, ElemType val)
{
	CNode* p = Search(plist,val);
	if (p == NULL)
		return NULL;
 
	return p->next;
}

11.输出plist的所有数据

void Show(CList plist)
{
	//从头到尾遍历数据节点
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		printf("%d ",p->data);
	}
	printf("\n");
}

#include 
#include "clist.h"
//#include //需要安装vld
 
int main()
{
	CNode head;//循环链表的表头节点
	InitList(&head);
	
	for (int i = 0; i < 10; i++)
	{
		Insert_head(&head,i);//9 8 7 6 5 4 3 2 1 0
		Insert_tail(&head,i);//0,1,2,3,4,5,6,7,8,9
	}
	Show(&head);
	CNode* p;
	for (int i = -1; i < 12; i++)
	{
		if ((p = Search(&head, i)) != NULL)
		{
			printf("%d找到了\n",i);
		}
		else
		{
			printf("%d没有找到\n",i);
		}
	}
 
	//for (int i = -1; i < 11; i++)
	//{
	//	DeleteVal(&head,i);
	//}
 
	int val;
	GetElem(&head,3,&val);
	printf("%d\n",val);
 
	Show(&head);
	Destroy(&head);
	//Destroy(&head);
 
	return 0;
}