Intereting Posts
CGI не будет запускаться только на сервере Apache Как я могу получить UTCTime в миллисекундах с 1 января 1970 года на языке c Есть ли демон вызовов разницы (0,0) из программы и запуск программы, которая будет в фоновом режиме и перенаправляет ее вывод Использование GDB с OpenMP MinGW dlltool создает пустой файл Объяснение ++ val ++ и ++ * p ++ в C FreeTds без freetds.conf Альтернативы Autoconf и Autotools? Проверка состояния и присвоение переменной в одном выражении if Понимание распределения памяти, сбой тестовой программы Как сделать клавиши со стрелками и backspace правильно работать при запросе ввода от пользователя в программе на C с помощью termios.h? Почему это законно в C? C Программирование; Получение 2-мерной матрицы со случайными числами без повторения Почему MSVC генерирует предупреждение C4127, когда константа используется в «while» – C Матричные матрицы разброса разного размера с использованием MPI

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

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

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

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

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

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

Чтобы сделать вопрос понятным: какой из вышеперечисленных вариантов лучше?

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

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

Мои $ .002:

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

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

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

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

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

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

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

Я бы выбрал первый выбор.

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

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

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

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

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

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

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

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

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

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

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

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

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

    Вот как выглядит один набор функций:

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

    Скрипт awk – ужас на 150 строк; он ищет код C для typedef s и генерирует набор функций списка для каждого из них. Он очень старый; Вероятно, теперь я мог бы сделать лучше 🙂

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

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

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

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

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