Динамические структуры данных
Міністерство освіти і науки УкраїниНаціональний технічний університет України «КПІ»Кафедра медичної кібернетики та телемедициниЛабораторна робота №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. Структура и тип таких данных могут меняться во время выполнения программы. При работе с указателями обязательны этапа два:объявление указателя; формирование динамических данных, память которых отводится во время выполнения программы. Для работы с указателями используются следующие процедуры: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 = ^ re...
Другие файлы:
Динамические структуры данных: двусвязные списки и двоичные деревья
Линейные динамические структуры. Построение списочной структуры, состоящей из трехнаправленного и двух однонаправленных списков, связанных между собой...
Основы структур данных
Способы ограждения пользователей от деталей фактического устройства данных. Список описателей переменных, указателей или массивов. Статические или дин...
Динамические структуры данных
Проблемы с организацией данных. Определение и классификация динамических структур данных. Линейные односвязные, двухсвязные, кольцевые списки. Очередь...
Динамические структуры данных
Главной особенностью динамических структур является возможность изменения их структуры и размера в процессе работы программы. Это существенно повышает...
C/C++. Структурное программирование
В книге на примерах рассматриваются средства C++, используемые в рамках структурной парадигмы: стандартные типы данных, основные конструкции, массивы,...
