Wu Yudong's Blog

循环链表在单向链表的基础之上作了一进步的概念延伸，循环链表让链表操作变的更加灵活，单向链表的尾结点的next链域指向其头结点，本文使用C语言实现一个通用的单向循环链表

定义一个头文件clits.h

文件里面先定义一个循环链表的元素：

#ifndef CLIST_H
#define CLIST_H

#include <stdlib.h>
typedef struct CListElmt_ {
    void *data;
    struct CListElmt_ *next;
} CListElmt;

接着定义循环链表的结构体

typedef struct CList_ {
    int size;
    int (*match) (const void *key1, const void *key2);
    void (*destroy) (void *data);
    CListElmt *head;
} CList;

接着定义公共接口

void clist_init(CList *list, void (*destroy) (void *data));
void clist_destroy(CList *list);
int clist_ins_next(CList *list, CListElmt *element, const void *data);
int clist_rem_next(CList *list, CListElmt *element, void **data);

#define clist_size(list) ((list)->size)
#define clist_head(list) ((list)->head)
#define clist_data(element) ((element)->data)
#define clist_next(element) ((element)->next)

接下来是对应的实现文件clist.c

#include <stdlib.h>
#include <string.h>

#include "clist.h"

//初始化链表
void clist_init(CList *list, void (*destroy) (void *data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    return;
}

//销毁链表
void clist_destroy(CList *list)
{
    void *data;

    //移除每一个元素
    while (clist_size(list) > 0) {
        if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy != NULL) {
            //调用一个用户调用的函数释放动态分配数据
            list->destroy(data);
        }
    }
    //现在不能进行任何操作，清除结构体作为预防
    memset(list, 0, sizeof(CList));
    return;
}

//在新元素插入到指定元素的后面
int clist_ins_next(CList *list, CListElmt *element, const void *data)
{
    CListElmt *new_element;

    //为元素分配存储空间
    if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL)
        return -1;

    //将新元素插入链表
    new_element->data = (void *)data;
    if (clist_size(list) == 0) {

        //当链表为空的时候处理插入
        new_element->next = new_element;
        list->head = new_element;
    } else {

        //链表非空的时候处理插入
        new_element->next = element->next;
        element->next = new_element;
    }
    list->size++; //插入元素后修改链表的size
    return 0;
}

//在指定元素的后面移除元素
int clist_rem_next(CList *list, CListElmt *element, void **data)
{
    CListElmt *old_element;

    //不允许在空链表移除元素
    if (clist_size(list) == 0)
        return -1;

    //从链表中移除元素
    *data = element->next->data;

    if (element->next == element) {

        //如果链表只剩下一个元素
        old_element = element->next;
        list->head = NULL;

    } else {
        old_element = element->next;
        element->next = element->next->next;
    }
    free(old_element); //释放已分配的抽象数据类型
    list->size--;    //删除元素后修改链表的size
    return 0;
}

最后的测试文件test.c

/*
    Copyright：wuyudong
    License: as you wish
    Author: wuyudong <codingwu@gmail.com>
    Date: 2016-12-06
    Blog: www.wuyudong.com
*/

#include <stdio.h>
#include <stdlib.h>

#include "clist.h"

//打印链表
static void print_list(const CList *list)
{
    CListElmt *element;
    int *data, size, i;

    //显示循环链表
    fprintf(stdout, "List size is %d (circling twice)\n", clist_size(list));

    size = clist_size(list);
    element = clist_head(list);

    //重复两次遍历链表来验证是循环链表
    i = 0;
    while (i < size * 2) {
        data = clist_data(element);
        fprintf(stdout, "list[%03d]=%03d\n", (i % size), *data);
        element = clist_next(element);
        i++;
    }
    return;
}

int main(int argc, char **argv)
{
    CList list;
    CListElmt *element;
    int *data, i;

    clist_init(&list, free);    //初始化链表
    element = clist_head(&list); //执行一些循环链表的操作
    for (i = 0; i < 10; i++) {
        if ((data = (int *)malloc(sizeof(int))) == NULL)
            return 1;
        *data = i + 1;
        if (clist_ins_next(&list, element, data) != 0)
            return 1;
        if (element == NULL)
            element = clist_next(clist_head(&list));
        else
            element = clist_next(element);
    }
    print_list(&list);
    element = clist_head(&list);
    for (i = 0; i < 10; i++)
        element = clist_next(element);

    data = clist_data(element);
    fprintf(stdout, "Circling and removing an element after the one containing " "%03d\n", *data);

    if (clist_rem_next(&list, element, (void **)&data) != 0)
        return 1;

    free(data);
    print_list(&list);

    element = clist_head(&list);

    for (i = 0; i < 15; i++)
        element = clist_next(element);

    data = clist_data(element);
    fprintf(stdout, "Circling and inserting 011 after the element containing " "%03d\n", *data);

    if ((data = (int *)malloc(sizeof(int))) == NULL)
        return 1;
    *data = 11;
    if (clist_ins_next(&list, element, data) != 0)
        return 1;
    print_list(&list);
    fprintf(stdout, "Destroying the list\n");
    clist_destroy(&list);        //销毁循环链表

    return 0;
}