Двойная реализация связанных списков в C


Пожалуйста, ознакомьтесь с этой двусвязный список в C. Она обладает основными связанный список функций, как вы ожидали бы плюс некоторые алгоритмы для выполнения в списке.

список.файл заголовка H:

/*
Double linked list.  data represented as void*
*/
#ifndef LIST_H_
#define LIST_H_

#include <stdlib.h>  // size_t def

// signature for compare / match function
typedef int(*list_compare) (const void* a, const void* b);

/* double linked list node representation
   double links to next and previous node
   data element represented as void* to support generic data */
typedef struct node {
    struct node* next;
    struct node* prev;
    void* data;
} node_t;

/* list structure has following field:
   size: number of nodes
   destroy: user defined function for deleting dynamically allocated data element 
   first: head of list
   last: tail of list */
typedef struct list {
    size_t size;
    void(*destroy)(void *data);
    node_t* first;
    node_t* last;
} list_t;

// Lifecycle and misc functions
/* Initialise list with zero nodes. destroy argument can be NULL or a 
user defined function for custom deallocation of user supplied data 
O(1) complexity */
list_t* list_init(void(*destroy)(void *data));

/* Deallocate memory used by list.
O(n) complexity - dependent on no. nodes remaining in list */
void list_free(list_t* list);

/* Returns 1 if empty, zero otherwise. O(1) complexity. */
int list_empty(list_t* list);

/* Returns size of list. O(1) complexity. */
size_t list_size(list_t* list);

// Iterators
/* Returns head of list. O(1) complexity. */
node_t* list_first(list_t* list);

/* Returns tail of list. O(1) complexity. */
node_t* list_last(list_t* list);

/* Returns node_t* after node_t* p in list. O(n) complexity worst case. */
node_t* list_next(node_t* p);

/* Returns node_t* prior to node_t* p in list. O(n) complexity worst case. */
node_t* list_previous(node_t* p);

// Setters and getters
/* Inserts element at head of list. O(1) complexity. */
void list_push_front(list_t* list, void* element);

/* Inserts element at tail of list. O(1) complexity. */
void list_push_back(list_t* list, void* element);

/* Returns data item in node at head of list. node erased. O(1) complexity. */
void* list_pop_front(list_t* list);
/* Returns data item in node at tail of list. node erased. O(1) complexity. */
void* list_pop_back(list_t* list);

/* Returns data item in node at head of list. Containing node retained. 
O(1) complexity. */
void* list_top_front(list_t* list);

/* Returns data item in node at tail of list. Containing node retained.
O(1) complexity. */
void* list_top_back(list_t* list);

/* Removes node p and returns next node.  O(n) complexity. */
node_t* list_remove(list_t* list, node_t* p);

/* Inserts before p and returns node pointing to data. O(n) complexity. */
node_t* list_insert(list_t* list, node_t* p, void* data);

// Algorithms on list
/* Find first item with data in list. Arguments:
list - list to search
data - data item to find
cmp - comparison function - use ordering function like memcmp 
Returns found node or NULL if not found.
O(n) complexity. */
node_t* list_find(list_t* list, void* data, list_compare cmp);

/* Sort list (using mergesort). Arguments:
list - list to sort
cmp  - comparison function - use ordering function like memcmp 
Returns sorted list (actually will be same as list after function ends).
O(n log(n)) complexity. */
list_t* list_sort(list_t* list, list_compare cmp);

/* Reverse elements in list. Returns reversed list.  O(n) complexity. */
list_t* list_reverse(list_t* list);

/* Insert list elements from list2 into list1 after node pos. list2 is 
invalidated after the splice - DO NOT call list_free on list2 after splicing.
Arguments:
list1 - list to splice into
list2 - source list where nodes are moved into list1 after node pos
pos   - list2 nodes are inserted after node pos.  Can use NULL which inserts
list2 nodes after list1 tail node.
returns spliced list.
O(1) complexity - nodes are not copied. */
list_t* list_splice(list_t* list1, list_t* list2, node_t* pos);

