1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

Логический порядок элементов определяетсяадресными частями при проходе от последнего элемента к первому. Структура оперативной памяти вэтом случае может выглядеть следующим образом:Для построения логического порядка следования элементов достаточно знать вершинныйэлемент, все остальное восстанавливается по адресным частям элементов независимо от их реальногоразмещения в памяти.Для программной реализации элемент стека надо объявить как структуру, содержащую покрайней мере два поля – информационное и связующее. Для простоты будем считать, чтоинформационное поле каждого элемента содержит только одно целое число.struct StackItem {int Info;StackItem *Next;};Какие ссылочные переменные необходимы для поддержки работы стека? Во-первых, всегданеобходимо знать адрес элемента, находящегося на вершине стека, т.е.

помещенного в стек самымпоследним:StackItem *Sp=NULL;Тогда конструкция Sp->Info будет представлять саму информационную часть, а конструкцияSp->Next - адрес предыдущего элемента, который был помещен в стек непосредственно передтекущим.Кроме того, для прохода по стеку от вершинного элемента к самому первому элементунеобходима вспомогательная ссылочная переменная (например – с именем Current). Она на каждомшаге прохода по стеку должна определять адрес текущего элемента.

В самом начале прохода надоустановить значение Current = Sp, а затем циклически менять его на значение Current->Next до техпор, пока не будет достигнут первый элемент стека. Очевидно, что для прохода надо использоватьцикл с неизвестным числом повторений, а признаком его завершения должно быть получение в полеCurrent->Next пустой ссылки NULL. Отсюда следует, что ссылочное поле самого первого элементастека должно содержать значение NULL.Тогда схематично проход по стеку можно представить следующим образом:StackItem *Current = Sp;while(Current != NULL){cout << Current->Info << " ";Current = Current->Next;}Добавление нового элемента в вершину стекаНеобходимые шаги:выделить память для размещения нового элемента с помощью вспомогательнойссылочной переменной Tmp и стандартной программы newStackItem *Tmp = new StackItem;заполнить информационную часть нового элементаcin >> Tmp->Infoустановить адресную часть нового элемента таким образом, чтобы она определялаадрес бывшего вершинного элемента:Tmp->Next = Sp;изменить адрес вершины стека так, чтобы он определял в качестве вершины новыйэлемент:Sp = Tmp;В этой последовательности шагов важен их порядок.

Перестановка шагов 3 и 4 приведет кнеправильной работе алгоритма вставки, т.к. на шаге 4 происходит изменение указателя Sp, которыйперед этим на шаге 3 используется для установки правильного адреса в ссылочной части новогоэлемента.Удаление элемента с вершины стекаНеобходимые шаги:с помощью вспомогательной переменной Tmp адресуем удаляемый элемент:Tmp = Sp;изменяем значение переменной Sp на адрес новой вершины стека:Sp = Tmp->Next;каким-то образом обрабатываем удаленный с вершины элемент, например – простоосвобождаем занимаемую им память вызовомdelete Tmp;или включаем его во вспомогательную структуру (например – стек удаляемыхэлементов).Сравнение статической и динамической реализации стека: при статической реализациирасходуется меньше памяти, но требуется знание максимального числа элементов в стеке-массиве;динамическая реализация более гибкая, но каждый элемент стека дополнительно расходует памятьна ссылочную часть (чаще всего – 4 байта), что при большом числе элементов может стать весьмаощутимым.Реализации (с кодом)Для стека с n элементами требуетсяэлементов.памяти, так как она нужна лишь для хранения самихНа массивеОперация вставки нового элемента применительно к стекам часто называется push (запись встек), а операция удаления — pop (снятие со стека).

Стек, способный вместить не более n элементов,можно реализовать с помощью массива S[1..n]. Этот массив обладает атрибутом S.top,представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементовS[1..S.top], где S[1] — элемент на дне стека, а S[S.top] — элемент на его вершине.Если S.top=0, то стек не содержит ни одного элемента и является пустым (empty).Протестировать стек на наличие в нем элементов можно с помощью операции-запроса Stack_Empty.Если элемент снимается с пустого стека, говорят, что он опустошается (underflow), что обычноприводит к ошибке.

Если значение S.top больше n, то стек переполняется (overflow). (Впредставленном ниже псевдокоде возможное переполнение во внимание не принимается.)Каждую операцию над стеком можно легко реализовать несколькими строками кода:Stack_Empty(S)if S.top == 0return trueelsereturn falsepush(S,x)S.top = S.top + 1S[S.top] = xpop(S)if Stack_Empty(S)return error "underflow"elseS.top = S.top - 1return S[S.top + 1]На спискеСтек можно реализовать и на списке.

