【C语言数据结构】循环单链表

CircleLinkList.h

#ifndef CIRCLE_LINK_LIST
#define CIRCLE_LINK_LIST

//链表节点
typedef struct _CircleLinkListNode
{
    struct _CircleLinkListNode *next;

}CircleLinkListNode;


//循环单链表
typedef void CircleLinkList;



/*
 * 创建循环单链表
 * @return 返回循环单链表的指针
 */
CircleLinkList* CircleLinkList_Create();

/*
 * 销毁循环单链表
 * @param list 循环单链表的指针
 */
void CircleLinkList_Destroy(CircleLinkList *list);

/*
 * 清空循环单链表
 * @param list 循环单链表的指针
 */
void CircleLinkList_Clear(CircleLinkList *list);

/*
 * 向循环单链表pos位置处插入元素
 * @param list 循环单链表指针
 * @param node 元素指针
 * @param pos 插入的索引
 */
int CircleLinkList_Insert(CircleLinkList *list,CircleLinkListNode *node,int pos);

/*
 * 获取循环单链表中索引位置处的元素
 * @param list   循环单链表指针
 * @param pos   循环单链表索引值
 * @param return 元素指针
 */
CircleLinkListNode* CircleLinkList_Get(CircleLinkList *list,int pos);

/*
 * 删除循环单链表中索引位置处的值
 * @param list 循环单链表的指针
 * @param pos   循环单链表索引
 * @param return 非0表示删除成功
 */
int CircleLinkList_Remove(CircleLinkList *list,int pos);

/*
 * 获取循环单链表当前已存储元素的个数
 * @param list 循环单链表的指针
 * @return 循环单链表中已存储元素的个数
 */
int CircleLinkList_Length(CircleLinkList *list);

/*
 * 删除循环单链表中的特定元素
 * @param list 循环单链表的指针
 * @param pos   循环单链表元素指针
 * @param return 非0表示删除成功
 */
int CircleLinkList_DeleteNode(CircleLinkList* list, CircleLinkListNode* node);

/*
 * 重置循环单链表中的游标，指向表头
 * @param list 循环单链表的指针
 * @return 返回游标指向的元素的指针
 */
CircleLinkListNode* CircleLinkList_Reset(CircleLinkList* list);

/*
 * 获取当前游标指向的元素指针
 * @param list 循环单链表的指针
 * @return 返回当前游标指向的元素指针
 */
CircleLinkListNode* CircleLinkList_Current(CircleLinkList* list);

/*
 * 移动当前游标到下一个元素
 * @param list 循环单链表的指针
 * @return 移动后的游标指向的元素的指针
 */
CircleLinkListNode* CircleLinkList_Next(CircleLinkList* list);




#endif // CIRCLECircleLinkList

CircleLinkList.c

#include "Circlelinklist.h"
#include <malloc.h>

//循环单链表
typedef struct _CircleLinkList
{
    CircleLinkListNode header;//链表头节点
    CircleLinkListNode* cursor;//游标
    int length;//链表长度

}TCircleLinkList;



/*
 * 创建循环单链表
 * @return 返回循环单链表的指针
 */
CircleLinkList* CircleLinkList_Create()
{
    TCircleLinkList *list  = (TCircleLinkList *)malloc(sizeof(TCircleLinkList));

    if(list != 0)
    {
        list->header.next = 0;
        list->length= 0;
    }

    return list;
}

/*
 * 销毁循环单链表
 * @param list 循环单链表的指针
 */
void CircleLinkList_Destroy(CircleLinkList *list)
{
    free(list);
}

/*
 * 清空循环单链表
 * @param list 循环单链表的指针
 */
void CircleLinkList_Clear(CircleLinkList *list)
{
    if(list != 0)
    {
        TCircleLinkList *c_list = (TCircleLinkList *)c_list;
        c_list->header.next = 0;
        c_list->length = 0;
        c_list->cursor = 0;
    }
}

/*
 * 向循环单链表pos位置处插入元素
 * @param list 循环单链表指针
 * @param node 元素指针
 * @param pos 插入的索引
 */
int CircleLinkList_Insert(CircleLinkList *list,CircleLinkListNode *node,int pos)
{
    //类型转换
    TCircleLinkList* l_list = (TCircleLinkList *)list;
    //判断链表指针和节点指针不能为空,当前插入的位置是否合法
    int ret = ((list != 0) && (node != 0) && (pos >= 0) && (pos <= l_list->length));

    if(ret)
    {
        CircleLinkListNode* current = (CircleLinkListNode *)l_list;
        int i;
        //移动到需要插入的位置的前驱
        for(i = 0; i < pos;i++)
        {
            current = current->next;
        }

        node->next = current->next;   //被插入节点的后继指针指向前驱节点的后继指针
        current->next = node;         //前驱节点的后继指针指向被插入节点

        //如果插入的位置是0，则需要修改尾节点的后继指针
        if(pos == 0)
        {
            current = l_list->header.next;
            for(i = 0;i < l_list->length;i++)
            {
                current = current->next;
            }
            current->next = node;//改变尾节点的指针

            //判断插入是否是空表
            if(l_list->length == 0)
            {
                l_list->cursor = node;
                 node->next = node;
            }
        }

        l_list->length++;

    }

    return ret;
}