/* Removes all consecutive duplicate elements from the list. Only the first 
element in each group of equal elements is left.
Note that list should be sorted in order for remaining elements to be unique because
comparison is of consecutive elements.
Arguments:
list - list to remove duplicate elements
cmp  - comparison function - use ordering function like memcmp
returns de-duplicated list.
O(n) complexity. */
list_t* list_unique(list_t* list, list_compare cmp);

#endif // LIST_H_

список.файл реализации с:

#include "list.h"

/* helper functions */

// create a new node
static node_t* make_node(void* element) {
    node_t* newnode = calloc(1, sizeof(node_t));
    newnode->data = element;
    return newnode;
}

// split uses tortoise and hare going at different speeds to find middle node
static node_t* split(node_t* p) {
    node_t* tortoise = p;
    node_t* hare = p;

    while (hare->next && hare->next->next) {
        tortoise = tortoise->next;
        hare = hare->next->next;
    }

    node_t* middle = tortoise->next;
    // we now want 2 lists from original
    // stop list at start going into 2nd list
    tortoise->next = NULL;  
    return middle;
}

// merge nodes based on comparison function
static node_t* merge(node_t* left, node_t* right, list_compare cmp) {
    if (!left)
        return right;

    if (!right)
        return left;

    // arbitrarily choose left if they are the same
    if (cmp(left->data, right->data) <= 0) {
        left->next = merge(left->next, right, cmp);
        left->next->prev = left;
        left->prev = NULL;
        return left;
    }
    else {
        right->next = merge(left, right->next, cmp);
        right->next->prev = right;
        right->prev = NULL;
        return right;
    }
}

// mergesort algorithm on list
static node_t* mergesort(node_t* head, list_compare cmp) {
    if (!head || !head->next)
        return head;

    node_t* left = head;
    node_t* right = split(head);

    left = mergesort(left, cmp);
    right = mergesort(right, cmp);

    return merge(left, right, cmp);
}

// swap data item in nodes
static void swap_data(node_t* n1, node_t* n2) {
    void* tmp = n1->data;
    n1->data = n2->data;
    n2->data = tmp;
}

// append list2 onto tail of list1
static list_t* append(list_t* list1, list_t* list2) {
    node_t* last1 = list1->last;
    node_t* first2 = list2->first;
    last1->next = list2->first;
    first2->prev = last1;
    list1->last = list2->last;
    return list1;
}


list_t* list_init(void(*destroy)(void *data)) {
    list_t* ll = calloc(1, sizeof(list_t));
    ll->destroy = destroy;
    return ll;
}

void list_free(list_t* list) {

    node_t* it = list->first;
    while (it) {
        node_t* tmp = it;
        it = it->next;
        if (list->destroy) {
            list->destroy(tmp);
        }
        free(tmp);
    }

    free(list);
}


int list_empty(list_t* list) {
    return list->size == 0;
}

size_t list_size(list_t* list) {
    return list->size;
}

node_t* list_first(list_t* list) {
    return list->first ? list->first : NULL;
}
node_t* list_last(list_t* list) {
    return list->last ? list->last : NULL;
}

node_t* list_next(node_t* p) {
    return p ? p->next : NULL;
}

node_t* list_previous(node_t* p) {
    return p ? p->prev : NULL;
}


void list_push_front(list_t* list, void* element) {

    node_t* newnode = make_node(element);

    if (list->first == NULL) {
        list->first = newnode;
        list->last = newnode;
    }
    else {
        node_t* prevfirst = list->first;
        list->first = newnode;
        list->first->next = prevfirst;
        prevfirst->prev = newnode;
    }
    list->size++;
}


void list_push_back(list_t* list, void* element) {

    node_t* newnode = make_node(element);

    if (list->first == NULL) {
        list->first = newnode;
        list->last = newnode;
    }
    else {
        node_t* prevlast = list->last;
        list->last = newnode;
        list->last->prev = prevlast;
        prevlast->next = newnode;
    }
    list->size++;
}


