Полустатические структуры данных
Цель работы: изучение структуры стека и очереди различной организации и освоение алгоритмов работы с ними; изучение способов представления строк и средств языков программирования (С++, 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 |
Контрольные вопросы
1. Принципы работы структуры данных – очереди.
2. Алгоритмы основных операций для работы с линейной очередью.
3. Что такое кольцевая очередь? Сколько параметров очереди необходимо фиксировать для работы с ней?
4. Для какой структуры данных должен быть реализован принцип LIFO (last in, first out)?
5. Что такое дек, ограниченный дек?
6. Организация строк какой структуры реализована средствами Object Pascal?
Лабораторная работа № 5
(4 часа)
Динамические структуры данных - односвязные и двусвязные списковые структуры
Цель работы:
Изучение организации списковых структур и построение реальных структур данных на базе списков.
Домашнее задание:
1. Освоить организацию адресного типа (указатели) в Object Pascal и построение динамического списка.
2. Изучить алгоритмы. Позволяющие работать со списковыми структурами различной организации:
а) линейный и кольцевой стек;
б) линейная и кольцевая очередь;
в) дек.
Порядок выполнения работы
1. Открыть проект Delphi Stuctures.
2. На главной форме в главное меню проекта добавить пункт «Лабораторная работа №5», при выборе которого должно появляться окно модуля «DinamicStuct». Для этого модуль DinamicStuct с формой добавить в проект.
3. Установить на форму модуля DinamicStuct компоненты, обеспечивающие ввод исходных данных и вывод результатов работы программы в соответствии с вашим вариантом задания (табл. 5.1), а также управляющую кнопку для запуска программного кода при нажатии на кнопку (событие onClic) в работающей программе. Для ввода и вывода в этих задачах использовать компоненты класса Tmemo.
4. В обработчике события onClic управляющей кнопки написать программный код, моделирующий работу структуры данных динамического характера, соответствующей заданию вашего варианта.
5. отладить приложение на тестовых примерах и продемонстрировать работу смоделированной структуры данных преподавателю.
6. Составить отчет о выполненной лабораторной работе, в который должны войти:
а) задание, в соответствии с вариантом;
б) блок-схема решения задачи;
в) программа решения задачи;
г) распечатка формы с демонстрацией работы смоделированной структуры данных.
7. Защитить работу преподавателю.
Таблица 5.1
| № вар. | Содержание задания | |||
| 1. | Организовать программно линейный односвязный список следующей структуры:
Опишите в программе запись, в поле bukv которой заносится буква. Порождая записи, поместить их в стек, а затем «вытолкнуть» их из списка, получив буквы в порядке, обратном исходному. Проверьте работу примера для исходного набора букв: const A: array [1 .. 9] of char =(‘A’, ’P’, ‘Y’, ‘T’, ‘K’, ‘Y’, ’P’, ‘T’, ‘C’).
| |||
| 2. | С помощью стека, организованного в соответствии со структурой вар. 1 организовать получение палиндрома, в котором вторая половина является зеркальным отражение первой без последнего символа. Первую половину вводить с клавиатуры. Например:
| |||
| 3. | Программно организазать очередь в виде однонаправленого списка из элементов типа rec:
Type ptr =^ rec;
rec = record
key : integer;
s : ptr;
end;
var t : rec;
Заполняются ссылки на первое ипоследнее звенья списка.
Во входном файле задана последовательность из равного количества положительных и отрицательных целых чисел, за которой следует нуль. Ввести эти числа и вывести их, чередуя положитедльные числа (на нечетных местах) с отрицательными ( на четных), причем исходный взаимный порядок как среди положительных, так и среди отрицательных чисел должен быть сохранен. | |||
| 4. | Многочлен
P(х) = anxn + an-1xn-1 +… + a1x + a0
с целыми коэффициентами можно представить в виде списка, элементы которого расположены по убыванию степеней одночленов:
Описать на Object Pascal тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками-многочленами:
а) логическую функцию Equal(p,q), проверяющую на равенство многочлены p и q;
б) функцию Value(p,x), вычисляющую значение p в точке x;
в) процедуру Dif(p,q), которая строит многочлен p-производную многочлена q;
г) процедуру Addit(p,q,r), которая строит многочлен p-сумму многочленов q и r.
| |||
| 5. | Кольцевым списком называется однонаправленный список, в последнем звене которого вместо Nil указывается ссылка на первое звено:
Пусть L - кольцевой список с элементами типа Type prt =^ rec rec = record; key : integer; s : ptr; end; а E - величина типа rec.
Описать и отладить: а) процедуру, которая строит кольцевой список L и выводит в компонент класса TstringGrid таблицу: t1 t2 … tn-1 tn t2 t3 … tn t1 t3 t4 … t1 t2 -- - - - - - - - - - tn t1 … tn-2 tn-1
б) процедуру, которая строит кольцевой список L и функцию, которая удаляет из непустого списка L последний элемент. в) процедуру, которая строит кольцевой список L и функцию, которая добавляет в конец списка L новый элемент. |
Контрольные вопросы
1 Определения типизированного и обобщенного указателя.
2 Что такое линейный цепной список, и алгоритмы основных операций при работе с ним.
3 Принцип работы кольцевого списка.
4 Организация стека на базе линейного и кольцевого списка.
5 Организация очереди на базе линейного и кольцевого списка.
Лабораторная работа № 6
(8 часов)