Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1327


12. указатели и динамическая память

 

Все переменные, объявленные в программе, размещаются в оперативной памяти в непрерывном сегменте, размер которого не может превышать 64 кБайт. Для размещения данных, требующих больший размер памяти, или для данных, количество которых неизвестно заранее и может модифицироваться в программе (массивы с динамическими размерами, переменными) используется механизм управления динамической  памятью (ДП).

 

ДП – это оперативная память компьютера, предоставляемая программе за вычетом сегмента в 64 кБайта (для статических   пере- менных, стека 16 кБайт) и соответственно кода тела программы.

 

Для управления ДП, с целью изменения ее размеров, используется следующая директива компилятора:

{ $M,<стек>,<min ДП>,<max ДП> }

По умолчанию    предполагается    существование следующей директивы:

{ $M,16384,0,655360 }

Для управления данными ДП в TURBO PASKAL существует  гибкое средство – указатели.

 

Указатель – это переменная, которая в качестве своего значения содержит адрес некоторого байта памяти.

 

Адрес  байта  оперативной  памяти  задается  совокупностью  двух

16-разрядных слов, которые называются сегментом и смещением.

Cегмент –  это  участок оперативной памяти длиной в  64  кбайта,

который начинается с адреса, кратного 16.

Смещение – указывает, сколько байт от начала сегмента надо пропустить, чтобы обратиться к нужному адресу. Вообще можно узнать каждый адрес переменной с помощью операции взятия адреса @.

Таким образом, по своей структуре любой указатель представляет совокупность двух слов (данных типа WORD). С помощью указателя ДП можно разместить данные любого типа. Для описания указателей используются ссылочные типы.

 

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

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

Для объявления типизированного указателя  используется значок ^ и имя типа.

Пример:

var p1,p2:^byte; k:byte;

 

Для того, чтобы присвоить переменной ссылочного типа  некоторое значение, необходимо следовать правилам:

1) если присваивается переменной ссылочного типа   значение того же ссылочного типа, то они должны принадлежать одному и тому же типу.

Например:

 

begin

....... p2:=p1; p1:=k;невозможно

 

2) для реализации  присваивания ссылочной переменной некоторого значения, не являющегося указателем, необходимо воспользоваться опе- рацией взятия адреса @.

Пример:

var i:byte;

.............

begin p1:=@i;

p2:=nil;

p1 присваивается адрес,

где хранится переменная, определяемая идентификатором i;

nil  –  это  совместимое по  типу  с  любым  указателем значениe,

которое означает указатель в никуда.

 

Вся ДП может  рассматриваться как  сплошной  массив, этот массив называется кучей. Адрес начала кучи хранится в стандартной переменной

HEAPORG,

конец кучи хранится в стандартной переменной

HEAPEND.

 

Границу кучи указывает стандартная переменная HEAPPTR.

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

 

NEW(P); Р – указатель.

 

В результате обращения к этой процедуре указатель P приобретает значение, соответствующее адресу, начиная с  которого могут размещаться

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

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

Стандартная функция Maxavail возвращает максимальный размер непрерывного участка ДП.

Функция Sizeof (<переменная или ее тип>) возвращает число байт необходимых для хранения переменной.

Функция    Memavail    –    суммарный    размер    всех    свободных областей ДП.

Для освобождения ДП во время работы программы используют функцию Dispose с параметром указателем на динамическую переменную, причем эта переменная должна быть ранее размещена в куче.

 

Var

P: ^Person;

................ begin

new(p);

 

Действия

 

 

 

end.

Dispose(p)

 

 

12.1. Работа со списком

 

Односвязный  список   –   это   динамическая   структура,   каждый элемент которой содержит информационную (info) и адресную (next) компоненты. Адресная компонента указывает на адрес следующего эле- мента списка.

 

Рассмотрим односвязный список

 

info       info       info       info next          next     next                 nil

который объявлен в программе так:

 

type      ptr = ^zap;

zap = record;

info:string[35];

 

 

var

next:ptr;

end;

headptr:ptr;

s,p:ptr;

 

Пример 12.1. Процедура добавления элемента в начало списка. procedure Add_begin;

begin

p:=headptr;

new(s);{выделение памяти под новый элемент списка}

s^.next:=p;{связывание нового элемента с головой исходного списка}

s^.info:='добавляемая запись';

headptr:=s;{объявление нового элемента головой списка}

end;

 

Пример           12.2.    Пример           процедуры     добавления    элемента в конец списка.

procedure Add_End;

begin

 

 

end;

p:=headptr;{установка на начало}

while p^.next<>nil do

p:=p^next;{переход к последней записи}

new(p^.next); p^.info:='добавляемая запись'; p^.next:=nil;

 

 

Пример 12.3. Процедура удаления из ДП элементов списка. Procedure DelAllZap;

Var

PP,P : Ptr;

begin

P := HeadPtr; {связывание текущего указ.Р с головой списка} PP := P^.Next; {связывание указ.РР со след.элементом списка} Dispose(P); {освобождение памяти для указ.Р}

While PP^.Next <> Nil Do       {пока РР не последний}

begin