void* list_pop_front(list_t* list) {
    if (list->first == NULL) {
        return NULL;
    }

    node_t* top = list->first;
    void* data = top->data;
    list->first = list->first->next;
    free(top);

    list->size--;

    if (list_empty(list)) {
        list->first = NULL;
        list->last = NULL;
    }
    else {
        list->first->prev = NULL;
    }

    return data;
}


void* list_top_front(list_t* list) {
    if (list->first == NULL) {
        return NULL;
    }

    return list->first->data;
}


void* list_pop_back(list_t* list) {
    if (list->first == NULL) {
        return NULL;
    }

    node_t* top = list->last;
    void* data = top->data;
    list->last = list->last->prev;
    free(top);

    list->size--;

    if (list_empty(list)) {
        list->first = NULL;
        list->last = NULL;
    }
    else {
        list->last->next = NULL;
    }

    return data;
}


void* list_top_back(list_t* list) {
    if (list->first == NULL) {
        return NULL;
    }

    return list->last->data;
}


node_t* list_remove(list_t* list, node_t* p) {
    if (list_empty(list) || !p)
        return NULL;

    for (node_t* it = list->first; it != NULL; it = it->next) {
        if (p == it) {
            // we have found node to remove
            list->size--;

            // 4 cases - only node, start, end, middle

            // if only node in list
            if (!it->prev && !it->next) {
                if (list->destroy) {
                    list->destroy(it->data);
                }
                free(it);

                list->first = list->last = NULL;
                return NULL;
            }
            // else start
            else if (!it->next) {
                it->prev->next = NULL; // because we are deleting it
                if (list->destroy) {
                    list->destroy(it->data);
                }
                free(it);
                return NULL;
            }
            // else at end
            else if (!it->prev) {
                node_t* next = it->next;
                next->prev = NULL;
                if (list->destroy) {
                    list->destroy(it->data);
                }
                free(it);

                list->first = next;

                return next;
            }
            // else somewhere in middle
            else {
                // we have a previous and a next
                node_t* next = it->next;
                node_t* prior = it->prev;

                next->prev = prior;
                prior->next = next;

                if (list->destroy) {
                    list->destroy(it->data);
                }
                free(it);
                return next;
            }
        }
    }

    return NULL;  // node to remove not found
}


node_t* list_insert(list_t* list, node_t* p, void* data) {

    // if get to here we didn't find p - if NULL just insert into first
    if (p == NULL) {
        list_push_back(list, data);
        return list->last;
    }

    for (node_t* it = list->first; it != NULL; it = it->next) {
        if (p == it) {
            // we have found node to insert before
            if (!it->prev) {
                // insert at  head
                list_push_front(list, data);
                return list->first;
            }
            else {
                node_t* newnode = make_node(data);

                it->prev->next = newnode;
                newnode->prev = it->prev;
                newnode->next = it;

                it->prev = newnode;
                list->size++;
                return newnode;
            }
        }
    }

    // if get to here we didn't find p - if NULL just insert at end of list
    list_push_back(list, data);
    return list->last;
}


list_t* list_sort(list_t* list, list_compare cmp) {
    if (list_size(list) <= 1)
        return list;

    node_t* n = mergesort(list->first, cmp);

    list->first = n;

    // need to re-assign list->last - seek to end of list to find new last element
    node_t* it = list->first;
    while (it && it->next) {
        it = it->next;
    }

    list->last = it;

    return list;
}


node_t* list_find(list_t* list, void* data, list_compare cmp) {
    for (node_t* it = list->first; it != NULL; it = it->next) {
        if (cmp(it->data, data) == 0) {
            return it;
        }
    }
    return NULL;
}


list_t* list_reverse(list_t* list) {
    node_t* fwd = list->first;
    node_t* bck = list->last;
    while (fwd && bck && fwd != bck && fwd != bck->next) {
        swap_data(fwd, bck);
        fwd = fwd->next;
        bck = bck->prev;
    }
    return list;
}


