Geum.ru

Потопахин Виталий Валерьевич 3 Задачи прикладного характера по информатике 3 миф-2, №2, 2000 8 Потопахин Виталий Валерьевич 8 решение

Вид материалаРешение

Содержание


МИФ-2, №1, 2003 Информатика 10-11 Богоутдинов Дмитрий Гилманович Структуры данных (часть 2)
Top) списка. Подносы в столовой или стопка коробок являются моделями стека. Основными операциями для стека являются операции про
Последовательности ( ), { }, [ ] являются правильно построенными.
Алгоритм ПРАВПОСТР (правильно построенная).
ADT очередь.
Конец ADT
Подобный материал:
1   ...   11   12   13   14   15   16   17   18   ...   21
^

МИФ-2, №1, 2003


Информатика 10-11

Богоутдинов Дмитрий Гилманович

Структуры данных (часть 2)


В предыдущей статье мы рассмотрели понятия структуры данных и абстрактного типа данных, а также начали рассмотрение основных видов динамических структур. В этой статье мы рассмотрим два важных вида динамических структур, основанных на связанных списках – стеки и очереди.

Напомним, что в списках доступ к элементам ничем не ограничивается. Но существуют также и такие списковые структуры данных, в которых доступ к элементам ограничен, наиболее важная из них – стековый список или просто стек (Stack). В стеке доступ ограничен только к элементу, который внесен в него самым последним. По этой причине он имеет также название списка по принципу «последний пришел, первым вышел» (список типа LIFO). Стеки применяются очень часто. Например, распознавание синтаксиса в компиляторе, оценка выражений основаны на стеке.

Стек – это список элементов, доступных только в одном конце списка. Элементы добавляются или удаляются только в вершине (^ Top) списка. Подносы в столовой или стопка коробок являются моделями стека.

Основными операциями для стека являются операции проталкивания (Push) и выталкивания (Pop). При выполнении операции проталкивания элемент заносится в стек, а операция выталкивания выбирает из стека элемент, записанный в него последним. Абстрактное понятие стека допускает неопределенно большой список, т.е. мы видим, что стек относится к динамическим структурам данных. В действительности же, стек всегда имеет некоторое максимальное количество элементов, которыми он может управлять. При достижении этого количества элементов, о стеке говорят, что он полон (Stack full). Наоборот, условие пустого стека (Stack empty) подразумевает, что мы не можем удалить элемент. В нашем случае ADT Стек содержит только условие пустого стека. Условие полного стека уместно в том случае, если реализация содержит верхнюю границу размера списка (например, при реализации в виде массива). Приведем здесь описание ADT Стек.

ADT Стек

Данные: Список элементов с позицией Top, указывающей на вершину стека.

Операции

Конструктор

Начальные значения: Нет.

Процесс: Инициализация вершины стека.

StackEmpty

Вход: Нет.

Предусловия: Нет.

Процесс: Проверка, пустой ли стек.

Выход: Возвращать True, если стек пустой, иначе

возвращать False.

Постусловия: Нет.

Pop

Вход: Нет.

Предусловия: Стек не пустой.

Процесс: Удаление элемента из вершины стека.

Выход: Возвращать элемент из вершины стека.

Постусловия: Элемент удаляется из вершины стека.

Push

Вход: Элемент для стека.

Предусловия: Нет.

Процесс: Сохранение элемента в вершине стека.

Выход: Нет.

Постусловия: Стек имеет новый элемент в вершине.

Peek

Вход: Нет.

Предусловия: Стек не пустой.

Процесс: Нахождение значения элемента в вершине

стека.

Выход: Возвращать значение элемента из вершины стека.

Постусловия: Стек неизменный.

ClearStack

Вход: Нет.

Предусловия: Нет.

Процесс: Удаление всех элементов из стека и

переустановка вершины стека.

Выход: Нет.

Постусловия: Стек переустановлен в начальные условия.

Конец ADT Стек

Р
ассмотрим эти операции на примере.

Пример 3.1. Данный пример иллюстрирует моделирование стека на основе массива из пяти целых чисел со следующей последовательностью операций: Push 10; Push 25; Push 50; Pop; Pop. Индекс Top увеличивается на 1 при операции Push и уменьшается на 1 при операции Pop.

Как видно из примера, самая простейшая реализация стека использует массив. Наряду с этим стек можно организовать и при помощи указателей.

Рассмотрим еще один пример.

Пример 3.2. Разработать алгоритм определения того, что произвольная последовательность круглых, квадратных и фигурных скобок является правильно построенной. Под правильно построенной понимают последовательность, удовлетворяющую следующему определению:

^ Последовательности ( ), { }, [ ] являются правильно построенными.

Если последовательность x правильно построенная, то правильно построены и последовательности (x), {x}, [x].

Если последовательности x и y правильно построенные, то такова же и последовательность xy.

Правильно построенными являются лишь те последовательности, правильность которых следует из конечной последовательности применений правил 1, 2, 3.

Обычно, чтобы установить, являются ли выражения правильно построенными, используют стековую память.

