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

Под динамические переменные память выделяется в куче во время выполнения программы с помощью процедур 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.