[数据结构与算法] 数据结构笔记23-循环链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构笔记23-循环链表 -> 正文阅读

[数据结构与算法]数据结构笔记23-循环链表

文章目录

概念

循环链表是一种头尾相连的链表，最后一个结点的指针域指向头结点，从而使整个链表形成环
在这里插入图片描述
从表中的任一个结点出发均可以找到表中其他结点，最后一个链表结点的指针域不为空，指向头结点

注意点

循环链表中没有NULL指针，所以在遍历的时候，其终止条件不再像非循环链表那样子去判断p或者p->next是否为空，而是判断其是否等于头指针
在这里插入图片描述

头插法创建循环链表

static bool initcircularListHead(circularList* circularListHead, int N)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularListHead->next = circularListHead;

	for (i = 0; i < N; i++)
	{
		circularList* newNode = (circularList*)malloc(sizeof(circularList));
		newNode->value = i;
		newNode->next = circularListHead->next;
		circularListHead->next = newNode;
	}

	return true;
}

尾插法创建循环链表


//尾插法初始化循环单链表
static bool initcircularListTail(circularList* circularListHead, int N)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}


	circularListHead->next = circularListHead;
	circularList* circularListCurrent = circularListHead;
	for (i = 0; i < N; i++)
	{
		circularList* newNode = (circularList*)malloc(sizeof(circularList));
		newNode->value = i;
		circularListCurrent->next = newNode;
		circularListCurrent = newNode;
	}

	circularListCurrent->next = circularListHead;

	return true;
}

遍历循环单链表

static bool ergodicCircularListTail(circularList* circularListHead)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	if (circularListHead->next == circularListHead)
	{
		printf("circularList->next is NULL,please init it\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;

	while (circularListCurrent != circularListHead)
	{
		printf("circularListCurrent->value=%d\n", circularListCurrent->value);
		circularListCurrent = circularListCurrent->next;
	}


	return true;
}

链表长度


static int getCircularListLength(circularList* circularListHead)
{
	int length = 0;

	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;


	while (circularListCurrent != circularListHead)
	{
		circularListCurrent = circularListCurrent->next;
		length++;
	}

	return length;
}

指定位置插入元素


//指定位置之后插入元素
static bool insertCircularList(circularList* circularListHead, int pos, int data)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	circularList* newNode = (circularList*)malloc(sizeof(circularList));
	newNode->value = data;
	newNode->next = circularListCurrent->next;
	circularListCurrent->next = newNode;

	return true;
}

根据下标删除元素

static bool delCircularList(circularList* circularListHead, int pos)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	circularList* toDelNode = circularListCurrent->next;
	circularListCurrent->next = toDelNode->next;

	free(toDelNode);
	toDelNode = NULL;

	return true;
}

根据元素值删除元素

static bool delCircularListAsElem(circularList* circularListHead, int value)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	circularList* toDelNodePre = circularListHead;
	while ((circularListCurrent != circularListHead))
	{
		if (circularListCurrent->value != value)
		{
			toDelNodePre = circularListCurrent;
			circularListCurrent = circularListCurrent->next;
		}
		else
		{

			circularList* toDelNode = circularListCurrent;
			toDelNodePre->next = toDelNode->next;

			free(toDelNode);
			toDelNode = NULL;
			break;
		}

	}

	return true;
}

根据元素获取下标

static int  getCircularListIndexByVal(circularList* circularListHead, int val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead))
	{
		i++;
		if (circularListCurrent->value == val)
		{
			return i;
		}
		circularListCurrent = circularListCurrent->next;
	}

	return -1;

}

根据下标来获取元素值