P := PP; {текущий указ.P стал равен РР } PP := PP^.Next; {переход с след.элементу}

Dispose(P); {освобождение памяти для текущ.указателя}

end;

end;

 

Пример 12.4. Программа вывода на экран студентов группы ПМ–11. uses crt;

type ptr=^student; student=record fio,group:string[10]; next:ptr;

end;

var headptr:ptr;

PROCEDURE FORMSPISOK;

var p:ptr; let:char;

procedure vvod(var stud:student);

begin

with stud do begin write(' fio '); READLN(fio);

writeln(' Не забудьте ввести группу ПМ–11');

write(' group '); READLN(group); end

end; Begin{простроение списка}

headptr:=nil;

repeat

write(' s–закончить '); READLN(let); let:=Upcase(let);

if let='S' then exit; if headptr=nil then begin

new(headptr);

p:=headptr;

end

else begin

new(p^.next);

p:=p^.next;

end; vvod(p^); p^.next:=nil;

until false; end;{formspisok} Procedure pechspisok;

var p:ptr; begin

p:=headptr;

while p <> nil do begin

with p^ do

if group = 'ПМ–11' then writeln(' ',fio,' ',group);

p:=p^.next;

end;

end; {pechspisok} Procedure Writefile; VAR

P:PTR; i :byte; begin

writeln(' |––––––––––––––––––|––––––––––––––––|');

writeln(' |     ФИО       | Группа     |');

writeln(' |––––––––––––––––––|––––––––––––––––|'); P := Headptr ;

i := 1;

while p <> Nil do begin with p^ do

writeln(' |',fio:17,'|',group:14,'|');

p := p^.next;

if p <> nil then writeln(' |––––––––––––––––––|––––––––––––––––|');

else writeln(' |––––––––––––––––––|––––––––––––––––|');

i := i + 1;

end; End;{writefile}

{********************************} Begin

clrscr; window(14,2,70,23); textbackground(3); clrscr;

textcolor(0);

writeln(' Программа вывода на экран студентов группы ПМ–11');

formspisok; writefile; textcolor(1);

writeln('            Студенты группы ПМ–11');

pechspisok;

textcolor(4);

writeln(' Нажмите на клавишу..');

repeat until keypressed

End.

 

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

 

Пример 12.5. Организация стека. uses crt;

type cc=^zap; zap=record

inf:string; next:cc; end;

var p,top,newelement:cc; value:string;

procedure sozdsteka;

begin    top:=nil; {top – вершина}

while true do begin

write('Введи информацию (конец ввода – 999) '); READLN(value);

if value='999' then exit;

new(p); p^.next:=top; p^.inf:=value; top:=p;

end

end;

 

Пример 12.6. Добавление элементов в стек. procedure dobavs;

begin

while true do begin

write('Введи добавляемую информацию (конец ввода – 999)'); READLN(value);

if value='999' then exit; new(newelement); newelement^.next:=top; newelement^.inf:=value; top:=newelement

end end;

 

Пример 12.7. Удаление элементов из стека. procedure udals;

begin top:=top^.next

end;

 

Пример 12.8. Просмотр элементов стека. procedure rasps;

begin kon:=top;

while kon<>nil do begin

writeln('            ',kon^.inf);

kon:=kon^.next end

end; begin textbackground(1); textcolor(15); window(1,1,80,25); clrscr;

writeln('Программа работы со стеком');

writeln('выполняет процедуры создания,добавления и удаления');

writeln('Создание стека');

sozdsteka;

writeln(' Содержимое стека ()');

rasps; READLN; textcolor(6);

writeln(' Добавление элемента в стек');

dobavs;

textcolor(14);

writeln(' Содержимое стека после добавления (всегда в вершину)');

rasps; READLN; textcolor(7);

writeln(' Удаление элемента из стека (последним пришел – первым ушел)');

udals; rasps  ; READLN; end.

 

Задания для самостоятельного выполнения

1. Создать список, содержащий сведения о месячной заработной плате рабочих завода. Каждая запись содержит поля – фамилии рабочего, наименование  цеха,  размер  заработной  платы  за  месяц.  Количество записей произвольное.

2. Создать список, содержащий сведения о количестве изделий, собранных сборщиками цеха за неделю. Каждая запись содержит поля: фамилия сборщика, количество изделий, собранных им ежедневно в течении шестидневной недели, т. е. раздельно – в понедельник, вторник и т. д. Количество записей произвольное.

3. Создать список, содержащий сведения о количестве изделий категорий А, В, С, собранных рабочим за месяц. Структура записи имеет поля: фамилия  сборщика,  наименование  цеха,  количество  изделий  по категориям, собранных рабочим за месяц. Количество записей произвольное.

4. Создать список со следующими полями

 

 

Название книги

ФИО автора

Издательство

Число томов

 

Вывести         информацию  о          книгах,            выпущенных  издательством

«Прогресс», в виде:

 

Название книги         Фамилия автора

Контрольные  вопросы

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

мятью?

2. Что используется для описания указателей?

3. Что называется кучей?

4. Что такое односвязный список?

5. Что такое стек?