循环链表的实现
程序员文章站
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