Сд типа циклический линейный список.
Start Ptr
Данные указатель
Данные
указатель
Данные указатель
Такая модификация линейного списка позволяет упростить алгоритмы для работы со списком, любой элемент доступен, но необходимо отслеживать зацикливание, т.е. должен быть внешний указатель.
Операции для работы с циклическим линейным списком те же, что и для односвязного линейного списка.
Сд типа двусвязный линейный список.
В списке такого типа указатель можно перемещать как в одну, так и в другую сторону.
Дескриптор данной структуры состоит из трех полей указательного типа:
L R Ptr
указатель Данные
указатель Данные
указатель
указатель Данные указатель
Допустимые операции:
инициализация;
сделать список пустым:
проверка: список пуст / список не пуст;
установить указатель в конец списка / начало списка (две отдельные процедуры);
передвинуть указатель вперед / назад на один шаг;
включить элемент в список до указателя / после указателя;
исключить элемент из списка до указателя / после указателя.
При этом для включения элемента в список необходимо распознать следующие три ситуации:
список пуст;
включение элемента в середину списка;
включение элемента в список в качестве первого.
Для упрощения операции включения / исключения реализуют циклические двусвязные списки. При реализации такого списка формируют указатели (вместо маркеров конца и начала списка), указывающие на первый и последний элементы списка. Допустимые операции для СД типа циклический двусвязный список аналогичны операциям для линейного двусвязного списка.
Сд типа дек.
Дек – линейная структура (последовательность) в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности.
Вкл. Искл.
Искл. Вкл.
начало
конец
Допустимые операции:
инициализация;
проверка: дек пуст / дек не пуст;
включение элемента в начало / конец дека;
исключение элемента из начала / конца дека.
Многосвязные списки.
В общем случае число указателей может быть произвольным. В результате такого обобщения мы получаем многосвязный список. Рассмотрим несколько примеров таких списков.
Пример 1. Каждый элемент многосвязного списка может входить одновременно в несколько односвязных списков. Т.е. получается, что многосвязный список “прошит” в нескольких направлениях.
Например, необходимо организовать данные об абитуриентах, но кроме организации всех сведений, необходимо из общего списка выбрать абитуриентов, характеризующихся некоторыми общими данными (абитуриенты-медалисты, абитуриенты, проживающие в одном городе, абитуриенты, сдавшие экзамен на “отлично”).
В таком случае данные можно организовать в виде четырехсвязного списка, каждый элемент которого содержит все необходимые сведения, а также четыре указателя: первый связывает всех студентов; второй – проживающих в одном городе; и т.д. Для каждого из четырех односвязных списков имеется свой дескриптор, в который входит количество элементов, условия их размещения в списке.
S1 300 1
S2 100 2
S3 30
3
S4 40 4
Данные
Данные
Данные
Данные
Пример 2. Рассмотрим нелинейный связный список, который удобен для представления диаграмм состояния дискретных систем.
X1, Y1
X2, Y2
X5, Y5
X6, Y6 X3,
Y3
X4, Y4
Имеем диаграмму из трех состояний. Дуги показывают изменение текущего состояния. Изменение состояния осуществляется под действием входного сигнала X, при этом система переходит в новое состояние и выдает выходной сигнал Y. Подобная диаграмма может быть использована в диалоговой вычислительной системе, где входные сигналы представляют собой команды, вводимые в систему с терминала пользователя, а выходные представляют собой имена подпрограмм. Таким образом, получив команду X и отыскав в списке по текущему состоянию соответствующий этой команде элемент описания исходящей дуги системы, выполняется подпрограмма, указанная в найденном элементе. Тем самым реализуется требуемая реакция Y. После этого система переходит в другое состояние, и с этого момента это состояние становится текущим.
1
2
3
список состояния
S
X1 Y1 1
X2 Y2 3
X5 Y5 2
X4 Y4 3
X6 Y6 1
X3 Y3 1