Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-12-21 | 181 |
5.00
из
|
Заказать работу |
|
|
Проблема распределения памяти - проблема ее фрагментированности ("проблема кучек"):
- необходимо сохранить некоторую последовательность 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;
Здесь список хранит компоненты исходной последовательности в обратном порядке, что не всегда приемлимо и удобно. Мы обязаны хранить ссылку на начало (первую компоненту) списка, но мы можем хранить ссылки и на другие его компоненты. Такие компоненты назовем активными.
Реализацию операций вставки и исключения из списка - см. "Задачи текстовой обработки"
|
|
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!