// returns list1 after splice.  list2 becomes invalidated after splice
list_t* list_splice(list_t* list1, list_t* list2, node_t* pos) {

    list1->size += list2->size;

    // special case pos null, append list2 on end of list1
    if (pos == NULL) {
        list1 = append(list1, list2);

        free(list2);
        return list1;
    }

    // find pos in list1
    int found = 0;
    for (node_t* it = list1->first; it != NULL; it = it->next) {
        if (it == pos) {
            found = 1;
            node_t* next = it->next;
            it->next = list2->first;
            if (next) {
                node_t* nextnext = next->next;
                it->next = list2->last;
                it->next->prev = list1->last;
                nextnext = it;

                free(list2);
                return list1;
            }
            else {
                // pos must have been list1->last
                list1 = append(list1, list2);

                free(list2);
                return list1;
            }
        }
    }

    // do same as if pos = NUL
    if (!found) {
        list1 = append(list1, list2);

        free(list2);
        return list1;
    }
    return list1;
}

// caller must sort first
list_t* list_unique(list_t* list, list_compare cmp) {
    void* previous = NULL;
    for (node_t* it = list->first; it != NULL; it = it->next) {
        if (previous && cmp(previous, it->data) == 0) {
            // we delete this node
            it = list_remove(list, it);  // returns next node
            // skip back one - otherwise for loop will skip a node
            it = it->prev;
        }
        previous = it->data;
    }
    return list;
}

главная.программа c водителем:

#include "list.h"

#include <stdio.h>

int mycomp(const void* a, const void* b) {
    const int* ia = a;
    const int* ib = b;
    if (*ia > *ib) return 1;

    if (*ib > *ia) return -1;

    return 0;
}

