C语言数据结构之循环链表

一 、循环链表

1. 定义：循环链表（Circular Linked List）是一种特殊的数据结构，它与单链表相似，但是最后一个节点的指针指向第一个节点，形成一个环状结构。在循环链表中，可以通过任何一个节点来遍历整个链表。
2. 优点：可以支持O(1)时间复杂度的情况下的前驱节点查找，双向链表在某些情况下的插入、删除等操作要比单链表简单、高效。循环链表是一种首尾相连的单链表，从当前任意一个节点起都能遍历整个链表
3. 缺点：循环链表不支持随机访问，缓存命中率相对低。循环链表的设计和操作比单链表更加复杂。

二、 运算      

循环链表是一种链表，其中最后一个元素指向第一个元素，形成循环。循环链表的基本运算包括创建、插入、删除、遍历等。下面简要介绍这些基本运算的方法。

1.创建循环链表：
创建一个循环链表需要先定义一个节点结构体，包含数据域和指针域。指针域至少包括一个指向下一个节点的指针，一个指向前一个节点的指针（在第一个节点中为NULL），以及一个指向链表头节点的指针。根据需要，还可以添加其他指针域。

2.插入节点：
插入节点包括在链表尾部插入节点和在指定位置插入节点。

在链表尾部插入节点的步骤如下：

创建一个新节点；
将新节点的数据域赋值；
将新节点的next指针指向头节点；
将头节点的prev指针指向新节点；
将新节点的prev指针指向头节点；
将头节点的next指针指向新节点。
在指定位置插入节点的步骤如下：

找到插入位置的前一个节点；
将新节点的next指针指向前一个节点的next指针所指向的节点；
将新节点的prev指针指向前一个节点；
将前一个节点的next指针指向新节点；
将前一个节点的next指针指向新节点的next指针所指向的节点。
3.删除节点：
删除节点包括删除头节点和删除指定节点。删除头节点的步骤如下：

将头节点的prev指针的next指针指向头节点的next指针所指向的节点；

将头节点的next指针的prev指针指向头节点的prev指针所指向的节点；

释放头节点的内存空间。
删除指定节点的步骤如下：

找到要删除的节点的前一个节点；

将要删除的节点的prev指针的next指针指向要删除的节点的next指针所指向的节点；

将要删除的节点的next指针的prev指针指向要删除的节点的prev指针所指向的节点；

释放要删除的节点的内存空间。

4.遍历链表：
遍历循环链表的基本思路是从头节点开始，依次遍历每个节点，直到回到头节点。每个节点被遍历一次后，它的next指针所指向的节点将被遍历。当next指针指向头节点时，表明已经遍历到链表的尾部。

• 简单链表的定义及初始化

typedef struct node
{
	DataType		data;	/*数据域*/
	struct node		*next;	/*指针域*/
}SingleLinkList, SingleLinkNode;
int init(SingleLinkList **Head)
{
	if(1)
	{
		/*申请内存*/
		(*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList));
		/*判断内存申请是否成功*/
		if(*Head == NULL)
		{
			printf("申请内存错误， 初始化失败！[100001]\n");
			return 100001;
		}
		(*Head)->next = NULL;
		/*循环链表*/
		/*
			(*Head)->next = *Head;
		*/
		return 0;
	}
	else
	{
		printf("该链表已经初始化！请删除后再执行此操作！[100002]\n");
		return 100002;
	}
}

• 插入元素,头插法 

int insert_head(SingleLinkList **Head, DataType x)
{
	SingleLinkNode *newNode;
 
	if(0)
	{
		printf("链表未初始化！[100003]\n");
		return 100003;
	}
	
	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
	if(!newNode)
	{
		printf("申请节点内存空间失败！[100004]\n");
		return 100004;
	}
	newNode->data = x;
	newNode->next = (*Head)->next;
 
	(*Head)->next = newNode;
 
	return 0;
}

•  插入元素， 尾插法

int insert_tail(SingleLinkList **Head, DataType x)
{
	SingleLinkNode *newNode;
	SingleLinkNode *p;
 
	if(0)
	{
		printf("链表未初始化！[100003]\n");
		return 100003;
	}
	
	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
	if(!newNode)
	{
		printf("申请节点内存空间失败！[100004]\n");
		return 100004;
	}
 
	newNode->data = x;
	newNode->next = *Head;
 
	p = (*Head);
 
	while(p->next)
	{
		p = p->next;
	}
 
	p->next = newNode;
 
	return 0;
}

• 插入元素，在位置i处插入元素x

