9 Списковые структуры. Формирование списка. Пример.
Формирование связанного однонаправленного списка.
Исключение из списка элемента F.
Наиболее часто ссылочные типы данных применяют для организации динамических списковых структур. К ним относятся очереди, списки, деревья и подобные структуры. Здесь рассматриваются только однонаправленные списки.
Для задания списковых структур необходимо определить объект комбинированного типа, в состав которого входит ссылка на объект данного типа. В языке ПАСКАЛЬ разрешено определить ссылки на объекты до описания объектов, следовательно,
TYPE ССЫЛКА=^ЭЛЕМЕНТ;
VAR ДАННЫЕ=<ТИП>;
ЭЛЕМЕНТ=RECORD
C:ССЫЛКА;
D:ДАННЫЕ
END;
Определив таким образом ссылочный тип, можно, например, построить связанный однонаправленный список –рисунок 23.
Рисунок 23- связанный однонаправленный список
Указатель НАЧ содержит ссылку на первый элемент списка. Каждый элемент списка содержит поле С – ссылку на следующий элемент – и поле данных D, которое, в свою очередь, может быть достаточно сложной структурой. Поле ссылки последнего элемента списка содержит пустую ссылку (NIL). Двигаясь по указателям (ссылкам), можно последовательно просмотреть весь список. Если из списка необходимо удалить любой элемент, кроме первого, то для этого достаточно изменить поле ссылки предыдущего элемента.
Рисунок 24- Исключение из списка элемента F
На рисунке 24. показано исключение из списка элемента F. Для этого адреса элемента В, который хранился в поле ссылки элемента F, записывается в поле ссылки элемента A, после чего элемент А будет указывать на В, а элемент F станет недоступным, так как на него никто не ссылается.
Пусть ПРЕД – переменная ссылочного типа, содержащая ссылку на элемент, предшествующий удаляемому тогда, чтобы осуществить операцию исключения, достаточно выполнить следующий оператор присваивания:
ПРЕД^.С:= ПРЕД^.С^.С
Правая часть оператора присваивания читается так: идти по ссылке, хранящейся в ПРЕД, взять ссылку из поля С, идти по ней, взять ссылку из поля С удаляемого элемента. Полученное ссылочное значение записывается в поле С элемента, предшествующего удаляемому.
Чтобы вставить элемент в произвольное место связанного списка, кроме начала, также необходимо изменить только значение указателей. Сами элементы списка при этом не перемещаются. Например, на рисунке 25 показано включение в связанный список элемента Х.
ПОС
А F B
НОВ
X
Рисунок25- включение в связанный список элемента Х
Пусть ссылочная переменная ПОС указывает на элемент, после которого необходимо вставить в список элемент Х. На элемент Х указывает ссылочная переменная НОВ. Операция вставки реализуется двумя операторами присваивания:
НОВ^.С:=ПОС^.С;
ПОС^.С:=НОВ
Первый оператор заносит в поле ссылки вставляемого элемента ссылочное значение, указывающее на элемент В и содержащееся ранее в F. Второй оператор записывает в поле ссылки элемента F ссылку на вставляемый элемент.
ПОС НОВ
Рисунок 26- Добавления в конец списка элемента Х
Для добавления в конец списка элемента Х (рисунок 26) достаточно найти последний элемент списка (у него после ссылки имеет значение NIL) и переслать в его поле ссылки указатель на добавляемый элемент. При этом поле ссылки добавляемого элемента должно содержать NIL.
Эти действия реализуются операторами
НОВ^.С:=NIL; ПОС^.С:=НОВ
Приведенный пример является частным случаем добавления элемента в список.
а) б)
НАЧ НАЧ НАЧ НАЧ
С
D
С
D
С
D
НОВ
Рисунок 27 – а) удаление первого элемента,
б) вставка нового элемента в начало списка
Обычно при построении связанных списков вводят ссылочную переменную, указывающую на начало списка, на его первый элемент. Поэтому при удалении первого элемента (рисунок 27, а) или при вставке нового элемента в начало списка (рисунок 27, б) необходимо переопределять не указатель предыдущего элемента, как в рассмотренных выше примерах, а значение начального указателя.
Операция удаления реализуется одним оператором
НАЧ:=НАЧ^.С,
а операция вставки – двумя операторами:
НОВ^.С:=НАЧ;
НАЧ:=НОВ.