Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-12-21 | 184 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!