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

Цель работы:  изучение структуры стека и очереди различной организации и освоение алгоритмов работы с ними; изучение способов представления строк и средств языков программирования (С++, Object Pascal) для реализации операций над строками.

Домашнее задание:

1. Изучить организацию стека линейной и кольцевой структуры, построенного на базе массива, и освоить основные алгоритмы для реализации базовых операций – занесение и извлечение элементов из стека.

2. Освоить организацию очереди линейной и кольцевой структуры (на базе массива) и алгоритмы, позволяющие работать с очередью.

3. Изучить организацию строк различной структуры и средства языка Object Pascal для работы сними.

Теоретические сведения:

Реализация стека на массивах

Стек — важная структура данных в программировании. Он предназначен для временного хранения данных, которые извлекаются из стека в порядке, обратном их добавлению.

Стек широко используется в программировании:

для хранения адресов возврата в программу из подпрограмм или из процедур обработки прерываний

для передачи параметров в процедуры (функции)

для размещения локальных параметров процедур и функций

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

Язык Pascal не имеет типа данных стек, поэтому для его моделирования наиболее подходящими структурами являются:

массивы (статический стек)

указатели (динамический стек).

Операции с массивами выполняются значительно быстрее, нежели переход по указателям, поэтому в этой статье рассматривается реализация стека на массивах. Используемый язык программирования – Pascal

 Определение стека

Стек (stack(англ.) - стопка) –упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека (top).

Стек функционирует по принципу LIFO(Last - In - First- Out ) - "последним пришел - первым исключается".

Понятие стека в 1946 ввел Алан Тьюринг.

 При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес (top), от которого производятся все операции со стеком. Эта переменная будет определять индекс элемента , который в данный момент времени находится в вершине стека. В случае, когда стек пуст (top=0), адреса вершины и основания стека совпадают.

Операции со стеком

Основные операции со стеком:

запись элемента в стек (push– «вталкивание»);

извлечение элемента из стека (pop– «выталкивание»);

проверка наличия элементов в стеке (empty- «стек пустой» или full- «переполнение стека»).

Рассмотрим, как реализовать стек на базе массива. Будем считать, что для реализации стека используется массив статического типа. Тип компонент и размерность массива зависят от конкретной задачи.

Некоторые трудности при этом возникают в силу того, что число элементов стека не известно, а число элементов массива ограничено. Поэтому при объявлении размерности массива надо указать предполагаемый максимальный размер стека. Например, если мы уверены, что число элементов в стеке не превысит 100, то надо использовать массив из 100 элементов. 2

const size=100;

var a:array[0..size]of integer;

i,x,n,top:integer;

Операции «вытолкнуть» popи «втолкнуть» pushбудут выглядеть следующим образом:

procedure pop( var x:integer);

begin top:=top+1;

x:=a[top];

end;

procedure push(x:integer);

begin a[top]:=x;

top:=top-1;

end;

Если начальное состояние элементов массива должно быть равно нулю, то для этого можно использовать процедуру инициализации init

procedure init;

var i:integer;

begin for i:=0 to size do a[i]:=0;

top:=size;

end;

Для проверки пустоты(empty)или переполнения (full)стека достаточно написать следующие функции:

function empty:boolean;

begin if top=size then empty:=true else empty:=false;end;

function full:boolean;

begin if top=0 then full:=true else full:=false;end;

Для того, чтобы узнать размер заполненного стека, можно воспользоваться функцией sizestack:

function sizestack:integer;

begin sizestack:=size-top; end;

Теоретически возможна и другая реализация стека через массив, когда вершина стека зафиксирована внизу. Как тогда изменятся процедуры popи push?

При программировании очереди на базе массива- операции аналогичного характера , но: очередь имеет две точки доступа : для добавления элемента в конец и извлечения элемента из начала, т.к. очередь работает в соответствии с дисциплиной FIFO – первым пришел, первым вышел( подобно очереди в магазине).

Порядок выполнения работы

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 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 18

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

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

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

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

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

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

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

Лабораторная работа № 5

(4 часа)

Динамические структуры данных - односвязные и двусвязные списковые структуры

Цель работы:

Изучение организации списковых структур и построение реальных структур данных на базе списков.

Домашнее задание:

1. Освоить организацию адресного типа (указатели) в Object Pascal и построение динамического списка.

2. Изучить алгоритмы, позволяющие работать со динамическими списками различной организации:

а) линейный и кольцевой стек;

б) линейная и кольцевая очередь;

в) дек.

Теоретические сведения

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

Односвязный список

Односвязным списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. На самый первый элемент (голову списка) имеется отдельный указатель.

Из определения следует, что каждый элемент списка содержит поле данных (оно может иметь сложную структуру) и поле ссылки на следующий элемент. После ссылки последнего элемента должно содержать пустой указатель (nil).

Число элементов связанного списка может расти или уменьшаться в зависимости от того, сколько данных мы хотим хранить в нем. Чтобы добавить новый элемент в список, необходимо:

1. Выделить фрагмент динамической памяти для него;

2. Поместить туда информацию;

3. Добавить элемент в конец списка (или начало).

Элемент списка состоит из разнотипных частей (хранимая информация и указатель), и его ,естественно, представить записью. Перед описанием самой записи описывают указатель на нее:

Создание списка.

Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Определим запись типа TList с полями, содержащими характеристики данных – значения очередного элемента и адреса следующего за ним элемента

Создадим первый элемент: New(Head); { выделяем место в памяти для переменной Head } Head^.Next := nil; { указатель на следующий элемент пуст (такого элемента нет) } Head^.Data := 3; { заполняем информационное поле первого элемента }

Продолжим формирование списка, для этого нужно добавить элемент в конец списка.

Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка: x := Head; {сейчас последний элемент списка совпадает с его началом}

New(x^.Next); { выделим области памяти для следующего (2-го) элемента и поместим его адрес в адресную часть предыдущего (1-го) элемента }

x := x^.Next ; { переменная x принимает значение адреса выделенной области. Таким образом осуществляется переход к следующему (2-ому) элементу списка }

x^.Data := 5; { значение этого элемента } x^.Next := nil; {следующего значения нет }

Остальные числа заносятся аналогично: New(x^.Next); { выделим области памяти для следующего элемента } x := x^.Next ; { переход к следующему (3-му) элементу списка } x^.Data := 1; { значение этого элемента } x^.Next := nil; {следующего значения нет } New(x^.Next); { выделим области памяти для следующего элемента } x := x^.Next ; { переход к следующему (4-му) элементу списка } x^.Data := 9; { значение этого элемента } x^.Next := nil; {следующего значения нет }

Замечание. Как видно из примера, отличным является только создание первого (Head) элемента – головы списка. Все остальные действия полностью аналогичны и их естественно выполнять в цикле.

Присоединение нового элемента к голове списка производится аналогично: ……………….. New(x); { ввод значения элемента x^.Data := … } x^.Next := Head; Head := x; ………………..

В этом случае последний введенный элемент окажется в списке первым, а первый – последним.

Просмотр списка.

Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель List последовательно ссылается на первый, второй и т. д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется некоторая операция– например, печать элемента. Начальное значение List – адрес первого элемента списка (Head).