Для этого необходимо создать список и операцииработы стека на созданном списке. Ниже представлен пример реализации стека на односвязномсписке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции pushбудут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека спомощью pop будет текущая голова. После вызова функции push текущая голова уже станет старой ибудет являться следующим элементом за добавленным, то есть ссылка на следующий элемент новогоэлемента будет указывать на старую голову. После вызова функции pop будет получена и возвращенаинформация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станетэлемент, который следовал за изъятой головой.push(element)OldHead = new ListItemNewHead = new ListItemOldHead = headNewHead.data = elementNewHead.next = OldHeadhead = NewHeaddelete NewHeadpop()OldHead = new ListItemOldHead = headint element = OldHead.datahead = OldHead.nextdelete OldHeadreturn elementВ реализации на списке, кроме самих данных, хранятся указатели на следующие элементы,которых столько же, сколько и элементов, то есть, так же n.

Стоит заметить, что, хотя общая оценказатрачиваемой памяти, в ней скрыта бóльшая константа, и реализация на списке требуетнесколько больше памяти.38, 39. Очереди, их реализация с помощью динамические переменные (39) очереди, ихреализация с использованием массивов и записейЛекции: фото 33, 34Очередь – это линейная структура данных, в которую элементы добавляются с одного конца(конец очереди), а удаляются – с другого (начало очереди).

Очередь работает по принципу “элемент,помещенный в очередь первым, извлечен будет тоже первым”. Иногда этот принцип обозначаетсясокращением FIFO (First In – First Out, т.е. первым зашел – первым вышел). Элементами очередеймогут быть любые однотипные данные. Очереди очень широко используются в системныхпрограммах, в частности – в операционных системах и компиляторах. Программная реализацияочереди возможна двумя способами:1. статически с помощью массива2. динамически с помощью механизма указателейСтатическая реализация очередиПусть в очереди требуется сохранять целые числа, причем заранее известно их максимальноеколичество. Тогда для реализации очереди надо объявить массив и две переменные – указательначала очереди First и указатель конца очереди Last.

Будем считать, что очередь-массив заполняется(растет) от первых элементов массива к последним. Тогда указатель First будет определять первуюзанятую ячейку массива, а указатель Last – первую свободную ячейку. Тогда пустую очередьопределим как First = Last = 0 (если индексация элементов массива начинается с 0), и при каждомдобавлении нового элемента переменная Last увеличивается на 1, а при удалении на 1 увеличиваетсяуказатель First.

Последовательность операций для массива из пяти элементов показана на следующейсхеме:Рассмотренная выше простейшая реализация очереди-массива имеет один существенныйнедостаток: освобождающиеся при удалении ячейки в начале массива НЕ используются припоследующих добавлениях, и поэтому при интенсивном использовании очереди быстро можетвозникнуть ситуация, когда указатель Last выходит за пределы массива, тогда как в начале массиваесть свободные ячейки.Для устранения этого недостатка можно использовать два подхода: при очередном удалении элемента из начала очереди сдвигать все элементы влево на одну ячейку,что при большом числе элементов в очереди может привести к большим вычислительным затратам более эффективно использовать так называемую кольцевую очередь, в которой при достиженииуказателем Last конца массива добавление производится в начало массива:В этом случае добавление становится невозможным только если в массиве нет ни однойсвободной ячейки, как в рассмотренном примере.Для программной реализации удобно ввести переменную-счетчик числа элементов вочереди, с помощью которой легко отслеживаются состояния пустой и заполненной очереди.Само добавление элемента в очередь выполняется следующим образом: проверить возможность добавления (в массиве есть свободные ячейки?) добавить элемент в массив по индексу Last увеличить Last на 1 если Last выходит за пределы массива, то установить Last в 0 увеличить счетчик числа элементов в очередиУдаление элемента из очереди: проверить возможность удаления (в очереди есть элементы?) извлечь элемент из массива по индексу First и выполнить с ним необходимые действия увеличить First на 1 если First выходит за пределы массива, то установить First в 0 уменьшить счетчик числа элементов в очередиДинамическая реализация очередиАналогично стеку, каждый элемент очереди должен иметь ссылку на следующий за нимэлемент, поэтому элемент очереди объявляется как структура с двумя полями – информационноеполе и связующее поле.

Характеристики

Список файлов ответов (шпаргалок)