C语言循环链表的原理与使用操作

 

一.引入

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

 

二.循环链表的定义

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

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

 

三.单链表与循环链表对比

3.1图示对比

单链表:

循环链表:

3.2代码对比

单链表:

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

循环链表:

typedef int ELEMTYPE;
typedef struct Clist
{
	ELEMTYPE data; //数据域   存放数据
	struct Clist* next;
//指针域存放下一个节点的地址(尾结点的next保存头结点的地址)
}Clist, * PClist;

 

四.循环链表的操作

循环链表是单链表中扩展出来的结构,所以有很多的操作是和单链表相同的,如求长度,查找元素,获取一个元素,这里我们对循环链表进行初始化,创建,插入,删除,销毁的一系列操作。

4.1循环链表的初始化

单链表和循环链表初始化对比如下:

单链表循环链表
数据域不处理数据域不处理
next域赋值为NULLnext域赋值为头结点自身的地址

代码如下:

void InitClist(struct Clist* plist)
{
	//assert
	//plist->data; // 数据域不处理
	plist->next = plist;
}

4.2循环链表的建立

循环链表的建立是基于单链表所以也有头插和尾插两种方式。

4.2.1头插法建立循环链表

头插法建立循环链表的主要是这两行代码:

pnewnode->next=plist->next;
plist->next=pnewnode;

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

不是空链:

是空链:

代码如下:

bool Insert_head(PClist plist, ELEMTYPE val)
{
	//assert
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置  (头插  不用找)
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}

4.2.2尾插法建立循环链表

尾插法建立循环链表主要代码如下:

for(p=plist;p->next!=plist;p=p->next);

代码如下:

