История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-12-21 | 185 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!