Министерство цифрового развития и массовых коммуникаций

Российской Федерации

Ордена Трудового Красного Знамени федеральное государственное

бюджетное образовательное учреждение

высшего образования

«Московский технический университет связи и информатики»

(МТУСИ)

Кафедра Математическая кибернетика и информационные технологии

Отчет по лабораторной работе № 4

по дисциплине «Структуры и алгоритмы обработки данных»

на тему: «Методы поиска»

Выполнила: студентка группы БСТ2001

Курило Анна

Проверил: Чайка А.Д.

Москва 2022

1 Цель работы

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

2 Задание

Первым заданием является реализация стека и дека, а также их операций. В случае стека требуется: инициализация, проверка на пустоту, добавление нового элемента в начало, извлечение элемента из начала. А в случае дека требуется: инициализация, проверка на пустоту, добавление нового элемента в начало, добавление нового элемента в конец, извлечение элемента из начала, извлечение элемента из конца.

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

Говоря о самих заданиях, следует сказать, что их 8 и каждое условие задания будет представлено ниже, перед результатом его выполнения.

Ход работы

Стек — это структура данных, в которой элементы добавляются и удаляются в вершине стека. Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Такую структуру можно представить как стопка тарелок (или книг): доступ ко второй (сверху) тарелке можно получить только после того, как будет взята первая тарелка.

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

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

3.1 Задание 1

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

Рисунок 1 - Расставление названий книг в алфавитном порядке

3.2 Задание 2

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

Рисунок 2 - Реализация расшифровки текста

Рисунок 3 – Реализация расшифровки текста

3.3 Задание 3

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

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

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

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

Выполнение данного задания представлено на рисунке 4.

Рисунок 4- Выполнение задания "Ханойские башни"

3.4 Задание 4

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

Рисунок 5- Проверка баланса круглых скобок

3.5 Задание 5

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

Рисунок 6 - Проверка баланса квадратных скобок

3.6 Задание 6

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

Рисунок 7 - Исходный текст

Рисунок 8 - Отредактированный программой текст в соответствии с заданием

3.7 Задание 7

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

Рисунок 9 - Исходный список чисел

Рисунок 10 - Результат выполнения программы

3.8 Задание 8

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

Рисунок 11 - Результат выполнения программы с переворчаиванием текста

Вывод

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