int insert(SingleLinkList **Head, int i, DataType x)
{
	int j;
	SingleLinkNode *p;
	SingleLinkNode *newNode;
 
	
	/*对i进行判断，0<i<=length+1*/
	if(i<1 || i>length(*Head)+1)
	{
		printf("位置i不是链表有效位置！[100005]\n");
		return 100005;
	}
	p = (*Head);
	j = 1;
 
	while(j<i)
	{
		j++;
		p = p->next;
	}
 
	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
	/*此处省略检测newNode是否申请成功*/
 
	newNode->data = x;
	newNode->next = p->next;
	p->next = newNode;
	return 0;
}

• 删除元素, 删除值为x的元素

int delete(SingleLinkList **Head, DataType x)
{
	int i;
	int j;
 
	SingleLinkNode *p;
	SingleLinkNode *q; /*要删除的元素x*/
 
	i = find(*Head,x);
	if(!i)
	{
		printf("元素x【%d】不存在！100006\n", x);
		return 100006;
	}
	
	p = (*Head);
	j=1;
 
	while(j<i)
	{
		j++;
		p = p->next;
	}
	
	q = p->next;
	p->next = q->next;
 
	free(q); /*释放内存*/
 
	return 0;
}

• 查找值为x的元素，返回位置i

int find(SingleLinkList *Head, DataType x)
{
	int i;
	SingleLinkNode *p;
 
	i = 1;
	p = Head->next;
 
	while( p!= Head && p->data != x)
	{
		i++;
		p = p->next;
	}
 
	if(p->next == Head)
	{
		return 0;
	}
	else
	{
		return i;
	}
 
}

• 链表长度

int length(SingleLinkList *Head)
{
	int len=0;
	SingleLinkNode *p;
 
	p = Head->next;
	while(p!=Head) 
	{
		len++;
		p = p->next;
	}
	return len;
}

• 输出链表 

void print(SingleLinkList *Head)
{
	SingleLinkNode *p;
	int i=0;
 
	p = Head->next;
	if(!p)
	/*if(p!=Head)*/
	{
		printf("链表为空！\n");
		return;
	}
	while(p!=Head)
	{
		printf("Node[%d]. = %d\n", ++i, p->data);
		p = p->next;
	}
}

循环链表程序

int main(int argc, char* argv[])
{
	SingleLinkList *Head;
	DataType x;
	int i,m,n,cmd;
 
	for(i=0;i<strlen(welcome);i++)
	{
		printf("%c",welcome[i]);
		for(m=0;m<1000;m++)
			for(n=0;n<1000;n++)
			{
				;
			}
	}
 
	printf("-----------简单链表演示程序----------\n");
	do
	{
		printf("1. 初始化链表表\n");
		printf("2. 插入元素（头插法）\n");
		printf("3. 插入元素（尾插法）\n");
		printf("4. 插入元素（在位置i插入）\n");
		printf("5. 查找元素x\n");
		printf("6. 求链表长度\n");
		printf("7. 输出链表\n");
		printf("8. 删除元素\n");
		printf("10. 帮助\n"); 
		printf("0. 退出\n");
		printf("请输入您要进行的操作（1~6,0退出）：");
		scanf("%d", &cmd);
		switch(cmd)
		{
		case 1:
			if(!init(&Head))
			{
				printf("链表已初始化！\n");
			}
			break;
		case 2:
			printf("请输入插入元素x：x=");
			scanf("%d",&x);
			if(!insert_head(&Head,x))
			{
				printf("元素（%d）已插入\n", x);
			}
			break;
		case 3:
			printf("请输入插入元素x：x=");
			scanf("%d",&x);
			if(!insert_tail(&Head,x))
			{
				printf("元素（%d）已插入\n", x);
			}
			break;
		case 4:
			printf("请输入插入元素位置i和元素x（i，x）：");
			scanf("%d,%d", &i, &x);
			if(!insert(&Head, i, x))
			{
				printf("已在位置（%d）插入元素（%d）！\n",i, x);
			}
			break;
		case 5:
			printf("请输入要查找的元素x：");
			scanf("%d", &x);
			if(i = find(Head,x))
			{
				printf("元素%d存在，在链表位置%d.\n", x, i);
			}
			else
			{
				printf("在链表中未找到元素x。\n");
			}
			break;
		case 6:
			printf("链表的长度为：%d\n", length(Head));
			break;
		case 7:
			print(Head);
			break;
		case 8:
			printf("请输入要删除的元素x：");
			scanf("%d", &x);
			if(!delete(&Head, x))
			{
				printf("元素x【%d】已删除!\n", x);
			}
			break;
		case 10:
			printf(" 本程序为链表的演示程序，有XXX设计开发，程序完成了。。。。功能！。。。\n");
			break;
			
		}
	}while(cmd != 0);
 
	return 0;
}

三、结果运算图

 

小结：

 感谢季老师的辛勤付出和教诲，为我们的成长和发展奠定了坚实的基础