Практические задания

Задание 1.Реализовать программу, выполняющую стандартный набор операций со стеком на основе массива:

· проверку пустоты стека

· проверку заполненности стекового массива

· добавление элемента в вершину стека

· удаление элемента из вершины стека

· вывод текущего состояния стека на экран

Требования:

· все действия должны быть оформлены как процедуры или функции

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

· главная программа реализует следующий набор действий:

o инициализация пустого стека

o организация диалогового цикла с пользователем

Задание 2.Реализовать тот же набор действий на основе динамического распределения памяти.

Требования аналогичны заданию 1, за исключением того, что проверку заполненности стека проводить не надо. Пустой стек задается установкой sp := nil.

Задание 3. Добавить в предыдущую программу возможность занесения в стек сразу нескольких значений. Количество вводимых значений должно запрашиваться у пользователя, а сами значения можно формировать случайным образом с помощью функции Random (не забыть предварительно вызвать функцию Randomize). Проверить работоспособность программы при различных количествах вводимых элементов, в том числе – для больших значений (десятки тысяч элементов).

Задание 4 (дополнительно).Добавить в предыдущую программу следующие возможности:

· при удалении элемента из основного стека запросить у пользователя, что делать далее с этим элементом: действительно удалить с освобождением памяти или включить его в вершину вспомогательного стека удаленных элементов

· при добавлении нового элемента запросить у пользователя происхождение этого элемента: действительно создание нового элемента или выбор его с вершины вспомогательного стека

· вывод содержимого вспомогательного стека удаленных элементов

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

· проверку пустоты очереди

· проверку заполненности очереди

· добавление элемента в конец очереди

· удаление элемента из начала очереди

· вывод текущего состояния очереди на экран

Требования к программе:

· все действия должны быть оформлены как процедуры или функции

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

· главная программа реализует следующий набор действий:

o инициализация пустой очереди

o организация диалогового цикла с пользователем

Задание 6.Реализовать тот же набор действий на основе динамического распределения памяти.

Требования аналогичны заданию 1, за исключением того, что проверку заполненности очереди проводить не надо. Пустая очередь содержит только заголовочный элемент

Задание 7.Написать программу для моделирования работы очереди со случайным числом добавляемых и удаляемых элементов.

Пусть за единицу времени (например – 1 минуту) в очередь либо добавляется, либо удаляется случайное число элементов в количестве от 1 до 3-х. Одновременно добавление и удаление НЕ происходит. Для наглядности элементами пусть являются большие латинские буквы (коды ASCII от 65 до 90), выбираемые случайным образом. Тип операции с очередью (добавление или удаление) также задается случайно. Это приводит к тому, что очередь случайно растет и убывает. Программа должна наглядно показывать состояние очереди в каждый момент времени.

Рекомендации по разработке программы.

За основу взять предыдущую программу, внеся в ее процедуры следующие изменения:

· процедура добавления вместо запроса у пользователя информационной части нового элемента должна получать ее как входной параметр

· процедура удаления должна выполнять удаление одного элемента только если очередь НЕ пустая

Главная программа должна:

· после создания пустой очереди, содержащей только заголовок, инициировать датчик псевдослучайных чисел (процедура Randomize) и вывести соответствующее сообщение

· организовать цикл с выходом при вводе пользователем какого-либо специального символа (например – буквы q)

· сгенерировать случайное число в диапазоне от 1 до 100 и проверить его четность с помощью операции взятия остатка от деления этого числа на 2

· если число четное – реализовать операцию добавления, если нечетное – операцию удаления

· в том и другом случае выполнить:

o генерацию случайного числа добавляемых или удаляемых символов в диапазоне от 1 до 3-х

o вывод сообщения о выполняемом действии и количестве добавляемых/удаляемых элементов

o выполнение цикла для добавления или удаления заданного числа элементов с вызовом соответствующих процедур работы с очередью, причем при добавлении новый символ должен генерироваться случайно с помощью его кода (диапазон 65 – 90) с последующим преобразованием кода в сам символ с помощью стандартной функции CHR

· вывести текущее состояние очереди

· запросить у пользователя символ для окончания цикла (при выполнении программы для продолжения работы цикла можно просто дважды нажать клавишу ввода)

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

· случайное число добавляемых и удаляемых элементов одинаково (например – от 1 до 3-х)

· число добавляемых элементов чуть больше (в среднем!) числа удаляемых (например, добавляется случайное количество элементов в диапазоне от 1 до 4-х, а удаляется – от 1 до 3-х)

· число удаляемых элементов чуть больше числа добавляемых

Для каждого случая выполнить программу при достаточно большом числе добавлений/удалений (30-40) и сделать вывод о поведении очереди.

.

2.7. Контрольные вопросы по теме

1. Что такое стековый принцип сохранения элементов?

2. Какие основные операции реализуются для стеков?

3. Какие шаги выполняются при добавлении элемента в стек-массив?

4. Какие шаги выполняются при удалении элемента из стека-массива?

5. Какие особые ситуации возможны при реализации стека с помощью массива?

6. Какую структуру должен иметь элемент стека при динамической реализации?

7. Что такое физический и логический порядок следования элементов в стеке?

8. Как между собой связываются соседние элементы стека?

9. Какие типы данных необходимы для динамической реализации стека?

10. Какие переменные необходимы для реализации операций с динамическим стеком?

11. Как реализуется проход по динамическому стеку?

12. Как выполняется добавление элемента в динамический стек?

13. Как выполняется удаление элемента из динамического стека?

14. Сравните динамическую и статическую реализации стека

15. Что такое структура данных типа очередь?

16. Какие основные операции необходимы для реализации структур типа очередь?

17. Как реализуется очередь с помощью массива?

18. Как работает кольцевая очередь, реализованная с помощью массива?

19. Какие особые ситуации возможны при реализации очереди с помощью массива?

20. Как выполняется добавление элемента в очередь-массив?

21. Как выполняется удаление элемента из очереди-массива?

22. На чем основана динамическая реализация очереди?

23. Зачем в очередь вводится фиктивный заголовочный элемент?

24. Что включает в себя создание пустой динамической очереди с заголовком?

25. Какие типы данных необходимы для динамической реализации очереди?

26. Какие переменные используются для реализации основных операций с динамической очередью?

27. Как реализуется проход по динамической очереди?

28. Как реализуется добавление элемента в динамическую очередь?

29. Как реализуется удаление элемента из динамической очереди?

30. Какие особенности имеет приоритетная очередь?

31. Сравните статическую и динамическую реализации очереди.