Универсальная функция управления списком в C?

Question

Что такое универсальная функция управления списком в C? (Я видел это, когда просматривал некоторые материалы.)

В чем разница между этой функцией и функцией, которая может принимать элементы любого типа?

Они такие же ...? Как мы можем реализовать их индивидуально, если они не совпадают?

Answer 1

C не имеет понятия «общих» указателей или объектов - самое близкое, что вы можете получить, это использовать указатель void*. Если вы хотите, чтобы один фрагмент кода мог обрабатывать любой тип данных, вам в значительной степени придется использовать указатели void*. Для типов данных с размерами не больше указателя вы можете приводить между типом и void*; для больших типов данных вам придется использовать динамическую память и указать член void* для динамической памяти. Просто следите за утечками памяти!

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

void list_insert(list_node *node, void *data) {
  // ...
}

С другой стороны, если вы хотите сгенерировать код для каждого возможного типа данных, вам придется делать это с макросами, а затем создавать макросы для каждого типа данных, который вы можете использовать. Например:

#define DEFINE_LIST(type) \
  typedef struct list_node_##type { \
    struct list_node_##type *next; \
    type data; \
  }

#define IMPLEMENT_LIST_INSERT(type) \
  void list_##type##_insert(list_node_##type *node, type data) { \
    ... \
  }

DEFINE_LIST(int);     // defines struct list_node_int
DEFINE_LIST(double);  // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert

Answer 2

Общий список, вероятно, будет односвязным и, вероятно, предполагает, что элементы в списке имеют такую ​​структуру:

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

Используя этот макет, вы можете написать функции для управления списками, используя только следующие указатели.

Иногда '...data for node...' будет простым 'void *'; то есть элементы списка будут содержать указатели на следующий узел в списке (или NULL, если следующего узла нет) и указатели на данные.

typedef struct list list;

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

Поскольку вы можете привести любой указатель к 'void *', в списке может быть любое сочетание типов данных, но ваш код должен знать, как с ними обращаться.

Вы спрашиваете об универсальной функции списка 'a', но, вероятно, не существует единого дизайна "одна функция делает все" и, конечно, не простой. Существует ряд возможных наборов функций, которые могут создавать общие списочные функции. Один набор, вдохновленный Lisp, будет состоять из:

void *car(list *lp);    // Return the data for the first item on the list
list *cdr(list *lp);    // Return the tail of the list
list *cons(list *lp1, list *lp2);   // Construct a list from lists lp1 and lp2

list *cond(list *lp, void *data);  // Append data item to list

Вы, вероятно, хотите предоставить возможность проверить, пуст ли список, и некоторые другие элементы.

Одно хорошее изложение, по общему признанию в C ++, можно найти в книге Кенига " Ruminations on C ++ ". Идеи могут быть легко адаптированы к C - это не очень сложно (хотя управление хранилищем в C сложнее, чем в C ++).

Answer 3

Ядро Linux имеет интересную реализацию общего связанного списка в C в своем заголовке linux / list.h . Это двусвязный список с головным узлом, используемый следующим образом:

struct mystruct {
    ...
    /* Contains the next and prev pointers */
    struct list_head mylist;
    ...
    /* A single struct can be in several lists */
    struct list_head another_list;
    ...
};

struct list_head mylist_head;
struct list_head another_list_head;

Некоторые интересные вещи в этом небольшом примере:

• Узел списка встроен в целевую структуру без указания указателя данных.
• Узел списка не обязательно должен находиться в начале целевой структуры.
• Одна структура может находиться в нескольких связанных списках одновременно.
• Следующие и предыдущие указатели в списке указывают на struct list_head, а не на целевую структуру (в приведенном выше примере они указывают на &(foo->mylist) для первого списка и &(foo->another_list) для второго списка).

Все функции манипулирования списком принимают указатели на struct list_head (и большинству вообще все равно, является ли это отдельным головным узлом или одним из встроенных узлов). Чтобы перейти от struct list_head к целевой структуре, вы используете макрос list_entry (который совпадает с макросом containter_of из заголовка linux / kernel.h ), который расширяется до вычитание простого указателя.

Поскольку это двусвязный список с головным узлом, вы можете в O(1):

