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

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

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

Лабораторна робота №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):

Рис. ............