double arrow

Полустатические структуры данных

Цель работы: изучение структуры стека и очереди различной организации и освоение алгоритмов работы с ними; изучение способов представления строк и средств языков программирования (С++, 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 ... Эm     ...

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, в начале которого располагаются элементы стека, при этом запоминается индекс компоненты массива, занятой последним элементом стека:

Э1 Э2 ... Эк   ...
      к к+1  
к  

В библиотеку 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

Контрольные вопросы

1. Принципы работы структуры данных – очереди.

2. Алгоритмы основных операций для работы с линейной очередью.

3. Что такое кольцевая очередь? Сколько параметров очереди необходимо фиксировать для работы с ней?

4. Для какой структуры данных должен быть реализован принцип LIFO (last in, first out)?

5. Что такое дек, ограниченный дек?

6. Организация строк какой структуры реализована средствами Object Pascal?



Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: