Работа с динамической памятью и указателями в системе Turbo Pascal: Методические указания

ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО НАУКЕ, ВЫСШЕЙ ШКОЛЕ И ТЕХНИЧЕСКОЙ ПОЛИТИКЕ РОССИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ВОЛЖСКИЙ ГУМАНИТАРНЫЙ ИНСТИТУТ

РАБОТА С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ И УКАЗАТЕЛЯМИ В СИСТЕМЕ TURBO PASCAL Методические указания для студентов 1 и 2 курсов специальности "Прикладная математика"

УДК 519.6 Составители: И.Ю. Мирецкий, А.Б. Батхин Рецензент В.Н. Лебедев Печатается по решению учебно-методической комиссии (протокол N___ от___________ )

Работа с динамической памятью и указателями в системе Turbo Pascal: Методические указания для студентов 1 и 2 курсов специальности "Прикладная математика" / Сост. И.Ю. Мирецкий, А.Б. Батхин - Волгоград: Издательство ВолГУ, 1997. - с. 22. Изложены основные приемы работы с динамической памятью и с динамическими переменными в системе Turbo Pascal. Описаны классы задач, для решения которых целесообразно использовать динамические структуры данных. Рассмотрены примеры программ с использованием указателей. Приведены задания для самостоятельного выполнения. Цель методического пособия - научить студента использованию указателей при написании программ на языке Pascal и работе с динамическими структурами данных. Методические указания написаны в соответствии с курсом "ЭВМ и программирование".

Издательство Волгоградского государственного университета

1. Введение. Статические и динамические переменные Все переменные, объявленные в программе, размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных. Длина сегмента данных составляет 64К. Для локальных переменных, описанных в подпрограмме, память отводится при вызове подпрограммы. При выходе из нее эта память освобождается, а сами переменные прекращают свое существование. Глобальным переменным программы память отводится в начале ее выполнения. Эти переменные существуют в течение всего периода работы программы. Переменные, память под которые распределяется описанным образом, называются статическими. Использование одних лишь статических переменных лишает возможности писать программы, обрабатывающие достаточно большие информационные массивы. Turbo Pascal дает возможность программисту использовать для размещения переменных так называемую "кучу" (heap) - динамическую память. Чтобы оценить размер и положение кучи в оперативной памяти компьютера, рассмотрим карту памяти Turbo Pascal (см. рис. 1). Верхняя граница памяти DOS HeapEnd свободная память HeapPtr куча (растет вверх) HeapOrg

OvrHeapEnd оверлейный буфер OvrHeapOrg стек (растет вниз)

SSeg:SPtr свободный стек SSeg:0000 глобальные переменные типизованные константы DSeg:0000 кодовый сегмент модуля System кодовый сегмент первого модуля кодовый сегмент других модулей

содержат образ .EXE - файла

кодовый сегмент последнего модуля кодовый сегмент главной программы префикс сегмента программы (PSP) PrefixSeg Нижняя граница памяти DOS Рис. 1. Распределение памяти в Turbo Pascal. Префикс сегмента программы (Program Segment Prefix - PSP) -это 256-ти байтовая область, создаваемая DOS при загрузке программы. Адрес сегмента PSP хранится в переменной PrefixSeg. Каждый модуль (и главная программа, и каждый модуль) имеет свой кодовый сегмент. Главная программа занимает первый кодовый сегмент; кодовые сегменты, которые следуют за ним, занимают модули (в порядке, обратном тому, как они следовали в операторе uses), и последний кодовый сегмент занимает библиотека времени выполнения (модуль System). Размер одного кодового сегмента не может превышать 64К, но общий размер кода ограничен только имеющейся памятью.