static int getCircularListValByIndex(circularList* circularListHead, int pos, int* val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	if (pos < 0 || pos > getCircularListLength(circularListHead) - 1)
	{
		printf("pos is invaild\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	//找到前一个元素
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent->next == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	*val = circularListCurrent->next->value;

	return true;

}

根据下标来修改元素的值

static bool setCircularListValByIndex(circularList* circularListHead, int pos, int val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	//0 1 2 3
	if (pos > getCircularListLength(circularListHead) - 1)
	{
		printf("pos is invaild\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;

	for (i = 0; i < getCircularListLength(circularListHead); i++)
	{
		if (circularListCurrent == circularListHead)
		{
			break;
		}

		if (i == pos)
		{
			circularListCurrent->value = val;
			return true;
		}

		circularListCurrent = circularListCurrent->next;
	}


	return false;

}

删除链表

static bool clearCircularList(circularList* circularListHead)
{
	if (circularListHead == NULL)
	{
		printf("CircularList is NULL\n");
		return false;
	}


	circularList* toDelNode = circularListHead->next;
	circularList* toDelNodeNext;

	//头部删除
	while (toDelNode != circularListHead)
	{
		toDelNodeNext = toDelNode->next;
		free(toDelNode);
		toDelNode = toDelNodeNext;
	}

	circularListHead->next = circularListHead;

	return true;
}

链表合并

static bool mergeCircularList(circularList* aHead, circularList* bHead)
{
	circularList* aCurrent = aHead;
	circularList* bCurrent = bHead;

	while (aCurrent->next != aHead )
	{
		aCurrent = aCurrent->next;
	}

	while (bCurrent->next != bHead)
	{
		bCurrent = bCurrent->next;
	}

	aCurrent->next = bCurrent->next->next;
	free(bCurrent->next);
	bCurrent->next = aHead;


	return true;
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct  circularList
{
	int value;
	struct circularList* next;
}circularList;

struct circularList* g_circularListA;
struct circularList* g_circularListB;

//头插法初始化单链表
static bool initcircularListHead(circularList* circularListHead, int N)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularListHead->next = circularListHead;

	for (i = 0; i < N; i++)
	{
		circularList* newNode = (circularList*)malloc(sizeof(circularList));
		newNode->value = i;
		newNode->next = circularListHead->next;
		circularListHead->next = newNode;
	}

	return true;
}



//尾插法初始化循环单链表
static bool initcircularListTail(circularList* circularListHead, int N)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}


	circularListHead->next = circularListHead;
	circularList* circularListCurrent = circularListHead;
	for (i = 0; i < N; i++)
	{
		circularList* newNode = (circularList*)malloc(sizeof(circularList));
		newNode->value = i;
		circularListCurrent->next = newNode;
		circularListCurrent = newNode;
	}

	circularListCurrent->next = circularListHead;

	return true;
}

//遍历循环单链表
static bool ergodicCircularListTail(circularList* circularListHead)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	if (circularListHead->next == circularListHead)
	{
		printf("circularList->next is NULL,please init it\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;

	while (circularListCurrent != circularListHead)
	{
		printf("circularListCurrent->value=%d\n", circularListCurrent->value);
		circularListCurrent = circularListCurrent->next;
	}


	return true;
}


static int getCircularListLength(circularList* circularListHead)
{
	int length = 0;

	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;


	while (circularListCurrent != circularListHead)
	{
		circularListCurrent = circularListCurrent->next;
		length++;
	}

	return length;
}


//指定位置之后插入元素
static bool insertCircularList(circularList* circularListHead, int pos, int data)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	circularList* newNode = (circularList*)malloc(sizeof(circularList));
	newNode->value = data;
	newNode->next = circularListCurrent->next;
	circularListCurrent->next = newNode;

	return true;
}


//根据下标删除元素
static bool delCircularList(circularList* circularListHead, int pos)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	circularList* toDelNode = circularListCurrent->next;
	circularListCurrent->next = toDelNode->next;

	free(toDelNode);
	toDelNode = NULL;

	return true;
}


//根据元素值来删除元素
static bool delCircularListAsElem(circularList* circularListHead, int value)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	circularList* toDelNodePre = circularListHead;
	while ((circularListCurrent != circularListHead))
	{
		if (circularListCurrent->value != value)
		{
			toDelNodePre = circularListCurrent;
			circularListCurrent = circularListCurrent->next;
		}
		else
		{

			circularList* toDelNode = circularListCurrent;
			toDelNodePre->next = toDelNode->next;

			free(toDelNode);
			toDelNode = NULL;
			break;
		}

	}

	return true;
}

