Краткий курс лекций по основам структурного программирования на языке Pascal

Вид материала

Курс лекций

Содержание Тема 14. Динамические переменные в языке Pascal Типизированные указатели Nil – пустой указатель. Значение Nil Nil необходима при работе с динамическими структурами данных, что будет рассмотрено ниже. Нетипизированные указатели Динамические структуры данных Стек Стеком Record), одно из полей которых есть указатель Список литературы

Подобный материал:

• Правила преобразований из одного типа в другой и правила приведения типов в языке Object, 19.03kb.
• Курс лекций по основам программирования Учебно-методическое пособие, 726.7kb.
• Программа элективного курса «Программирование на языке Pascal» 10 класс, 63.48kb.
• Курс «Программирование на языке Turbo Pascal 0» Цель курса, 19.6kb.
• Краткий курс лекций "Основы программирования на языке Паскаль" Основные понятия, 265.68kb.
• Программирование на языке высокого уровня, 59.92kb.
• Структура программы в языке программирования С++. Обмен данными между функциями (параметры, 37.24kb.
• Краткий курс лекций "Основы программирования на языке Паскаль", 291.49kb.
• Структура программы на языке Turbo Pascal, 26.15kb.
• Тематическое планирование кружка на 2009/2010 уч г. «Основы алгоритмизации и программирования, 63.72kb.

Тема 14. Динамические переменные в языке Pascal

Статические и динамические переменные

Переменные в тексте программы описываются в разделе описания переменных. Например:

Var a, b : integer;

s : string;

m : array [1..100] of real;

Такие «обычные» статические переменные располагаются в части оперативной памяти компьютера, называемой стеком (stack). Объем стека не превышает 64 Кбайтов. Перед исполнением программы в стеке резервируются участки памяти, размер которых соответствует типу переменных, описанных в разделе описания переменных (VAR).

Кроме того, программист имеет возможность использовать в своей программе динамические переменные, память для которых резервируется уже в процессе исполнения программы и затем, если в них больше нет необходимости, может быть освобождена. Такие переменные располагаются в другой части оперативной памяти компьютера. Такая динамически распределяемая память называется кучей (Heap-областью).

Необходимость в использовании динамических переменных возникает в следующих случаях:

1. Программа должна обрабатывать большие объемы данных (более 64 Кбайтов).
   
2. Программа должна обрабатывать данные, объем памяти для хранения которых заранее неизвестен.
   
3. Тип обрабатываемых данных заранее неизвестен.
   
4. Программа использует динамические структуры данных (стек, очередь, двунаправленный список, дерево, граф и т.п.).
   

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

Указатели

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

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

Например, после исполнения команды присваивания

p := Addr (a);

в переменную p будет записан адрес¹ переменной a. Вместо функции Addr можно использовать оператор @. То есть, вместо записанной выше команды можно написать:

p := @a;

В языке Turbo Pascal указатели бывают двух видов – типизированные и нетипизированные.

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

Типизированным называется указатель, который указывает (ссылается) на данные определенного типа. Для его объявления используется символ , который размещается перед соответствующим типом данных. Например:

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

Var p1 : integer;

p2 : mas;

В этом случае p1 – это ссылка (указатель) на целое число, p2 – ссылка на массив из 100 вещественных чисел. Для того, чтобы обратиться к данным по этим адресам, необходимо указать: 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); Dispose (p2);

После выполнения такой команды память, ранее связанная с указателем, возвращается в кучу (и может быть вновь использована уже для хранения других данных). Однако значение самого указателя не меняется, т.е. в нем остается адрес «несуществующего» (уже отданного обратно в кучу) блока памяти. Поэтому обращение к указателю после выполнения команды Dispose может привести к ошибке.

В паскале существует константа Nil – пустой указатель. Значение Nil может быть присвоено любому указателю, например:

p2 := nil;

Однако выполнение такого присваивания до вызова процедуры
Dispose (p2) к тому, что указатель p2 не будет ссылаться ни на какой участок динамической памяти, а данные в памяти останутся, т.е. этот участок не будет возвращен в кучу. Это плохо по той причине, что при выполнении серии таких команд значительная часть динамической памяти будет считаться занятой, но использоваться не будет.

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

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

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

Var p : pointer;

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

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

GetMem ( p, size );

где p – указатель, переменная типа Pointer; size – размер выделяемого участка памяти, выражение типа Word (целочисленный тип). За одно обращение к процедуре GetMem возможно выделение не более 65521 байта памяти (максимальное значение типа Word).

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

FreeMem ( p, size );

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

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

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

Динамическими называют структуры данных, динамически создаваемые в ходе выполнения программы. Они размещаются в динамической памяти. К ним относятся списки: однонаправленные (стек, очередь), двунаправленные; графы (и прежде всего дерево как ориентированный граф).

Стек

Стеком называется структура данных, организованная по правилу LIFO: last input – first output, т.е последним вошел – первым вышел.

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

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

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

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

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.