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

Цель лабораторной работы: изучение способов создания и принципов использования динамических структур данных типа стек, дек, очередь; изучение стандартных средств языка C/C++ для работы с динамической памятью; совершенствование навыков структурного программирования на языке C/С++ при решении задач обработки динамических структур данных.

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

Порядок выполнения работы:

1) Получить у преподавателя индивидуальное задание.

2) Построить схему алгоритма решения задачи.

3) Использовать функции, реализующие полный набор операций для этой структуры:

- допустимые операции для стека: инициализация, проверка пустоты, добавление нового элемента в начало, извлечение элемента из начала;

- допустимые операции для очереди: инициализация, проверка пустоты, добавление нового элемента в конец, извлечение элемента из начала;

- допустимые операции для дека: инициализация, проверка пустоты, добавление нового элемента в начало, добавление нового элемента в конец, извлечение элемента из начала, извлечение элемента из конца.

4) Составить спецификации функций.

5) Составить программу на языке C/С++.

6) Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ в окнах на экране входных и выходных данных.

7) Оформить отчет о лабораторной работе в составе: постановка задачи, математическая модель, схема алгоритма решения, спецификация функций, текст программы, контрольные примеры.

Варианты индивидуальных заданий

Отсортировать строки файла, содержащие названий книг, в алфавитном порядке с использованием двух деков.

Дек содержит последовательность символов для шифровки сообщений. Дан текстовый файл, содержащий зашифрованное сообщение. Пользуясь деком, расшифровать текст. Известно, что при шифровке каждый символ сообщения заменялся следующим за ним в деке по часовой стрелке через один.

Дек содержит последовательность символов для шифровки сообщений. Дан текстовый файл, содержащий сообщение. Пользуясь деком, зашифровать текст, заменяя каждый символ сообщения следующим за ним в деке против часовой стрелки через один.

Написать программу, моделирующую железнодорожный сортировочный узел. Исходный файл содержит информацию об имеющихся вагонах двух типов, при этом количество вагонов обоих типов одинаково. Последовательность элементов файла неупорядочена, в каждом элементе файла: тип вагона и идентификационный номер вагона. Используя стек (“тупик”), за один просмотр исходного файла сформировать новый файл (“состав вагонов”), в котором типы вагонов чередуются.

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

на каждом шаге со стержня на стержень переносить только один диск;

диск нельзя помещать на диск меньшего размера;

для промежуточного хранения можно использовать стержень В.

Реализовать алгоритм, используя три стека вместо стержней А, В, С. Информация о дисках хранится в исходном файле.

Дан файл из вещественных чисел. Используя очередь, за один просмотр файла напечатать сначала все числа, меньшие a, затем все числа из интервала [a, b], и, наконец, все остальные числа, сохраняя исходный порядок в каждой группе.

Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в тексте, используя стек.

Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в тексте, используя очередь.

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

Дан файл из символов. Используя очередь, за один просмотр файла напечатать сначала все цифры, затем все буквы, и, наконец, все остальные символы, сохраняя исходный порядок в каждой группе символов.

Дан текстовый файл. Используя стек, сформировать новый текстовый файл, каждая строка которого содержит символы соответствующей строки исходного файла, записанные в обратном порядке.

Дан файл из целых чисел. Используя очередь, за один просмотр файла напечатать сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе.

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

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

Дан текстовый файл. Используя стек, вычислить значение логического выражения, записанного в текстовом файле в следующей форме:

< ЛВ >:: = T | F | (N < ЛВ>) | (< ЛВ> A < ЛВ>) | (< ЛВ> X < ЛВ>) | (< ЛВ> O < ЛВ>),

где буквами обозначены логические константы и операции:

T – True, F – False, N – Not, A – And, X – Xor, O – Or.

Дан текстовый файл. В текстовом файле записана формула следующего вида:

< Формула>:: = < Цифра> | M (< Формула>, < Формула>) | N (Формула>, < Формула>)

< Цифра >:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

где буквами обозначены функции:

M – определение максимума, N – определение минимума.

Используя стек, вычислить значение заданного выражения.

Дан текстовый файл. Используя стек, проверить, является ли содержимое текстового файла правильной записью формулы вида:

< Формула >:: = < Терм > | < Терм > + < Формула > | < Терм > - < Формула >

< Терм >:: = < Имя > | (< Формула >)

< Имя >:: = x | y | z

В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, вычислить значение выражения.

Пример выражения: 2 3 5 + * 7 6 - * => 16

В текстовом файле хранится выражение, записанное в инфиксной форме. Используя стек, перевести его в постфиксную форму и в таком виде записать в новый текстовый файл.

Пример выражения: a + b / c / d * e => a b c / d / e * +

В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, перевести его в инфиксную форму и в таком виде записать в новый текстовый файл.

Пример выражения: a b + c * d – f * => ((a + b) * c – d) * f