//根据元素获取下标
static int  getCircularListIndexByVal(circularList* circularListHead, int val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	while ((circularListCurrent != circularListHead))
	{
		i++;
		if (circularListCurrent->value == val)
		{
			return i;
		}
		circularListCurrent = circularListCurrent->next;
	}

	return -1;

}

//根据下标来获取元素值
static int getCircularListValByIndex(circularList* circularListHead, int pos, int* val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	if (pos < 0 || pos > getCircularListLength(circularListHead) - 1)
	{
		printf("pos is invaild\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;
	//找到前一个元素
	while ((circularListCurrent != circularListHead) && (i < pos - 1))
	{
		circularListCurrent = circularListCurrent->next;
		i++;
	}

	if (circularListCurrent->next == circularListHead)
	{
		printf("circularListCurrent is equal circularListHead\n");
		return false;
	}

	*val = circularListCurrent->next->value;

	return true;

}

//根据下标来修改元素的值
static bool setCircularListValByIndex(circularList* circularListHead, int pos, int val)
{
	int i = 0;
	if (circularListHead == NULL)
	{
		printf("circularList is NULL\n");
		return false;
	}

	//0 1 2 3
	if (pos > getCircularListLength(circularListHead) - 1)
	{
		printf("pos is invaild\n");
		return false;
	}

	circularList* circularListCurrent = circularListHead->next;

	for (i = 0; i < getCircularListLength(circularListHead); i++)
	{
		if (circularListCurrent == circularListHead)
		{
			break;
		}

		if (i == pos)
		{
			circularListCurrent->value = val;
			return true;
		}

		circularListCurrent = circularListCurrent->next;
	}


	return false;

}

//删除链表
static bool clearCircularList(circularList* circularListHead)
{
	if (circularListHead == NULL)
	{
		printf("CircularList is NULL\n");
		return false;
	}


	circularList* toDelNode = circularListHead->next;
	circularList* toDelNodeNext;

	//头部删除
	while (toDelNode != circularListHead)
	{
		toDelNodeNext = toDelNode->next;
		free(toDelNode);
		toDelNode = toDelNodeNext;
	}

	circularListHead->next = circularListHead;

	return true;
}

//链表合并
static bool mergeCircularList(circularList* aHead, circularList* bHead)
{
	circularList* aCurrent = aHead;
	circularList* bCurrent = bHead;

	while (aCurrent->next != aHead )
	{
		aCurrent = aCurrent->next;
	}

	while (bCurrent->next != bHead)
	{
		bCurrent = bCurrent->next;
	}

	aCurrent->next = bCurrent->next->next;
	free(bCurrent->next);
	bCurrent->next = aHead;


	return true;
}

int main()
{
	bool ret;
	int val;
	struct  circularList* p = (circularList*)malloc(sizeof(circularList));
	struct  circularList* p1 = (circularList*)malloc(sizeof(circularList));

	ret = initcircularListHead(p, 4);
	if (ret == false)
	{
		printf("initcircularListHead failed\n");
	}
	else
	{
		//insertCircularList(p,4,5);
		//ergodicCircularListTail(p);
	}

	printf("+++++++++++++++++++++++++++\n");
	ret = initcircularListHead(p1, 8);
	if (ret == false)
	{
		printf("initcircularListHead failed\n");
	}
	else
	{
		//insertCircularList(p,4,5);
		//ergodicCircularListTail(p1);
	}

	mergeCircularList(p, p1);
	ergodicCircularListTail(p);


	//delCircularListAsElem(p,5);
	//ergodicCircularListTail(p);	
	//printf("circularListLength=%d\n",getCircularListLength(p));
	//getCircularListValByIndex(p,6,&val);
	//printf("getCircularListIndexByVal=%d\n",getCircularListIndexByVal(p,3));
	//setCircularListValByIndex(p,0,5);
	//setCircularListValByIndex(p,1,5);
	//setCircularListValByIndex(p,2,5);
	//setCircularListValByIndex(p,3,5);
	//setCircularListValByIndex(p,4,5);
	//ergodicCircularListTail(p);
	//clearCircularList(p);
	//ergodicCircularListTail(p);


	return 0;
}