[数据结构与算法] 数据结构 (五) 线性表

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

-> 数据结构与算法 -> 数据结构 (五) 线性表_循环链表 -> 正文阅读

[数据结构与算法]数据结构 (五) 线性表_循环链表

文章目录

一. 循环链表介绍

① 循环链表的定义

常规的链表,有头部,头部指向链表中的第一个节点,尾部最后一个节点指向NULL
循环链表就是将尾部指向头部
所以一个空的循环链表,它的next不再指向NULL,而是指向自身.
正常链表的遍历结束条件是 NULL,而循环链表的遍历结束条件是next是否为head

② 循环链表的分类

单向循环链表. 头部->尾部->头部.
双向循环链表. 头部 <=> 尾部 <=> 头部

③ 单向循环链表的实现

函数声明头文件的实现 CircleLinkList.h

#ifndef CIRCLE_LINK_LIST
#define CIRCLE_LINK_LIST
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_IS_EMPTY 1
#define LIST_NOT_EMPTY 0
// 链表的小节点
typedef struct CircleLinkNode
{
	struct CircleLinkNode *next;
} CircleLinkNode;

// 链表结构体
typedef struct CircleLinkList
{
	CircleLinkNode head;
	int size;
}CircleLinkList;

// 定义比较的函数指针
typedef int (*COMPARE_PTR)(CircleLinkNode *, CircleLinkNode *);

// 定义打印的函数指针
typedef void (*PRINT_PTR)(CircleLinkNode *);

// 初始化
CircleLinkList *init_circle_linklist();

// 插入函数
void insert_circle_linklist(CircleLinkList *list, int pos, CircleLinkNode *data);

// 获取第一个元素
CircleLinkNode *front_circle_linklist(CircleLinkList *list);

// 根据位置删除
void remove_by_pos_circle_linklist(CircleLinkList *list, int pos);

// 根据值去删除
void remove_by_val_circle_linklist(CircleLinkList *list, CircleLinkNode *data,
COMPARE_PTR compare);

// 获取链表的长度
int get_size_circle_linklist(CircleLinkList *list);

// 查找
int find_circle_linklist(CircleLinkList *list, CircleLinkNode *data, COMPARE_PTR compare);

// 打印节点
void print_circle_linklist(CircleLinkList *list, PRINT_PTR print);

// 判断是否为空
int is_empty_circle_linklist(CircleLinkList *list);

// 释放内存
void free_space_circle_linklist(CircleLinkList *list);

// 清空链表
void clear_circle_linklist(CircleLinkList *list);

#endif // !CIRCLE_LINK_LIST

实现部分.c

#include "CircleLinkList.h"

// 定义比较的函数指针
typedef int (*COMPARE_PTR)(CircleLinkNode *, CircleLinkNode *);

// 定义打印的函数指针
typedef void (*PRINT_PTR)(CircleLinkList *);

// 初始化
CircleLinkList *init_circle_linklist()
{
	//循环链表初始化的时候,注意一点就是,头部指向自身
	CircleLinkList *list = (CircleLinkList *)malloc(sizeof(CircleLinkList));
	if (list != NULL)
	{
		// 指向自己.
		list->head.next = &(list->head);
		list->size = 0;
	}
	return list;
}

// 插入函数
void insert_circle_linklist(CircleLinkList *list, int pos, CircleLinkNode *data)
{
	// 下标越界的友好处理
	if (pos <0 || pos > list->size)
	{
		pos = list->size;
	}
	if (list != NULL && data != NULL)
	{
		CircleLinkNode *pCurrent = &(list->head); // 首先是指向第一个节点,非头节点
		for (int i = 0; i < pos; i++)
		{
			// 找到pos的前驱节点
			pCurrent = pCurrent->next;
		}
		// 找到了前驱节点,然后就是插入的操作
		// 将新节点指向前驱节点的下一个节点
		// 将前驱节点执行新节点
		data->next = pCurrent->next;
		pCurrent->next = data;
		list->size++;
	}
}

// 获取第一个元素
CircleLinkNode *front_circle_linklist(CircleLinkList *list)
{
	if (list != NULL)
	{
		CircleLinkNode *node = list->head.next;
		return node;
	}
	return NULL;
}

// 根据位置删除
void remove_by_pos_circle_linklist(CircleLinkList *list, int pos)
{
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	if (list != NULL)
	{
		CircleLinkNode *pCurrent = &(list->head);
		for (int i = 0; i < pos; i++)
		{
			pCurrent = pCurrent->next;
		}
		// 找到前驱节点
		// 将前驱节点指向pos的下一个,就删除了pos节点
		pCurrent->next = pCurrent->next->next;
		list->size--;
	}
}

