circlelist.h
===========================================
#ifndef _CIRCLELIST_H_
#define _CIRCLELIST_H_
typedef void CircleList;
typedef struct _tag_CircleListNode
{
struct _tag_CircleListNode* next;
}CircleListNode;
CircleList* CircleList_Create();
void CircleList_Clear(CircleList* clist);
int CircleList_Length(CircleList* clist);
int CircleList_Insert(CircleList* clist, int pos, CircleListNode* node);
CircleListNode* CircleList_Get(CircleList* clist, int pos);
CircleListNode* CircleList_Delete(CircleList* clist, int pos);
void CircleList_Destroy(CircleList* clist);
//add
CircleListNode* CircleList_DeleteNode(CircleList* clist, CircleListNode* node);
CircleListNode* CircleList_Reset(CircleList* clist);
CircleListNode* CircleList_Current(CircleList* clist);
CircleListNode* CircleList_Next(CircleList* clist);
#endif // _CIRCLELIST_H_
========================================
circlelist.c
========================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circlelist.h"
typedef struct _tag_CircleList
{
CircleListNode header;
CircleListNode* slider;
int length;
}TCircleList;
CircleList* CircleList_Create()
{
TCircleList* tclist = (TCircleList*)malloc(sizeof(TCircleList));
if(tclist == NULL)
{
return NULL;
}
tclist->header.next = NULL;
tclist->slider = NULL;
tclist->length = 0;
return tclist;
}
void CircleList_Clear(CircleList* clist)
{
if(clist == NULL)
{
return;
}
TCircleList* tclist = (TCircleList*)clist;
tclist->header.next = NULL;
tclist->slider = NULL;
tclist->length = 0;
}
int CircleList_Length(CircleList* clist)
{
TCircleList* tclist = (TCircleList*)clist;
if(clist == NULL)
{
return -1;
}
return tclist->length;
}
int CircleList_Insert(CircleList* clist, int pos, CircleListNode* node)
{
TCircleList* tclist = (TCircleList*)clist;
if(clist == NULL || node == NULL)
{
return -1;
}
if(pos < 0 || pos > CircleList_Length(tclist))
{
return -2;
}
CircleListNode* current = (CircleListNode*)tclist;
int i;
for(i = 0; (i < pos) &&(current->next != NULL); i++)
{
current = current->next;
}
//current->next 0号节点的地址
node->next = current->next;
current->next = node;
//若第一次插入节点
if(tclist->length == 0)
{
tclist->slider = node;
}
tclist->length++;
//若头插法
if(current == (CircleListNode*)tclist)
{
CircleListNode* last = CircleList_Get(tclist, tclist->length - 1);
last->next = current->next;
}
return 0;
}
CircleListNode* CircleList_Get(CircleList* clist, int pos)
{
TCircleList* tclist = (TCircleList*)clist;
if(clist == NULL || pos < 0 || tclist->length <= 0)
{
return NULL;
}
CircleListNode* current = (CircleListNode*)tclist;
CircleListNode* ret = NULL;
int i;
for(i = 0; (i < pos)&&(current->next != NULL) ; i++)
{
current = current->next;
}
ret = current->next;
return ret;
}
CircleListNode* CircleList_Delete(CircleList* clist, int pos)
{
TCircleList* tclist = (TCircleList*)clist;
if(clist == NULL || pos < 0 || pos > tclist->length || tclist->length <= 0)
{
return NULL;
}
CircleListNode* current = (CircleListNode*)tclist;
CircleListNode* ret = NULL;
CircleListNode* last = NULL;
int i;
for(i = 0; (i < pos)&&(current->next != NULL) ; i++)
{
current = current->next;
}
if(current == (CircleListNode*)tclist)
{
last = CircleList_Get(tclist, tclist->length -1);
}
//求要删除的元素
ret = current->next;
current->next = ret->next;
tclist->length--;
//判断链表是否为空
if(last != NULL)
{
tclist->header.next = ret->next;
last->next = ret->next;
}
//若删除的元素为游标所指的元素
if(tclist->slider == ret)
{
tclist->slider = ret->next;
}
//若删除元素后，链表长度为0
if(tclist->length == 0)
{
tclist->header.next = NULL;
tclist->slider = NULL;
}
return ret;
}
void CircleList_Destroy(CircleList* clist)
{
if(clist != NULL)
{
free(clist);
}
return;
}
CircleListNode* CircleList_DeleteNode(CircleList* clist, CircleListNode* node)
{
TCircleList* tclist = (TCircleList*)clist;
if(clist == NULL || node == NULL)
{
return NULL;
}
CircleListNode* current = (CircleListNode*)tclist;
CircleListNode* ret = NULL;
int i;
for(i = 0; i < tclist->length; i++)
{
if(current->next == node)
{
ret = current->next;
break;
}
current = current->next;
}
if(ret != NULL)
{
CircleList_Delete(tclist, i);
}
return ret;
}
CircleListNode* CircleList_Reset(CircleList* clist)
{
TCircleList* tclist = (TCircleList*)clist;
CircleListNode* ret = NULL;
if(clist == NULL)
{
return NULL;
}
tclist->slider = tclist->header.next;
ret = tclist->slider;
return ret;
}
CircleListNode* CircleList_Current(CircleList* clist)
{
TCircleList* tclist = (TCircleList*)clist;
CircleListNode* ret = NULL;
if(clist == NULL)
{
return NULL;
}
ret = tclist->slider;
return ret;
}
CircleListNode* CircleList_Next(CircleList* clist)
{
TCircleList* tclist = (TCircleList*)clist;
CircleListNode* ret = NULL;
if(tclist == NULL || tclist->slider == NULL)
{
return NULL;
}
ret = tclist->slider;
tclist->slider = ret->next;
return ret;
}
=========================================
circlelist_test.c
=========================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circlelist.h"
typedef struct Value
{
CircleListNode header;
int v;
}Value;
int main01()
{
CircleList* clist = CircleList_Create();
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_Clear(clist);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v1);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v2);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v3);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v4);
int i;
for(i = 0; i < 2*CircleList_Length(clist); i++)
{
Value* tmp;
tmp = (Value*)CircleList_Get(clist, i);
printf("the clist node: %d \n", tmp->v);
}
Value* delNode = (Value*)CircleList_Delete(clist, 0);
printf("the delNode node: %d \n", delNode->v);
for(i = 0; i < CircleList_Length(clist); i++)
{
Value* tmp;
tmp = (Value*)CircleList_Get(clist, i);
printf("the clist node: %d \n", tmp->v);
}
Value* tmp;
tmp = (Value*) CircleList_DeleteNode(clist, (CircleListNode*)&v2);
printf("the tmp node: %d \n", tmp->v);
for(i = 0; i < CircleList_Length(clist); i++)
{
Value* tmp;
tmp = (Value*)CircleList_Get(clist, i);
printf("the clist node: %d \n", tmp->v);
}
CircleList_Reset(clist);
while(CircleList_Length(clist) > 0)
{
Value *pv = NULL;
for(i = 1; i<3; i++)
{
CircleList_Next(clist);
}
pv = (Value*)CircleList_Current(clist);
printf("%d \n", pv->v);
CircleList_DeleteNode(clist, (CircleListNode*)pv);
}
CircleList_Destroy(clist);
printf("Hello world!\n");
return 0;
}
====================================
circlelist_test01.c
====================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circlelist.h"
//=======约瑟夫问题==========//
typedef struct Value
{
CircleListNode header;
int v;
}Value;
int main()
{
CircleList* clist = CircleList_Create();
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_Clear(clist);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v1);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v2);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v3);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v4);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v5);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v6);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v7);
CircleList_Insert(clist, CircleList_Length(clist), (CircleListNode*)&v8);
int i;
for(i = 0; i < CircleList_Length(clist); i++)
{
Value* tmp;
tmp = (Value*)CircleList_Get(clist, i);
printf("the clist node: %d \n", tmp->v);
}
printf("\n");
CircleList_Reset(clist);
while(CircleList_Length(clist) > 0)
{
Value *pv = NULL;
for(i = 1; i<3; i++)
{
CircleList_Next(clist);
}
pv = (Value*)CircleList_Current(clist);
printf("%d \n", pv->v);
CircleList_DeleteNode(clist, (CircleListNode*)pv);
}
CircleList_Destroy(clist);
printf("Hello world!\n");
return 0;
}
