扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言循环链表的原理与使用操作
  • 237

0
分享到

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

2024-04-02 19:04:59 237人浏览 薄情痞子
摘要

目录一.引入二.循环链表的定义三.单链表与循环链表对比3.1图示对比3.2代码对比四.循环链表的操作4.1循环链表的初始化4.2循环链表的建立4.2.1头插法建立循环链表4.2.2尾

一.引入

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

二.循环链表的定义

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

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

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

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;
}
//判满（循环链表不需要这个操作）
//获取长度

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语言循环链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C语言循环链表的原理与使用操作

本文链接: https://lsjlt.com/news/149433.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C语言循环链表的原理与使用操作
    目录一.引入二.循环链表的定义三.单链表与循环链表对比3.1图示对比3.2代码对比四.循环链表的操作4.1循环链表的初始化4.2循环链表的建立4.2.1头插法建立循环链表4.2.2尾...
    99+
    2024-04-02
  • C语言双向链表的原理与使用操作
    目录一.引入二.双向链表的定义三.双向链表与单链表对比3.1图示对比3.2代码对比四.双向链表的操作4.1双向链表的创建4.2双向链表的插入4.3双向链表的删除4.4双向链表的销毁五...
    99+
    2024-04-02
  • C语言实现循环双链表
    本文实例为大家分享了C语言实现循环双链表的具体代码，供大家参考，具体内容如下 #include<stdio.h> #include<stdlib.h> #...
    99+
    2024-04-02
  • C语言无头单向非循环链表的操作方法有哪些
    这篇文章主要介绍“C语言无头单向非循环链表的操作方法有哪些”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C语言无头单向非循环链表的操作方法有哪些”文章能帮助大家解决问题。链表引入问：上次我们看了顺序...
    99+
    2023-06-30
  • C语言单双线性及循环链表与实例
    目录链表思维顺序存储结构单链表单链表存储结构 单链表的读取单链表的插入 单链表的删除 单链表的整表创建 头插法建立单链表尾插法建立单链表单链表...
    99+
    2023-03-24
    C语言单双链表 C语言循环链表
  • C语言用循环单链表实现约瑟夫环
    用循环单链表实现约瑟夫环（c语言），供大家参考，具体内容如下 源代码如下，采用Dev编译通过，成功运行，默认数到三出局。 主函数： main.c文件 #include <s...
    99+
    2024-04-02
  • C语言怎么实现循环双链表
    这篇文章主要介绍“C语言怎么实现循环双链表”，在日常操作中，相信很多人在C语言怎么实现循环双链表问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C语言怎么实现循环双链表”的疑惑有所帮助！接下来，请跟着小编一起来...
    99+
    2023-06-25
  • C语言详解无头单向非循环链表各种操作方法
    目录链表引入链表介绍创建链表打印链表创建结点单链表尾插单链表头插单链表尾删单链表头删在pos位置之前插入数据在pos位置之后插入数据删除pos位置结点删除pos位置之后的结点销毁链表...
    99+
    2024-04-02
  • C语言中for循环与while循环怎么使用
    本文小编为大家详细介绍“C语言中for循环与while循环怎么使用”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言中for循环与while循环怎么使用”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。一、单层f...
    99+
    2023-07-02
  • C语言链表的操作有哪些
    这篇“C语言链表的操作有哪些”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C语言链表的操作有哪些”文章吧。前言编译工具：vs...
    99+
    2023-06-30
  • C语言实现带头双向循环链表
    目录前言1. 创建结构体2.malloc新节点3.创建哨兵位节点4.尾插5.打印6.尾删7.头插8.在指定位置pos的前面进行插入9. 删除指定位置pos节点10.销毁链表前言 在...
    99+
    2024-04-02
  • c语言如何创建双向循环链表
    要创建一个双向循环链表，你可以按照以下步骤进行：1. 首先，定义一个节点结构体，包含一个数据域和两个指针域，分别指向前一个节点和后一...
    99+
    2023-08-25
    c语言
  • C语言选择、循环、函数、数组与操作符
    目录1、选择语句2、循环语句3、函数4、数组5、操作符5、单目操作符6、关系操作7、逻辑操作符8、条件操作符9、逗号表达式10、下标引用、函数调用和结构成员1、选择语句 如果你好好学...
    99+
    2024-04-02
  • c语言中for循环的作用
    for循环是一种控制流语句，用于重复执行代码块，直到满足特定条件。其主要作用包括：重复执行代码块；遍历数据结构；执行特定次数的操作。 C语言中for循环的作用 for循环是一种在C语言...
    99+
    2024-05-09
    c语言
  • C语言如何实现双向链表和双向循环链表
    本文小编为大家详细介绍“C语言如何实现双向链表和双向循环链表”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言如何实现双向链表和双向循环链表”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。双向链表和双向循环链表...
    99+
    2023-06-16
  • C语言数据结构之双链表&循环链表&静态链表详解
    目录单链表 VS 双链表双链表双链表的初始化（带头结点）双链表的插入双链表的删除双链表的遍历循环单链表循环双链表循环双链表的初始化循环双链表的插入循环双链表的删除静态链表什么是静态链...
    99+
    2024-04-02
  • 详解C语言中双向循环链表的实现
    目录实现细节辅助理解图具体实现代码1、对链表进行初始化2、任意位置前的插入3、任意位置的删除4、头插和尾删完整代码头文件具体函数测试实现细节 1、带一个哨兵位（哨兵节点，初始节点，不...
    99+
    2024-04-02
  • C语言中双链表的基本操作
    目录带头结点的双向循环链表基本操作创建销毁打印尾插法尾删头插头删查找元素位置任意位置插入任意位置删除完整代码及测试总结带头结点的双向循环链表 链表结构如下： 每个节点都有一个数据域和...
    99+
    2023-02-05
    C语言双链表 双链表的基本操作 C语言双链表操作
  • C语言实现带头双向循环链表的接口
    本文实例为大家分享了C语言实现带头双向循环链表的接口，供大家参考，具体内容如下 各函数功能如下 申请空间 ListNode* BuyListNode(LTDataType x) ...
    99+
    2024-04-02
  • C语言带头双向循环链表的示例代码
    目录前言结构分析链表的基本操作实现创建节点初始化链表链表销毁打印链表链表尾插链表尾删链表头插链表头删链表查找链表pos位置前面去插入删除pos位置链表判空代码复用总代码及头文件前言 ...
    99+
    2022-11-13
    C语言带头双向循环链表 C语言 双向循环链表 C语言 循环链表
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作