Olej писал(а):Динамическими такие структуры являются не в силу динамичности её узлов (это дело 2-е), а в силу динамичности связей этих узлов, выраженных через ссылки. Поэтому куда точнее для таких структур будет название, иногда употребляемое, как "ссылочные структуры данных".
По поводу связных структур (динамических) у меня тоже есть замечание, которое а). не очевидное, б). появилось в процессе длительных разборок с кодом ядра Linux (т.е. в Linux особо актуально) и в). совсем не лишне обратить на это внимание тех, кто совершенствуется в использовании C:
... во многих (
во всех?) книгах, где затрагиваются списковые структуры, объяснения и примеры строятся на связанных в список структурах по типу:
Код: Выделить всё
struct list_head {
struct list_head *next;
... // здесь все остальные поля данных увязываемых структур
}
В таком списке признаком конца списка является равенство NULL поля связи next (это классика, описываемая в любой книжке).
Естественно, что в коде ядра любой ОС полно разнообразных списковых структур (кольцевая очередь задач шедулера, очереди обслуживания ... и всё, всё, всё).
Но начиная с ядра 2.6:
а).
все списковые структуры ядра Linux были переписаны на использование
только одной структуры связи (см. определения "/lib/modules/<версия_ядра>/source/include/linux/list.h"):
Код: Выделить всё
struct list_head {
struct list_head *next, *prev;
} list_head_t;
б). все списки строятся как
кольцевые 2-х-связные списки, независимо от того, как они будут использоваться (возможно, как простейшая одностязная очередь)...
в). как оказалось, на основе именно таких списков можно построить
любые связные структуры: деревья, направленные графы и т.д.
г). но ещё одним важнейшим преимуществом есть то, что из-за отсутствия признака проверки поля связи на NULL (поля связи теперь никогда
не могут стать NULL), исключаются тяжелейшие ошибки разыменования указателя NULL в результате ошибки кода.
А вот это уже не классика, и не описана она ни в одной книжке
... не считая нескольких книг в природе (а их таких совсем немного) по ядру Linux.
Но часто и станет читать книжки по ядру Linux
прикладной программист, работающий в Windows?