// 根据值去删除
void remove_by_val_circle_linklist(CircleLinkList *list, CircleLinkNode *data, COMPARE_PTR compare)
{
	// 根据值去删除,先找到要删除的节点的前驱节点
	CircleLinkNode *pPre = &(list->head);
	CircleLinkNode *pCurrent = list->head.next;
	int i = 0;
	for (int i = 0; i < list->size; i++)
	{
		if (compare(pCurrent, data) == 0)
		{
			// 如果找到了,就删除,前驱节点指向下一个节点
			pPre->next = pCurrent->next;
			break;
		}
		pPre = pPre->next;
		pCurrent = pCurrent->next;
	}
}

// 获取链表的长度
int get_size_circle_linklist(CircleLinkList *list)
{
	if (list != NULL)
	{
		return list->size;
	}
	return -1;
}

// 查找
int find_circle_linklist(CircleLinkList *list, CircleLinkNode *data, COMPARE_PTR compare)
{
	if (data != NULL && list != NULL)
	{
		CircleLinkNode* pCurrent = list->head.next;
		int index = -1;
		while (pCurrent != (&list->head))
		{
			if (compare(data, pCurrent) == 0)
			{
				break;
			}
			pCurrent = pCurrent->next;
			index++;
		}
		return index;
	}
	else
	{
		return -1;
	}
}

// 打印节点
void print_circle_linklist(CircleLinkList *list, PRINT_PTR print)
{
	if (list != NULL)
	{
		CircleLinkNode *pCurrent = list->head.next;
		while (pCurrent != &(list->head))
		{
			print(pCurrent);
			pCurrent = pCurrent->next;
		}
	}
}

// 判断是否为空
int is_empty_circle_linklist(CircleLinkList *list)
{
	if (list != NULL)
	{
		return list->size == 0 ? LIST_IS_EMPTY : LIST_NOT_EMPTY;
	}
	return LIST_IS_EMPTY;
}

// 释放内存
void free_space_circle_linklist(CircleLinkList *list)
{
	if (list != NULL)
	{
		free(list);
	}
}

// 清空链表
void clear_circle_linklist(CircleLinkList *list)
{
	// 将头部指向自身
	list->head.next = &(list->head);
	list->size = 0;
}

测试部分

#include "CircleLinkList.h"

typedef struct
{
	CircleLinkNode *node;
	char name[64];
	int age;
} Person;

// 打印的函数指针
void my_print(CircleLinkNode *node)
{
	Person *p1 = (Person *)node;
	printf("Name: %s,Age: %d\n", p1->name, p1->age);
}

int my_compare(CircleLinkNode *node1, CircleLinkNode *node2)
{
	Person *p1 = (Person *)node1;
	Person *p2 = (Person *)node2;
	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age)
	{
		return 0;
	}
	return -1;
}

int main()
{
	Person p1, p2, p3, p4, p5;
	int copyLen = sizeof(p1.name) / sizeof(p1.name[0]);
	strcpy_s(p1.name, copyLen, "AAAA");
	strcpy_s(p2.name, copyLen, "BBBB");
	strcpy_s(p3.name, copyLen, "CCCC");
	strcpy_s(p4.name, copyLen, "DDDD");
	strcpy_s(p5.name, copyLen, "EEEE");

	p1.age = 10;
	p2.age = 20;
	p3.age = 30;
	p4.age = 40;
	p5.age = 50;

	CircleLinkList *list = init_circle_linklist();
	insert_circle_linklist(list, 0, (CircleLinkNode *)&p1);
	insert_circle_linklist(list, 0, (CircleLinkNode *)&p2);
	insert_circle_linklist(list, 0, (CircleLinkNode *)&p3);
	insert_circle_linklist(list, 0, (CircleLinkNode *)&p4);
	insert_circle_linklist(list, 0, (CircleLinkNode *)&p5);

	print_circle_linklist(list,my_print);

	printf("______________________________\n");
	// 删除一个节点
	remove_by_pos_circle_linklist(list, 2);
	print_circle_linklist(list, my_print);
	printf("______________________________\n");

	// 根据值进行删除
	remove_by_val_circle_linklist(list,(CircleLinkList*)&p2,my_print);
	printf("------------------------------------\n");
	print_circle_linklist(list, my_print);

	// 根据值去查找
	int pos = find_circle_linklist(list, (CircleLinkNode *)(&p2), my_compare);
	if (pos == 1)
	{
		printf("未找到!\n");
	}
	else
	{
		printf("找到了,位置是: %d\n", pos);
	}

	pos = find_circle_linklist(list, (CircleLinkNode *)(&p1),my_compare);
	if (pos == 1)
	{
		printf("未找到!\n");
	}
	else
	{
		printf("找到了,位置是: %d\n", pos);
	}

	printf("list大小为: %d\n", list->size);
	Person *frontPerson = (Person *)front_circle_linklist(list);
	printf("list的第一个元素: Name:%s,Age:%d \n", frontPerson->name, frontPerson->age);

	clear_circle_linklist(list);
	printf("清空之后的大小为: %d", list->size);

	free_space_circle_linklist(list);

	system("pause");
	return 0;
}