/*
 * 获取循环单链表中索引位置处的元素
 * @param list   循环单链表指针
 * @param pos   循环单链表索引值
 * @param return 元素指针
 */
CircleLinkListNode* CircleLinkList_Get(CircleLinkList *list,int pos)
{
    CircleLinkListNode* node = 0;
    TCircleLinkList * l_list = (TCircleLinkList *)list;
    //判断链表指针不为空，且获取的索引合法
    if( (l_list != 0) && (pos >= 0))
    {

        CircleLinkListNode* current = (CircleLinkListNode *)l_list;
        int i;
        for(i = 0; i < pos; i++)
        {
            current = current->next;
        }
        node = current->next;
    }

    return node;
}

/*
 * 删除循环单链表中索引位置处的值
 * @param list 循环单链表的指针
 * @param pos   循环单链表索引
 * @param return 非0表示删除成功
 */
int CircleLinkList_Remove(CircleLinkList *list,int pos)
{
    TCircleLinkList * l_list = (TCircleLinkList *)list;
    int ret = ((l_list != 0) && (pos >= 0) && (pos < l_list->length));

    if(ret)
    {
        CircleLinkListNode* current = (CircleLinkListNode *)list;
        CircleLinkListNode* first = l_list->header.next;
        CircleLinkListNode* last = (CircleLinkListNode*)CircleLinkList_Get(l_list, l_list->length - 1);
        CircleLinkListNode *del;
        int i;
        for(i=0; i<pos; i++)
        {
            current = current->next;
        }

        del = current->next;
        current->next = del->next;

        l_list->length--;

        if( first == del )
        {
            l_list->header.next = del->next;
            last->next = del->next;
        }

        if( l_list->cursor == del )
        {
            l_list->cursor = del->next;
        }

        if( l_list->length == 0 )
        {
            l_list->header.next = 0;
            l_list->cursor = 0;
        }
    }

    return ret;
}

/*
 * 获取循环单链表当前已存储元素的个数
 * @param list 循环单链表的指针
 * @return 循环单链表中已存储元素的个数
 */
int CircleLinkList_Length(CircleLinkList *list)
{
    int ret = -1;
    if(list != 0)
    {
        TCircleLinkList * l_list = (TCircleLinkList *)list;
        ret = l_list->length;
    }

    return ret;
}


/*
 * 删除循环单链表中的特定元素
 * @param list 循环单链表的指针
 * @param pos   循环单链表元素指针
 * @param return 被删除元素的索引
 */
int CircleLinkList_DeleteNode(CircleLinkList* list, CircleLinkListNode* node)
{
    int ret = -1;

    if((list != 0) && (node != 0))
    {
        TCircleLinkList * l_list = (TCircleLinkList *)list;
        CircleLinkListNode* current = l_list->header.next;
        int i;
        for(i = 0; i < l_list->length ;i++)
        {
            if(node == current)
            {
                CircleLinkList_Remove(l_list,i);
                ret = i;
                break;
            }
            current = current->next;
        }
    }

    return ret;
}

/*
 * 重置循环单链表中的游标，指向表头
 * @param list 循环单链表的指针
 * @return 返回游标指向的元素的指针
 */
CircleLinkListNode* CircleLinkList_Reset(CircleLinkList* list)
{
    CircleLinkListNode *node = 0;
    if(list != 0)
    {
         TCircleLinkList * l_list = (TCircleLinkList *)list;
         l_list->cursor = l_list->header.next;
         node = l_list->cursor;
    }

    return node;
}

/*
 * 获取当前游标指向的元素指针
 * @param list 循环单链表的指针
 * @return 返回当前游标指向的元素指针
 */
CircleLinkListNode* CircleLinkList_Current(CircleLinkList* list)
{
    CircleLinkListNode *node = 0;
    if(list != 0)
    {
         TCircleLinkList * l_list = (TCircleLinkList *)list;
         node = l_list->cursor;
    }

    return node;
}

/*
 * 移动当前游标到下一个元素
 * @param list 循环单链表的指针
 * @return 移动后的游标指向的元素的指针
 */
CircleLinkListNode* CircleLinkList_Next(CircleLinkList* list)
{
    CircleLinkListNode *node = 0;
    if(list != 0)
    {
         TCircleLinkList * l_list = (TCircleLinkList *)list;
         l_list->cursor = l_list->cursor->next;
         node = l_list->cursor;
    }

    return node;
}

测试代码

#include <stdio.h>
#include "Circlelinklist.h"

struct Value
{
    CircleLinkListNode node;
    int val;
};

int main(void)
{
   struct Value val[5];
   int i;
   struct Value *p;


   CircleLinkList *list = CircleLinkList_Create();
   for(i = 0;i < 5;i++)
   {
        val[i].val = i;
   }

   for(i = 0;i < 5;i++)
   {
       CircleLinkList_Insert(list,(CircleLinkListNode *)&(val[i]),0);
   }

 // CircleLinkList_DeleteNode(list,&(val[0]));



   for(i = 0;i < 6;i++)
   {
       p = CircleLinkList_Get(list,i);
       printf("%d\n",p->val);
       CircleLinkList_Next(list);

   }

   CircleLinkList_Reset(list);
   p = CircleLinkList_Get(list,0);
   printf("%d\n",p->val);







   return 0;
}