Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
Pred: ukazat;
End;
Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:
Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:
Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
|
|
Существуют различные методы использования динамических списков:
· Стек – особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
· Очередь – это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
· Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.
Ссылочный тип данных
Все изученные ранее типы данных относятся к так называемым статическим типам. Это значит, что место в памяти под переменные компилятор отводит до запуска программы(во время компиляции).
Существуют так называемые динамические типы данных. Для переменных этого типа резервирование и очистка памяти производится во время работы программы.
В языке Паскаль нет прямого доступа к динамическому объекту. Поэтому для обращения к ним используют указатели, которые по другому называются ссылочными именами (ссылками).
Ссылочный тип - это неограниченный набор переменных одного типа. Переменные ссылочного типа можно описать двумя способами:
|
|
1. В разделе описания типов.
Например:
TYPE m= array [1..100] of real;m1:^m; {указатель - m1} Var A:^integer; {А - ссылка на переменную} B:^real;mas:m1;Значением указателя является адрес ячейки в памяти, начиная с которой будут записываться данные типа.
Результатом ссылки является ячейка. Существует пустая ссылка - NIL -, в которой ничего нет, она возможна для указателя любого типа данных. Пустая ссылка обычно указывает конец переменных ссыльного типа.
Существует стандартная функция, которая уничтожает динамический объект при этом освобождая память машины, которую он занимал: DISPOSE(A).
Существует такое понятие, как переменная с указателем. Например: А^ - переменная с указателем, с ней можно обращаться также как с переменной указанного типа.
Пример:
A^:=5;A^ mod 5;mas^[ i ]:=20;Между указателями одного типа возможны операции сравнения: <>,=
Динамические переменные обычно используют в связанных структурах данных. Простейшим способом описания связанных объектов является однонаправленный список(как очередь).
Существует 5 основных операций над списками:
- Формирование списка.
- Просмотр элементов списка.
- Поиск элементов в списке.
- Удаление элементов звена в списке.
- Вставка элементов звена в списке.
Примеры операций над списками:
1. Формирование списка.
Type te= integer;ss=zveno;[...........] var s: integer;u,p:ss; {u-ссылка на заглавное звено, p-указатель на текущее звено} begin new(u); {выделяется место в памяти для заглавного звена} p:=u; {указатель текущего звена указывает на первое звено} u^.sled:= nil; {чтобы машина не повисла,обнуляем} writeln('Введите список чисел');read(s); while s>0 dobegin new(p^:sled); {организуется следующее звено} p:=p^:sled; {устанавливает указатель на ячейку p^:sled} p^.elem:=s; {записываем в ячейку число s} p^:sled:= nil; {означает, что у ячейки нет следующего адреса} read(s); end; end;2. Просмотр элементов списка.
Опишем в виде процедуры