Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Дисциплины:
2017-12-21 | 184 |
5.00
из
|
Заказать работу |
Псевдодинамические массивы - последовательности переменной длины m, m£MaxLen, где MaxLen - константа.
const MaxLen=100;
type
tIndex=1..MaxLen;
tArray=array[tIndex];
tPseudoArray=
record content:tArray; {содержимое/компоненты массива}
{можно задать len:tIndex; фактическая длина массива}
{или - принимаемый далее вариант}
top:tIndex; {len+1, первое свободная позиция в массиве, начало кучи -незаполненной части массива }
end;
Нетрудно сопоставить содержимому стеков содержимое массивов, а стековым операциям - соответствующие алгоритмы обработки массивов.
type
tStack=tPseudoArray;
procedure Pop(var stack:tStack; var x:T);
begin with stack do begin top:=top-1; x:=Content[top] end; end;
procedure Push(var stack:tStack;x:T);
begin with stack do begin Content[top]+1; top:=top+1; end; end;
{при неосмотрительном использовании, выполнение операторов чревато }
{выходом за границы массива [1..MaxLen]}
{но ситуация не совсем симметрична, у пользователя есть функция проверки пустоты стека, но нет функции проверки переполнения стека }
function Empty(Stack:tStack):boolean;
begin Empty:=Stack.top=1 end
procedure Create(var Stack:tStack); begin Stack.top:=1 end;
procedure Destroy(Stack:tStack)); begin Stack.top:=1 end;
Одинаковая реализация разных операций, конечно, настораживает. Create призвана порождать функцию (с пустой областью определения), Destroy - уничтожать функцию (с любой областью определения), наша релизация лишь опустошает область определения функции. Причина ясна - мы никак не моделируем понятие состояния (см. далее) Пока оставим нюансы - так или иначе, главные стековые операции push и pop работают правильно.
Обратимся к моделированию очередей. Определим "псевдодинамические" массивы с двумя концами.
tPseudoArray2=
record content:tArray; {содержимое/компоненты массива}
start, finish:tIndex; {начало+1 и конец-1 массива -}
{начало правой кучи и конец левой кучи}
end;
tQueue=tPseudoArray2;
Реализация операций как будто очевидна - класть значения в конец, а брать - из начала массива. Формально верная, такая реализация порождает частный случай проблемы динамического распределения памяти (общую формулировку см. ниже): Вводя в конец (занимая одну, "правую" часть кучи) и выводя из начала массива значения компонент (опустошая другую, "левую" часть кучи), мы весьма скоро можем оказаться в ситуации, когда свободной памяти много, а класть компоненты некуда!
Правда, в этом частном случае ее нетрудно решить, объединяя две части кучи, мысленно рассматривая массив как кольцо.
procedure Put(var Queue:tQueue; x:T); { Поставить В Очередь }
begin
with Queue do
begin content[finish]:=x;
if finish=nMax then finish:=1 else inc(finish) {» finish:=finish+1 (mod nMax)}}
{интересно - см. понятие модульной арифметики в курсе дискретной математики}
end; end;
procedure Get(r,x); { Вывести Из Очереди }
begin
with r do
begin x:= content[start];
if start=1 then start:=nMax else dec(start) {» start:=start-1 (mod nMax)}}
end; end;
function Empty(r): boolean;
begin Empty:= (start=finish) or ((start=nMax) and (finish=1)) {start=finish (mod nMax)} end;
Замечание. Снова более эффективная, но не защищенная реализация - пользователь процедур должен сам следить за переполнением очереди.
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!