Сегмент данных (адресуемый через DS) содержит все глобальные переменные и затем все типизованные константы. Регистр DS никогда не изменяется во время выполнения программы. Размер сегмента данных не может превышать 64К. При запуске программы регистр сегмента стека (SS) и указатель стека (SP) устанавливаются так, что SS:SP указывает на первый байт после сегмента стека. Регистр SS никогда не изменяется во время выполнения программы, а SP может передвигаться вниз пока не достигнет конца сегмента. Размер стекового сегмента не может превышать 64К; размер по умолчанию - 16К, он может быть изменен директивой компилятора $M. Буфер оверлеев используется стандартным модулем Overlay для хранения оверлейного кода. Размер оверлейного буфера по умолчанию соответствует размеру наибольшего оверлея в программе; если в программе нет оверлеев, размер буфера оверлеев равен 0. Размер буфера оверлеев может быть увеличен с помощью вызова программы OvrSetBuf модуля Overlay; в этом случае размер кучи соответственно уменьшается, смещением вверх HeapOrg. Куча занимает всю или часть свободной памяти, оставшейся после загрузки программы. Фактически размер кучи зависит от минимального и максимального значений кучи, которые могут быть установлены директивой компилятора $M. Размер кучи никогда не будет меньше минимального значения и не превысит максимального. Если в системе нет памяти равного минимальному значению, программа не будет выполняться. Минимальное значение кучи по умолчанию равно 0 байт, максимальное - 640К; это означает, что по умолчанию куча будет занимать всю оставшуюся память. Управление кучей осуществляет монитор кучи (который является частью библиотеки Turbo Pascal). Динамическая память (куча) используется для размещения динамических переменных. Динамическое размещение данных означает использование памяти непосредственно при работе программы. При динамическом размещении заранее не известны ни тип, ни количество размещаемых данных. Созданием и уничтожением динамических переменных управляет программист. К статическим переменным можно обратиться по идентификаторам. Для динамических переменных такой способ доступа непригоден. Единственным средством доступа к ним является указатель на место их текущего расположения в памяти. 2. Тип указатель Тип указатель определяет множество значений, которые указывают на динамические переменные определенного типа, называемого базовым типом. Реально значения указателей содержат адреса расположения в памяти конкретных значений базового типа. тип указатель

базовый тип

^

базовый тип

идентификатор типа

Если базовый тип является еще не объявленным идентификатором, то он должен быть объявлен в той же самой части объявления, что и тип указатель. Рассмотрим следующий пример: type Buffer = string[255]; BufPtr = ^Buffer; var Buf1: Buffer; Buf2: BufPtr; Тип данных Buffer определен как строковая переменная размером 255 байт; BufPtr - указатель на Buffer. Переменная Buf1 имеет тип Buffer и занимает (255+1) байт памяти. Переменная Buf2 имеет тип BufPtr и, являясь 32-битовым адресом, занимает 4 байта памяти. Прежде чем использовать BufPtr, необходимо зарезервировать память и запомнить ее адрес в Buf2. Для этого используется процедура New, которая отводит новую область памяти в куче для динамической переменной и сохраняет адрес этой области в переменной указателе.

New(Buf2); Этот оператор выделит в памяти 256-байтовый буфер и его адрес поместит в Buf2. Ссылка на динамическую переменную, на которую указывает переменная указатель, записывается в виде переменной указателя, после которой ставится символ указателя (^); оператор ^ (разыменование) позволяет использовать данные, на которые указывает Buf2. Например, необходимо поместить строку и в Buf1 и в буфер, на который указывает Buf2: Buf1 : = 'Эта строка помещается в Buf1'; Buf2^ : = 'Эта строка помещается по указателю Buf2'; Здесь Buf2 означает 4-байтовую переменную указателя, а Buf2^ 256-байтовую строковую переменную, адрес которой содержит Buf2. Другие примеры ссылок на динамические переменные: P1^, P1^.Sibling^, Results[1].Data^. Для освобождения памяти, на которую указывает переменная указатель, используется процедура Dispose. После освобождения памяти следует присвоить указателю значение nil (указатель ни на что не указывает): Dispose(Buf2); Buf2 := nil; Помимо процедуры New, переменной указателя можно присвоить значение с помощью оператора @ или функции Ptr. Оператор @ устанавливает переменную указателя на область памяти, содержащую существующую переменную, включая и те переменные, которые имеют идентификаторы. Функция Ptr устанавливает переменную указатель на определенный адрес в памяти. Оператор @ возвращает адрес заданной переменной. Если Sum переменная целого типа, то @Sum - адрес в памяти этой переменной. Аналогично, если ChrPtr - это указатель на тип Сhar, то ChrPtr^ - это символ, на который указывает ChrPtr. 3. Оператор @ Оператор @ является унарным оператором, в качестве операнда которого используется ссылка на идентификатор переменной, процедуры или функции; операнду возвращается указатель. Тип этого значения является таким же, как тип указателя nil, и, таким образом, его можно присвоить любому указателю. Пример использования оператора @ для переменной. Введем объявления type TwoChar = array [0 .. 1] of Char; var Int : Integer; TwoCharPtr : ^TwoChar; Тогда строка TwoCharPtr := @Int; приводит к тому, что TwoCharPtr указывает на Int. TwoCharPtr^ становится повторной интерпретацией значения Int, как если бы она была символьным массивом array[0 .. 1] of Char.

