«Многоцелевая» реализация связанного списка на чистом C
https://stackoverflow.com/questions/736307
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Это не совсем технический вопрос, поскольку я знаю C достаточно, чтобы делать то, что мне нужно (я имею в виду, чтобы «не позволять языку мешать вам»), так что этот вопрос, по сути, сводится к тому, «в каком направлении?» взять' вопрос.
Ситуация такова:В настоящее время я прохожу углубленный курс по алгоритмам, и ради того, чтобы «вырасти программистом», мне необходимо использовать чистый C для реализации практических заданий (он работает хорошо:практически любая маленькая ошибка, которую вы совершаете, на самом деле заставляет вас полностью понять, что вы делаете, чтобы ее исправить).В ходе реализации я, очевидно, столкнулся с проблемой реализации «базовых» структур данных с нуля:на самом деле не только связанные списки, но и стеки, деревья и так далее.
В этой теме я концентрируюсь на списках, потому что обычно это структура, которую я часто использую в программе, либо в качестве «основной» структуры, либо в качестве «вспомогательной» структуры для других, более крупных структур (например, хэш-дерева, которое разрешает конфликты при использовании связанного списка).
Для этого необходимо, чтобы в списке хранились элементы множества разных типов. Здесь я предполагаю, что не хочу перекодировать список для каждого типа.Итак, я могу предложить следующие варианты:
- Создание списка указателей void (довольно неэлегантно;труднее отладить)
- Составляя только один список, но имея союз как «тип элемента», содержащий все типы элементов, которые я буду использовать в программе (проще отлаживать;тратит пространство, если все элементы не одинакового размера)
- Использование макроса препроцессора для регенерации кода для каждого типа в стиле СГЛИБ, «имитируя» STL C++ (творческое решение;не тратит место;элементы имеют явный тип, которым они фактически являются на момент возврата; любое изменение в коде списка может быть очень драматичным)
- Ваша идея/решение
Чтобы прояснить вопрос:какой из вышеперечисленных лучше?
ПС:Поскольку я в основном работаю в академическом контексте, мне также очень интересно мнение людей, работающих с чистым 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 тип полезной нагрузки.
Используя этот метод, вы можете переносить в узел любой тип полезной нагрузки, даже разные типы полезной нагрузки в каждом узле, без пустого пространства союза.Эту потерю можно увидеть по следующему:
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;
Другие советы
Мои 0,002 доллара:
- Создание списка указателей на пустоту (довольно неэлегантно;труднее отладить)
ИМХО, это не такой уж плохой выбор, если вам приходится писать на C.Вы можете добавить методы API, чтобы приложение могло предоставлять метод print() для упрощения отладки.Подобные методы могут быть вызваны, когда (например) элементы добавляются в список или удаляются из него.(Для связанных списков в этом обычно нет необходимости, но для более сложных структур данных — например, хеш-таблиц) — иногда это может быть спасением.)
- Создание только одного списка, но с объединением в качестве «типа элемента», содержащего все типы элементов, которые я буду использовать в программе (проще отлаживать;тратит пространство, если все элементы не одинакового размера)
Я бы избегал этого, как чумы.(Ну, вы же спрашивали.) Наличие настраиваемой вручную зависимости времени компиляции структуры данных от содержащихся в ней типов — худший из всех миров.Опять же, ИМХО.
- Использование макроса препроцессора для регенерации кода для каждого типа в стиле SGLIB (sglib.sourceforge.net), «имитируя» STL C++ (творческое решение;не тратит место;элементы имеют явный тип, которым они фактически являются на момент возврата;любое изменение в коде списка может быть очень драматичным)
Интригующая идея, но поскольку я не знаю SGLIB, больше ничего сказать не могу.
- Ваша идея/решение
Я бы выбрал первый вариант.
Я делал это раньше в нашем коде (который с тех пор был преобразован в C++) и в то время остановился на подходе void*.Я сделал это просто для гибкости - мы все равно почти всегда сохраняли указатель в списке, а простота решения и удобство его использования перевешивали (для меня) недостатки других подходов.
При этом был один раз, когда это вызвало неприятную ошибку, которую было трудно отладить, так что это определенно не идеальное решение.Я думаю, что я бы все равно взял его, если бы делал это снова сейчас.
Использование макроса препроцессора — лучший вариант.А Связанный список ядра Linux — отличная эффективная реализация циклически связанного списка в C.Очень портативен и прост в использовании. Здесь отдельная версия заголовка list.h ядра Linux 2.6.29.
FreeBSD/OpenBSD система/очередь это еще один хороший вариант для общего связанного списка на основе макросов.
Я не программировал C много лет, но GLib утверждает, что предоставляет «большой набор служебных функций для строк и общих структур данных», среди которых есть связанные списки.
Хотя заманчиво подумать о решении такого рода проблем с использованием методов другого языка, скажем, дженериков, на практике это редко приводит к победе.Вероятно, существуют некоторые готовые решения, которые в большинстве случаев делают все правильно (и сообщают вам в своей документации, когда они ошибаются), их использование может упустить суть задания, поэтому я бы дважды подумал об этом.В очень немногих случаях может оказаться целесообразным развернуть собственный проект, но для проекта любого разумного размера вряд ли стоит затрачивать усилия на отладку.
Скорее, при программировании на языке x вам следует использовать идиомы языка x.Не пишите Java, когда используете Python.Не пишите C, когда используете схему.Не пишите C++, если используете C99.
Лично я, вероятно, в конечном итоге воспользуюсь чем-то вроде предложения Пакса, но на самом деле использую объединение char[1] и void* и int, чтобы сделать общие случаи удобными (и флаг перечислимого типа)
(Я также, вероятно, в конечном итоге реализовал бы дерево Фибоначчи, просто потому, что это звучит аккуратно, и вы можете реализовать RB-деревья только столько раз, прежде чем оно потеряет свой вкус, даже если это лучше для общих случаев, для которых оно будет использоваться. .)
редактировать: Судя по вашему комментарию, похоже, у вас есть довольно хороший случай для использования готового решения.Если ваш инструктор позволяет это и предлагаемый им синтаксис вам удобен, попробуйте.
Это хорошая проблема.Есть два решения, которые мне нравятся:
Дэйв Хэнсон C-интерфейсы и реализации использует список
void *указатели, что мне достаточно.Для меня студенты, я написал awk-скрипт для создания функций списка для конкретного типа.По сравнению с макросами препроцессора он требует дополнительного этапа сборки, но работа системы гораздо более прозрачна для программистов без большого опыта.И это действительно помогает обосновать параметрический полиморфизм, который они увидят позже в своей учебной программе.
Вот как выглядит один набор функций:
int lengthEL (Explist *l); Exp* nthEL (Explist *l, unsigned n); Explist *mkEL (Exp *hd, Explist *tl);Сценарий awk представляет собой ужастик на 150 строк;он ищет код C для
typedefs и генерирует набор функций списка для каждой из них.Он очень старый;Наверное, сейчас я мог бы сделать лучше :-)
Я бы не стал уделять списку профсоюзов время суток (или место на жестком диске).Это небезопасно и не расширяемо, поэтому вы можете просто использовать void * и покончим с этим.
Одним из улучшений по сравнению со списком void* было бы создание списка структур, содержащих void* и некоторые метаданные о том, на что указывает void*, включая его тип, размер и т. д.
Другие идеи:встроить интерпретатор Perl или Lisp.
Или пойти наполовину:свяжите его с библиотекой Perl и создайте список Perl SV или что-то в этом роде.
Я, вероятно, сам бы выбрал подход void*, но мне пришло в голову, что вы можете хранить свои данные в формате XML.Тогда в списке может быть просто символ char* для данных (который вы будете анализировать по требованию для любых необходимых вам подэлементов)....
