Процедуры для работы со ссылками

Под динамические переменные память выделяется в куче во время выполнения программы с помощью процедур new или getmem. После окончания работы с динамическими переменны­ми память можно возвратить в кучу.New (var р: тип указателя); - создает новую динами­ческую переменную и устанавливает на нее указатель р. Пара­метром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значе­ние, соответствующее адресу, начиная с которого, можно размес­тить данные.Dispose (var р:тип указателя); - освобождает па­мять, занимаемую динамической переменной.Getmem(var р:pointer, Size:)- создает новую ди­намическую переменную размером Sizeи устанавливает на нее указатель р.Freemem (var р:pointer, Size:word)- освобож­дение памяти, занятой динамической переменной рразмером Sizeбайт.Процедуры Getmem и Freememможно использова работы с нетипизированными указателями. Перед использованием указателей им всегда нужно при­сваиватьзначения. Если разыменовывается указатель, которому еще не присвоено значение, то считанные из него данные могут представлять собой случайные биты, а присваивание значения указываемому элементу может затереть другие данные, програм­му или даже операционную систему.Динамическая область памятиНачало кучи хранится в стандартной переменной Heaporg, конец - в переменной Heapend.Текущую границу незанятой динамической памяти указывает указатель Heapptr. При очередном обращении к процедуре newили getmemсистема отыскивает наименьший свободный фрагмент, в котором может разместиться требуемая переменная. Перед выделением большого объема в динамически распределяемой памяти полезно убедиться, что такой объем памяти имеется. Для этого можно ис­пользовать функцию MaxAvail,которая возвращает размер наибольшего доступного блока непрерывной памяти в динамиче­ски распределяемой области. Существует еще функция Ме-mAvail,возвращающие общее число байтов, доступных для рас­пределения в динамической памяти. Первоначально при запуске программы MaxAvailравно MemAvail,поскольку вся дина­мически распределяемая область памяти является доступной и непрерывной.Освободить фрагмент кучи можно при использовании про­цедур Mark и Release.Процедура Mark(varр : pointer) за­поминает состояние динамической памяти в тот момент, когда этапроцедура вызывается. Вуказателе р сохраняется адрес пер­вого байта свободной области памяти. Далее можно несколько раз выделить память. Процедура Release(varр : pointer) возвращает динамическую память в состояние, которое был помнено ранее при помощи процедуры Mark.

31.Использование переменных целосного типа

Использование переменных ссылочноготипа. Наиболее часто ссылочные переменные используются следующих случаях:1. Использование одной области данных для представле­ния разными типами.2. Программа должна работать с большими объемами дан. ных, под которые нет необходимости сразу выделять память.3. Программа во время компиляции использует данные, для которых заранее неизвестен необходимый объем памяти. Ес­ли расположить переменные в динамически распределяемой об­ласти памяти во время выполнения программы, то для хранения данных будет выделено столько байтов памяти, сколько потребу­ется.4. В программе необходимо использовать массив большой размерности, не помещающийся в сегменте стека.5. Возможность построения объектов со сложной, меняю­щейся структурой. Примерами таких структур являются списки, стеки, деревья

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

Списки.Список - это набор записей, каждая из которых имеет поле данных и ссылку на следующую запись в списке. Последний эле­мент списка содержит значение Nil, т.е. уже ни на что не ссыла­ется. Начало списка формирует переменная ссылочного типа, со­держащая адрес первого элемента списка. Поле данных еще на­зывают информационной частью списка.

Указатель в списке должен быть типизированным. Базовым типом для него является тот же тип данных, что и тип информа­ционной части списка.Обозначим тип элемента списка идентификатором Elem, а ссылочный тип на элемент списка - идентификатором Uk.Тогда формат описание списка следующий:type *Uk =^AElem; {описание типизированного указателя} Elem = Record {описание базового типа}<описание информационной части>next : Uk; end;var p, q : Uk;ВПаскале допускается описывать сначала типизированные указатели, а затем их базовый тип.

Список обычно задается указателем на свой первый эле­мент. Назовем этот указатель р. Значением переменной р в про­цессе построения всегда будет ссылка напервый элемент уже по­строенной части списка. Переменная q будет использоваться для выделения памяти под размещение новых элементов списка. Вы­полнение оператора р : = nil приводит к созданию пустого списка.Кроме рассмотренных списков, которые являются линей­ными однонаправленными списками, существуют двунаправлен­ные и кольцевые. Двунаправленный список называется очередью. Очередь - линейный список, элементы в который добавляются только в конец, а исключаются только из начала списка. Каждый элемент структуры содержит указатель на следующий элемент и еще на предыдущий. Для очереди определяют два указателя: на первый и на последний элемент списка. Начало списка называют головой очереди, а конец списка - хвостом очереди.В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыдущим является последний. При просмотре кольцевого списка надо переходить к следующему элементу до тех пор, пока не достигнем указателя на первый элемент. Поэтому первый эле­мент должен обрабатываться отдельно, а просмотр при помощи цикла следует начинать со второго элемента.Стек Стек - линейный список, в котором добавления и исключе­ния элемента производятся с одного конца, называемого верши­ной стека. Другие операции не определены. Стек оптимален для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке.Работа со стеком осуществляется через указатель стека. При выполнении загрузки элемента в стек, данные записываются на место, определяемое указателем стека, а указатель стека изме­няет свое состояние и задает следующую свободную ячейку бло­ка памяти. При извлечении элемента из стека указатель стека возвращается назад на один шаг.Деревья Структура «дерево» является обобщением линейного списка. В списке каждый узел содержит указатель на другой узел. В дереве каждый узел содержит несколько указателей на несколько узлов. Если указателей два (правый и левый), такое дерево называется би­нарным (рис. 1).Один из указателей может быть равен nil.