При использование операции @ для формального параметра-значения будет построен указатель, указывающий на ячейку стека, в которой содержится фактическое значение параметра. Предположим, что Foo является формальным параметром-значением процедуры, а FooPtr является переменной указателем. Если в процедуре выполняется операция FooPtr := @Foo; то FooPtr^ будет ссылкой на значение Foo. Однако, FooPtr^ не указывает на сам параметр Foo, поскольку он указывает на значение Foo, которое было взято из Foo и сохранено в стеке. Применение оператора @ к параметру-переменной приведет к тому, что будет сформирован указатель на фактический параметр (указатель берется из стека). Предположим, что One - параметрпеременная процедуры, Two - переменная, передаваемая в процедуру в качестве фактического параметра переменной One, а OnePtr является указателем на переменную. Если в процедуре выполняется оператор: OnePtr := @One; то OnePtr является указателем на переменную Two, а OnePtr^ ссылка на саму переменную Two. Оператор @ можно применять к процедуре или функции. При этом будет получен указатель на ее точку входа. В Turbo Pascal не предусмотрен механизм для использования такого указателя. Единственным применением указателя процедуры может быть передача его программе на языке ассемблер или использование в inline операторе. Наконец, оператор @ можно применить к уточненному идентификатору метода, чтобы создать указатель на точку входа метода. 4. Бестиповые указатели Turbo Pascal содержит особый стандартный ссылочный тип, который позволяет не конкретизировать свой базовый тип, то есть тип указуемых значений. Этот тип имеет идентификатор Pointer и совместим со всеми ссылочными типами. Например, описания var a : ^integer; b : ^char; c : pointer; допускают присваивания вида c := a; c := b; (присваивание a := b незаконно). Значения типа pointer называют нетипизированными указателями. Работа с ними подразумевает обычно их преобразование в типизированные указатели, ссылающиеся на значения определенного типа. Тип Pointer хранится как двойное слово с частью смещения в младшем слове и с сегментной частью в старшем слове. Значение указателя nil хранится как 0 в обоих словах. Turbo Pascal содержит (дополнительно к New и Dispose) две процедуры GetMem и FreeMem распределения памяти, которые выделяют и освобождают области кучи без учета типа тех значений, которые будут в них размещаться. 5. Приведение типов переменных Ссылка на переменную одного типа может быть преобразована в ссылку на переменную другого типа с помощью приведения типов переменных. приведение типов

идентификатор типа

(

ссылка на переменную

)

Когда приведение типов применяется к ссылке на переменную, ссылка на переменную рассматривается как экземпляр типа, представленного идентификатором типа. Размер переменной (число байтов, занимаемых переменной) должен быть равен размеру типа, представленного идентификатором типа. После приведения типа переменной можно указать один или несколько квалификаторов, если это допускается указанным типом. Приведем несколько примеров приведения типов переменных: type ByteRec = record Lo,Hi : Byte; end; WordRec = record Low, High : Word; end; PtrRec = record Ofs, Seg : Word; end; BytePtr = ^Byte; var B: Byte; W: Word; L: LongInt; P: Pointer; begin W := $1234; B := ByteRec(W).Lo; ByteRec(W).Hi := 0; L := $01234567; W := WordRec(L).Lo; B := ByteRec(WordRec(L).Lo).Hi; B := BytePtr(L)^; P := Ptr($40,$49); W := PtrRec(P).Seg; Inc(PtrRec(P).Ofs,4); end; Отметим использование типа ByteRec для доступа к байтам младшей и старшей части слова; это соответствует встроенным функциям Lo и Hi, за исключением того, что приведение переменных можно использовать также и в левой части оператора присваивания. Также обратите внимание на использование WordRec и PtrRec типов для доступа к младшему и старшему слову части длинного целого, и к сегментной части и смещению в указателе. Turbo Pascal полностью поддерживает приведение типов переменных, включая процедурные типы. Например, для объявлений type Func = function(X : Integer) : Integer; var F: Func; P: Pointer; N: Integer; можно написать следующие присваивания: F := Func(P); Func(P) := F; @F := P;

{присвоить процедурное значение из Р в F} {присвоить процедурное значение из F в P} {присвоить значение указателя из Р в F}

