Проблема распределения памяти. Списочные структуры.

Проблема распределения памяти - проблема ее фрагментированности ("проблема кучек"):

- необходимо сохранить некоторую последовательность f,

- но нет ни одной кучки (сплошного незанятого участка памяти), достаточной для хранения всех элементов последовательности f в естественном порядке,

-

хотя совокупного объема свободной памяти для этого достаточно.

Черные области - занятые участки памяти (область определения массива памяти как некоторой последовательности), белые - незанятые (область неопределенности), внешняя рамка - некоторый интервал [1..N] (область имен/указателей/индексов на участки память).

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

Надо придумать способ хранения компонент последовательности f:NàT, не зависящий от порядка расположения компонент (в массиве/памяти). Цель - уметь класть очередную компоненту на произвольное (первое попавшееся) свободное место. Необходимое и одновременно изящное решение - хранить f в виде функции F: NàN´T c произвольной (т.е. "дырявой" и не упорядоченной) областью определения Dom(F)= {n₁ ,n₂.,..., n_k}, такой, что

(*) F(n₁)=<n₂,f(1)>, F(n₂)=<n₃,f(2)>,.., F(n_i)=<n_{i+1,f(i)>,…} F(n_k)=< n_k+1,f(k)>

Такой способ хранения последовательностей называется списковой организацией памяти, или просто списком. По определению, список F хранит значения f и индекс (указатель,"имя") следующего ее значения. Указатель n₁ называют головой списка, указатель n_k+1, не принадлежащий Dom(F) - признаком конца списка. Обычно, в качестве признака выделяют специальный "пустой" указатель 0 (например, число 0 или -1), единственный смысл которого - ни на что не указывать (по определению, 0 ÏDom(F) для всех списков F).

Основные операции над списками - перечисление, вставка и удаление компонент - никак не используют арифметические операции на Dom(F), т.е. тот факт, Dom(F)ÌN, а лишь то, что они, в качестве имен, указывают (ссылаются) на значения. Это и делает возможным реализацию списков ссылочным типом.

type

tComponent=record value:T;next:p:pComponent end;

pComponent=^tComponent;

pList=pComponent;

{список задается ссылкой на голову - первую компоненту списка}

{или значением nil, если такового не существует, т.е. список пуст}

{перечисление компонент списка}

procedure Enumeration(List:pList);

var pt:pComponent;

{если pt¹nil, pt^.value=компонента хранимой последовательности f_i}

begin

pt:=List; {» i:=1}

while not (pt<>nil) {» i<=длины f} do

begin {Обработка f_i = pt^.value } pt:=pt^.next {» i:=i+1} end;

end;

{порождение списка (здесь: из компонент файла f: file of T)}

procedure Generation(var List:pList; var f: FileOfT);

var pt:pComponent;

{если pt¹nil, pt^.value=компонента хранимой последовательности f_i}

begin

reset(f); List:=nil; {» i:=0}

while not eof(f) {» i<=длины f} do

begin new(pt); read(f, pt^.value); { pt^.value:= f_i }

pt^.next:=List; List:=pt

end;

end;

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

Реализацию операций вставки и исключения из списка - см. "Задачи текстовой обработки"