Нелинейные связанные структуры

Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.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.        В чем отличительная особенность динамических объектов?