P := @F; {присвоить значение указателя из F в P} N := F(N); {вызов функции через F} N := Func(P)(N); {вызов функции через P} Адресный оператор @, примененный к процедурной переменной может использоваться в левой части присваивания. Заметим также, что приведение типа в последней строке вызывает функцию через переменную-указатель. 6. Константы с типом указатель В дополнение к обычным константным выражениям значение типизированной константы можно задать, используя константное адресное выражение. Константное адресное выражение - это выражение, которое включает получение адреса, смещения или сегмента глобальной переменной, типизированной константы, процедуры или функции. Константное адресное выражение не может ссылаться к локальным переменным или динамическим (в куче) переменным, поскольку их адреса нельзя вычислить во время компиляции. Объявление константы типа указатель обычно использует константное адресное выражение для указания значения. Приведем несколько примеров: type Direction = (Left, Right, Up, Down); StringPrt = ^String; NodePtr = ^Node; Node = record Next : NodePtr; Symbol : StringPrt; Value : Direction; end; const S1: string[4] = 'DOWN'; S2: string[2] = 'UP'; S3: string[5] = 'RIGHT'; S4: string[4] = 'LEFT'; N1: Node = (Next: nil; Symbol:#S1; Value: Down); N2: Node = (Next: @N1; Symbol:#S2; Value: Up); N3: Node = (Next: @N2; Symbol:#S3; Value: Right); N4: Node = (Next: @N3; Symbol:#S4; Value: Left); DirectionTable: NodePtr = @N4; 7. Сравнение указателей Для сравнения операндов типа указатель совместимых типов могут использоваться операторы = и <>. Два указателя равны только в том случае, если они ссылаются на один и тот же объект. При сравнении указателей в Turbo Pascal сравниваются сегменты и смещения. В соответствии со схемой размещения сегментов процессоров 80х86 два логически различных указателя могут фактически указывать на одну и ту же физическую ячейку памяти. Например, Ptr($0040, $0049) и Ptr($0000, $0049) являются указателями с одинаковыми адресами. Указатели, возвращаемые стандартными процедурами New и GetMem, всегда нормализованы (смещение находится в диапазоне от $0000 до $000F) и, таким образом, всегда будут сравниваться корректно. При создании указателей с помощью стандартной функции Ptr и последующем сравнении таких указателей нужно соблюдать особую осторожность. 8. Монитор кучи Куча имеет стековую структуру, растущую от нижних адресов памяти в сегменте кучи. Нижняя граница кучи хранится в переменной HeapOrg, а вершина кучи, соответствующая нижней границе свободной памяти, хранится в переменной HeapPtr. Каждый раз, когда динамическая переменная распределяется в куче (через New или GetMem), монитор кучи передвигает HeapPtr вверх на размер этой переменной, ставя динамические переменные одну за другой.

HeapPtr нормализуется после каждой операции, устанавливая смещение в диапазоне от $0000 до $000F. Максимальный размер переменной, который может быть распределен в куче, равен 65519 байт ($10000 - $000F), поскольку каждая переменная должна полностью находиться в одном сегменте. 9. Освобождение памяти Динамические переменные, хранящиеся в куче, удаляются одним из двух путей: 1) через Dispose или FreeMem, 2) через Mark и Release. Рассмотрим второй способ. На рис. 2 показано начальное состояние кучи после выполнения операторов New(Ptr1); New(Ptr2); Mark(P); New(Ptr3); New(Ptr4); New(Ptr5); Ptr1

Нижняя граница памяти содержимое Ptr1^

Ptr2 содержимое Ptr2^ Ptr3 содержимое Ptr3^ Ptr4 содержимое Ptr4^ Ptr5 содержимое Ptr5^ HeapPtr HeapEnd

Верхняя граница памяти Рис. 2. Начальное состояние кучи

Оператор Mark(P) помечает состояние кучи перед распределением Ptr3 (сохранением текущего HeapPtr в P). Если выполнить оператор Release(P), то состояние кучи станет таким, как на рисунке 3 (освобождены все указатели, распределенные после вызова Mark). Ptr1

Нижняя граница памяти содержимое Ptr1^

Ptr2 содержимое Ptr2^ HeapPtr HeapEnd

Верхняя граница памяти Рис.3. Распределение кучи после выполнения Release(P)

Примечание. Выполнение оператора Release(HeapOrg) полностью очищает всю кучу, поскольку HeapOrg указывает на нижнюю границу кучи. Для программ, которые освобождают указатели в порядке, точно обратном порядку их распределения, процедуры Mark и Release очень эффективны. Однако большинство программ распределяют и освобождают указатели случайным образом. Это требует более сложной техники управления и реализуется процедурами Dispose и FreeMem. Эти процедуры позволяют программе освобождать любой указатель в любое время.

Когда динамическая переменная, которая не является последней (верхней) в куче, освобождается с помощью Dispose или FreeMem, куча становится фрагментированной. Если была выполнена та же последовательность операторов, а затем Dispose(Ptr3) - в середине кучи появится дырка (рис. 4). Ptr1

Нижняя граница памяти содержимое Ptr1^

Ptr2 содержимое Ptr2^ Ptr4 содержимое Ptr4^ Ptr5 содержимое Ptr5^ HeapPtr HeapEnd

Верхняя граница памяти Рис. 4. "Дырка" в куче

Если сейчас выполнить New(Ptr3), то он снова займет ту же область памяти. С другой стороны, выполнение Dispose(Ptr4) увеличит свободный блок, поскольку Ptr3 и Ptr4 были соседними блоками (рис. 5). Ptr1

Нижняя граница памяти содержимое Ptr1^

Ptr2 содержимое Ptr2^

Ptr5 содержимое Ptr5^ HeapPtr HeapEnd

Верхняя граница памяти Рис. 5. Увеличение свободного блока