二. 双向循环链表

① 为什么需要双向链表

单向链表维护一个指针域,指向下一个元素,在某些情况下,单链表并不是最优的存储结构.
比如算法中需要大量查找某个节点的前驱节点,使用单链表需要从头遍历才能找到.
单链表适合从前往后找,如果有些数据需要从后往前的话,就需要双向链表.

② 双向链表的构成

双向链表的指针域有两个一个是保存的它的前驱节点,一个保存的是它的后继节点

带头节点的双向链表

在这里插入图片描述
节点描述

指针域 prior: 用于指向当前节点的直接前驱节点
数据域 data: 用于存储数据元素
指针域 next: 用于指向当前节点的后继节点

双向循环链表的头节点

在这里插入图片描述

需要将头节点的prior和next都指向自己

实现头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct LinkNode
{
	void* data;
	struct LinkNode *prior;
	struct LinkNode *next;
} LinkNode;

typedef struct LinkList
{
	struct LinkNode *head;
	int size;
} LinkList;

typedef void (*PRINT_PTR)(void *);
typedef int (*COMPARE_PTR)(void *, void *);

// 初始化
LinkList* init_linklist();


// 头插
void push_front_linklist(LinkList *list, void *data);

// 尾插
void push_back_linklist(LinkList *list, void *data);

// 固定位置插入
void insert_by_pos_linklist(LinkList *list, int pos, void *data);

// 删除第一个元素,并返回
void* pop_front_linklist(LinkList *list);

// 删除最后一个元素,并返回
void* pop_back_linklist(LinkList *list);

// 根据位置查找元素
void *get_by_pos_linklist(LinkList *list, int pos);

// 根据值查找元素的位置
int get_by_val_linklist(LinkList *list, void *data,COMPARE_PTR mycompare);

// 根据位置删除元素
void remove_by_pos_linklist(LinkList *list, int pos);


void print_linklist(LinkList *list, PRINT_PTR print);

// 释放内存
void free_space_linklist(LinkList *list);

实现文件

#include "CircleListTwo.h"
// 初始化
LinkList* init_linklist()
{
	LinkList *list = (LinkList *)malloc(sizeof(LinkList));
	if (list != NULL)
	{
		LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
		if (node != NULL)
		{
			list->head = node;
			node->data = NULL;
			node->prior = node; // 
			node->next = node;
			list->size = 0; // list的大小初始化为0
		}
	}
	return list;
}

// 头插
void push_front_linklist(LinkList *list, void *data)
{
	// 准备新节点
	LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
	if (newNode != NULL && list != NULL && data != NULL)
	{
		// 找到第一个节点
		LinkNode *firstNode = list->head->next;
		// 新节点的下一个节点指向第一个节点,上一个节点指向头节点
		newNode->next = firstNode;
		newNode->prior = list->head;
		newNode->data = data;
		// 头节点的下一个节点指向新节点,第一个元素的上一个节点指向新节点
		list->head->next = newNode;
		firstNode->prior = newNode;
		list->size++;
	}
}

// 尾插
void push_back_linklist(LinkList *list, void *data)
{
	// 准备新节点
	LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
	if (newNode != NULL && list != NULL && data != NULL)
	{
		// 找到最后一个节点
		LinkNode *lastNode = list->head->prior;
		// 新节点的下一个节点是头节点,新节点的上一个节点是之前的最后按个节点
		newNode->prior = lastNode;
		newNode->next = list->head;
		newNode->data = data;
		// 头节点的上一个节点变成了新节点,最后一个节点的下一个节点变成了新节点
		list->head->prior = newNode;
		lastNode->next = newNode;
		list->size++;
	}
}

