Быстрая общего назначения связанного списка в C


Я хочу использовать это, когда какая-то функция должна возвращать список что-то. Это работает, как я думаю, что это должно или есть неопределенное поведение где-то? Что я действительно пытался добиться что-то вроде шаблона <list> из C++ - для любого типа. Я не уверен, если есть стандартное решение/включать/библиотеке для этого.

список.ч

#pragma once

#include <stddef.h>

struct list_handler
{
    struct list_node *head;
    struct list_node *tail;
    size_t count;
};

struct list_node
{
    void *data;
    struct list_node *next;
};

void list_init(struct list_handler *list);
void list_add(struct list_handler *list, void *data);
void list_free(struct list_handler *list);
void list_foreach(struct list_handler *list, void (*foreach_function)(void *));

список.с

#include "list.h"

#include <stdlib.h>

void list_init(struct list_handler *list)
{
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
}

void list_add(struct list_handler *list, void *data)
{
    struct list_node *new_node = malloc(sizeof(struct list_node));

    new_node->data = data;
    new_node->next = NULL;

    if (list->count > 0)
    {
        list->tail->next = new_node;
    }
    else
    {
        list->head = new_node;
    }

    list->tail = new_node;

    ++list->count;
}

void list_free(struct list_handler *list)
{
    struct list_node *current = list->head;
    struct list_node *previous;

    while (current != NULL)
    {
        previous = current;
        current = current->next;

        free(current);

        list->head = current;
        --list->count;
    }

    list->tail = NULL;
}

void list_foreach(struct list_handler *list, void (*foreach_function)(void *))
{
    struct list_node *current = list->head;

    while (current != NULL)
    {
        (*foreach_function)(current->data);
        current = current->next;
    }
}

Использование:

void list_print(void *data)
{
    int *temp = (int*) data;
    printf("%d\n", *temp);
}

void list_free_data(void *data)
{
    int *temp = (int*) data;
    free(temp);
    data = NULL;
}

int main(int argc, char *argv[])
{
    struct list_handler list;
    list_init(&list);

    for (size_t i = 0; i < 3; ++i)
    {
        int *data = malloc(sizeof(int));
        *data = i;
        list_add(&list, data);
    }

    list_foreach(&list, list_print);
    list_foreach(&list, list_free_data);

    list_free(&list);

    return 0;
}


166
2
задан 19 февраля 2018 в 07:02 Источник Поделиться
Комментарии
2 ответа


  1. "То, что я действительно пытался добиться что-то вроде шаблона <list> из C++ - для любого типа." Подход имеет ограниченную применимость, что он хорошо управляется с указателями на типы объектов, не любой тип. Все-таки это достаточно для многих приложений.

  2. size_t count элемент является необязательным с текущей функции интерфейса как только ноль-Несс испытаны и которые могут быть определены другие простой код.

  3. Дополнительно: с текущей функции интерфейса, отслеживание как head и tail не нужен. Указатель хвоста вполне достаточно. Пусть хвост указывают на главе списка, а не NULL. Сейчас struct list_handler может быть простой указатель вместо. list_init(); можно было бы заменить struct list_handler *list = NULL;

  4. Определение struct list_node не требуется list.h. Перейти к list.c для упрощения пользовательского представления этого list_... код.

  5. Как упомянул @Йоп Эгген, list_foreach должен иметь переменную состояния. Также имеет возвращаемое значение, которое останавливает цикл, если не равно нулю-это очень полезно. Возможно int или указатель на data. Вы можете использовать это, чтобы выполнить поиск.

    int list_foreach(struct list_handler *list, 
    int (*foreach_function)(void *state, void *data), void *state) {
    struct list_node *current = list->head;
    while (current != NULL) {
    int i = (*foreach_function)(state, current->data);
    if (i) {
    return i;
    }
    current = current->next;
    }
    return 0;
    }

  6. Как free() принимает free(NULL), list_free() следует также терпеть list_free(NULL).

2
ответ дан 19 февраля 2018 в 05:02 Источник Поделиться

В list_free есть небольшие погрешности.
Является ли функция должна освободить списка к проектированию API. Может быть, вы не хотите, висячие указатели. Тогда название должно быть лучше list_clear.

void list_free(struct list_handler *list)
{
struct list_node *current = list->head;
struct list_node *previous;

while (current != NULL)
{
previous = current;
current = current->next;

//- free(current);
free(previous); //+

list->head = current;
--list->count;
}

list->tail = NULL;
free(list); //+
}

Освобождение данные-это не список проблемы, вводит в заблуждение, особенно с void*.

void list_free_data(void *data)
{
//int *temp = (int*) data;
//free(temp);
//data = NULL;
free(data);
}

Присваивая значение null для данных не имеет никакого эффекта.

Однако, если вы хотите бесплатно список с освобождением данные:

list_foreach(list, free);
list_free(list);
free(list);

В list_foreach ограничена, так как она должна работать с побочные эффекты, сохранить результаты или другом контексте, в глобальные переменные. Лучше обеспечить для каждого дополнительного параметра. Так что плохой стиль кодирования не является неизбежным.

Для остальных: мне нравится API, чтобы предоставить полный набор операций, то есть с remove тоже.

2
ответ дан 19 февраля 2018 в 09:02 Источник Поделиться