问实现链接列表

EN

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <stddef.h> /* size_t */
#include <stdbool.h> /* _Bool */
#define _LINKEDLIST_DEFAULT_SIZE (1)

typedef struct _linkedlist _LinkedList;
typedef const unsigned int Index;

#define LinkedList _LinkedList *

LinkedList LinkedList_create();

int LinkedList_add(LinkedList, void *);
int LinkedList_get_val_index(LinkedList, void *);
int LinkedList_get_list_index(LinkedList, const LinkedList *);
int LinkedList_remove(LinkedList, const _Bool, const _Bool);

void LinkedList_set_data(LinkedList, void **, const _Bool, const size_t max);
void LinkedList_clear(LinkedList, const _Bool);
void LinkedList_destroy(LinkedList *, const _Bool);

void *LinkedList_get_value(const LinkedList);

LinkedList LinkedList_get(LinkedList, Index);

LinkedList *LinkedList_get_next(LinkedList);
LinkedList *LinkedList_get_previous(LinkedList);
LinkedList *LinkedList_get_pointer(LinkedList *, Index);

inline size_t LinkedList_get_size_of(const LinkedList);
inline size_t LinkedList_get_size(const LinkedList);

#endif /* _LINKEDLIST_H */

#include <stdlib.h>
#include "LinkedList.h"

#define VALID_LINKEDLIST_CODE (245)
#define _LinkedList_check(l) \
    if ((l) == NULL || (l)->_Valid != VALID_LINKEDLIST_CODE) \
        abort();

struct _linkedlist {
    size_t depth;
    int _Valid;
    void * value;
    struct _linkedlist *next;
    struct _linkedlist *previous;
};

struct _linkedlist *LinkedList_create(void * initial_value)
{ /* Allocate Memory */
    struct _linkedlist *list = malloc(sizeof(struct _linkedlist));

    if(list == NULL)
        return NULL;

    list->depth = 1;
    list->next = NULL;
    list->previous = NULL;
    list->value = initial_value;
    list->_Valid = VALID_LINKEDLIST_CODE;
    return list;
}

void LinkedList_set_data(struct _linkedlist * list, void ** data, const _Bool freeval, const size_t max)
{ /* Sets the internal array of the arraylist */
    _LinkedList_check(list);
    int length;
    for(length = 0; data[length]; ++length);
    if (length < max || max == 0)
        abort();
    LinkedList_clear(list, freeval);
    list->value = data[0];
    for(unsigned int i = 1; i < max; ++i)
        LinkedList_add(list, data[i]);
    list->depth = max;
}

int LinkedList_add(struct _linkedlist *list, void *elem)
{ /* Adds one linked list to the chain with elem as value */
    _LinkedList_check(list);
    ++list->depth;
    struct _linkedlist ** l;
    for(l = &list->next; ( *l != NULL ); l = &(*l)->next)
        ++(*l)->depth;
    (*l) = LinkedList_create(elem);
    (*l)->previous = *l;
    return ((*l)->next == NULL);
}

struct _linkedlist *LinkedList_get(struct _linkedlist *list, const unsigned int index)
{ /* Gets the index'th linked list in the chain */
    _LinkedList_check(list);
    if (index >= list->depth)
        return NULL;
    for(unsigned int i = 0; i < index; list = list->next, i++);
    return list;
}

struct _linkedlist **LinkedList_get_pointer(struct _linkedlist ** list, const unsigned int index)
{ /* Gets the index'th linked list in the chain as a pointer */
    _LinkedList_check(*list);
    if (index >= (*list)->depth)
        return NULL;
    for(unsigned int i = 0; i < index; list = &(*list)->next);
    return list;
}

inline size_t LinkedList_get_size_of(const struct _linkedlist *list)
{ /* Returns the size of the chain of lists in memory */
    _LinkedList_check(list);
    return (sizeof(struct _linkedlist) * list->depth);
}

inline size_t LinkedList_get_size(const struct _linkedlist *list)
{ /* Returns the number of elements in the arraylist */
    _LinkedList_check(list);
    return list->depth;
}

int LinkedList_remove(struct _linkedlist * list, const _Bool index, const _Bool freeval)
{ /* Removes one element at a chain index */
    _LinkedList_check(list);
    if (index >= list->depth)
        return 2;

    LinkedList_clear(LinkedList_get(list, index), freeval);
    --list->depth;
    return 0;
}

void LinkedList_clear(struct _linkedlist * list, const _Bool freeval)
{ /* Clears the list chain */
    _LinkedList_check(list);
    struct _linkedlist * l, * n;
    for( l = list->next; l; l = n) {
        if (freeval)
            free(l->value);
        n = l->next;
        free(l);
    }
    list->next = NULL;
}

void LinkedList_destroy(struct _linkedlist ** list, const _Bool freeval)
{ /* De-allocates the list and its chains from memory
    No usage of list is allowed after this function call */
    _LinkedList_check(*list);
    LinkedList_clear(*list, freeval);
    free(*list);
    *list = NULL;
}

int LinkedList_get_val_index(struct _linkedlist *list, void *elem)
{ /* Looks for elem in list and returns the index or -1 if not found */
    _LinkedList_check(list);
    for(unsigned int i = 0; i < list->depth; ++i)
        if (elem == (LinkedList_get(list, i)->value))
            return i;
    return -1;
}

int LinkedList_get_list_index(struct _linkedlist *list, const struct _linkedlist ** elem)
{
    _LinkedList_check(list);
    for(unsigned int i = 0; i < list->depth; ++i)
        if (*elem == LinkedList_get(list, i))
            return i;
    return -1;
}

void *LinkedList_get_value(const struct _linkedlist *list)
{ /* Return the list's essence, the value */
    return list->value;
}

struct _linkedlist **LinkedList_get_next(struct _linkedlist *list)
{ /* Return the next list in the chain */
    return &list->next;
}

struct _linkedlist **LinkedList_get_previous(struct _linkedlist *list)
{ /* Return the previous line in the chain */
    return &list->previous;
}