Лабораторная работа №3
Третья лабораторная работа посвящена методам обработки циклических, многомерных и двунаправленных списков
Теоретический материал.
1. Циклические списки.
Циклический список - это линейный список, в котором последний элемент указывает на первый.
Над циклическими списками выполняются практически те же операции, что и над линейными списками вообще (см п.2.1). Однако есть ряд операций специфичных для циклического списка: ввод/удаление элемента слева/справа от указателя;
сдвиг указателя на 1 элемент.
УДАЛЕНИЕ ЭЛЕМЕНТА СЛЕВА ОТ УКАЗАТЕЛЯ.
Удалим элемент хЗ. Необходимо перенаправить ссылку с элемента х2 на х1
p^.s:=b^.s;
dispose (b);
b:=p^ s;
Часто приходится иметь дело с информацией, имеющей начало и конец. В тоже время в циклических списках явного начала и конца нет. Существует два подхода к решению этой проблемы. Можно ввести особый элемент - голову списка - элемент, по формату такой же, как и остальные, однако его информационное поле содержит лишь служебную информацию о том, что это голова списка.
Другой вариант - использование дополнительных битов-признаков.
Ф
h
s
inf
Введем в каждый элемент дополнительное поле h, которое указывает, является ли этот элемент началом списка. Для этого достаточно одного бита.
2. Двунаправленные списки.
В двунаправленном списке используется два поля ссылки, таким образом каждый элемент хранит адрес последующего и предыдущего элемента
Ф
ормат
элемента
Изобразим двусвязный дек:
Двусвязным можно выполнить любой линейный список, но именно для дека он наиболее выгоден. Есть сложности удаления из конца односвязного дека. Использование двусвязного дека позволяет удалять элементы так же как и из начала без прохода по всем элементам дека.
Двунаправленным может быть и циклический список.
Все, что сказано выше о циклических списках справедливо и для двунаправленных циклических списках. Отличие в том, что над двунаправленным циклическим списком возможны такие операции как сдвиг указателя в обе стороны и т.д., а включение/удаление элемента одинаково легко производится и справа и слева от указателя.
5. Многомерные списки.
Рассмотрим пример организации двумерного массива при связном и последовательном распределении памяти.
Последовательное распределение памяти:
|
а11 |
а12 |
А13 |
а21 |
… |
а33 |
|
Связное распределение памяти:
Формат элемента
Inf |
astr |
ast |
Inf- поле информации;
Astr - адрес следующего элемента в данной строке;
Ast - адрес следующего элемента в данном столбце.
