«Многоцелевой» реализация связанного списка в чистом виде C

Question

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

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

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

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

• Составление списка пустых указателей (своего рода безвкусный; труднее отлаживать)
• Making только один список, но имеющий союз как «тип элемента», содержащий все типы элементов, которые я буду использовать в программе (проще отлаживать: тратить пространство, если элементы не имеют одинакового размера)
• Использование макроса препроцессора для регенерации кода для каждого типа в стиле SGLIB, 'имитация' C++ STL (творческое решение, не пустая трата, элементы имеют явный тип, на самом деле они есть, когда они возвращаются; любое изменение i п список кодов может быть очень драматичным)
• Ваша идея/решение

Для того, чтобы этот вопрос ясный: который один из вышеперечисленных лучше всего?

PS: Поскольку я в основном в академическом контексте, меня также очень интересует мнение людей, работающих с чистым C в этой отрасли. Я понимаю, что большинство чистых программистов C находятся во встроенных областях устройств, где я не думаю, что такая проблема, с которой я столкнулась, является общей. Однако, если кто-то знает, как это делается «в реальном мире», мне было бы очень интересно ваше мнение.

Answer 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)); 

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

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

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

+----------------+ 
| 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 полезной нагрузки.

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

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

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

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

#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; 

Answer 2

Мои $ 0,002:

• Составление списка пустых указателей (своего рода diselegant; труднее отлаживать)

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

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

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

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

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

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

Я бы с первым выбором.

Answer 3

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

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

Answer 4

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

Answer 5

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

• Дэйв Хэнсон C Interfaces and Implementations использует список void * указателей, который достаточно хорош для меня.

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

  Вот что один набор функций выглядит следующим образом:

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

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

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

Answer 6

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

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

Myself, я бы, вероятно, в конечном итоге, используя что-то вроде внушения Пакса, но на самом деле использовать объединение полукокса [1] и пустоту * и ИНТ, чтобы сделать общие дела удобно (и флаг enumed типа)

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

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

Answer 7

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

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

Или перейдите на полпути: ссылка на библиотеку Perl и сделайте список Perl SV или еще что-нибудь.

Answer 8

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

Answer 9

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

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