Лабораторная работа: Динамические структуры данных

3. исключить узел слева

Если nach1 и nach2 указывают на два разных списка L1 и L2 (см. рис.3), то можно включить справа в список L1 весь список L2 , для чего нужно выполнить присваивания, используя промежуточную переменную PP типа pointer :

Var PP: pointer {... } PP: =nach1. link nach1. link: =nach2. link nach2. link: = PP

Рис.3. Циклический список L1 + L2

Каждый элемент списка с двумя связями содержит два указателя: на соседние слева и справа элементы (см. рис.4). По такому списку удобно двигаться вперед и назад, так как он содержит два входа в список. Для создания двусвязного списка можно использовать следующий тип:

Type ptr=element element=record d: integer right,left: ptr end

Рис.4. Пример списка с двумя связями (двунаправленный список)

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

tek. left. right: =tek. right tek. right. left: =tek. left

Здесь вы можете проверить, как вы научились работать с двунаправленным списком.

Списки с полутора связями представляют собой чередование элементов с одной и двумя связями. Их преимущество: требуют меньше памяти, чем двусвязные, но ходить по списку можно вперед и назад.

Рис.5. Пример списка с полутора связями

Построение сложных структур в динамической памяти

С помощью указателей можно создавать самые разнообразные структуры, в том числе более сложные, чем простые линейные списки. Это обусловлено тем, что:

1) любой узел может быть началом другого списка;

2) один и тот же узел может быть включен в несколько различных списков.

Применение указателей придает памяти гибкость, необходимую для представления структур, при этом может понадобиться комбинация элементов с одной и двумя связями. На рис.1 можно видеть пример структуры, которая содержит чередование элементов с 1 и 2 связями.

Рис.1. Чередование элементов с 1 и 2 связями.

Для реализации сложной структуры следует описать два типа элементов:

Type ptr1=element1 element1=record info: string link: ptr1 end ptr2=element2 element2=record info: integer rlink,dlink: ptr2 end

Поскольку элемент с одной связью присоединяется к элементу с двумя связями (т.е. элементу другого типа), при попытке прямого построения связи компилятор выдает сообщение об ошибке на несовместимость типов. Эту сложность можно обойти, используя промежуточную переменную типа pointer .

Пусть имеются следующие описания:

Var E1: ptr1 E2: ptr2 p: pointer

Тогда чтобы присоединить элемент Е1 к элементу Е2 , следует исполнить:

p: = E1 E2. dlink: =p

В частном случае, когда адресная часть элемента Е2 ссылается всегда только на адрес элемента одного и того же типа, можно пользоваться описанием: