Полустатические структуры данных
Цель работы: изучение структуры стека и очереди различной организации и освоение алгоритмов работы с ними; изучение способов представления строк и средств языков программирования (С++, Object Pascal) для реализации операций над строками.
Домашнее задание:
1. Изучить организацию стека линейной и кольцевой структуры, построенного на базе массива, и освоить основные алгоритмы для реализации базовых операций – занесение и извлечение элементов из стека.
2. Освоить организацию очереди линейной и кольцевой структуры (на базе массива) и алгоритмы, позволяющие работать с очередью.
3. Изучить организацию строк различной структуры и средства языка Object Pascal для работы сними.
Порядок выполнения работы
1. Открыть проект Delphi Structures.
2. На главной форме в главное меню добавить пункт «Лабораторная работа №4», при выборе которого должно появляться окно модуля «PolustatStruct». Для этого модуль «PolustatStruct» с формой добавить в проект.
3. Установить на форму модуля «PolustatStruct» компоненты, обеспечивающие ввод исходных данных, вывод смоделированного стека или очереди (в зависимости от варианта задания из таблицы 4.1.) и управляющую кнопку.
4. В обработчике события onClick управляющей кнопки запрограммировать алгоритм, моделирующий работу структуры данных в соответствии с вашим вариантом задания.
5. Отладить приложение и продемонстрировать работу полученной модели данных преподавателю.
6. Составить отчет, в котором алгоритм работы модели данных должен быть отражен в виде блок-схемы, программы и в распечатках формы модуля «PolustatStruct» в двух состояниях: промежуточное состояние модели и после выполнения операции над данными.
Таблица 4.1
| № вар. | Текст задания | ||||||||||||||
| 1. | Смоделировать (т.е. объявить тип структуры и описать библиотеку UNIT1 статических процедур для работы со структурой) линейную очередь как массив из n компонент типа real, в котором элементы очереди занимают группу соседних компонент; индексы первой и последней компоненты запоминаются; когда очередь достигает правого края, все ее элементы сдвигаются к левому краю:
1 2 н-1 н н+1 к к+1
В библиотеку UNIT1 должны войти процедуры: Ochistka (Q) – создать пустую очередь (очистить очередь) PustOch (Q) – выдает истину, если очередь пустая InOchered (Q, x) – добавить элемент в конец очереди OutOchered (Q, x) – удалить из очереди первый элемент, присвоив его параметру x Oshibka (k) – выдает к- номер ошибки, если операция с очередью невыполнима: к=1 – очередь переполнена к=2 – очередь исчерпана Написать вызывающую программу, в которой подключается модуль UNIT1, для демонстрации работы линейной очереди. | ||||||||||||||
| 2. | Смоделировать очередь, описанную в вар.1 и, используя процедуры модуля UNIT1, решить задачу: type FR = file of real; За один просмотр файла f типа FR вывести на экран его элементы в следующем порядке: сначала все числа меньше а, потом все числа из отрезка [а;b], потом - все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (а и b задаются с клавиатуры, а < b). Использовать две очереди: Q1 – для элементов [а; b], Q2 – для остальных. | ||||||||||||||
| 3. | Смоделировать очередь, описанную в вар. 1 и, используя процедуры модуля UNIT1, решить задачу: содержимое текстового файла f , разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (для запоминания цифр организовать линейную очередь), с сохранением исходного взаимного порядка как среди цифр, так и среди остальных символов строки. | ||||||||||||||
| 4. | Смоделировать работу линейного стека - объявить тип структуры и описать статическую библиотеку UNIT2 (процедур и функций для работы с ним). Под стек отвести массив из n компонент типа real, в начале которого располагаются элементы стека, при этом запоминается индекс компоненты массива, занятой последним элементом стека:
В библиотеку UNIT2 должны войти процедуры: Ochistka (S) – создать пустой стек (очистить стек) PustSteck (S) – выдает истину, если стек пуст InSteck (S, x) – добавить элемент x в конец стека S OutSteck (S, x) – удалить из стека S последний элемент, присвоив его параметру x Oshibka (k) – выдает к- номер ошибки, если операция невыполнима: к = 1 – переполнение стека к = 2 – исчерпание стека Написать вызывающую программу, в которой подключается модуль UNIT2, для демонстрации работы линейного стека. | ||||||||||||||
| 5. | Смоделировать линейный стек в соответствии с описанием вар. 4 и, используя процедуры модуля UNIT2, решить задачу: вывести на экран содержимое текстового файла t, выписывая символы каждой его строки в обратном порядке. Передачу символов строки организовать с помощью линейного стека. | ||||||||||||||
| 6. | Организовать кольцевую очередь в виде статического массива:
const n = 50;
var z: array [1..n] of integer; i, j: integer;
{начало и конец очереди}
Записать в очередь 20 псевдослучайных чисел, а затем всякий раз, добавляя в конец новое число (в процедуре InOut), будем исключать из, головы очереди все числа, которые меньше. Здесь возможны 2 исхода: очередь пустеет (одно из новых чисел больше всех) или переполняется (в очереди оказалось такое число, которое не было превзойдено добавляемыми числами).
Замечание: для кольцевой очереди должен быть переход по кольцу на начало, если индекс конца, вышел за границу массива: | ||||||||||||||
| 7. | Реализуйте кольцевой стек на базе статического массива, фиксируя голову стека. Занесите в стек 10 псевдослучайных целых чисел, не превосходящих 100, причем суммируйте их в процессе генерации; затем, выталкивая их из стека, снова просуммируйте и убедитесь в совпадении сумм. Сформировать процедуры занесения элемента в кольцевой стек и выталкивания элемента из стека. | ||||||||||||||
| 8. | Ввести с клавиатуры две неубывающих строки символов – Byte-чисел > 0 и сохранить их в структурах типа Pchar. Слить их в единую структуру типа Pchar, сохранив при этом общий порядок неубывания. | ||||||||||||||
| 9. | Смоделировать стек, описанный в вар. 4. Используя стек, решить задачу: type FC = file of char; Проверить, сбалансировано ли содержимое файла t типа FC относительно круглых скобок. Файл читать один раз, а последовательности позиций скобок сохранять в стеке. При нарушении баланса распечатывать несбалансированную последовательность скобок в виде: пары позиций сбалансированных скобок, затем – номера позиций скобок без пар. Например, для текста: А+(45-F(x)*(B-C))) Вывод: 12 16 8 10 3 17 |
