Многосвязные списки.

СД типа дек.

Дек – линейная структура (последовательность) в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности.

Допустимые операции:

1. инициализация;

2. проверка: дек пуст / дек не пуст;

3. включение элемента в начало / конец дека;

4. исключение элемента из начала / конца дека.

В общем случае число указателей может быть произвольным. В результате такого обобщения мы получаем многосвязный список. Рассмотрим несколько примеров таких списков.

Пример 1. Каждый элемент многосвязного списка может входить одновременно в несколько односвязных списков. Т.е. получается, что многосвязный список “прошит” в нескольких направлениях.

Например, необходимо организовать данные об абитуриентах, но кроме организации всех сведений, необходимо из общего списка выбрать абитуриентов, характеризующихся некоторыми общими данными (абитуриенты-медалисты, абитуриенты, проживающие в одном городе, абитуриенты, сдавшие экзамен на “отлично”).

В таком случае данные можно организовать в виде четырехсвязного списка, каждый элемент которого содержит все необходимые сведения, а также четыре указателя: первый связывает всех студентов; второй – проживающих в одном городе; и т.д. Для каждого из четырех односвязных списков имеется свой дескриптор, в который входит количество элементов, условия их размещения в списке.

Пример 2. Рассмотрим нелинейный связный список, который удобен для представления диаграмм состояния дискретных систем.

Имеем диаграмму из трех состояний. Дуги показывают изменение текущего состояния. Изменение состояния осуществляется под действием входного сигнала X, при этом система переходит в новое состояние и выдает выходной сигнал Y. Подобная диаграмма может быть использована в диалоговой вычислительной системе, где входные сигналы представляют собой команды, вводимые в систему с терминала пользователя, а выходные представляют собой имена подпрограмм. Таким образом, получив команду X и отыскав в списке по текущему состоянию соответствующий этой команде элемент описания исходящей дуги системы, выполняется подпрограмма, указанная в найденном элементе. Тем самым реализуется требуемая реакция Y. После этого система переходит в другое состояние, и с этого момента это состояние становится текущим.