Наконец, выполнение Dispose(Ptr5) во-первых создаст еще больший свободный блок, а затем переместит HeapPtr вниз. Кроме того, этот свободный блок сольется со свободной памятью кучи, так как последний значащий указатель сейчас - Ptr2 (рис. 6). Ptr1

Нижняя граница памяти содержимое Ptr1^

Ptr2 содержимое Ptr2^ HeapPtr HeapEnd

Верхняя граница памяти Рис. 6. Удаление свободного блока Куча сейчас в таком же состоянии, как была после выполнения Release(P) (рис. 2). Однако, свободные блоки, создаваемые и разрушаемые в этом режиме, фиксировались для последующего использования. 10. Список свободных блоков Адреса и размеры свободных блоков, создаваемых Dispose и FreeMem хранятся в списке свободных блоков, который растет сверху вниз от верхней границы сегмента кучи. Когда распределяется динами-

ческая переменная, до размещения ее в куче проверяется список свободных блоков. Если есть свободный блок подходящего размера (размер больше или равен размеру распределяемого блока), то он используется. Примечание. Процедура Release всегда очищает список свободных блоков, что заставляет монитор кучи "забыть" о всех свободных блоках, которые могли быть ниже указателя кучи. Если вызовы Mark и Release чередуются с вызовами Dispose и FreeMem, то необходимо быть уверенным в том, что таких свободных блоков нет. Переменная FreeList (модуль System) указывает на первый свободный блок в куче. Этот блок содержит указатель на следующий свободный блок, который содержит указатель на следующий свободный блок и т.д. Последний свободный блок содержит указатель на вершину кучи (т.е. на положение, указываемое HeapPtr). Если список свободных блоков пуст, FreeList равна HeapPtr. Формат первых 8 байт свободного блока определяется типом TFreeRec: type PFreeRec = ^TFreeRec; TFreeRec = record Next : PFreeRec; Size : Pointer; end; Поле Next указывает на следующий свободный блок, или на то же положение, что и HeapPtr, если блок - последний свободный блок. Поле Size хранит размер свободного блока. Значение Size это нормализованное значение указателя с числом свободных параграфов (16-байтовых блоков) в старшем слове и числом свободных байт (от 0 до 15) в младшем слове. Функция BlockSize преобразует значение поля Size в нормальное значение LongInt: function BlockSize(Size: Pointer): Longint; type PtrRec = record Lo, Hi: Word; end; begin BlockSize := Longint(PtrRec(Size).Hi) * 16 + PtrRec(Size).Lo; end; Чтобы обеспечить место для TFreeRec в начале свободного блока, монитор кучи округляет размер каждого блока, распределяемого New или GetMem, до 8-байтовой границы. Так, для блоков, размером в 1..8 байт распределяется 8 байт, для блоков, размером 9..16 распределяется 16 байт и т. д. 11. Переменная HeapError Переменная HeapError позволяет установить функцию обработки ошибок кучи, которая вызывается, когда монитор кучи не может обработать запрос на распределение памяти. HeapError указывает на функцию со следующим заголовком: function HeapFunc(Size: Word): Integer; far; Функция обработки устанавливается присваиванием ее адреса переменной HeapError: HeapError := @HeapFunc; Функция обработки ошибок кучи вызывается, когда New или GetMem не могут обработать запрос. Параметр Size содержит размер блока, который не мог быть распределен и функция обработки должна попытаться освободить блок размером не меньшим этого. Функция обработки возвращает одно из значений 0, 1 или 2. В случае 0 будет немедленно возникать ошибка времени выполнения в программе. В случае 1 вместо аварийного завершения программы New или GetMem возвращают указатель, равный Nil. Наконец, 2 означает успех и повторяет запрос на распределение памяти (который может опять вызвать функцию обработки ошибок). Стандартная функция обработки ошибок кучи всегда возвращает 0, что приводит к аварийному завершению программы, если New или GetMem не могут быть выполнены.

