Динамические структуры данных

Міністерство освіти і науки України

Національний технічний університет України «КПІ»

Кафедра медичної кібернетики та телемедицини

Лабораторна робота №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] является последним узлом.

Среди возможных списковых структур выделяют некоторые специальные списки.

Стек - это линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка

Наглядный пример стеков: стопка подносов в столовой, железнодорожный тупик. Стеки используются в работе алгоритмов, имеющих рекурсивный характер. Конец стека называется вершиной стека. Принцип работы стека - “последний пришел - первый вышел”. Внизу находится наименее доступный элемент. Часто говорят, что элемент опускается в стек.

Очередь - это линейный список, в один конец которого добавляются элементы, а с другого конца исключаются. Принцип работы очереди: ”первый пришел - первый вышел”.