Динамические структуры данных (стр. 1 из 2)
Міністерство освіти і науки України
Національний технічний університет України «КПІ»
Кафедра медичної кібернетики та телемедицини
Лабораторна робота №1
Тема: Динамічні структури данних
Варіант №16 (задачі № 16.13(а), 16.18(а), 16.33).
Виконав:
студент ІМ-81
Плахтій Артур Миколайович
Перевірив:
старший викладач
Зінченко Ніна Павлівна
Київ 2009
Теоретична частина
1. Динамические структуры данных
Ранее изучаемые типы данных относятся к так называемым статическим. Память под них выделяется во время компиляции, количество таких объектов не меняется во время выполнения программы. Однако существует ряд задач, где статические структуры неэффективны. В языке Паскаль имеются средства создания динамических структур данных, которые позволяют во время выполнения программы:
· образовывать объекты;
· выделять для них память;
· уничтожать, когда в них исчезает необходимость.
Другое название динамической памяти – куча.
Для получения ясного представления о динамических переменных надо рассмотреть структуру памяти во время выполнения программы на языке Паскаль (см. рис.1).
Данные в динамической памяти размещают с использованием указателей. Указатель - это ссылка на определенную ячейку памяти, начиная с которой записывается значение переменной, поэтому данные такого типа называются еще и ссылочным типом данных.
Формат описания ссылочного типа данных:
Type <тип указателя> = ^ <идентификатор типа>,
то есть указатель связан с некоторым типом данных. Такие указатели называются типизированными.
Пример описания переменных ссылочного типа:
Type
p1=^integer;
p2=^real;
Var
A,B,C:p1;
X,Y,Z:p2;
P:char;
Cсылочные переменные A, B, C указывают на динамические объекты целого типа, X,Y,Z - вещественного, P - символьного. Значением ссылочной переменной является адрес в динамически выделенной памяти, где хранится объект этого типа.
Рис. 1. Структура памяти во время выполнения программы
Для обращения к ссылочной переменной используют запись “ A^ ”, что означает: ”идти по адресу, хранящемуся в A”. Память под указатели отводится на этапе компиляции.
Однако в Турбо Паскале можно объявлять указатель и не связывать его с конкретным типом данных. Такой указатель называется нетипизированным. Для его объявления служит стандартный тип pointer. Структура и тип таких данных могут меняться во время выполнения программы.
При работе с указателями обязательны этапа два:
1. объявление указателя;
2. формирование динамических данных, память которых отводится во время выполнения программы.
Для работы с указателями используются следующие процедуры:
New(P) - процедура, которая создает в динамической памяти новую переменную. Р - указатель переменной того типа, который надо создать. Каждая отдельная процедура new может создать только одну динамическую переменную.
Dispose(P) - процедура, позволяющая вернуть в кучу участок памяти, занятый объектом с указателем Р.
Параметрами процедур new и dispose может быть только типизированный указатель. Для работы с нетипизированными указателями используются аналогичные процедуры:
GetMem(P,Size) - резервирование памяти;
FreeMem(P,Size) - освобождение памяти.
Здесь Р - нетипизированный указатель,Size - размер в байтах требуемой или освобождаемой части кучи ( до 65521 байт).
Над указателями могут быть определены операции проверки на равенство и присваивание (рис.2):
Рис. 2. Допустимое присваивание
Пример.
Var x,y:^integer;
Begin
new(x); {порождаем динамический объект целого типа}
x^:=13; {по адресу x заносим значение 13}
y:=x; {в у заносим значение того же адреса, что и х}
writeln(y^);
end.
Ссылочной переменной может быть присвоенной “пустое” значение адреса, обозначенное служебным словом nil, что означает, что ссылочная переменная не указывает ни на один динамический объект. Это присваивание можно делать до выполнения процедуры new. Значение nil - это два нулевых слова. Оно может быть присвоено указателю любого типа.
Динамически размещенные данные можно использовать в любом месте программы, например:
Var a, b, c = ^ real;
Begin a^:=sqr(b^)+c^-17;
Недопустимо писать a:=sqr(b^), так как указателю нельзя присвоить значение вещественного выражения.
2. Линейные списки. Стек, очередь
Указатели являются эффективным средством построения списковых структур, к которым относятся, в частности, линейные списки.
Линейный список - это множество, состоящее из переменного числа узлов X[1], X[2], ... , X[n].
Структурные свойства такого списка:
1. Если n>0, то Х[1] является первым узлом;
2. Если 1<k<n, то k-му узлу Х[k] предшествует Х[k-1] и за ним следует Х[k+1];
3. Х[n] является последним узлом.
Среди возможных списковых структур выделяют некоторые специальные списки.
Стек - это линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка
Наглядный пример стеков: стопка подносов в столовой, железнодорожный тупик. Стеки используются в работе алгоритмов, имеющих рекурсивный характер. Конец стека называется вершиной стека. Принцип работы стека - “последний пришел - первый вышел”. Внизу находится наименее доступный элемент. Часто говорят, что элемент опускается в стек.
Очередь - это линейный список, в один конец которого добавляются элементы, а с другого конца исключаются. Принцип работы очереди: ”первый пришел - первый вышел”.
3. Организация списков в динамической памяти
Для организации списков используются структуры типа запись, состоящие из двух частей: информационной, где собственно и находятся данные, и ссылочной, содержащей указатель на следующий элемент списка (рис.1). Cоздадим в динамической памяти структуру:
Рис. 1. Пример списковой структуры
где Di - данные. Чтобы получить доступ к данным, достаточно хранить в памяти адрес начала этого списка nach.
В языке Турбо Паскаль последовательно проводится принцип, согласно которому, идентификатор, перед его использованием, должен быть описан. Исключение сделано только для указателей, которые могут ссылаться на еще не объявленный тип данных. Для описания элементов структуры подобной изображенной на рис. 3 можно использовать следующий ссылочный тип:
Type element=^Ptr;
Ptr=record
d:integer;
link:element;
end;
Список в динамической памяти можно создавать в прямом или обратном порядке (относительно последовательности вводимых элементов).
Пример создания списка в обратном порядке (см. рис.2):
Рис. 2. Пример создания списка в обратном порядке
Var i,n,a:integer;
tek,nach:Ptr;
Begin
tek:=nil;
readln(n);
for i:=1 to n do
begin
readln(a);
new(nach);
nach^.d:=a;
nach^.link:=tek;{цепочкаприсоединяетсяк nach}
{*} tek:=nach;
end;
end;
Обратим внимание на вызов процедуры new(nach). В результате этого вызова в динамической памяти отводится место для переменной типа record, которая в нашем случае состоит из двух полей: для хранения целочисленного значения и значения указателя, т.е. адреса. Здесь важно представлять, что после того, как переменная nach (или какая другая) создана в динамической памяти, тем самым имеем ее адрес, который сам является именем переменной, т.е. nach. Если у нас имеется другая переменная того же типа, tek, то мы знаем также и ее адрес, это tek. Поэтому, если в адресную часть переменной nach занести адрес tek, тем самым мы свяжем элементы nach и tek: nach^.link:=tek.
Алгоритм создания списка в прямом направлении:
1. Создать первый элемент nach.
Ввести nach^.d; pred:=nach;
2. Создать текущий элемент tek.
Ввести tek^.d;
Установить связь предыдущего с текущим: pred^.link:=tek;
текущий элемент становится предыдущим: pred:=tek;
3. Если не конец списка, то перейти на 2.
Обнулить адресную часть последнего элемента: tek^.link:=nil.
Рис. 3. Пример создания списка в прямом направлении
Таким образом, для обращения к списку достаточно хранить в памяти адрес первого элемента nach.Поскольку каждый элемент хранит адрес следующего за ним элемента, можно, двигаясь от начального элемента по адресам, получить доступ к любому элементу списка.
Просмотреть элементы списка можно следующим образом:
tek:=nach;{Встали на начало списка}
while tek<>nil do
begin
wtiteln(tek^.d);{Вывести информационную часть}
tek:=tek^.link; {Шаг по связи}
end;
Рассмотрим еще раз строку tek:=tek^.link; . Ее можно интерпретировать по-другому: значению адреса tek присвоить то, что хранится в адресной части элемента tek, а там хранится адрес элемента, следующего за tek. Вообще нотацию tek^.link следует различать в контексте ее нахождения: если она стоит слева от присваивания, имеется ввиду сама адресная часть элемента tek, а если справа от присваивания – то, что хранится в адресной части tek. Таким образом, например, tek^.link:=tek^.link будет означать: в адресную часть tek занести адрес элемента, следующего за tek.
С построенным списком можно выполнять различные операции: добавлять и удалять элементы в любом месте списка, причем в зависимости от местоположения элемента эти операции имеют свои особенности.
Алгоритм добавления элемента в начало списка:
1. Создать новый элемент nov.
Ввести информационную часть nov^.d.
2. Построить связь: nov^.link:=nach.
3. Новый элемент сделать начальным: nach=nov.
Рис. 4. Добавление элемента в начало списка