技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

数据结构单循环链表clist

 收录于 数据结构
   约 1895 字   预计阅读 4 分钟 
https://bing.ee123.net/img/rand?artid=146158198

数据结构——单循环链表clist

前言：大家好😍，本文主要介绍了数据结构——单循环链表clist

一、单循环链表 的定义

https://i-blog.csdnimg.cn/direct/f87f90b1254f4149acb2ce7957f6513b.png

单循环链表是一种线性数据结构，其中每个节点包含两个部分：

  1. 数据域 ：存储数据元素。
  2. 指针域 ：存储指向下一个节点的指针。

与普通单链表不同的是， 单循环链表的最后一个节点的指针指向头节点，而不是 NULL 。这种环状结构使得单循环链表在某些场景下具有独特的优势。

二、单循环链表 的操作

2.1 定义

typedef int ELEM_TYPE;
//单循环链表的有效节点的结构体设计
typedef struct CNode
{
    ELEM_TYPE data;//数据域
    struct CNode* next;//指针域(保存下一个有效节点的地址)
}CNode, * PCNode;

2.2 初始化

https://i-blog.csdnimg.cn/direct/eee40c38c77549e08f8d2aad8c1c3ae0.png

void Init_CList(CNode* plist)
{
	plist->next = plist;//指针域指向自身
}

  • plist->next = plist ; ：将头节点的 next 指针指向它自己。

    • 目的 ： 形成一个空的环状结构。
    • 意义 ：在单循环链表中，最后一个节点的 next 指针会指向头节点，而当链表为空时，头节点的 next 指针也指向它自己，表示链表中没有其他节点。

2.3 插入

2.3.1 头插

https://i-blog.csdnimg.cn/direct/6eb6b8d70a2e4a3bbfc29edd27418c29.png

bool Insert_head(CNode* plist, ELEM_TYPE val)
{
	//0.assert
	assert(plist != NULL);
	if (plist == NULL)
	{
		return false;
	}

	//1.购买新节点
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));
	if (pnewnode == NULL)
		exit(1);
	pnewnode->data = val;

	//2.找到合适的待插入位置
	//因为是头插 比较特殊，就是插入在辅助节点的后边

	//3.插入
	pnewnode->next = plist->next;
	plist->next = pnewnode;

	return true;
}

2.3.2 尾插

https://i-blog.csdnimg.cn/direct/a6dff51eab1d413f8bc87f3a798850fe.png

bool Insert_tail(CNode* plist, ELEM_TYPE val)
{
	//0.assert
	assert(plist != NULL);

	//1.购买新节点
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));
	if (pnewnode == NULL)
		exit(1);
	pnewnode->data = val;

	//2.找到合适的待插入位置
	//尾插，需要让临时指针p，停在当前的尾结点处
	CNode* p = plist;
	while (p->next != plist)
	{
		p = p->next;
	}

	//3.插入(两行代码)
	pnewnode->next = p->next;
	p->next = pnewnode;

	return true;
}

  • 从头节点开始，通过循环找到链表的尾节点。

  • 条件 ： p->next != plist

    ，说明当前节点的下一个节点不是头节点，即当前节点不是尾节点。

  • 当循环结束时， p

    指向尾节点 。

  • pnewnode->next = p->next; ：将新节点的 next 指针指向头节点（因为尾节点的 next 指向头节点）。

  • p->next = pnewnode; ：将尾节点的 next 指针指向新节点，完成插入操作。

2.3.3 按位置插

2.4 删除

2.4.1 头删

https://i-blog.csdnimg.cn/direct/2fbbc9fe01b147f1aa6344acf7f45a4d.png

bool Del_head(CNode* plist)
{
	//0.安全性处理
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//1.对单循环链表判空
	if (Is_Empty(plist))
		return false;

	//2.需要一个临时指针q指向待删除节点
	//因为是头删，所以待删除节点就是第一个有效值节点
	CNode* q = plist->next;

	//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)
	//因为是头删,所以这里的p用辅助节点plist代替即可

	//4.跨越指向+释放
	plist->next = q->next;
	free(q);
	q = NULL;

	return true;
}
  • 定义一个临时指针 q ，指向第一个有效节点（即头节点的下一个节点 ）
  • plist->next = q->next; ：将头节点的 next 指针指向 q 的下一个节点，即跨越 q 节点。
  • free(q); ：释放 q 节点的内存。
  • q = NULL; ：将 q 指针置为 NULL ，避免野指针。

2.4.2 尾删

