欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

循环链表的实现

程序员文章站 2024-03-21 20:12:28
...

circlelist.h文件

#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef void CircleList;

typedef struct _tag_CircleListNode
{
	struct _tag_CircleListNode* next;
}CircleListNode;

typedef struct _tag_CircleList
{
	int length;
	CircleListNode header;
	CircleListNode* slider;
}TCircleList;

CircleList* CircleList_Create();

int CircleList_Destroy(CircleList* list);

int CircleList_Length(CircleList* list);

void CircleList_Clear(CircleList* list);

CircleListNode* CircleList_Get(CircleList* list,int pos);

CircleListNode* CircleList_Insert(CircleList* list, CircleListNode* node,int pos);

int CircleList_Delete(CircleList* list,int pos);

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

circlelist.c文件

#include "circlelist.h"


CircleList* CircleList_Create()
{
	TCircleList* list = NULL;
	list = (TCircleList*)malloc(sizeof(TCircleList));
	memset(list, 0, sizeof(TCircleList));

	return list;
}

int CircleList_Destroy(CircleList* list)
{
	if (list != NULL)
	{
		free(list);
		list = NULL;
	}
	return 0;
}

int CircleList_Length(CircleList* list)
{
	TCircleList* rList = NULL;
	if (list == NULL)
	{
		printf("Length:list is NULL\n");
		return -1;
	}
	rList = (TCircleList*)list;

	return rList->length;
}

void CircleList_Clear(CircleList* list)
{
	TCircleList* rList = NULL;
	if (list == NULL)
	{
		printf("Clear:list is NULL\n");
		return ;
	}
	rList = (TCircleList*)list;
	rList->length = 0;
	rList->header.next = NULL;
	rList->slider = NULL;
	return ;
}

CircleListNode* CircleList_Get(CircleList* list,int pos)
{
	TCircleList* rList = NULL;
	CircleListNode* current = NULL;
	int i;
	if (list == NULL || pos < 0)
	{
		printf("Get:list is NULL or pos<0\n");
		return NULL;
	}
	rList = (TCircleList*)list;
	current = &(rList->header);

	for (i = 0;i < pos;i++)
	{
		current = current->next;
	}

	return current->next;
}

CircleListNode* CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
	TCircleList* rList = NULL;
	CircleListNode* current = NULL;
	int i;
	if (list == NULL || node == NULL || pos < 0)
	{
		printf("Insert:list is NULL or pos<0\n");
		return NULL;
	}
	rList = (TCircleList*)list;
	current = &(rList->header);

	for (i = 0; (i < pos) && (current->next != NULL); i++)
	{
		current = current->next;
	}

	node->next = current->next;
	current->next = node;

	//若第一次插入节点
	if (rList->length == 0)
	{
		rList->slider = node;
	}

	rList->length++;

	//若为头插法
	if (current == &(rList->header))
	{
		//获取最后一个元素
		CircleListNode* last = CircleList_Get(list, rList->length - 1);
		last->next = current->next;
	}
	return node;
}

int CircleList_Delete(CircleList* list, int pos)
{
	TCircleList* rList = NULL;
	CircleListNode* current = NULL;
	CircleListNode* last = NULL;
	CircleListNode* node = NULL;
	int i = 0;
	if (list == NULL || pos < 0)
	{
		printf("Delete:list is NULL or pos<0\n");
		return -1;
	}
	rList = (TCircleList*)list;
	current = &(rList->header);

	if (pos >= 0 && rList->length > 0)
	{
		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		//若删除第一个元素
		if (current == &(rList->header))
		{
			last = (CircleListNode*)CircleList_Get(rList, rList->length - 1);
		}

		//求要删除的元素
		node = current->next;
		current->next = node->next;

		rList->length--;
		//判断链表是否为空
		if (last != NULL)
		{
			rList->header.next = node->next;
			last->next = node->next;
		}

		//若删除的元素为游标所指的元素
		if (rList->slider == node)
		{
			rList->slider = node->next;
		}

		//若删除元素后链表长度为0
		if (rList->length == 0)
		{
			rList->header.next = NULL;
			rList->slider = NULL;
		}
	}

	return 0;
}

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;
	int i = 0;

	if (sList != NULL)
	{
		CircleListNode* current = &(sList->header);

		//查找node在循环链表中的位置
		for (i=0;i<sList->length;i++)
		{
			if (current->next == node)
			{
				ret = current->next;
				break;
			}
			current = current->next;
		}

		//如果ret找到,根据i去删除
		if (ret != NULL)
		{
			CircleList_Delete(list, i);
		}
	}

	return ret;
}

CircleListNode* CircleList_Reset(CircleList* list)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;

	if (sList!=NULL)
	{
		sList->slider = sList->header.next;
		ret = sList->slider;
	}
	return ret;
}

CircleListNode* CircleList_Current(CircleList* list)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;

	if (sList != NULL)
	{
		ret = sList->slider;
	}
	return ret;
}

//把当前位置返回,并且游标下移
CircleListNode* CircleList_Next(CircleList* list)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;

	if (sList != NULL && sList->slider != NULL)
	{
		ret = sList->slider;
		sList->slider = ret->next;
	}

	return ret;
}

main.c文件

#include "circlelist.h"

struct Value
{
	CircleListNode circlenode;
	int v;
};

int main()
{
	//约瑟夫问题求解
	int i = 0;
	CircleList* list = CircleList_Create();

	struct Value v1, v2, v3, v4, v5, v6, v7, v8;
	v1.v = 1;
	v2.v = 2;
	v3.v = 3;
	v4.v = 4;
	v5.v = 5;
	v6.v = 6;
	v7.v = 7;
	v8.v = 8;

	CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));

	//怎样证明是循环链表
	for (i = 0; i < CircleList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)CircleList_Get(list,i);
		printf("%d\n", pv->v);
	}

	printf("\n");

	for (i=0;i<CircleList_Length(list);i++)
	{
		struct Value* pv = (struct Value*)CircleList_Next(list);
		printf("%d\n", pv->v);
	}

	printf("\n");

	//重置游标
	CircleList_Reset(list);

	while (CircleList_Length(list)>0)
	{
		struct Value* pv= NULL;
		for (i=1;i<3;i++)
		{
			CircleList_Next(list);
		}
		pv = (struct Value*)CircleList_Current(list);
		printf("%d\n", pv->v);
		CircleList_DeleteNode(list, (CircleListNode*)pv);
	}

	CircleList_Destroy(list);

	system("pause");
	return 0;
}

关于循环链表概念,请看:https://www.cnblogs.com/zhaobinyouth/p/9826312.html

相关标签: 循环链表