Сборка мусора

Дек

Else

Begin

Begin

Then

Begin

Then

Begin

Очередь

В очереди существует указатель не только на «голову», но и на «хвост» очереди.

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

Например, ввод данных с клавиатуры производится через буфер данных – это область оперативной памяти персонального компьютера, в которой хранятся по мере поступления/извлечения коды вводимых символов.

Если значения указателей начала и конца совпадают, то значит, что буфер пустой.

Пример программы создания и удаления очереди:

program oсhered;

uses Crt;

type Ptr=^Elem;

Elem= record

Inf: real;

Link: Ptr

end;

var BegQ,EndQ: Ptr;

Znach: real;

i: byte;

procedure AddEl(var Val:real);

var P: Ptr;

new (P);

P^.Inf:=Val;

P^.Link:= nil;

if EndQ= nil {если значение указателя на конец

очереди}

BegQ:=P {то создаем первый элемент очереди}

else

EndQ^.Link:=P; {иначе создаем очередной

элемент очереди}

EndQ:=P

end;

procedure DelEl(var Val: real);

var P: Ptr;

Val:= BegQ^.Inf;

P:= BegQ;

BegQ:=P^.Link;

if BegQ= nil {если значение указателя на начало

очереди}

EndQ:= nil; {то удаляем последний элемент очереди}

Dispose (P)

end;

begin {oсhered}

ClrScr;

{начальные установки указателей}

BegQ:= nil;

EndQ:= nil;

{создаем очередь из 10 элементов}

for i:=1 to 10 do

AddEl(i);

{удаляем очередь, распечатывая значения элементов}

while BegQ<> nil do

DelEl(Znach);

writeln (‘Znach= ’, Znach:5:2);

end;

end. {oсhered}

Пример программы, формирующей связанный список в процессе ввода данных:

program Spisok;

uses crt;

type Pe=^Typelem; {описание элемента списка}

Typelem= record

T:real

P: Pe;

end;

var Elem,first: Pe;

X: real;

Ch: char;

n: integer;

begin {Spisok}

ClrScr;

new (Elem); {выделение памяти}

first:=Elem;

Elem^.P:=Elem;

while Elem^.P<> nil do {пока не конец списка,

выполнять}

write (‘Ввелите число: ’);

readln (Elem^.T); {ввод значений элементов}

write (‘Повторить ввод? (Y/N)’);

readln (Ch);

if (Ch=’n’) or (Ch=’N’) {если введено ’n’ или

’N’ (т.е. нет)}

then Elem^.P:= nil {то ссылке последнего

элемента присваивается значение nil}

begin {иначе выделяем память под новый

элемент}

new (Elem^.P);

Elem:=Elem^.P;

end;

n:=n+1; {подсчитываем количество элементов

списка}

end;

writeln (‘Ввод данных закончен’);

writeln (‘Вывод элементов списка’);

Elem:=first;

repeat {выводим элементы, пока не конец списка}

writeln (‘ ’,Elem^.T:8:3);

Elem:=Elem^.P;

until Elem= nil;

writeln (‘Количество элементов=’,n);

writeln;

end. {Spisok}

Над очередью определены две операции:

1) занесение элемента в очередь,

2) выбор элемента из очереди.

Придумал Дональд Кнут (7 томов «Искусство программирования»). Deque – «кольцевая очередь» – Dek.

В каждый момент времени Dek-а возможно перемещение как вперед так и назад. Если указатели показывают в одно и то же место, то двунаправленная очередь пуста.

Как только список свободных областей становится пустым, производится проверка всех активных списков. Любой элемент, который не входит нив один из активных списков, считается не нужным, а область, в которой он находится, возвращается в список свободных областей. Эта операция называется сборкой мусора. (Какой бы не была по объему память компьютера, она все равно кончается – для этого и нужна сборка мусора.)

17 марта

СРС: 1. Какие из операторов неправильные? Ответ пояснить.

var p,q: ^integer;

r: char;

p:=q;

q:=r;

p:= nil;

r:= nil;

q:=p^;

r^:=p^;

q^:=ord(r^);

if r<>nil then r^:=nil^;

if q>nil then q^:=p^;

2.Что будет выведено на экран в результате выполнения программы?

program Ukazatel;

type ref=^integer;

var p,q: ref;

Дата добавления: 2014-01-20