https://i-blog.csdnimg.cn/direct/5c5ab1515b54474cbda6c726c8d44b72.png

bool Del_tail(CNode* plist)
{
	//0.安全性处理
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//1.对单循环链表判空
	if (Is_Empty(plist))
		return false;

	//2.需要一个临时指针q指向待删除节点
	CNode* q = plist;
	for (; q->next != plist; q = q->next);

	//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)
	CNode* p = plist;
	for (; p->next != q; p = p->next);


	//4.跨越指向+释放
	p->next = q->next;
	free(q);
	q = NULL;

	return true;
}

2.4.3 按位置删

https://i-blog.csdnimg.cn/direct/ae743219106e44ad9cc50961995f32ee.png

bool Del_pos(CNode* plist, int pos)
{
	//0.安全性处理
	assert(plist != NULL);
	if (plist == NULL)
		return false;
	assert(pos >= 0 && pos < Get_length(plist));

	//1.对单循环链表判空
	if (Is_Empty(plist))
		return false;

	//2.需要一个临时指针q指向待删除节点
	//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)

	CNode* p = plist;
	for (int i = 0; i < pos; i++)
		p = p->next;
	CNode* q = p->next;


	//4.跨越指向+释放
	p->next = q->next;
	free(q);
	q = NULL;

	return true;
}

2.4.4 按值删


//8.按值删(删除值val出现的第一次的地方)
bool Del_val(CNode* plist, ELEM_TYPE val)
{
	//0.安全性处理
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//1.对单循环链表判空
	if (Is_Empty(plist))
		return false;

	//2.需要一个临时指针q指向待删除节点
	//通过Search去找一下，val值出现的第一次的位置
	CNode* q = Search(plist, val);
	if (q == NULL)
		return false;

	//3.再找到待删除节点的前驱，用p指向
	CNode* p = plist;
	for (; p->next != q; p = p->next);

	//4.跨越指向+释放
	p->next = q->next;
	free(q);
	q = NULL;

	return true;
}


//8.5 按值删(删除值val出现的所有的地方)
bool Del_val_all(CNode* plist, ELEM_TYPE val)
{
	CNode* p = plist;
	CNode* q = plist;

	while (p->next != plist)
	{
		q = p->next;
		if (q->data == val)
		{
			p->next = q->next;
			free(q);
			q = NULL;
		}
		else
		{
			p = q;
		}
	}

	return true;
}

2.5 其余代码

//9.查找(查找值val出现的第一次的地方)
CNode* Search(CNode* plist, ELEM_TYPE val)
{
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		if (p->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//10.清空
void Clear(CNode* plist)
{
	Destroy1(plist);
}

//11.销毁1(需要辅助节点参与进来)
void Destroy1(CNode* plist)
{
	while (plist->next != plist)
	{
		CNode* p = plist->next;
		plist->next = p->next;
		free(p);
		p = NULL;
	}

}

//12.销毁2(不需要辅助节点参与进来)
void Destroy2(CNode* plist)
{
	//0.assert  head
	//1.申请指针p，让其保存辅助节点的指针域
	CNode* p = plist->next;

	//2.申请指针q，先不给q赋值
	CNode* q = NULL;

	//3.反复通过p和q打配合，去销毁后续节点
	while (p != plist)
	{
		q = p->next;
		free(p);
		p = q;
	}

	//4.节点全部销毁完毕，别忘了把辅助节点的指针域处理一下
	plist->next = plist;
}

//13.判空 
bool Is_Empty(CNode* plist)
{
	return plist->next == plist;
}

//14.获取有效值长度
int Get_length(CNode* plist)
{
	int count = 0;
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		count++;
	}
	return count;
}

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

2.6 主函数测试代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "clist.h"


单循环链表的测试用例
int main()
{
	CNode head;
	Init_CList(&head);
	Insert_head(&head, 100);
	Insert_tail(&head, 200);
	Insert_head(&head, 300);
	Insert_tail(&head, 400);
	Show(&head);


	Del_head(&head);
	Show(&head);
	Del_tail(&head);
	Show(&head);
	Del_pos(&head, 1);
	Show(&head);
	Del_val(&head, 100);
	Show(&head);

	Insert_tail(&head, 1);
	Insert_tail(&head, 2);
	Insert_tail(&head, 1);
	Insert_tail(&head, 4);
	Insert_tail(&head, 1);
	Show(&head);
	
		Del_val_all(&head, 1);
		Show(&head);
		return 0;
}
更新于 2025-03-13
 数据结构
返回 | 主页