46
8. Динамические структуры данных, связные списки
Вид занятия – лабораторная работа Цель – исследование организации и способов представления в памяти динамических структур данных
Продолжительность – 4 часа
Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.
Любая переменная представляет собой ни что иное, как область памяти, содержащую какие то данные. Когда мы объявим переменную MyValue : integer, то в памяти компьютера будет зарезервировано 4 байта для хранения значения этой переменной. Содержимое переменной MyValue можно просмотреть непосредственно в этой области памяти. Объявив какую-нибудь другую переменную, мы заставим операционную систему отвести под эту переменную новые свободные ячейки памяти. Соответственно значения указателей на MyValue и новую переменную будут различны.
Указатель представляет собой переменную, содержащую адрес области памяти. Повторяюсь еще раз, так как это важно: указатель хранит не содержимое памяти, а адрес к ячейкам памяти. По этому он сам не занимает никакого места, кроме того, что нужно для хранящегося в нём адреса.
На практике работа с указателем выглядит следующим образом:
var MyValue : integer; pMyValue : pointer;
begin
MyValue:=100;
pMyValue:=@MyValue; // указателю присвоен адрес переменной MyValue end;
Обратите внимание на то, что при операции присвоения адреса указателю – перед названием переменной установлен символ “@”. Теперь, дабы увидеть данные, хранящиеся в MyValue (допустим у нас существует переменная i : Integer и мы хотим через указатель передать ей данные из переменной MyValue) воспользуемся следующими строками кода:
i:=INTEGER(pmyValue^);
Эквивалентом оператора @ служит метод:
function Addr(X): Pointer;
Функция возвращает указатель на объект X.
Тип данных Pointer называют нетипизированным указателем, так как он может указывать на переменную любого типа. Очень часто применяют типизированные указатели, которые способны работать с переменными определённого типа. Объявление такого указателя выглядит следующим образом:
var pInt:^integer;
Рассмотрим ещё один небольшой пример:
var |
pInt |
: ^integer; |
|
begin |
MyValue |
: integer; |
|
|
//целочисленной переменной присвоено значение 100 |
||
MyValue:=100; |
|||
pInt |
:=Addr(MyValue); |
//указатель установлен в область памяти, где хранится |
|
MyValue |
|
//в область памяти записано значение 123 |
|
pInt^ |
:=123; |
|
|
end; |
|
|
|
|
|
|
|
47
Результатом данного упражнения стало изменение значения переменной MyValue без обращения к ней.
Если указатель пуст (ссылается “в никуда”), то он возвращает особое значение nil. Пустой указатель называют неопределённым. В языке Delphi nil – специальная константа, предназначенная для описания пустых (несуществующих) данных.
Списки
Наиболее простым способом связать (соединить) множество элементов это расположить их линейно в списке или очереди.
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения.
При таком подходе элемент динамической структуры должен состоять из двух полей:
1.информационного поля (поля данных), в котором содержатся те данные, ради которых и создается структура;
2.поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры.
Всамом общем случае, если мы планируем создать список, специализирующийся на хранении целых чисел то элемент списка может быть представлен в следующем виде:
type pItem=^TItem; TItem = Record
Data:Integer; //поле данных P:Pointer; //поле связок
end;
В зависимости от стоящих перед программистом задач в качестве поля данных может быть использована любая другая произвольная структура.
Идея построения односвязного списка представлена на рисунке 8.1. Обратите внимание на то, что поле связок последнего элемента не имеет ссылки на другой элемент, поэтому здесь находится неопределённый указатель nil.
Рисунок 8.1 – Структура односвязного списка
Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такое положение вещей исправляется введением дополнительного указателя на предыдущий элемент в списке. Структуру двусвязного списка вы найдёте на рисунке 8.2.
Рисунок 8.2. - Структура двусвязного списка
Для выделения памяти одному элементу списка следует воспользоваться процедурой:
procedure New(var P: Pointer);
В процедуре имеется единственный параметр P в который будет возвращён указатель на созданный в памяти элемент.
Для уничтожения элемента вам пригодится процедура:
procedure Dispose(var P: Pointer);
Процедура освободит ранее выделенную память на которую ссылается указатель P.
48
Пример создания и заполнения списка
Рассмотрите пример создания списка из нескольких элементов.
var pFirstItem: pItem; //глобальная переменная
Procedure CreateList; //процедура создания списка var pTempItem:pItem;
begin
Randomize;
New(pFirstItem); //создаём первый элемент списка
{теперь указатель pFirstItem будет нашим связным со всем списком} pFirstItem^.Data:=Random(100); //передаём случайное значение в поле данных
//============================================================ New(pTempItem); //создаём новый элемент списка
//передаём полученный указатель в предыдущий элемент pFirstItem^.P:=pTempItem; pTempItem^.Data:=Random(100);
end;
Задание
1.Разработайте программу, позволяющую хранить целочисленные данные в формате односвязного списка. Программа должна позволять пользователю:
−Создавать список.
−Добавлять элемент в конец списка.
−Вставлять элемент в произвольное место списка.
−Удалять любой элемент из списка.
−Читать данные из списка.
−Уничтожать весь список.
2.Разработайте программу, позволяющую хранить целочисленные данные в формате двусвязного списка. Реализуйте в вашей программе те же функции, что и в первом задании.