IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 循环链表的实现 -> 正文阅读

[数据结构与算法]循环链表的实现

循环链表的实现

说明

  1. 参考资料
    • 传智播客扫地僧的数据结构教学视频
  2. 线性表基本知识
  3. 该实现的说明
    • C语言实现
    • 基于单向链表，参考
    • 实现算法和数据的分离

实现

  • circular_list.h
    #ifndef _CIRCULAR_LIST_H_
#define _CIRCULAR_LIST_H_

#ifdef __cplusplus
extern "C"{
#endif


typedef void CIRCULAR_LIST;					// 循环链表类型
typedef struct CIRCULAR_LIST_NODE			// 循环链表节点类型
{
	struct CIRCULAR_LIST_NODE* next;
}CIRCULAR_LIST_NODE;


/* 创建循环链表，返回循环链表的地址 */
CIRCULAR_LIST* CircularList_Create();

/* 销毁循环链表的空间 */
void CircularList_Destroy(CIRCULAR_LIST* list);


/* 清空循环链表的元素 */
void CircularList_Clear(CIRCULAR_LIST* list);


/* 获取循环链表中元素的个数 */
int CircularList_Length(CIRCULAR_LIST* list);


/* 获取循环链表中下标为pos的元素的地址 */
CIRCULAR_LIST_NODE* CircularList_Get(CIRCULAR_LIST* list, int pos);


/* 在下标为pos的位置插入元素node，返回实际插入的位置 */
int CircularList_Insert(CIRCULAR_LIST* list, CIRCULAR_LIST_NODE* node, int pos);


/* 删除循环链表中下标为pos的节点 */
CIRCULAR_LIST_NODE* CircularList_Delete(CIRCULAR_LIST* list, int pos);


/* 删除循环链表中的节点node */
CIRCULAR_LIST_NODE* CircularList_DeleteNode(CIRCULAR_LIST* list, CIRCULAR_LIST_NODE* node);


/* 重置游标 */
CIRCULAR_LIST_NODE* CircularList_ResetSlider(CIRCULAR_LIST* list);


/* 获取当前游标指向的节点 */
CIRCULAR_LIST_NODE* CircularList_Current(CIRCULAR_LIST* list);


/* 返回当前游标指向的节点，并且游标向前移动一步 */
CIRCULAR_LIST_NODE* CircularList_SliderNext(CIRCULAR_LIST* list);

#ifdef __cplusplus
}
#endif

#endif
  • circular_list.c
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circular_list.h"


typedef struct TAG_CIRCULAR_LIST
{
	CIRCULAR_LIST_NODE header;
	CIRCULAR_LIST_NODE* slider;
	int length;
}TAG_CIRCULAR_LIST;


/* 创建循环链表，返回循环链表的地址 */
CIRCULAR_LIST* CircularList_Create()
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 申请头节点
	circular_list = (TAG_CIRCULAR_LIST*)malloc(sizeof(TAG_CIRCULAR_LIST));
	if(circular_list == NULL)
	{
		printf("func CircularList_Create() err: circular_list == NULL\n");
		return NULL;
	}

	// 给申请的空间赋一个初值
	memset(circular_list, 0, sizeof(TAG_CIRCULAR_LIST));

	return circular_list;
}


