【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;
}