// 固定位置插入
void insert_by_pos_linklist(LinkList *list, int pos, void *data)
{
	// 先找到固定位置的前驱节点
	if (pos < 0 || pos > list->size)
	{
		pos = list->size;
	}
	if (list != NULL)
	{
		LinkNode *pCurrent = list->head; // 头节点
		for (int i = 0; i < pos; i++)
		{
			pCurrent = pCurrent->next;
		}
		// 创建新节点
		LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
		if (newNode != NULL && data != NULL)
		{
			// 首先是确定新节点的位置,上一个节点-> 前驱节点 下一个节点-> pos位置节点
			// 更改前驱节点的下一个节点, 更改pos节点的前驱节点
			newNode->prior = pCurrent;
			newNode->next = pCurrent->next;
			newNode->data = data;
			
			// 将pos节点的上一个节点指向新节点
			pCurrent->next->prior = newNode;// 这一步和下一步不能颠倒,因为颠倒了之后next就变了
			// 将pos的前驱节点的下一个指向新节点
			pCurrent->next = newNode; // 这里顺序不能搞反
			list->size++;
		}
	}
}

// 删除第一个元素,并返回
void *pop_front_linklist(LinkList *list)
{
	if (list != NULL)
	{
		// 找到要删除的节点
		LinkNode *nodeDel = list->head->next;
		// 将头节点的后继节点指向要删除的节点的后继节点
		list->head->next = nodeDel->next;
		// 将删除的后继节点的前驱节点改成头节点
		nodeDel->next->prior = list->head;
		// 取出数据
		void *data = nodeDel->data;
		free(nodeDel);
		list->size--;
		return data;
	}
}

// 删除最后一个元素,并返回
void* pop_back_linklist(LinkList *list)
{
	// 找到要删除的节点
	LinkNode *nodeDel = list->head->prior;
	// 将头结点的前驱节点改成要删除的节点的前驱节点
	// 将要删除的前驱节点的后继节点改成头节点
	list->head->prior = nodeDel->prior;
	nodeDel->prior->next = list->head;
	// 取出数据
	void *data = nodeDel->data;
	free(nodeDel);
	list->size--;
	return data;
}

// 根据位置查找元素
void *get_by_pos_linklist(LinkList *list, int pos)
{
	if (pos < 0 || pos >= list->size)
	{
		return NULL;
	}
	if (list != NULL)
	{
		LinkNode *pCurrent = list->head;
		for (int i = 0; i <= pos; i++)
		{
			pCurrent = pCurrent->next; // 获取到pos位置的节点信息 
		}
		return pCurrent->data;
	}
	return NULL;
}

// 根据值查找元素的位置
int get_by_val_linklist(LinkList *list, void *data,COMPARE_PTR my_compare)
{
	if (list != NULL && data != NULL)
	{
		// 先找到这个数据,要传入一个数据对比的函数指针
		LinkNode *pCurrent = list->head->next; // 第一个节点
		int indexFinded = -1; // 找到的位置
		
		for (int i = 0; i < list->size; i++)
		{
			if (my_compare(pCurrent->data, data) == 0)
			{
				indexFinded = i;
				break;
			}
		}
		return indexFinded;
	}
}

// 根据位置删除元素
void remove_by_pos_linklist(LinkList *list, int pos)
{
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	if (list != NULL)
	{
		// 先找到pos位置的节点
		LinkNode *pCurrent = list->head;
		for (int i = 0; i <= pos; i++)
		{
			pCurrent = pCurrent->next;
		}
		// 将pos位置的前驱节点的下一个节点指向pos位置的下一个节点
		pCurrent->prior->next = pCurrent->next;
		// 将pos位置的后继节点的上一个节点指向pos节点的前驱节点
		pCurrent->next->prior = pCurrent->prior;
		free(pCurrent);
		list->size--;
	}
}


void print_linklist(LinkList *list, PRINT_PTR print)
{
	if (list != NULL)
	{
		// 正向循环遍历
		LinkNode *pCurrent = list->head->next;
		for (int i = 0; i < list->size; i++)
		{
			if (pCurrent == list->head)
			{
				break;
			}
			print(pCurrent->data);
			pCurrent = pCurrent->next;
		}
	}
	else
	{
		return;
	}
}

void free_space_linklist(LinkList *list)
{
	if (list != NULL)
	{
		// 这里释放内存的时候,先缓存下头节点
		LinkNode *pHead = list->head;
		LinkNode *pCurrent = pHead->next;
		while (pCurrent != pHead)
		{
			// 缓存下一个节点
			LinkNode *pNext = pCurrent->next;
			free(pCurrent);
			pCurrent = pNext;
		}
		free(pHead);// 删除头节点
		// 释放链表内存
		free(list);
	}
}

测试代码

#include "CircleListTwo.h"

