Курс лекций для специальности «Прикладная математика» Первый семестр
| Вид материала | Курс лекций |
- Курс лекций для специальности Прикладная математика и информатика, 774.04kb.
- Календарный план лекций по курсу «математический анализ» Для специальности «Математика», 39.98kb.
- Рабочая программа, 160.99kb.
- Рабочая программа, 182.62kb.
- Цифровая обработка сигналов, 137.86kb.
- Курс лекций (28 часов) канд филос наук О. В. Аронсон Курс лекций «Математика и современная, 27.49kb.
- Урс «Численное решение обыкновенных дифференциальных уравнений» читает кафедра фн-2, 24.78kb.
- Курс IV семестр 8 Всего аудиторных занятий 52 Лекций, 117.53kb.
- Курс лекций в электронной форме содержит все лекции предусмотренные программой дисциплины, 32.88kb.
- Календарный план учебных занятий по обязательной дисциплине «Дискретная математика, 109.62kb.
Лекция 11
11.1 Статическая и динамическая память программы
Для выполнения оттранслированной программы объектный код ее загружается в оперативную память вычислительной машины. Под код программы и под ее данные отводится участок оперативной памяти, называемый статической памятью программы. При загрузке программы относительные адреса объектного кода и данных (констант, переменных, массивов и т.д.) заменяются на реальные адреса отведенного участка памяти. Если операционная система допускает многозадачный режим работы, статическая память программы не доступна другим программам, так же как и статическая память других программ не доступна данной программе. Однако, существует свободная, не используемая никакой программой, память, которая может быть временно задействована каждой из программ. Такая память называется динамической памятью.
В языке ТР имеются механизмы использования динамической памяти на этапе выполнения программы. Необходимость в использовании динамической памяти возникает, если по условию задачи не удается заранее предвидеть потребный объем статической памяти. Вот пример такой задачи: (*) Распечатать последовательность вводимых с клавиатуры символов в обратном порядке.
11.2 Динамическая память (куча, heap) с точки зрения ТР
Пусть Т – некоторый тип данных, тогда T – новый тип данных, такой, что q:T – переменная (называемая указателем), которая может принимать значение адреса участка динамической памяти, куда может быть записано значение типа Т.
Инициализация указателя осуществляется процедурой new(q). Процедура new выделяет в области динамической памяти участок свободной памяти, объем которой достаточен для хранения данного типа Т, и переменной q присваивает значение адреса начала этого участка. Выделенный участок памяти объявляется занятым в области динамической памяти, сам выделенный участок является динамической переменной типа Т с именем q.
Инициализация динамической переменной может быть осуществлена как и инициализация обычных статических переменных. Например, если t:T – инициализированная переменная типа Т, то можно выполнить присваивание динамической переменной q:=t.
Когда динамическая переменная q выполнила свою функцию, и больше не нужна, от нее следует избавиться, освободив отведенную под нее память. Это можно сделать с помощью процедуры DISPOSE(q). Динамическая переменная q перестает существовать, память, отведенная под нее, становится свободной, а указатель q становится неопределенной (неинициализированной) переменной.
В ТР существует предопределенная константа NIL, совместимая со всеми указателями, которую можно трактовать, как «несуществующий адрес». Если переменной-указателю присвоить значение NIL (q:=NIL), то указатель q становится инициализированной переменной, однако q - бессмысленно.
11.3 Операции над указателями
Указатель может находиться в одном из трех состояний:
- Указатель не инициализирован. Указатель можно инициализировать процедурой NEW, значением другого (инициализированного) указателя, или константой NIL.
- Указатель инициализирован процедурой NEW. Можно использовать динамическую переменную q, сам указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);
- Указатель инициализирован константой NIL. Можно указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);
11.4 Геометрическая интерпретация
Указатель q:T описан в тексте программы на ТР. С помощью процедуры new(q) указатель q инициализируется. Диспетчер динамической памяти выделяет участок свободной памяти размером sizeof(T) в области динамической памяти (в куче) и адрес его начала присваивает переменной q. Теперь динамическая переменная q типа Т доступна для использования, однако, пока не инициализирована. Инициализировать ее можно, например, присваиванием q:=t, где t – константа типа Т.
11.5 Динамическая цепочка
Зачем нужна динамическая переменная? Одиночная динамическая переменная не представляет никакого интереса. Интерес представляют различные структуры данных, созданные в области динамической памяти. Такие структуры создаются и развиваются на этапе выполнения программы, они могут быть адаптированы к текущим данным, объемы которых становятся известными лишь на этапе выполнения программы. Вернемся к задаче (*). Пользователь набирает на клавиатуре последовательность символов. Окончание набора фиксируется набором комбинации клавиш Ctrl+z, Enter. Для хранения введенных символов необходимо использовать структуру данных достаточного объема. Все статические структуры данных (структуры данных, созданные в статической памяти) имеют ограничения на количество вводимых символов. Попробуем организовать хранение введенных с клавиатуры символов в динамической памяти. Для этого в программе опишем новый тип данных, представляющий собой запись, содержащую поле типа char для хранения введенного символа, и поле типа «указатель» на следующую запись:
PElem=Elem;
Elem=Record
inf:char;
next:PElem
end
В начале работы программы создается пустая цепочка записей. После каждого ввода очередного символа создается новая запись и подсоединяется к цепочке. Пусть p – данное типа PElem, x:char, тогда
- p:=nil; {Создана пустая цепочка}
- while not eof do
begin
readln(x);
new(q);
q.inf:=x;
q.next:=p;
p:=q;
end;
Задача: Распечатать третью запись цепочки, если она есть.
writeln(p.next.next.inf) {а если ее нет?!}
Задача: Распечатать k-ую запись цепочки.
q:=p;
i:=1;
while (q<>nil) and (i
begin
i:=i+1;
q:=q.next;
end;
if q<>nil then writeln(q.inf) else writeln(‘нет записи’);
Распечатать информационные части стека p.
| Традиционное решение | Рекурсивное решение |
| Procedure prnchar(p:PElem); Var q:PElem; begin q=p; while p<>NIL do begin write(p.inf); p=p.next end end | Procedure prnchar(p:PElem); begin if p<>NIL then begin write(p.inf); prnchar(p.next) end end |
Задача: Распечатать информацию, вводимую с клавиатуры, в прямом порядке.
Задача: Перевернуть файл (используем цепочку)