int main() {

    list_t* ll = list_init(NULL); // using ints stored on stack so no need for user defined destroy function.

    int el1 = 1;
    printf("push front %d\n", el1);
    list_push_front(ll, &el1);

    int el2 = 2;
    printf("push front %d\n", el2);
    list_push_front(ll, &el2);

    int el3 = 3;
    printf("push front %d\n", el3);
    list_push_front(ll, &el3);

    int el4 = 4;
    int el5 = 5;
    int el6 = 6;
    printf("push back %d\n", el4);
    list_push_back(ll, &el4);
    printf("push back %d\n", el5);
    list_push_back(ll, &el5);
    printf("push back %d\n", el6);
    list_push_back(ll, &el6);

    printf("size of list now: %d\n", list_size(ll));

    if (list_find(ll, &el5, mycomp) != NULL) {
        printf("item %d found in list\n", el5);
    }
    else {
        printf("item %d not found in list\n", el5);
    }


    int* rettop = list_top_back(ll);
    printf("top back = %d\n", *rettop);

    rettop = list_top_front(ll);
    printf("top front = %d\n", *rettop);

    for (node_t* it = list_first(ll);  it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    int el7 = 7;
    list_insert(ll, list_last(ll), &el7);

    printf("after inserting 7 just before the last element\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    printf("remove each node in list\n");
    node_t* current = list_first(ll);
    while (current) {
        printf("about to remove %p, data=%d\n", current, *(int*)current->data);
        current = list_remove(ll, current);
    }

    // now regenerate list
    int selection[] = { 85, 57, 44, 4, 24, 96, 30, 93, 96, 64 };
    int size = sizeof(selection) / sizeof(selection[0]);

    node_t* next = list_insert(ll, list_first(ll), &selection[0]);
    for (int i = 1; i < size; ++i) {
        next = list_insert(ll, next, &selection[i]);
    }

    printf("linked list now looks like this:\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    if (list_find(ll, &selection[7], mycomp) != NULL) {
        printf("item %d found in list\n", selection[7]);
    }
    else {
        printf("item %d not found in list\n", selection[7]);
    }

    int f = 108;
    if (list_find(ll, &f, mycomp) != NULL) {
        printf("item %d found in list\n", f);
    }
    else {
        printf("item %d not found in list\n", f);
    }

    list_sort(ll, mycomp);

    printf("linked list after sort now looks like this:\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
        if (it->next && *p > *((const int*)it->next->data)) {
            printf("sort failed: %d > %d (next data item)\n", *p, *((const int*)it->next->data));
        }
    }

    ll = list_reverse(ll);
    printf("linked list after list_reverse now looks like this:\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    // test unique
    ll = list_unique(ll, mycomp);
    printf("linked list after list_unique now looks like this:\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    list_t* ll2 = list_init(NULL);
    int el8 = 8;
    int el9 = 9;
    int el10 = 10;
    printf("push back %d on ll2\n", el8);
    list_push_back(ll2, &el8);
    printf("push back %d on ll2\n", el9);
    list_push_back(ll2, &el9);
    printf("push back %d on ll2\n", el10);
    list_push_back(ll2, &el10);

    ll = list_splice(ll, ll2, NULL);
    printf("linked list 1 after splicing ll2 on end:\n");
    for (node_t* it = list_first(ll); it != NULL; it = it->next) {
        const int* p = it->data;
        printf("ptr=%p, data=%d\n", it, *p);
    }

    int* ret1 = list_pop_front(ll);
    printf("pop front %d\n", *ret1);
    int* ret2 = list_pop_front(ll);
    printf("pop front %d\n", *ret2);
    int* ret3 = list_pop_front(ll);
    printf("pop front %d\n", *ret3);

    printf("list size now = %d\n", list_size(ll));

    list_free(ll);

    // do not free a list_t spliced onto another list
    // ie do not call list_free(ll2);
}


1132
4
задан 4 марта 2018 в 03:03 Источник Поделиться
Комментарии
4 ответа


  • Тестирование list->destroy делается слишком много раз. Лучше сделать это в list_init:

        if (!destroy) {
    destroy = dummy_destroy;
    }
    list->destroy = destroy;

    с

    static void dummy_destroy(void * data) {}

  • list_splice излишне многословен.


    1. Он повторяет то, что list_find для.

    2. found это лишнее: Когда if(!found) линия будет достигнута гарантируется, что p не существует (в противном случае один из ранних возвращений был казнен).

    3. Последовательность

          free(list2);
      return list1;

      повторяется слишком много раз.


    4. Функция всегда возвращает list1и поэтому возвращаемое значение не доносит информацию до абонента. Я бы предпочел сделать это void или выяснить что-то полезное для возврата.

      Как Примечание стороны, я не согласен с дизайном решение для лечения несуществующего pos как сигнал для добавления. В такой ситуации мне кажется более логичным, чтобы потерпеть неудачу.


    Все, что сказал, Считаю

    list_splice(list_t * list1, list_t * list2, node_t * pos)
    {
    pos = list_find(list1, pos);
    if (!pos) {
    return NULL;
    }

    list2->last->next = pos->next;
    pos->next->prev = list2->last;
    pos->next = list2->first;
    list2->first->prev = pos;

    free(list2);
    return list1;
    }

    Же самое относится к list_insert и list_remove.


  • В found п. в list_remove можно упростить:

    if (!pos->prev) {
    list->first = pos->next;
    } else {
    pos->prev->next = pos->next;
    }
    if (!pos->next) {
    list->last = pos->prev;
    } else {
    pos->next->prev = pos->prev;
    }

  • Когда появляются последний элемент сверху, list->first автомагически становится NULL после list->first = list->first->next; назначение. Явный list->first = NULL является избыточным. Возможно, вы захотите превратить его в утверждение:

    if (list_empty(list)) {
    assert(list->first == NULL);
    list->last = NULL;
    }

    Же самое относится к list_pop_back.


  • В list_push_front можно упростить (обратите внимание, что определенные вещи, должно произойти, не важно, что):

    newnode->next = list->first;
    if (!list->first) {
    list->last = newnode;
    } else {
    list->first->prev = newnode;
    }
    list->first = newnode;

    Же самое относится к list_push_back.


  • return list->first ? list->first : NULL; это долгий путь, чтобы сказать

    return list->first;

  • Как общее замечание, я не уверен, что разоблачение node_t для клиента это хорошая идея.

4
ответ дан 4 марта 2018 в 06:03 Источник Поделиться

Мои общие соображения:


  • Я могу понять ваш код, и это явным намерением. Я бы спросила еще несколько замечаний вокруг, если заявления, чтобы убедиться, что будущий хранитель не запутаться

  • Потому что вы используете указатели, у вас есть 'уничтожить' функция, чтобы иметь возможность удалять записи из своего списка. Но также, потому что вы используете указатели, вы не требуя, используя код, чтобы убедиться, что он не принял копию указателя, который может быть разрушен'. Если вы предполагаете какой-то подсчет ссылок системы в 'уничтожить' функции или требовать, чтобы копия объекта, указатель никогда не сделано, то вы, вероятно, получите неопределенное поведение'

  • Возможной альтернативой для вас, чтобы вернуть отфильтрованный список элементов, которые были удалены в результате вызова API. например

    resultThing OperationThatRemovesFromList( list_t* класс MyList, list_t* appendWithDiscards);


  • Вызывающий код будет отвечать за уничтожение собственные объекты, это когда он знает, что это можно сделать безопасным образом. (Это сродни ручной сбор мусора)

  • mallocing и освобождая ваши объекты list_t прекрасно, так как ваша библиотека всегда имеет право собственности на них в любом случае

  • Чтобы предотвратить код от условии и использование/манипуляция внутренней структуры, можно скрыть детали вашего list_t имея открытый и закрытый вариант одного из них. Общественное заголовочный файл объявляет значимые внутренние детали и просто байтовый массив такого же размера, как настоящая частная list_t. например

    структура public_list_t {
    Чара[LIST_ELEMENT_SIZE] частная;
    }


где LIST_ELEMENT_SIZE-это макрос, который возвращает правильный размер в зависимости от размера указателей и size_t видах на вашей системе


  • Модульное тестирование: ваша основная функция пример почти очертания модульного тестирования, я хотел бы предложить вам расширить его в качестве модульного теста вашей библиотеки. После каждой операции, делать предположения о свойствах вашего расценено список. (Я надеюсь, что это утверждение будет давать ненулевой код выхода, который может быть использован для автоматизированного модульного тестирования на каждой сборки).

3
ответ дан 4 марта 2018 в 04:03 Источник Поделиться

list_free(ll);

Обратите внимание, что после вызова этой линии, ll это не null, а на самом деле болтались указатель. Решения:

Сделать эти функции возвращают значение null:

ll = list_free(ll);

или сделать "Лл" двойной указатель, и делает это нулевая форма самой функции.

3
ответ дан 4 марта 2018 в 05:03 Источник Поделиться

Я знаю, что обзор код должен просто улучшить код и то, что я предлагаю вам, вероятно, потребуется, чтобы переписать большую его часть, однако я хотел бы поделиться подхода к реализации двусвязный список, который я нашел особенность элегантно. И умопомрачительных, что нужно понять-это то, что большинство из кропотливых если еще разветвления можно избежать путем простого введения дополнительного "конец" узел вместо "первого" и "последнего" указатели.

typedef struct node {
struct node *next;
struct node *prev;
void *data;
} node_t;

typedef struct list {
size_t size;
node_t end;
} list_t;

list_t *list_create()
{
list_t *list = malloc(sizeof(list_t));
list->size = 0;
list->end.next = list->end.prev = &list->end;
return list;
}

node_t *list_insert(list_t *list, node_t *next, void *data)
{
if (!next)
next = &list->end;

node_t *node = malloc(sizeof(node_t));
node->data = data;
node->next = next;
node->prev = next->prev;
node->next->prev = node->prev->next = node;
++list->size;
return node;
}

node_t *list_remove(list_t *list, node_t *node)
{
node_t *next = node->next;
node->next->prev = node->prev;
node->prev->next = node->next;
free(node);
--list->size;
return next;
}

Очевидно вышеперечисленных функций необходимо добавить некоторые проверки безопасности и остальные функции могут быть реализованы на основе тех, как только вы получите ваши головы вокруг этого подхода.

2
ответ дан 4 марта 2018 в 11:03 Источник Поделиться