Skip to main content

单向循环链表

1. 单向循环链表​

单向循环链表和普通单向链表的操作逻辑几乎一样，唯一就是初始化和结尾判断有区别。

单向循环链表里面每一个节点的next都要有指向，最后一个节点的next指向head节点。

  • 带头结点循环单链表

Zhi1Hv.png

  • 初始化（与普通单链表不同）
singly_link_list *list_init(void)
{
	singly_list head = malloc(sizeof(listnode));
	if (head != NULL)
	{
		head->next = head;
	}
	return head;
}
  • 尾插法（与普通单链表不同）
//在链表的尾部添加一个结点
void inster_tail(singly_link_list *head, singly_link_list *new)
{
	singly_link_list *tmp = head;
	//找到链表的最后一个结点
	while(head->next != tmp)
		head = head->next;
	
	head->next = new; //把新的节点添加到这个链表的最后一个结点上
	new->next = tmp;
}
  • 其他算法与单向链表几乎一样
只需要将原来判断结尾的 p->next == NULL; 的这些地方改为 p->next == head;

2. 代码示例​

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

typedef int datatype;	//给int取了一个别名，叫做datatype

//节点设计
typedef struct node
{
	datatype data;	//数据域
	struct node *next;	//指针域，存放下一个节点的地址
}singly_link_list;

//初始化一条循环单链表
singly_link_list *list_init(void)
{
	singly_link_list *head = malloc(sizeof(singly_link_list));
	if(head != NULL)
	{
		head->next = head;
		return head;
	}
	return NULL;
}

//创建一个新节点
singly_link_list *create_node(datatype data)
{
	singly_link_list *new = malloc(sizeof(singly_link_list));
	if(new != NULL){
		new->data = data;	//把传进来的数据，存储节点数据域
		new->next = NULL;	//让节点的指针域先指向空，防止野指针危害
		return new;
	}
		
	return NULL;
}

//在链表的尾部添加一个节点
void inster_tail(singly_link_list *head, singly_link_list *new)
{
	singly_link_list *tmp = head;
	//找到链表的最后一个节点。这里的head是inster_tail()中的一个形参遍历，与main函数的head没有关联
	while(head->next != tmp)
		head = head->next;
	
	//把新的节点添加到这个链表的最后一个节点上
	head->next = new;
	new->next = tmp;
}

//在链表的头节点后面添加一个节点
// 在head后面添加一个新的节点new
void inster_head(singly_link_list *head, singly_link_list *new)
{
	//1，把新节点指向头节点的下一个
	new->next = head->next;
	
	//2，把头节点指向新节点
	head->next = new;
}

//遍历链表
void dispaly_list(singly_link_list *head)
{
	struct node *tmp = head;
	//遍历链表的每一个元素，直到最后一个
	while(head->next != tmp)
	{
		printf("%d->", head->next->data);
		head = head->next;
	}
	printf("\n");
}

//判断链表是否为空
bool is_empty(singly_link_list *head)
{
	return head->next == NULL;
}

int main(int argc, char *argv[])
{
	//1. 初始化一条新链表
	singly_link_list *head = list_init();
    // singly_link_list *head = NULL;  // 不带头结点
	if(head == NULL){
		printf("链表初始化失败\n");
		exit(0);	//结束程序
	}
	
	// 2. 插入若干个自然数
	int n, i;
	printf("请输入要初始化多少个自然数\n");
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		// 2.1 创建链表节点
		struct node *new  = create_node(i);
		if(new == NULL){
			printf("%d节点创建失败\n", i);
			continue;	//跳过下面的操作，继续创建新的节点
		}
		
		// 2.2 在链表末尾插入节点
		// 要插入哪条链表？
		// 要插入的是哪一个节点？
		inster_tail(head, new);
	}
	
	// 3. 遍历所有元素
	// 要遍历哪一条链表呢？
	dispaly_list(head);
	return 0;
}
0%