Структуры и алгоритмы обработки данных
Нелинейные связанные структуры
Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.3.13).
LST1 - указатель на начало 1 - ого списка (ориентированного указателем P1). Он линейный и состоит из 5-и элементов.
2-ой список образован из этих же самых элементов, но в произвольной последовательности. Началом 2-ого списка является 3-ий элемент, а концом 2-ой элемент.
В общем случае элемент списочной структуры может содержать сколь угодно много указателей, то есть может указывать на любое количество элементов.
Можно выделить 3 признака отличия нелинейной структуры:
1) Любой элемент структуры может ссылаться на любое число других элементов структуры, то есть может иметь любое число полей-указателей.
2) На данный элемент структуры может ссылаться любое число других элементов этой структуры.
3) Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.
Представим, что имеется дискретная система, в графе состояния которой узлы - это состояния, а ребра - переходы из состояния в состояние (рис. 3.14).
Входной сигнал в систему это X. Реакцией на входной сигнал является выработка выходного сигнала Y и переход в соответствующее состояние.
Граф состояния дискретной системы можно представит в виде двусвязного нелинейного списка. При этом в информационных полях должна записываться информация о состояниях системы и ребрах. Указатели элементов должны формировать логические ребра системы (рис. 3.15).
Для реализации вышесказанного:
1) должен быть создан список, отображающий состояния системы (1, 2, 3);
2) должны быть созданы списки, отображающие переходы по ребрам из соответствующих состояний .
В общем случае при реализации многосвязной структуры получается сеть.
Контрольные вопросы
1. Какие динамические структуры Вам известны?
2. В чем отличительная особенность динамических объектов?
