【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 //循环单链表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; inext;        }        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 #include "Circlelinklist.h"struct Value{    CircleLinkListNode node;    int val;};int main(void){   struct Valueval[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;}