Проблема распределения памяти. Списочные структуры.
Проблема распределения памяти - проблема ее фрагментированности ("проблема кучек"):
- необходимо сохранить некоторую последовательность f,
- но нет ни одной кучки (сплошного незанятого участка памяти), достаточной для хранения всех элементов последовательности f в естественном порядке,
-
![]() |
хотя совокупного объема свободной памяти для этого достаточно.
Черные области - занятые участки памяти (область определения массива памяти как некоторой последовательности), белые - незанятые (область неопределенности), внешняя рамка - некоторый интервал [1..N] (область имен/указателей/индексов на участки память).
![]() |
Очевидный вариант решения проблемы - дефрагментация - копирование полезной информации в одну, а куч свободной памяти - в другую часть памяти - действительно, иногда применяется, но очевидно, крайне трудоемок (по времени).
Надо придумать способ хранения компонент последовательности f:NàT, не зависящий от порядка расположения компонент (в массиве/памяти). Цель - уметь класть очередную компоненту на произвольное (первое попавшееся) свободное место. Необходимое и одновременно изящное решение - хранить f в виде функции F: NàN´T c произвольной (т.е. "дырявой" и не упорядоченной) областью определения Dom(F)= {n1 ,n2.,..., nk}, такой, что
(*) F(n1)=<n2,f(1)>, F(n2)=<n3,f(2)>,.., F(ni)=<ni+1,f(i)>,… F(nk)=< nk+1,f(k)>
Такой способ хранения последовательностей называется списковой организацией памяти, или просто списком. По определению, список F хранит значения f и индекс (указатель,"имя") следующего ее значения. Указатель n1 называют головой списка, указатель nk+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=компонента хранимой последовательности fi}
begin
pt:=List; {» i:=1}
while not (pt<>nil) {» i<=длины f} do
begin {Обработка fi = 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=компонента хранимой последовательности fi}
begin
reset(f); List:=nil; {» i:=0}
while not eof(f) {» i<=длины f} do
begin new(pt); read(f, pt^.value); { pt^.value:= fi }
pt^.next:=List; List:=pt
end;
end;
Здесь список хранит компоненты исходной последовательности в обратном порядке, что не всегда приемлимо и удобно. Мы обязаны хранить ссылку на начало (первую компоненту) списка, но мы можем хранить ссылки и на другие его компоненты. Такие компоненты назовем активными.
Реализацию операций вставки и исключения из списка - см. "Задачи текстовой обработки"