• Проверьте, является ли список пустым или нет узла в каком-либо списке.
• Получить узел после или перед любым другим узлом (если узел является головой, вы получите первый или последний элемент списка).
• Вставить узел после или перед любым другим узлом (если узел является головкой, вы вставляете в начало или конец списка).
• Удалить узел из списка (для этого нужен только указатель на сам узел).
• Несколько других операций.

Answer 4

Для моего обучения я пришел к разработке этого «универсального» модуля списка, возможно, упрощенной версии ядра Linux, с дополнительными, хотя и необнаруженными ошибками, и использующими расширения gcc ... Любые комментарии приветствуются!

#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
  struct liste_s * suivant ;
} * liste ;


#define newl(t) ( (liste) malloc ( sizeof ( struct liste_s ) + sizeof ( t ) ) )
#define elt(l,t) ( * ( ( t * ) ( l + 1 ) ) )

#define liste_vide NULL
#define videp(l) ( l == liste_vide )
#define lvide() liste_vide
#define cons(e,l) \
  ({ liste res = newl(typeof(e)) ;      \
     res->suivant = l ; \
     elt(res,typeof(e)) = e ;           \
    res ; }) 

#define hd(l,t) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; elt(res,t) ; })
#define tl(l)   ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; res->suivant ;})


#endif

Answer 5

C и его стандартная библиотека не предлагают никаких функций, специфичных для списка.

Но есть библиотеки с множеством полезных функций для C, которые поддерживают типы данных, известные из других языков программирования: http://library.gnome.org/devel/glib/2.18/glib-data-types.html

Answer 6

Я пробовал что-то другое. Это еще одна точка зрения, как доска проблема

Если мы имеем следующую структуру:

typedef struct token {
    int id;
    char *name;
    struct token *next;
} Token;

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

void* tail(void* list, void* (*f)(void *)) {
    void *head = list;

    while(f(head) != NULL) {
        head = f(head);
    }

    return head;
}

Теперь будет необходимо создать функцию, отвечающую за мост между нашей пользовательской структурой и общей практичностью в хвостовой функции. Таким образом, мы имеем:

void* nextToken(void *a) {
    Token *t = (Token *) t;
    return (void *) (a->next);
}

Наконец, мы можем просто использовать:

Token *listTokens;
(...)
Token *lastToken = tail(listTokens, nextToken);

Answer 7

Как уже упоминалось выше, я попытался использовать подход MACROS для создания функций манипулирования списком. Легко создать подпрограмму операции INSERT, но сложно создать операции удаления и перемещения. Далее следует структура списка и подпись подпрограммы INSERT:

#define LIST_DEFINE(type) \
    struct list_node_##type \
    { \
        type *data; \`
        struct list_node_##type *next; \
   };

LIST_INSERT(&ListHead,&Data, DataType);

Где:
ListHead - заголовок связанного списка
Data - Данные, для которых будет создан новый узел, и данные будут вставлены в узел DataType - тип данных передаваемых данных

К вашему сведению, я выделяю память в функции и копирую все данные, переданные во вновь созданный узел, и они добавляют этот узел в связанный список.

Теперь, когда создается подпрограмма LIST_DELETE, узел, который необходимо удалить, будет идентифицирован с использованием уникального идентификатора в данных. Этот идентификатор также передается в подпрограмме MACRO как ключ, который будет заменен в расширении MACRO. Обычная подпись может быть:

LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);

Где:
ListHead - Глава связанного списка
DataType - тип данных данных
myvar->data->str - Уникальный ключ
char* - Тип ключа

Теперь, когда ключ раскрыт, этот же ключ нельзя использовать для сравнения, как если бы мы написали

if((keytype)ListHead->data->key == (keytype)key)

Расширяется до

ListHead->data->myvar->data->str == myvar->data->str

А здесь нет такой переменной, как: ListHead->data->myvar->data->str

Таким образом, этот подход не может работать для записи подпрограмм удаления, и поскольку процедуры обхода и поиска также используют уникальный ключ, с ними также столкнется та же проблема.

И, на несвязанном замечании, как определить логику сопоставления для уникального ключа, поскольку уникальный ключ может быть чем угодно.