typedef struct Person
{
	char name[64];
	int age;
}Person;

void my_print(void *v)
{
	Person *p = (Person *)v;
	printf("姓名: %s, 年龄: %d\n", p->name, p->age);
}

int my_compare(void *v1, void *v2)
{
	Person *p1 = (Person *)v1;
	Person *p2 = (Person *)v2;
	if (strcmp(p1->name, p2->name) == 0 && (p1->age == p2->age))
	{
		return 0;
	}
	return -1;

}

int main()
{
	Person p1 = { "Person1",10 };
	Person p2 = { "Person2",20 };
	Person p3 = { "Person3",30 };
	Person p4 = { "Person4",40 };
	LinkList *list = init_linklist();

	push_front_linklist(list, &p1);
	printf("list的大小: %d\n", list->size);
	print_linklist(list, my_print);

	printf("尾部插入p2---------------------------\n");
	push_back_linklist(list, &p2);
	print_linklist(list, my_print);

	printf("在1的位置插入p3-----------------\n");
	insert_by_pos_linklist(list, 1, &p3);
	print_linklist(list, my_print);

	printf("在2的位置插入p4-------------\n");
	insert_by_pos_linklist(list, 2, &p4);
	print_linklist(list, my_print);

	// 删除第一个节点
	Person * p = (Person*)pop_front_linklist(list);
	printf("删除的第一个节点: 姓名:%s,年龄:%d\n", p->name, p->age);
	printf("删除之后的大小: %d\n", list->size);

	// 删除最后一个节点
	p = (Person *)pop_back_linklist(list);
	printf("删除的最后一个节点: 姓名:%s,年龄:%d\n", p->name, p->age);
	printf("删除之后的大小: %d\n", list->size);

	printf("当前的节点信息: \n");
	print_linklist(list,my_print);
	// 现在还剩下p3,p4,根据值进行查找
	int pos = get_by_val_linklist(list, (void *)&p3, my_compare);

	if (pos == -1)
	{
		printf("未找到!");
	}
	else
	{
		printf("找到了,位置是: %d\n", pos);
	}

	pos = get_by_val_linklist(list, (void *)&p2, my_compare);
	if (pos == -1)
	{
		printf("未找到!\n");
	}
	else
	{
		printf("找到了,位置是: %d\n", pos);
	}

	// 根据位置去查找
	p = (Person *)get_by_pos_linklist(list, 1);
	if (p != NULL)
	{
		printf("找到了,姓名: %s,年龄: %d\n", p->name, p->age);
	}
	else
	{
		printf("未找到\n");
	}

	// 根据位置去删除
	remove_by_pos_linklist(list, 1);
	printf("删除之后: \n");
	print_linklist(list, my_print);

	// 释放内存
	free_space_linklist(list);

	system("pause");
	return 0;
}

三. 约瑟夫问题(循环链表解决)

问题描述:
假设: m = 8, n = 3;

使用上面的循环链表解决约瑟夫问题

#include "CircleListTwo.h"
#define M 8
#define N 3

void my_print_int(void *data)
{
	int* p = (int *)data;
	printf("%d ", *p);
}
int main()
{
	// 创建链表
	int myNum[M];
	LinkList *list = init_linklist();
	for (int i = 0; i < M; i++)
	{
		myNum[i] = i + 1;
		insert_by_pos_linklist(list, i, (void *)(&myNum[i]));
	}
	print_linklist(list, my_print_int);
	printf("\n");

	// 约瑟夫问题,遍历链表直到剩下最后一个元素
	// 记录当前的index
	int index = 1;
	LinkNode *pCurrent = list->head->next; // 第一个元素
	while(list->size > 1)
	{
		if (index == N)
		{
			// 如果是第N个元素,就出列,删除,找到要出列的那个元素
			// 先把后驱元素缓存
			LinkNode *next = pCurrent->next;
			printf("%d ", *((int*)(pCurrent->data)));
			// 删除当前节点
			pCurrent->next->prior = pCurrent->prior;
			pCurrent->prior->next = next;
			list->size--;
			free(pCurrent);
			pCurrent = next;
			if (pCurrent == list->head)
			{
				pCurrent = pCurrent->next;
			}
			index = 1;
		}
		pCurrent = pCurrent->next;
		if (pCurrent == list->head)
		{
			pCurrent = pCurrent->next;
		}
		index++;
	}
	if (list->size == 1)
	{
		int num = *((int *)pop_front_linklist(list));
		printf("%d ", num);
	}
	else
	{
		printf("出错!");
	}

	printf("\n");

	system("pause");
	return 0;
}