Методичка Паскаль

При работе с динамическими переменными возникает необходимость работы с данными ссылочного типа, или указателями.

Указатели

Указатель – это переменная целого типа, которая интерпретируется как адрес какого-либо элемента данных (переменной, константы, адреса дру-

гого элемента данных). Т.е. указатель – это адрес. Кроме этого, употребля-

ют термин ссылка. Это синонимы.

В языке Паскаль существует возможность получить значение адреса любой переменной, как статической, так и динамической. Это можно сделать посредством функции Addr.

Например, после исполнения команды присваивания p := Addr (a);

в переменную p будет записан адрес1 переменной a. Вместо функции

Addr можно использовать оператор @. То есть, вместо записанной выше ко-

манды можно написать: p := @a;

В языке Турбо Паскаль указатели бывают двух видов – типизирован-

ные и нетипизированные.

Типизированные указатели

Типизированным называется указатель, который указывает (ссылает-

ся) на данные определенного типа. Для его объявления используется символ

^, который размещается перед соответствующим типом данных. Например:

Type mas = array[1..100] of real;

Var p1 : ^integer;

p2 : ^mas;

В этом случае p1 – это ссылка (указатель) на целое число, p2 – ссылка на массив из 100 вещественных чисел. Для того, чтобы обратиться к данным

1 Память в персональном компьютере адресуется двумя шестнадцатеричными словами (BA:BS), где BA - сегментный адрес, BS - смещение. Сегмент – участок памяти длиной 64 Кбайта, который начинается с физического адреса, значение которого кратно числу 16. Смещение определяет номер байта в сегменте.

91

по этим адресам, необходимо указать: p1^, p2^. То есть, p1 – это адрес, а p1^

- то, что по этому адресу находится.

Для выделения участка динамически распределяемой памяти (кучи) в

целях размещения там необходимых данных используется стандартная про-

цедура

New (p); , где p – указатель.

После выполнения такой команды будет выделен блок памяти необхо-

димого размера (для размещения тех данных, на которые ссылается указатель p), а сам указатель p приобретет значение адреса этого выделенного участка памяти. Например, после выполнения команд:

New (p1);

New (p2);

будет выделено два непрерывных участка кучи, первый размером 2

байта (т.к. целое число занимает 2 байта оперативной памяти), второй – 400

байтов (100 * 4 байта для каждого из 100 вещественный чисел).

После выполнения этих команд указатели p1 и p2 приобрели конкрет-

ные значения. Поэтому по адресам, на которые они указывают, можно раз-

мещать конкретные значения соответствующего типа. Например, p1^ := 52;

p2^[1] := 8;

Если в момент выполнения процедуры New в куче не окажется непре-

рывного участка памяти требуемого размера, то программа аварийно завер-

шится с сообщением «Out of Memory». Для контроля размера доступного участка в динамически распределяемой памяти (куче) можно использовать функцию MaxAvail, которая возвращает размер максимального непрерыв-

ного участка кучи в текущий момент времени.

Для освобождения динамической памяти используется процедура

Dispose (p); , где p – указатель.

Например:

Dispose (p1);

92

Dispose (p2);

После выполнения такой команды память, ранее связанная с указате-

лем, возвращается в кучу (и может быть вновь использована уже для хране-

ния других данных). Однако значение самого указателя не меняется, т.е. в

нем остается адрес «несуществующего» (уже отданного обратно в кучу) бло-

ка памяти. Поэтому обращение к указателю после выполнения команды Dispose может привести к ошибке.

В паскале существует константа Nil – пустой указатель. Значение Nil

может быть присвоено любому указателю, например: p2 := nil;

Однако выполнение такого присваивания до вызова процедуры

Dispose (p2) к тому, что указатель p2 не будет ссылаться ни на какой участок динамической памяти, а данные в памяти останутся, т.е. этот участок не бу-

дет возвращен в кучу. Это плохо по той причине, что при выполнении серии таких команд значительная часть динамической памяти будет считаться за-

нятой, но использоваться не будет.

Константа Nil необходима при работе с динамическими структурами данных, что будет рассмотрено ниже.

Нетипизированные указатели

Нетипизированным называется указатель, не связанный с каким-то конкретным типом данных. Для его описания используется стандартный тип

Pointer. Например,

Var p : pointer;

Нетипизированные указатели используются для динамического разме-

щения данных, структура и тип которых могут меняться в ходе выполнения программы.

Для выделения памяти используется стандартная процедура

GetMem ( p, size );

где p – указатель, переменная типа Pointer; size – размер выделяемого участ-

ка памяти, выражение типа Word (целочисленный тип). За одно обращение к

93

