дек. Лабораторная работа Реализация стекадека
 Скачать 18.26 Kb.
|
|
Лабораторная работа 4. Реализация стека/дека. Используя технологию модульного программирования разработать программу обработки данных, содержащихся в заранее подготовленном файле, в соответствии с индивидуальным заданием. Применить динамическую структуру указанного в задании вида: стек, очередь или дек. Программа должна включать модуль, содержащий набор всех необходимых средств (типов, подпрограмм и т.д.) для решения поставленной задачи. Порядок выполнения работы: 1) Получить у преподавателя индивидуальное задание. 2) Разработать математическую модель: описать с помощью формул и рисунков вид используемой динамической структуры и процессы её создания и использования. 3) Построить схему алгоритма решения задачи. 4) Использовать подпрограммы, реализующие полный набор операций для этой структуры: - допустимые операции для стека: инициализация, проверка на пустоту, добавление нового элемента в начало, извлечение элемента из начала; - допустимые операции для дека: инициализация, проверка на пустоту, добавление нового элемента в начало, добавление нового элемента в конец, извлечение элемента из начала, извлечение элемента из конца. 5) Составить спецификации используемых подпрограмм. 6) Составить программу, включающую модуль обработки соответствующей динамической структуры. 8) Проверить работу программы на полном наборе тестов. Обеспечить одновременный показ в окнах на экране содержимого входного и выходного файлов. 9) Оформить отчет о лабораторной работе. Варианты 1.Отсортировать строки файла, содержащие названий книг, в алфавитном порядке с использованием двухдеков. 2.Дексодержит последовательность символов для шифровки сообщений. Дан текстовый файл, содержащий зашифрованное сообщение. Пользуясь деком, расшифровать текст. Известно, что при шифровке каждый символ сообщения заменялся следующим за ним вдекепо часовой стрелке через один. 3.Дексодержит последовательность символов для шифровки сообщений. Дан текстовый файл, содержащий сообщение. Пользуясьдеком, зашифровать текст, заменяя каждый символ сообщения следующим за ним в декепротив часовой стрелки через один. 4.Написать программу, моделирующую железнодорожный сортировочный узел. Исходный файл содержит информацию об имеющихся вагонах двух типов, при этом количество вагонов обоих типов одинаково. Последовательность элементов файла неупорядочена, в каждом элементе файла: тип вагона и идентификационный номер вагона. Используя стек(“тупик”), за один просмотр исходного файла сформировать новый файл (“состав вагонов”), в котором типы вагонов чередуются. 5.Даны три стержня иnдисков различного размера. Диски можно надевать на стержни, образуя из них башни. Перенестиnдисков со стержняАна стерженьС, сохранив их первоначальный порядок. При переносе дисков необходимо соблюдать следующие правила: на каждом шаге со стержня на стержень переносить только один диск; диск нельзя помещать на диск меньшего размера; для промежуточного хранения можно использовать стерженьВ. Реализовать алгоритм, используя три стекавместо стержнейА, В, С. Информация о дисках хранится в исходном файле. 6.Дан файл из вещественных чисел. Используя стекза один просмотр файла напечатать сначала все числа, меньшие a, затем все числа из интервала[a,b], и, наконец, все остальные числа, сохраняя исходный порядок в каждой группе. 7.Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в тексте, используястек. 8.Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс квадратных скобок в тексте, используядек. 9.Дан текстовый файл. Используядек, переписать содержимое его строк в новый текстовый файл, перенося при этом в конец каждой строки все входящие в нее цифры, сохраняя исходный порядок следования среди цифр и среди остальных символов строки. 10.Дан файл из символов. Используястек, за один просмотр файла напечатать сначала все цифры, затем все буквы, и, наконец, все остальные символы, сохраняя исходный порядок в каждой группе символов. 11Дан текстовый файл. Используястек, сформировать новый текстовый файл, каждая строка которого содержит символы соответствующей строки исходного файла, записанные в обратном порядке. 12.Дан файл из целых чисел. Используя дек, за один просмотр файла напечатать сначала все отрицательные числа, затем все положительные числа, сохраняя исходный порядок в каждой группе. 13.Дан текстовый файл. Используястек, сформировать новый текстовый файл, содержащий строки исходного файла, записанные в обратном порядке: первая строка становится последней, вторая – предпоследней и т.д. 14.Дан текстовый файл. Используядек, переписать содержимое его строк в новый текстовый файл, перенося при этом в начало каждой строки все входящие в нее буквы, затем все цифры, и, наконец, все остальные символы строки, сохраняя исходный порядок в каждой группе символов. 15.Дан текстовый файл. Используястек, вычислить значение логического выражения, записанного в текстовом файле в следующей форме: < ЛВ > ::= T | F | (N<ЛВ>) | (<ЛВ>A<ЛВ>) | (<ЛВ>X<ЛВ>) | (<ЛВ>O<ЛВ>), где буквами обозначены логические константы и операции: T – True, F – False, N – Not, A – And, X – Xor, O – Or. 16.Дан текстовый файл. В текстовом файле записана формула следующего вида: <Формула> ::= <Цифра> | M(<Формула>,<Формула>) | N(Формула>,<Формула>) < Цифра > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 где буквами обозначены функции: M – определение максимума, N – определение минимума. Используя стек, вычислить значение заданного выражения. 17.Дан текстовый файл. Используя стек, проверить, является ли содержимое текстового файла правильной записью формулы вида: < Формула > ::= < Терм > | < Терм > + < Формула > | < Терм > - < Формула > < Терм > ::= < Имя > | (< Формула >) < Имя > ::= x | y | z 18.В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, вычислить значение выражения. Пример выражения: 235+*76-*=>16 19.В текстовом файле хранится выражение, записанное в инфиксной форме. Используя стек, перевести его в постфиксную форму и в таком виде записать в новый текстовый файл. Пример выражения: a + b / c / d * e =>abc / d / e * + 20.В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, перевести его в инфиксную форму и в таком виде записать в новый текстовый файл. Пример выражения: ab + c * d – f * =>((a + b) * c – d) * f 21.Отсортировать строки файла, содержащие названий фильмов, в алфавитном порядке с использованием двухдеков. 22.Дан файл из символов. Используястек, за один просмотр файла напечатать сначала все буквы, затем все цифры, и, наконец, все остальные символы, сохраняя исходный порядок в каждой группе символов. 23.Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить фигурных круглых скобок в тексте, используястек. 24.Дан файл из целых чисел. Используя дек, за один просмотр файла напечатать сначала все положительныечисла, затем все отрицательныечисла, сохраняя исходный порядок в каждой группе. 25.Отсортировать строки файла, содержащие фамилии студентов, в алфавитном порядке с использованием двухдеков. |