泛型链表——C语言实现

使用C语言实现的“泛型链表”，该链表为循环双链表，它的设计参考了C++的STL容器库中的容器list及泛型算法的接口，并使用迭代器来遍历链表。使用时只需要include头文件即可，隐藏了List类型的具体实现。用户并不需要知道链表的具体实现，只需要调用头文件中的接口来进行相应的操作即可。

#include 
#include 
#include “list_v2.h“

typedef struct node
{
    //循环双链表的结点结构
    void* data;//数据域指针
    struct node *next;//指向当前结点的下一结点
    struct node *last;//指向当前结点的上一结点
}Node;

struct list
{
    struct node *head;//头指针，指向头结点
    int data_size;//链表对应的数据所占内存的大小
    int length;//链表list的长度
};

static Node* Position（List list int index）;
static Node* NewNode（int data_size）;
static void linkNodeToList（List list Node *node Node *next_node）;
static int RemoveNode（List list Node *node）;

int InitList（List *list_ptr int data_size）
{
    /***
    函数功能：初始化链表数据域所占内存的大小由data_size给出
    ***/

    List new_list = （List）malloc（sizeof（struct list））;
    *list_ptr = new_list;
    if（new_list == NULL）
        return -1;

    Node *node = （Node*）malloc（sizeof（Node））;
    if（node == NULL）
    {
        free（new_list）;
        *list_ptr = NULL;
        return -1;
    }
    //把头结点的数据域指针置为空
    node->data = NULL;
    //使其指针指向自身
    node->next = node;
    node->last = node;
    //设置list的头指针、数据所占内存的大小和长度
    （*list_ptr）->head = node;
    （*list_ptr）->data_size = data_size;
    （*list_ptr）->length = 0;
    return 0;
}

Iterator Append（List list void *data
                void （*assign）（void* const void*））
{
    /***
    函数功能：把data的内容插入到链表list的末尾
        assign指定数据data间的赋值方法
    ***/

    //调用Insert函数实现，插入位置为end
    return Insert（list data End（list） assign）;
}

static void linkNodeToList（List list Node *node Node *next_node）
{
    /***
    函数功能：把node连接到next_node之前
    ***/
    Node *last_node = next_node->last;
    //把node连接入list中
    //设置相关的结点的next指针
    last_node->next = node;
    node->next = next_node;
    //设置相关结点的last指针
    next_node->last = node;
    node->last = last_node;
    //把node的值连入list后，list的长度加1
    ++list->length;
}

static int RemoveNode（List list Node *node）
{
    /***
    函数功能：从list中，移除node结点，但并不free
        注意，并不free结点，只是把结点从链中分离
    ***/
    if（node == list->head）
        return -1;//不移除头结点
    Node *next_node = node->next;
    Node *last_node = node->last;
    //使结点node从list中分离
    next_node->last = last_node;
    last_node->next = next_node;
    //分享后，list的长度减1
    --list->length;
    return 0;
}

static Node* Position（List list int index）
{
    /***
    函数功能：返回第index个结点的指针
    ***/
    Node *node = NULL;
    int i = 0;
    //如果index比长度的一半小，则从前往后找
    if（index <= list->length>>1）
    {
        //设置node初值
        node = list->head->next;
        for（i = 0; i < index; ++i）
        {
            node = node->next;//向后移一个结点
        }
    }
    //否则从后往前找
    else
    {
        node = list->head;//设置node初值
        for（i = list->length; i > index; --i）
        {
            node = node->last;//向前移一个结点
        }
    }
    return node;
}

static Node* NewNode（int data_size）
{
    /***
    函数功能：新建一个结点，并返回结点的指针，
        结点由两部分组成，一部分是结点本身，
        一部分为data指针指向的数据域空间
        数据所占的内存空间由参数d

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-01-24 23:25  List\
     文件        9991  2014-01-19 00:10  List\list_v2.c
     文件        2874  2013-12-08 19:03  List\list_v2.h