Пример функции обработки ошибок. function HeapFunc(Size: Word): Integer; far; begin HeapFunc := 1; end; Когда эта функция установлена, New и GetMem будут возвращать nil при невозможности распределить память, не приводя к аварийному завершению программы. 12. Процедуры и функции для работы с указателями и адресами Процедура Dispose. Уничтожает динамическую переменную и возвращает в кучу фрагмент памяти, который ранее был зарезервирован за типизированным указателем (TP). Обращение: Dispose(TP) Процедура FreeMem. Уничтожает динамическую переменную данного размера (Size) и возвращает в кучу фрагмент памяти, который ранее был зарезервирован за нетипизированным указателем (P). Обращение: FreeMem(P, Size) Процедура GetMem. Создает новую динамическую переменную заданного размера и устанавливает переменную-указатель для нее. Обращение: GetMem(P, Size) Процедура Mark. Запоминает текущее состояние указателя кучи (HeapPTR) в переменной-указателе (PTR). Используется совместно с процедурой Release для освобождения части кучи. Обращение: Mark(PTR) Процедура New. Создает новую динамическую переменную и устанавливает на нее переменнуюуказатель. Обращение: New(TP) Процедура Release. Обращение: Release(PTR) Освобождает участок кучи от адреса, записанного в PTR (процедурой Mark), до конца кучи. Функция MaxAvail. Возвращает размер наибольшего непрерывного свободного блока кучи, соответствующей размеру наибольшей динамической переменной, которая может быть распределена в момент Вызова MaxAvail. Тип результата - Longint. Обращение: MaxAvail Функция MemAvail. Возвращает количество имеющихся в куче свободных байт. Тип результата Longint. Обращение: MemAvail Функция Addr. Возвращает адрес заданного объекта V (имя любой переменной, процедуры, функции). Обращение:

Addr(V) Функция CSeg. Возвращает текущее значение регистра CS (тип результата - Word). Обращение: CSeg Функция DSeg. Возвращает текущее значение регистра DS (тип результата - Word). Обращение: DSeg Функция Ofs. Возвращает смещение заданного объекта V (тип результата - Word). Обращение: Ofs(V) Функция Ptr. Возвращает значение типа Pointer по заданным сегменту Seg (выражение типа Word) и смещению Ofs (выражение типа Word). Обращение: Ptr(Seg, Ofs) Функция Seg. Возвращает сегмент для заданного объекта V (тип результата - Word). Обращение: Seg(V) Функция SiseOf. Возвращает размер в байтах внутреннего представления указанного объекта W (имя переменной, функции или типа). Обращение: SizeOf(W) Функция SPtr. Возвращает текущее значение регистра SP (тип результата - Word). Обращение: Sptr Функция SSeg. Возвращает текущее значение регистра SS (тип результата - Word). Обращение: SSeg 13. Пример использования динамических переменных Рассмотрим следующую задачу: составить модель работы регистратуры поликлиники по организации очереди пациентов к врачу. Схема организации очереди такова: 1) все пациенты в возрасте до 60 лет обслуживаются в порядке регистрации; 2) пациенты, возраст которых превышает 60 лет, направляются в начало общей очереди и образуют собственную очередь, где обслуживаются в порядке регистрации; 3) удаление пациента из очереди осуществляется либо по окончании приема, либо по желанию пациента. На каждого посетителя заводится электронная карточка, в которой указываются его фамилия, адрес, пол и год рождения. Организуем очередь в виде списка. Каждый элемент списка имеет два поля: содержательное и ссылочное. В первом поле содержится информация о пациенте. Второе поле указывает на следующий элемент списка. Последний элемент списка имеет "пустой" указатель nil. Указатель на первый элемент списка (то есть на весь список) содержится в некоторой переменной (first).

first

карточка карточка ссылка элемент 1

ссылка

...

элемент 2 карточка ... ссылка

nil

последний элемент Рис. 7. Однонаправленный список Для построения модели необходимо уметь 1) создавать элемент списка; 2) вносить элемент в список (в начало, в середину и в конец очереди); 3) удалять элемент из списка (из начала, из середины и из конца очереди). Тело программы включает создание элемента типа patient и управление очередью. program queue; uses crt; {для описания пациента и организации списка} {вводим следующий тип} type s_t_r = string[40]; elem = ^patient; patient = record {сведения о пациенте} fio : s_t_r; {Ф.И.О.} sex : s_t_r; addr: s_t_r; age : integer; next: elem end;

{пол} {адрес} {возраст} {поле, указывающее на следующий элемент списка}

var p : pointer; first : elem; {указатель на первый элемент списка} n : elem; {указатель на очередной элемент списка} o : char; {управление очередью:} {o='i' - вставить элемент;} {o='d' - удалить элемент;} {o='s' - показать очередь;} {o='e' - завершить работу} name : s_t_r; {функция pospat определяет позицию элемента,}

{вводимого в очередь; age - возраст пациента} function pospat(age:integer):elem; var a,b:elem;

{a - текущий элемент списка}

begin a:=first; while (a^.next <> nil) and (a^.age > age) do begin {организация движения по списку от элемента к следующему элементу} b := a; a := a^.next end; if a^.age > age then pospat := a else pospat := b end; {процедура inspat вводит элемент в очередь на} {позицию, соответствующую возрасту пациента} procedure inspat(pat:elem); var a:elem; begin a:=first; if pat^.age > 60 then if a^.age <= 60

{a - текущий элемент списка}

