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

Динамические структуры данных: стек, дек, очередь

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

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

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

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

2) Разработать математическую модель: описать с помощью формул и рисунков вид используемой динамической структуры и процессы её создания и использования.

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

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

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

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

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

5) Составить спецификации используемых подпрограмм.

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

7) Использовать оконный интерфейс предыдущих лабораторных работ.

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

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

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

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

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

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

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

Даны три стержня и 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