/* 销毁循环链表的空间 */
void CircularList_Destroy(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 检查输入
	if (list == NULL)
	{
		printf("func CircularList_Destroy() err: list == NULL\n");
		return ;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 避免野指针
	if (circular_list != NULL)
	{
		free(circular_list);
		circular_list = NULL;
	}
		
	return;
}


/* 清空循环链表的元素 */
void CircularList_Clear(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 检查输入
	if (list == NULL)
	{
		printf("func CircularList_Clear() err: list == NULL\n");
		return;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 清空链表
	memset(circular_list, 0, sizeof(TAG_CIRCULAR_LIST));
	
	return;
}


/* 获取循环链表中元素的个数 */
int CircularList_Length(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 检查输入
	if (list == NULL)
	{
		printf("func CircularList_Length() err: list == NULL\n");
		return -1;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	return circular_list->length;
}


/* 获取循环链表中下标为pos的元素的地址 */
CIRCULAR_LIST_NODE* CircularList_Get(CIRCULAR_LIST* list, int pos)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;
	CIRCULAR_LIST_NODE* current_ptr = NULL;
	int i = 0;

	// 检查输入
	if (list == NULL || pos < 0)
	{
		printf("func CircularList_Get() err: list == NULL || pos < 0\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;
	
	// 检查位置合法性
	if (pos >= circular_list->length)
	{
		printf("func CircularList_Get() err: pos >= circular_list->length\n");
		return NULL;
	}

	// 将辅助指针移动到pos位置前一个位置
	current_ptr = (CIRCULAR_LIST_NODE*)circular_list;
	for (i = 0; i < pos; ++i)
	{
		current_ptr = current_ptr->next;
	}

	// 返回pos位置的地址
	return current_ptr->next;
}


/* 在下标为pos的位置插入元素node，返回实际插入的位置 */
int CircularList_Insert(CIRCULAR_LIST* list, CIRCULAR_LIST_NODE* node, int pos)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;
	CIRCULAR_LIST_NODE* current_ptr = NULL;
	CIRCULAR_LIST_NODE* last_ptr = NULL;
	int i = 0;

	// 检查输入
	if (list == NULL || node == NULL || pos < 0)
	{
		printf("func CircularList_Insert() err: list == NULL || node == NULL || pos < 0\n");
		return -1;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 容错检查：当pos >= circular_list->length时，采用尾插法
	if (pos >= circular_list->length)
	{
		pos = circular_list->length;
	}

	// 将辅助指针变量跳转到pos-1位置
	current_ptr = (CIRCULAR_LIST_NODE*)circular_list;
	for (i = 0; i < pos; ++i)
	{
		current_ptr = current_ptr->next;
	}

	// 按照单向链表方式直接插入节点
	node->next = current_ptr->next;
	current_ptr->next = node;
	circular_list->length++;

	// 处理特殊情况
	// 如果此次插入之前循环链表没有节点，需要将链表最后一个节点指向第一个节点
	if (circular_list->length == 1)
	{
		node->next = node;
	}

	// 如果此次插入之前已经有了节点，并且在0号位置插入，正常插入之后最后一个节点指向的节点变成第2个节点，需要修正
	if (circular_list->length != 1 && current_ptr == (CIRCULAR_LIST_NODE*)circular_list)
	{
		// 获取最后一个节点
		last_ptr = (CIRCULAR_LIST_NODE*)circular_list;
		for(i = 0; i < circular_list->length; ++i)
		{
			last_ptr = last_ptr->next;
		}
		// 将最后一个节点指向第一个节点
		last_ptr->next = current_ptr->next;
	}

	return pos;
}


/* 删除循环链表中下标为pos的节点 */
CIRCULAR_LIST_NODE* CircularList_Delete(CIRCULAR_LIST* list, int pos)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;
	CIRCULAR_LIST_NODE* deleted_node = NULL;

	CIRCULAR_LIST_NODE* current_ptr = NULL;
	CIRCULAR_LIST_NODE* last_ptr = NULL;
	int i = 0;

	// 检查输入
	if (list == NULL || pos < 0)
	{
		printf("func CircularList_Delete() err: list == NULL || pos < 0\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 检查pos的合法性
	if (pos >= circular_list->length)
	{
		printf("func CircularList_Delete() err: pos >= circular_list->length\n");
		return NULL;
	}

	// 将current_ptr移动到pos-1的位置
	current_ptr = (CIRCULAR_LIST_NODE*)circular_list;
	for (i = 0; i < pos; ++i)
	{
		current_ptr = current_ptr->next;
	}

	// 按照单向链表的方式删除节点
	deleted_node = current_ptr->next;
	current_ptr->next = deleted_node->next;
	circular_list->length--;

	// 处理特殊情况
	// 如果此次删除之后循环链表中将没有节点，那么此次删除之后circular_list->header->next将指向被删除的元素，需要将其置零
	if (circular_list->length == 0)
	{
		current_ptr->next = NULL;
	}

	// 如果此次删除之后循环链表中还有节点，并且这次删除的是第一个节点，那么删除之后，最后一个节点指向的是一个已经删除的节点，需要修正
	if (circular_list->length > 0 && current_ptr == (CIRCULAR_LIST_NODE*)circular_list)
	{
		// 获取最后一个节点
		last_ptr = (CIRCULAR_LIST_NODE*)circular_list;
		for (i = 0; i < circular_list->length; ++i)
		{
			last_ptr = last_ptr->next;
		}

		// 将最后一个节点指向第一个节点
		last_ptr->next = current_ptr->next;
	}	
	return deleted_node;
}


/* 删除循环链表中的节点node */
CIRCULAR_LIST_NODE* CircularList_DeleteNode(CIRCULAR_LIST* list, CIRCULAR_LIST_NODE* node)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;
	int i = 0;
	CIRCULAR_LIST_NODE* current_ptr = NULL;
	CIRCULAR_LIST_NODE* deleted_node = NULL;
	
	// 参数检查
	if (list == NULL || node == NULL)
	{
		printf("func CircularList_DeleteNode() err: list == NULL || node == NULL\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 遍历循环链表，找到和node相同的节点就退出循环
	current_ptr = (CIRCULAR_LIST_NODE*)circular_list;
	for(i = 0; i < circular_list->length; ++i)
	{
		current_ptr = current_ptr->next;
		if (current_ptr == node)
		{
			deleted_node = current_ptr;
			break;
		}
	}

	// 如果查找不到node，报错；找到node之后删除
	if (i >= circular_list->length)
	{
		printf("func CircularList_DeleteNode() err: node is not in circular list\n");
		return NULL;
	}
	else if(i < circular_list->length)
	{
		CircularList_Delete(circular_list, i);
	}

	return deleted_node;
}


/* 重置游标，返回重置之后游标指向的节点 */
CIRCULAR_LIST_NODE* CircularList_ResetSlider(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 参数检查
	if (list == NULL)
	{
		printf("func CircularList_ResetSlider() err: list == NULL\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 重置slider
	circular_list->slider = circular_list->header.next;

	return circular_list->slider;
}


/* 获取当前游标指向的节点 */
CIRCULAR_LIST_NODE* CircularList_Current(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;

	// 参数检查
	if (list == NULL)
	{
		printf("func CircularList_Current() err: list == NULL\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;
	
	// 返回节点，使用者自己保证游标指向的正确性
	return circular_list->slider;
}


/* 返回当前游标指向的节点，并且游标向前移动一步 */
CIRCULAR_LIST_NODE* CircularList_SliderNext(CIRCULAR_LIST* list)
{
	TAG_CIRCULAR_LIST* circular_list = NULL;
	CIRCULAR_LIST_NODE* current_ptr = NULL;

	// 参数检查
	if (list == NULL)
	{
		printf("func CircularList_SliderNext() err: list == NULL\n");
		return NULL;
	}

	// 将CIRCULAR_LIST_NODE类型的地址转换为TAG_CIRCULAR_LIST类型的地址
	circular_list = (TAG_CIRCULAR_LIST*)list;

	// 记录当前游标位置
	current_ptr = circular_list->slider;

	// 如果循环列表没有节点，报错
	if (circular_list->length == 0)
	{
		printf("func CircularList_SliderNext() err: circular_list->length == 0\n");
		return NULL;
	}
	else
	{
		circular_list->slider = circular_list->slider->next;
	}
	return current_ptr;
}
  • test.c
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "circular_list.h"


/* 约瑟夫问题：N个人围成一圈，由第一个人从1开始报数，报M的人会被淘汰，然后从后一个人重新开始报数，重复以上过程，求出淘汰的人的顺序 */


/* 业务结构，包含一个节点域和一个整形域 */
typedef struct VALUE
{
	CIRCULAR_LIST_NODE* circular_node;
	int value;
}VALUE;


int main(void)
{
	int i = 0;
	int number_of_people = 16;			// 16个人围成一圈
	int death_number = 3;				// 报数为3的人死亡
	VALUE* v = NULL;
	CIRCULAR_LIST* circular_list = NULL;

	// 创建循环链表
	circular_list = CircularList_Create();
	if (circular_list == NULL)
	{
		printf("func main(): circular_list == NULL\n");
		return -1;
	}

	// 设置随机数种子
	srand((unsigned int)time(NULL));

	// 随机生成16个人的value
	for (i = 0; i < number_of_people; ++i)
	{
		v = (VALUE*)malloc(sizeof(VALUE));
		v->circular_node = NULL;
		v->value = rand()%100;			// 随机生成[0,100)的value值

		// 使用头插法插入循环链表
		CircularList_Insert(circular_list, (CIRCULAR_LIST_NODE*)v, 0);
	}

	// 打印循环链表（人围成的圈的顺序）
	for (i = 0; i < CircularList_Length(circular_list); ++i)
	{
		v = (VALUE*)CircularList_Get(circular_list, i);
		printf("%d ",v->value);
	}
	printf("\n");

	// 重置游标，使其指向第一个节点
	CircularList_ResetSlider(circular_list);

	// 报数，并开始淘汰
	while (CircularList_Length(circular_list) > 0)
	{
		// 报数，开始之后第1个人和第death_number个人中间隔着（death_number - 1）跳
		for (i = 0; i < (death_number - 1); ++i)
		{
			CircularList_SliderNext(circular_list);
		}

		// 此时游标刚好指向淘汰的人，通过游标得到这个人的信息，并将这个人踢出游戏
		v = (VALUE*)CircularList_Current(circular_list);
		CircularList_SliderNext(circular_list);			// 删除之前先将游标移动到下一个开始的位置
		CircularList_DeleteNode(circular_list, (CIRCULAR_LIST_NODE*)v);

		// 处理淘汰的节点：1. 输出； 2. 销毁空间（循环链表的库不负责销毁）
		printf("%d\n",v->value);
		if(v != NULL)
		{
			free(v);
			v = NULL;
		}
	}


	// 销毁循环链表
	CircularList_Destroy(circular_list);

	printf("Hello world!\n");
	return 0;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-10-16 19:53:24  更:2021-10-16 19:55:08 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:30:56-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码