Структуры и алгоритмы обработки данных

       

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


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


        3.        Какой тип представлен для работы с динамическими объектами?

        4.        Как связаны элементы в динамической структуре ?

        5.        Назовите основные особенности односвязного списка..

        6.        В чем отличие линейных списков от кольцевых ?

        7.        Зачем были введены двусвязные списки ?

        8.        В чем разница в операциях, производимых над односвязными и двусвязными списками ?

        9.        Какой список является более удобным в обращении, односвязный или двусвязный ?

     10.     Что такое указатель?

     11.     Какие стековые операции можно производить над списками ?

     12.     Какие операции, производимые над очередью, можно производить над списками ?

     13.     Почему можно производить все эти операции над списками ?

     14.     Для чего предназначены операции Getnode и Freenode?

     15.     Какие методы утилизации вы знаете ?

     16.     Перечислите элементы заголовков в списках.

     17.     Зависит ли время, затраченное на вставку элемента в односвязный список, от количества элементов в списке ?

     18.     Где процесс вставки и удаления эффективнее, в списке или в массиве ?

     19.     Как можно производить просмотр односвязного списка?

     20.     Что означает AVAIL?

     21.     Какой недостаток односвязных списков по сравнению с

     22.     массивом?

     23.     Какие структуры являются нелинейными ?

     24.     Каковы признаки отличия нелинейных структур?

     25.     Как можно создать нелинейную связную структуру?

     26.     Что такое граф состояния ?


Содержание раздела