Приведем алгоритм, который определяет, является ли произвольная последовательность скобок x1, x2, ... , xn, где xi – одна из скобок (, {, [, ), }, ], правильно построенной. Назовем элементы (, {, [ ЛЕВЫМИ символами. Будем говорить, что xi – левый партнер xj, если xi = [ и xj = ], или xi = ( и xj = ), или xi = { и xj = }.

^ Алгоритм ПРАВПОСТР (правильно построенная).

Установить TOP := 0; I:=1.

Пока I<=N выполнять шаги 2 и 3.

Если xi ЛЕВЫЙ символ тогда записать xi

иначе

если TOP – левый партнер xi ,то выбрать элемент TOP из памяти,

иначе напечатать «Неправильно построенная» и остановиться.

Присвоить I:=I+1;

Е
сли TOP = 0, то напечатать «Правильно построенная» иначе напечатать «Неправильно построенная» и остановиться.

Применим данный алгоритм к следующей последовательности:

Н
а рисунке приведено содержимое стека, соответствующее операциям чтения элементов из g слева направо, целое значение над i – той конфигурацией стека указывает на то, что в данный момент читается xi символ.

Очереди

В стековой памяти для внесения и удаления элементов можно пользоваться только словом TOP. В очереди элементы добавляются с одного конца, а выбираются с другого. Эти элементы обычно называются началом (Front) и концом (Rear) очереди. Термин «очередь» выбран потому, что эти структуры данных используются для моделирования обслуживающих линий, например люди в очереди к парикмахеру, автомобили у светофора, очередь заданий операционной системы.

Для моделирования очереди, как правило, используют линейный массив (например, QUEUE [500]) и две целые переменные Front и Rear, которые указывают на первый и последний элементы очереди соответственно. Вначале Rear  Front, но когда к очереди добавится свыше 500 элементов, то по-видимому, некоторые записи будут удалены из начала очереди. Если это так, то, чтобы не допустить переполнения массива, мы присваиваем Rear = 1 и продолжаем заполнять очередь с начала массива. Впрочем, Rear никогда не должен перегонять Front.

Приведем пример ADT Очередь.

^ ADT очередь.

Данные

Список элементов

Front: позиция первого элемента в очереди

Rear: позиция последнего элемента в очереди

Count: число элементов в очереди в любое данное время

Операции:

Конструктор

Начальные значения: Нет

Процесс: Инициализация начала и конца очереди

QLength:

Вход: Нет

Предусловия: Нет

Процесс: Определение количества элементов в очереди

Выход: Возвращать количество элементов в очереди

Постусловия: Нет

QEmpty:

Вход: Нет

Предусловия: Нет

Процесс: Проверка: пуста ли очередь

Выход: Возвращать True, если очередь пуста и False иначе.

Постусловия: Нет

QDelete:

Вход: Нет

Предусловия: Очередь не пуста

Процесс: Удаление элемента из начала очереди

Выход: Возвращать элемент, удаляемый из очереди

Постусловия: Элемент удаляется из очереди

QInsert:

Вход: Элемент для сохранения в очереди

Предусловия: Нет

Процесс: Запись элемента в конец очереди

Выход: Нет

Постусловия: Новый элемент добавляется в очередь

QFront:

Вход: Нет

Предусловия: Очередь не пуста

Процесс: Выборка значения элемента в начале очереди

Выход: Возвращать значение элемента в начале очереди

Постусловия: Нет

ClearQueue:

Вход: Нет

Предусловия: Нет

Процесс: Удаление всех элементов из очереди и

восстановление начальных условий

Выход: Нет

Постусловия: Очередь пуста

^ Конец ADT очередь.

ПРИМЕР. Пусть емкость очереди составляет 5 «клиентов», конкретные клиенты помечены метками от A до H, первый ожидающий в очереди клиент обслуживается за 3 единицы времени, после чего он покидает очередь. В момент T=0 очередь пуста, и значения Front (f) и Rear (r) равны нулю. Требуется показать как заполняется очередь в моменты времени от T=1 до T=9.

З
аполнение очереди можно представить в виде следующего рисунка.

В момент T=1 прибывает A и ждет три единицы времени и покидает очередь в момент Т=4. Клиенты B, C, D, E, G и H прибывают в моменты времени 2, 3, 4, 7, 8 и 9 соответственно. С ждет 4 единицы, прежде чем продвинуться в начало очереди, и покидает ее в момент Т=10. Когда прибывает G, в момент Т=8, конец очереди находится в массиве в положении 5. Здесь мы помещаем G в положение 1 очереди и присваиваем r=1. Когда в момент Т=9 прибывает H, в r записывается 2, в этот момент очередь полностью заполнена. Теперь конец очереди сравнялся с ее началом, и, пока С не покинет очередь, в нее становиться нельзя.

Итак, очередь – это линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце.

Также существует понятие очереди с двумя концами или дек. Дек (double-ended queue) – линейный список, в котором все включения и исключения делаются на обоих концах списка.