{если возраст пациента больше60 лет и все пациенты в очереди } {моложе 60 лет, элемент становится первым в списке} then begin pat^.next := first; first := pat; exit end {если возраст пациента больше 60 лет и не все пациенты в очереди } {моложе 60 лет, позицию элемента определяется функцией pospat } else a := pospat(60); {если возраст пациента не превышает } {60 лет, pospat ищет "хвост" очереди} if pat^.age <= 60 then a := pospat(0); pat^.next := a^.next; a^.next := pat end;

{переопределение ссылок}

{процедура delpat удаляет элемент из очереди по имени nm пациента} procedure delpat(nm:s_t_r); var a,b:elem;

{a - текущий элемент списка}

begin a:=first; while a <> nil do if a^.fio = nm then begin if a = first then begin {удаление первого элемента} first := a^.next;

dispose(a) end else begin {удаление элемента, не являющегося первым в списке} b^.next := a^.next; dispose(a) end; exit end else begin b := a; a := a^.next end end; {процедура showqueue показывает очередь} procedure showqueue; var a:elem; begin clrscr; a:=first; writeln; while a<>nil do begin writeln (a^.fio,', ',a^.age,' a:=a^.next end; readln end;

{a - текущий элемент списка}

');

{тело программы} begin clrscr; mark(p); {p хранит исходное состояние кучи} first:=nil; repeat clrscr; writeln('укажите операцию:'); writeln('i - поместить элемент в очередь'); writeln('d - удалить элемент из очереди'); writeln('e - завершить работу'); writeln('s - показать очередь'); readln(o); case o of {управление очередью} 'i' : begin n:=new(elem); {создание элемента списка} {заполнение "карточки" пациента} writeln('введите Ф.И.О. пациента'); readln(n^.fio); writeln('введите пол пациента'); readln(n^.sex); writeln('введите адрес пациента'); readln(n^.addr); writeln('введите возраст пациента'); readln(n^.age); n^.next:=nil; {элемент помещается в очередь} if first=nil then first:=n else inspat(n); end;

'd' : begin writeln('введите Ф.И.О. пациента'); readln(name); delpat(name); {элемент удаляется из очереди} end; 's' : showqueue; 'e' : release(p); end; until o='e';

{демонстрация очереди} {освобождение памяти}

repeat until keypressed end.

14. Контрольные вопросы и варианты индивидуальных заданий Пусть задано описание type ss=^integer; d=record a:boolean; b,c:^real end; var p,q:ss; r:^d; e:^char; Ответьте на следующие вопросы. 1. Что обозначают p, q^? 2. Каковы типы p, q^? 3.Что будет выдано на печать в результате выполнения следующих операторов? p^:=5; q^:=4; p^:=q^; if p=q then p:=nil else if p^=q^ then q:=p; if p=q then q^:=6; writeln(p^); 4. Какой будет структура переменной r после выполнения трех первых операторов и какой станет после выполнения трех последних? r^.a:=false; r^.b^:=15; r^.c:=nil if r^.b<>nil then r^.c:=r^.b; r^.b^:=r^.c^-1.1; r^.a:=r^.c=r^.b; Структуры нарисуйте. 5. Какие из следующих операторов некорректны? p:=q; q:=r; r:=nil; p:=nil; q:=p^; p^:nil; r^:=p^; q^:=ord(r^); if r<>nil then r^:=nil^; if p>nil then q^:=p^; if p=q then write(q); if p<>q then write(q^); 14. Индивидуальные задания Выполните индивидуальные задания в соответствии со своим вариантом. Задание 1 Произвольный текст T1, хранящийся на диске, разместить в динамической памяти в виде Т2, разбив Т1 на строки длины d и создав массив размера n cсылок на эти строки (n и d не зависят от размера Т1 и

задаются при выполнении программы в диалоговом режиме; если в Т2 менее n строк, то последние элементы массива nil). Описать 1) функцию для подсчета числа строк в Т2; 2) функцию для проверки, есть ли Т2 строка с номером k; 3) процедуру перестановки строк i и j в Т2; 4) процедуру замещения строки i и строкой j в Т2; 5) процедуру вставки строки i за строкой j в Т2; 6) процедуру удаления строки i из Т2; 7) процедуру удаления строк с i-й по j-ю из Т2; 8) функцию проверки неоднократного вхождения некоторого символа в Т2 с фиксацией координат первого вхождения. Задание 2 (однонаправленные списки) Располагая структурой вида type ТЭ=...; {тип элементов списка} список = ^звено; звено = record элем:ТЭ; след_элем:список end; описать функцию или процедуру, которая 1) определяет, пуст ли список; 2) находит среднее арифметическое непустого списка; 3) заменяет в списке все вхождения элемента е1 на элемент е2; 4) меняет местами первый и последний элементы непустого списка; 5) проверяет, упорядочены ли по алфавиту элементы списка; 6) находит сумму двух последних элементов списка; 7) находит сумму n последних элементов списка; 8) подсчитывает количество слов в списке, начинающихся и оканчивающихся одним и тем же символом; 9) подсчитывает количество слов в списке, начинающихся тем же символом, что и следующее слово; 10) подсчитывает количество слов в списке, совпадающих с последним словом; 11) по исходному списку L строит список L1 из неотрицательных компонент L и список L2 из отрицательных компонент L; 12) вставляет в начало списка новый элемент; 13) вставляет в конец списка новый элемент; 14) вставляет в список новый элемент после каждого вхождения элемента е1; 15) вставляет в список новый элемент перед каждым вхождением элемента е1; 17) удаляет из списка первый элемент; 18) удаляет из списка второй элемент; 19) удаляет из списка все положительные элементы; 20) удаляет из списка элемент после каждого вхождения элемента е1; 21) проверяет списки L1 и L2 на равенство; 22) проверяет списки L1 и L2 на вхождение; 23) оставляет в списке только первые вхождения одинаковых элементов. Задание 3 (кольцевые двунаправленные списки) Располагая структурой вида type ТЭ=...; {тип элементов списка} список = ^звено; звено = record элем:ТЭ; пред_элем, след_элем:список end; описать функцию или процедуру, которая 1) определяет, пуст ли список; 2) печатает элементы списка в обратном порядке; 3) печатает все элементы списка, начиная с некоторого элемента е1;