bool Insert_tail(PClist plist, ELEMTYPE val)
{
	//assert
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置(通过带前驱的for循环)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此时 for循环执行结束   p指向尾结点
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

4.3循环链表的插入操作

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

bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
	assert(plist != NULL);
	assert(pos >= 0 && pos <= Get_length(plist));
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置(通过带前驱的for循环)
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此时 for循环执行结束   p指向待插入的合适位置
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

4.4循环链表的删除操作

循环链表的删除操作相当于单链表的删除操作,主要分为以下三个步骤:

  • 指针p指向待删除的结点;
  • 指针q指向待删除结点的前一个结点;
  • 跨越指向。
void Delete(list **pNode,int place)  //删除操作
{
	list *temp,*target;
	int i;
	temp=*pNode;
	if(temp==NULL)				//首先判断链表是否为空
	{
		printf("这是一个空指针 无法删除\n");
		return;
	}
	if(place==1)		//如果删除的是头节点	
	{				//应当特殊处理,找到尾节点,使尾节点的next指向头节点的下一个节点
                  // rear->next=(*head)->next;然后让新节点作为头节点,释放原来的头节点
		for(target=*pNode;target->next!=*pNode;target=target->next);
		temp=*pNode;
		
		*pNode=(*pNode)->next;
		target->next=*pNode;
		free(temp);
	}
	else //删除其他节点
	{		//首先找出尾节点
		for(i=1,target=*pNode;target->next!=*pNode&&i!=place-1;target=target->next,i++); 
		if(target->next==*pNode)		//判断要删除的位置是否大于链表长度,若大于链表长度,        
                                      //特殊处理直接删除尾节点
		{
              //找出尾节的前一个节点
			for(target=*pNode;target->next->next!=*pNode;target=target->next);
			temp=target->next;	 //	尾节点的前一个节点直接指向头节点  释放原来的尾节点									
			target->next=*pNode;
			printf("数字太大删除尾巴\n");
			free(temp);
		}
		else
		{
			temp=target->next;//  删除普通节点  找到要删除节点的前一个节点target,
                              //使target指向要删除节点的下一个节点  转存删除节点地址
			target->next=temp->next;	//  然后释放这个节点
			free(temp);
		}
	}
}

4.5循环链表的销毁

循环链表这里有两种销毁方式:

4.5.1无限头删

void Destroy1(PClist plist)
{
	//assert
	while (plist->next != plist)
	{
		struct Clist* p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = plist;
}

4.5.2两个指针变量

void Destroy2(PClist plist)
{
	//assert
	struct Clist* p = plist->next;
	struct Clist* q = NULL;
	plist->next = plist;
	while (p != plist)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

4.6其他操作

循环链表还有查找值,判空,求链表长度,清空等一系列操作,这些操作与单链表那的操作基本相同,这里不进行详细赘述,在后面的完整代码中会写出来。

 

五.总结

循环链表相对于单链表来说会稍微复杂一点,主要思想还是和单链表差不多的,只不过是将链表的首位进行相连,但是正是因为首尾的相连,便于我们通过任意一个结点出发都可以找到链表中的其它结点。

 

六.全部代码

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
//循环链表里边很少出现NULL, nullptr
//初始化
void InitClist(struct Clist* plist)
{
	//assert
	//plist->data; // 数据域不处理
	plist->next = plist;
}
//头插
bool Insert_head(PClist plist, ELEMTYPE val)
{
	//assert
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置  (头插  不用找)
	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}
//尾插
bool Insert_tail(PClist plist, ELEMTYPE val)
{
	//assert
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置(通过带前驱的for循环)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此时 for循环执行结束   p指向尾结点
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}
//按位置插
bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
	assert(plist != NULL);
	assert(pos >= 0 && pos <= Get_length(plist));
	//1.购买新节点
	struct Clist* pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
	assert(pnewnode != NULL);
	pnewnode->data = val;//购买的新节点  处理完毕
	//2.找到插入位置(通过带前驱的for循环)
	struct Clist* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//此时 for循环执行结束   p指向待插入的合适位置
	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}
//头删
bool Del_head(PClist plist)
{
	//assert
	if (IsEmpty(plist))//不空  则至少存在一个有效值
	{
		return false;
	}
	//1.指针p指向待删除节点
	struct Clist* p = plist->next;
	//2.指针q指向待删除节点的前一个节点
	//q 就是 头结点  这里就不再额外处理
	//3.跨越指向
	plist->next = p->next;
	free(p);
	return true;
}
//尾删
bool Del_tail(PClist plist)
{
	//assert
	if (IsEmpty(plist))//不空  则至少存在一个有效值
	{
		return false;
	}
	//1.指针p指向待删除节点(尾删的话,这里指向尾结点)
	struct Clist* p = plist;
	for (p; p->next != plist; p = p->next);
	//此时 for指向结束  代表着p指向尾结点
	//2.指针q指向倒数第二个节点
	struct Clist* q = plist;
	for (q; q->next != p; q = q->next);
	//此时 for指向结束  代表着q指向p的上一个节点
	//3.跨越指向
	q->next = p->next;
	free(p);
	return true;
}
//按位置删
bool Del_pos(PClist plist, int pos)
{
	assert(plist != NULL);
	assert(pos >= 0 && pos < Get_length(plist));
	if (IsEmpty(plist))
	{
		return false;
	}
	//1.指针p指向待删除节点
	//2.指针q指向待删除节点的上一个节点
	//这里采用第二种方案找pq,先找q再找p
	struct Clist* q = plist;
	for (int i = 0; i < pos; i++)
	{
		q = q->next;
	}
	struct Clist* p = q->next;
	//3.跨越指向
	q->next = p->next;
	free(p);
	return true;
}
//按值删除
bool Del_val(PClist plist, ELEMTYPE val)
{
	//assert
	struct Clist* p = Search(plist, val);
	if (p == NULL)
	{
		return false;
	}
	struct Clist* q = plist;
	for (q; q->next != p; q = q->next);
	q->next = p->next;
	free(p);
	return true;
}
//查找(如果查找到,需要返回找到的这个节点的地址)
struct Clist* Search(struct Clist* plist, ELEMTYPE val)
{
	//assert
	for (struct Clist* p = plist->next; p != plist; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return NULL;
}
//判空
bool IsEmpty(PClist plist)
{
	//assert
	return plist->next == plist;
}
//判满(循环链表不需要这个操作)
//获取长度
/*指针p从头结点的下一个节点开始向后跑,如果p再次遇到了头结点,
证明p走了一圈回来了,这是有效节点肯定已经遍历结束*/
int Get_length(PClist plist)
{
	//不带前驱的for循环 跑一遍就好
	int count = 0;
	for (struct Clist* p = plist->next; p != plist; p = p->next)
	{
		count++;
	}
	return count;
}
//清空
void Clear(PClist plist)
{
	//assert
	Destroy1(plist);
}
//销毁1(无限头删)
void Destroy1(PClist plist)
{
	//assert
	while (plist->next != plist)
	{
		struct Clist* p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = plist;
}
//销毁2(要用到两个指针变量)
void Destroy2(PClist plist)
{
	//assert
	struct Clist* p = plist->next;
	struct Clist* q = NULL;
	plist->next = plist;
	while (p != plist)
	{
		q = p->next;
		free(p);
		p = q;
	}
}
//打印
void Show(struct Clist* plist)
{
	//assert
	for (struct Clist* p = plist->next; p != plist; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

关于C语言循环链表的原理与使用操作的文章就介绍至此,更多相关C语言循环链表内容请搜索编程宝库以前的文章,希望以后支持编程宝库

 一.引入我们在单链表中,有了next指针,这个指针是用来指向下一个节点的,如果我们需要查找下一个结点的时间复杂度为o(1),如果我们需要查找上一个节点的时候,那么时间复杂度就变为o(n)了,需要从 ...