Динамические структуры данных (стеки и очереди)

Лабораторная работа №12

Задание.

Для решения каждого варианта Вам понадобится использовать одну из динамических структуру данных: стек или очередь. Ваша задача состоит в следующем:

• Реализовать необходимую динамическую структуру данных (создать элемент динамической структуры и три допустимые функции-операции) и описать ее в отдельном вспомогательном модуле.
• Создать заголовочный файл, содержащий интерфейсную часть этого модуля (то, что должно быть доступно извне другим модулям).
• Подключив заголовочный файл в основной модуль (содержащий функцию main), решить задачу согласно варианту, используя реализованную динамическую структуру данных.

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

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

· чтение элемента из вершины без удаления;

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

· проверка стека на пустоту.

//Примерный вид элемента стека

struct StackItem

{

ElementType data; //Данные

StackItem* next; //Указатель на следующий элемент

};

//Объявления функций-операций над стеком

void Push(StackItem* & s_top, ElementType elem); – добавление нового элемента в вершину стека;

ElementType Top(StackItem* s_top); – чтение без удаления элемента из вершины стека;

void Pop(StackItem* & s_top); – удаление элемента из вершины стека,

bool IsEmpty(StackItem* & s_top); - возвращает истину, если стек пуст

где

ElementType – тип хранимых в стеке данных.

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

· добавления элемента в хвост очереди;

· чтение без удаления элемента из головы очереди;

· удаление элемента из головы очереди;

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

//Примерный вид элемента динамической структуры

struct QueueItem

{

ElementType data; //Данные

QueueItem* next; //Указатель на следующий элемент

};

void Enqueue(QueueItem* & q_head, QueueItem* & q_tail, ElementType elem); – добавление элемента в хвост очереди;

ElementType top(QueueItem* q_head, QueueItem* q_tail); – чтение без удаления элемента из головы очереди;

void Dequeue(QueueItem* & q_head, QueueItem* & q_tail); – удаление элемента из головы очереди.

bool IsEmpty(QueueItem* & q_head, QueueItem* & q_tail); – возвращает истину, если очередь пуста.

//Для работы с динамической структурой нужны две переменные

QueueItem* q_head; //Указатель на голову очереди

QueueItem* q_tail; //Указатель на хвост очереди

где

ElementType – тип хранимых очереди данных.

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

1. Текст программы должен быть структурирован, читабелен и комментирован.
2. Программа должна быть тщательно протестирована.
3. Входные данные должны вводиться пользователем с консоли, а результаты отображаться на экране. Возможен вариант с использованием файлов
4. Идентификаторы в программе не должны писаться транслитом с русского языка!!! Загляните в русско-английский словарь при необходимости.
5. Варианты, отмеченные символом *, повышенной сложности и предназначены, в первую очередь, для тех, кто хочет «проявить себя».

Варианты

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

Например.

Для строки «[(])» сообщить, что она не является правильной скобочной последовательностью, т.к. открывающая скобка «(» не соответствует закрывающей «]» и открывающая скобка «[» не соответствует закрывающей «)».

Для строки «[(()[])]([» сообщить, что она не является правильной скобочной последовательностью, т.к. нет закрывающих скобок для открывающих скобок «(» и «[»

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

Вариант 3. Задан стек целых чисел. Для всех чисел подсчитать количество их вхождений в данный стек.

Вариант 4. Имеются две очереди целых чисел. Напишите программу, добавляющую содержимое одной очереди в конец другой.

Вариант 5. Используя два стека символов определить, является ли заданная строка палиндромом.

Вариант 6. Задана очередь положительных действительных чисел. Напишите программу, вычисляющую их среднее геометрическое.

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

Например.

Для последовательности

100, 20, 25, 31, 7, 9, 11

вывести три подпоследовательности

31, 25, 20

11, 9, 7

Вариант 8. Имеется две очереди целых чисел, упорядоченных по возрастанию. Написать программу, которая объединяет их и формирует общую очередь из этих чисел, упорядоченных по возрастанию.

Вариант 9. Задан стек действительных чисел. Напишите программу, вычисляющую среднее арифметическое этих чисел.

Вариант 10*. Перечислить в порядке возрастания все целые числа в диапазоне от 1 до n (n <= 300), которые в качестве делителей имеют только числа 2 или 5.

Вариант 11. Имеется два стека действительных чисел, напишите программу, объединяющую их в один стек.

Вариант 12*. Имеются монеты номиналом 3 и 7 рублей. Определите можно ли их этих монет составить сумму в S рублей (S <= 50) и, если можно, предложите любой способ получить эту сумму.

Вариант 13. Имеется стек целых чисел. Напишите программу удаления самого глубокого (последнего) элемента в стеке, используя один вспомогательный стек. Порядок остальных элементов в стеке после удаления должен остаться прежним.

Вариант 14*. Задана очередь целых чисел. Напишите программу, удаляющую каждый второй элемент очереди. Для решения данной задачи ограничиться только очередью и несколькими переменным, не использовать вспомогательные массивы, списки, стеки и очереди.

Вариант 15. Имеется стек целых чисел. Напишите программу, удаляющую каждый второй элемент стека. Можно использовать один вспомогательный стек. Порядок остальных элементов в стеке после удаления должен остаться прежним.

Вариант 16*. Задана очередь целых чисел. Напишите программу удаления последнего элемента очереди, используя только допустимые операции над очередью. Для решения данной задачи ограничиться только очередью и несколькими переменным, не использовать вспомогательные массивы, списки, стеки и очереди.

Вариант 17. Задан стек целых чисел. Напишите программу, которая на его основе создает два новых стека. В первый стек помещаются положительные числа, во второй – отрицательные. Относительный порядок следования чисел в двух новых стеках обратный.

Вариант 18. Имеется две очереди действительных чисел. Напишите программу, формирующую новую очередь, чередуя числа из данных очередей. Если одна из исходных очередей закончится раньше другой, то оставшееся содержимое другой очереди добавить в конец новой.

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

Вариант 20. Задана очередь целых чисел. Напишите программу, формирующую на ее основе две новые очереди. В первую очередь с сохранением порядка помещаются все четные числа из исходной очереди, во вторую с сохранением порядка – все нечетные.

Поиск по сайту: