"Многоцелевая" реализация связанных списков в чистом C

Ответ 1

A void * - это немного боли в связанном списке, так как вам нужно распределить его отдельно по самому списку. Один из подходов, который я использовал в прошлом, - это иметь структуру с переменным размером, например:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

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

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

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

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

или, в графическом виде (где [n] означает n bytes):

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

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

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

Эта строка литья просто передает адрес символа payload (в типе tNode) как адрес фактического типа полезной нагрузки tPerson.

Используя этот метод, вы можете нести любой тип полезной нагрузки в node, даже разные типы полезной нагрузки в каждом node, без потерянного пространства объединения. Это снижение можно увидеть следующим образом:

union {
    int x;
    char y[100];
} u;

где 96 байтов теряются каждый раз, когда вы сохраняете целочисленный тип в списке (для 4-байтового целого).

Тип полезной нагрузки в tNode позволяет вам легко определить, какой тип полезной нагрузки этот node несет, поэтому ваш код может решить, как его обрабатывать. Вы можете использовать что-то по строкам:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

или (возможно, лучше):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Ответ 2

Мои $.002:

• Составление списка указателей void (неадекватный, более сложный для отладки)

Это не такой плохой выбор, ИМХО, если вы должны написать в C. Вы можете добавить API-методы, чтобы приложение могло предлагать метод print() для облегчения отладки. Аналогичные методы могут быть вызваны, когда (например) элементы будут добавлены или удалены из списка. (Для связанных списков это обычно не обязательно, но для более сложных структур данных - хэш-таблицы, например) - иногда это может быть спасатель.)

• Создание только одного списка, но объединение в виде "типа элемента", содержащее все типы элементов, которые я буду использовать в программе (проще отлаживать; тратить пространство, если элементы не имеют одинакового размера)

Я бы избегал этого, как чума. (Ну, вы спросили.) Наличие настроенной вручную зависимости от времени компиляции от структуры данных до ее содержащихся типов является наихудшим из всех миров. И снова ИМХО.

• Использование макроса препроцессора для регенерации кода для каждого типа, в стиле SGLIB (sglib.sourceforge.net), "имитация" С++ STL (творческое решение, не пустая трата, элементы имеют явный тип, на самом деле они когда они возвращаются, любое изменение в коде списка может быть действительно драматичным)

Интригующая идея, но поскольку я не знаю SGLIB, я не могу сказать гораздо больше.

• Ваша идея/решение

Я бы выбрал первый вариант.

Ответ 3

Я делал это в прошлом, в нашем коде (который с тех пор был преобразован в С++), и в то время решил использовать метод void *. Я просто сделал это для гибкости - мы почти всегда сохраняли указатель в списке в любом случае, а простота решения и удобство его перевешивали (для меня) недостатки других подходов.

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

Ответ 4

Использование макроса препроцессора - лучший вариант. Связанный с ядром Linux список - отличная эффективная реализация циклически связанного списка на C. Очень портативна и проста в использовании. Здесь отдельная версия linux kernel 2.6.29 list.h header.

FreeBSD/OpenBSD sys/queue является еще одним хорошим вариантом для общего списка связанных макросов на основе макросов

Ответ 5

Я не кодировал C в годах, но GLib утверждает, что предоставляет "большой набор служебных функций для строк и общих данных структуры", среди которых есть связанные списки.

Ответ 6

Это хорошая проблема. Есть два решения, которые мне нравятся:

• Dave Hanson C Интерфейсы и реализации использует список указателей void *, что достаточно для меня.

• Для моих учеников я написал awk script для создания функций списка типов. По сравнению с макросами препроцессора требуется дополнительный шаг сборки, но работа системы намного более прозрачна для программистов без большого опыта. И это действительно помогает сделать пример параметрического полиморфизма, который они видят позже в своей учебной программе.

  Здесь выглядит один набор функций:

  int      lengthEL (Explist *l);
  Exp*     nthEL    (Explist *l, unsigned n);
  Explist *mkEL     (Exp *hd, Explist *tl);
  

  awk script - это ужас на 150 строк; он ищет код C для typedef и генерирует набор функций списка для каждого из них. Он очень старый; Я мог бы, вероятно, сделать лучше сейчас: -)

Я бы не дал список профсоюзов время суток (или место на моем жестком диске). Он небезопасен и не расширяется, поэтому вы можете просто использовать void * и сделать с ним.

Ответ 7

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

Скорее, при программировании на языке х вы должны использовать идиомы языка x. Не пишите java, когда используете python. Не пишите C, когда вы используете схему. Не пишите С++, когда вы используете C99.

Сам я, вероятно, в конечном итоге использовал бы что-то вроде предложения Pax, но на самом деле использую объединение char [1] и void * и int, чтобы сделать обычные случаи удобными (и флагом перечислимого типа)

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

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

Ответ 8

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

Другие идеи: встройте интерпретатор Perl или Lisp.

Или перейдите на полпути: связь с библиотекой Perl и сделайте его списком SVS Perl или что-то в этом роде.

Ответ 9

Я бы, вероятно, пошел с помощью метода void *, но мне пришло в голову, что вы можете хранить свои данные в формате XML. Тогда в списке может быть только char * для данных (которые вы будете анализировать по запросу для любых вспомогательных элементов, которые вам нужны).