процедуре GetMem возможно выделение не более 65521 байта памяти (мак-

симальное значение типа Word).

Для освобождения памяти и возвращения ее в кучу используется стан-

дартная процедура

FreeMem ( p, size );

где p – указатель, переменная типа Pointer; size – размер освобождаемого участка памяти, выражение типа Word.

Константу Nil можно использовать и при работе с нетипизированными указателями.

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

Динамическими называют структуры данных, динамически создавае-

мые в ходе выполнения программы. Они размещаются в динамической памя-

ти. К ним относятся списки: однонаправленные (стек, очередь), двунаправ-

ленные; графы (и прежде всего дерево как ориентированный граф).

Стек

Стеком называется структура данных, организованная по правилу

LIFO: last input – first output, т.е последним вошел – первым вышел.

Глубина стека – количество элементов в нем.

Вершина стека – «верхний», т.е. доступный элемент.

Стек как структуру данных, размещенную в динамической памяти,

можно представить как «цепочку» записей (Record), одно из полей которых есть указатель на предыдущий элемент. Стек из четырех элементов «выгля-

дит» в памяти так, как изображено на Рис. 8:

указатель на вершину стека

4-й эл-т		3-й эл-т		2-й эл-т		1-й эл-т	Nil
ссылка		ссылка		ссылка		ссылка

Рис. 8. Стек из четырех элементов

94

Примеры решаемых задач Пример 1. Составить программу, которая формирует стек из 10 эле-

ментов, а затем удаляет его из памяти.

Программа:

Program stack10;

Uses Crt;

Const n=10;

Type stack = ^elem; elem = Record

num : Integer; p : stack

End;

Var st,beg_st : stack;

i : Integer;

Begin

Clrscr; beg_st := nil;

For i := 1 To n Do

Begin

New (st);

st^.p := beg_st; beg_st := st;

Write ('введите ', i ,' элемент стека ');

Readln (st^.num)

End;

Writeln ('в динамической памяти создан стек:'); st := beg_st;

While st <> nil Do

Begin

Writeln (st^.num);

95

st:=st^.p

End;

Readln;

Writeln ('Освобождаем память - удаляем элементы стека из кучи '); i := n;

st := beg_st;

While beg_st<>nil do

Begin

st := beg_st;

Writeln ('Удалили ', i ,' элемент '); beg_st := st^.p;

i := i - 1; Dispose (st);

End;

Readln

End.

Контрольные задания

14.1. Составить программу, которая создает стек из N элементов (про-

извольного типа) и:

a.) выводит содержимое стека на экран; b.) вставляет элемент в стек на k-е место; c.) удаляет элемент с номером k из стека.

14.2. Составить программу, которая создает очередь из N элементов

(произвольного типа) и:

a.) выводит элементы очереди на экран;

b.) вставляет элемент в очередь на k-е место; c.) удаляет элемент с номером k из очереди.

14.3. Составить программу, которая формирует двунаправленный спи-

сок из N элементов (произвольного типа) и:

96

a.) выводит элементы списка на экран;

b.) вставляет элемент в список на k-е место; c.) удаляет элемент с номером k из списка.

97

Список литературы

1.Алексеев Е.Р. Турбо Паскаль 7.0. М.: НТ Пресс, 1996.

2.Грызлова Т.П., Грызлов В.И. Турбо Паскаль 7.0: для школьников,

студентов и преподавателей. Изд. 4-е, испр-е. М.: ДМК Пресс, 2005.

3. Кораблев В. Турбо Паскаль 7.0. Самоучитель. Изд. 16-е . Спб.: Пи-

тер, 2005.

4. Немнюгин С., Перколаб Л. Изучаем Турбо Паскаль. Спб.: Питер,

2004.

5. Попов В.Б. Турбо Паскаль для школьников. М.: Финансы и стати-

стика, 2004.

6. Фаронов В.Р. Турбо Паскаль 7.0: начальный курс. М.: Нолидж,

1997.

7. Чеснокова О.Р. Турбо Паскаль 7.0. Шаг за шагом. М.: НТ Пресс,

2004.

98

Газейкина Анна Ивановна

Основы структурного программирования на языке Паскаль

Учебно-методическое пособие/ Урал. гос. пед. ун-т.

Оригинал-макет подготовлен автором

ЛР №040330 от 18.04.97

Подписано в печать Формат 60х84 1/16 Печать плоская. Бумага для множ. апп.

Гарнитура Таймс. Усл. печ. л. 6 . Тираж 100 экз. Заказ

Уральский государственный педагогический университет 620017, г. Екатеринбург, пр. Космонавтов, 26.

Тираж отпечатан в отделе множительной техники

99