4) подсчитывает число элементов списка, у которых равные "соседи"; 5) удаляет из списка все элементы, у которых равные"соседи"; 6) удаляет из списка каждый k-й элемент (до тех пор, пока в списке не окажется менее k элементов); 7) по исходному списку L строит список L1 из неотрицательных компонент L и список L2 из отрицательных компонент L; 8) вставляет в начало списка новый элемент; 9) вставляет в конец списка новый элемент; 10) вставляет в список новый элемент после каждого вхождения элемента е1; 11) вставляет в список новый элемент перед каждым вхождением элемента е1; 12) определяет, симметричен ли заданный во входном файле текст; 13) удаляет из списка отрицательные элементы; 14) проверяет, состоят ли списки L1 и L2 из одинаковых элементов; 15) проверяет, состоят ли списки L1 и L2 из одинаковых элементов и одинаково ли они упорядочены; 16) проверяет списки L1 и L2 на вхождение (L1 входит в L2, если L1 можно построить за один проход L2).

ЛИТЕРАТУРА 1. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. - М.: Наука, 1988. 2. Абрамов С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987. 3. Зуев Е.А. Программирование на языке Turbo Pascal 6.0, 7.0. - М.: Веста, Радио и связь, 1993. 4. Перминов О.Н. Программирование на языке Паскаль - М.: Радио и связь, 1988. 5. Пильщиков В.Н. Сборник упражнений по языку Паскаль. - М.: Наука, 1989. 6. Тумасонис В., Дагене В., Григас Г. Паскаль. Руководство для программиста: Справочник. - М.: Радио и связь, 1992. 7. Фаронов В.В. Основы Турбо-Паскаля. - М.: Учебно-инженерный центр "МВТУ-ФЕСТО ДИДАКТИК", 1992.

СОДЕРЖАНИЕ 1. Введение. Статические и динамические переменные ................................................................................... 3 2. Тип указатель........................................................................................................................................................ 4 3. Оператор @............................................................................................................................................................ 5 4. Бестиповые указатели ......................................................................................................................................... 6 5. Приведение типов переменных.......................................................................................................................... 6 6. Константы с типом указатель ............................................................................................................................ 8 7. Сравнение указателей ......................................................................................................................................... 8 8. Монитор кучи........................................................................................................................................................ 8 9. Освобождение памяти.......................................................................................................................................... 9 10. Список свободных блоков............................................................................................................................... 10 11. Переменная HeapError .................................................................................................................................... 11 12. Процедуры и функции для работы с указателями и адресами ............................................................... 12 13. Пример использования динамических переменных.................................................................................. 13 14. Индивидуальные задания ............................................................................................................................... 17 ЛИТЕРАТУРА ........................................................................................................................................................ 20

Составители: Мирецкий Игорь Юрьевич Батхин Александр Борисович

РАБОТА С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ И УКАЗАТЕЛЯМИ В СИСТЕМЕ TURBO PASCAL Методические указания для студентов 1 и 2 курсов специальности "Прикладная математика" Редактор Валентай С.И. Технический редактор Турченкова И.И.

Подписано в печать _______________. Формат _______________ . Бумага типографская N1. Гарнитура Таймс. Усл. печ. л._____. Тираж _______. Заказ ________.

Издательство Волгоградского государственного университета 440062, Волгоград, ул. 2-я Продольная, 30.