Динамические структуры данных: стек, дек, очередь

Цель лабораторной работы: изучение способов создания и принципов использования динамических структур данных типа стек, дек, очередь; изучение стандартных средств языка Турбо Паскаль для работы с динамической памятью; совершенствование навыков модульного программирования на языке Турбо Паскаль при решении задач обработки динамических структур данных.

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

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

1) Получить у преподавателя индивидуальное задание.

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

3) Построить схему алгоритма решения задачи.

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

- допустимые операции для стека: инициализация, проверка на пустоту, добавление нового элемента в начало, извлечение элемента из начала;

- допустимые операции для очереди: инициализация, проверка на пустоту, добавление нового элемента в конец, извлечение элемента из начала;

- допустимые операции для дека: инициализация, проверка на пустоту, добавление нового элемента в начало, добавление нового элемента в конец, извлечение элемента из начала, извлечение элемента из конца.

5) Составить спецификации используемых подпрограмм.

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

7) Использовать оконный интерфейс предыдущих лабораторных работ.

8) Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ в окнах на экране содержимого входного и выходного файлов.

9) Оформить отчет о лабораторной работе в составе: постановка задачи, математическая модель, схема алгоритма решения, спецификация подпрограмм, текст программы, контрольные примеры.

Варианты индивидуальных заданий

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

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

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

Написать программу, моделирующую железнодорожный сортировочный узел. Исходный файл содержит информацию об имеющихся вагонах двух типов, при этом количество вагонов обоих типов одинаково. Последовательность элементов файла неупорядочена, в каждом элементе файла: тип вагона и идентификационный номер вагона. Используя стек (“тупик”), за один просмотр исходного файла сформировать новый файл (“состав вагонов”), в котором типы вагонов чередуются.

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

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

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

для промежуточного хранения можно использовать стержень В.

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

Дан файл из вещественных чисел. Используя очередь, за один просмотр файла напечатать сначала все числа, меньшие a, затем все числа из интервала [a,b], и, наконец, все остальные числа, сохраняя исходный порядок в каждой группе.

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

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

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

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

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

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

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

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

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

< ЛВ > ::= T | F | (N<ЛВ>) | (<ЛВ>A<ЛВ>) | (<ЛВ>X<ЛВ>) | (<ЛВ>O<ЛВ>),

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

T – True, F – False, N – Not, A – And, X – Xor, O – Or.

Дан текстовый файл. В текстовом файле записана формула следующего вида:

<Формула> ::= <Цифра> | M(<Формула>,<Формула>) | N(Формула>,<Формула>)

< Цифра > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

где буквами обозначены функции:

M – определение максимума, N – определение минимума.

Используя стек, вычислить значение заданного выражения.

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

< Формула > ::= < Терм > | < Терм > + < Формула > | < Терм > - < Формула >

< Терм > ::= < Имя > | (< Формула >)

< Имя > ::= x | y | z

В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, вычислить значение выражения.

Пример выражения: 2 3 5 + * 7 6 - * => 16

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

Пример выражения: a + b / c / d * e => a b c / d / e * +

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

Пример выражения: a b + c * d – f * => ((a + b) * c – d) * f

Пример программы

{Дан текстовый файл, содержащий числа, разделённые пробелами.

Используя стек, реализовать программу быстрой сортировки.

Используется модуль M_Stek}

Program QSortStek;

Uses Crt, M_Stek;

{Рисование окна на экране}

Procedure Dialog(x1,y1,x2,y2,bkcl,cl:Byte;title:String);

Var i:Byte;

Begin

Window(x1,y1,x2,y2);

TextBackGround(bkcl);

TextColor(cl);

ClrScr;

GoToXY((x2-x1) Div 2 - Length(title) Div 2,1);

Write(title);

Window(x1,y1+1,x2,y2);

End;

{Проверка существования файла с таким именем}

Procedure Exist(Var fname:String);

Var

ch:Char;

fisx:Text;

Begin

Assign(fisx,fname);

{$I-} {Отключение контроля ошибок ввода-вывода}

Reset(fisx);

{$I+} {Включение контроля ошибок ввода-вывода}

If IOResult=0

Then Begin

WriteLn(' Такой файл уже существует!');

Write(' Хотите его уничтожить? Y/N ->');

ReadLn(ch);

If ch In ['n','N','т','Т']

Then Repeat

WriteLn(' Введите другое имя:');

ReadLn(fname);

Assign(fisx,fname);

{$I-}

Reset(fisx);

{$I+}

If IOResult=0

Then Begin

WriteLn(' Такой файл уже существует!');

Write(' Хотите его уничтожить? Y/N ->');

ReadLn(ch);

End;

Until (IOResult<>0)Or(ch In['y','Y','н','Н']);

End;

End;

{Создание текстового файла}

Procedure Make(fname:String);

Var

fisx:Text;

i:Byte;

st:String;

Begin

Assign(fisx,fname);

ReWrite(fisx);

WriteLn(' Начинаем ввод.');

WriteLn(' Признак окончания ввода-пустая строка.');

i:=0;

WriteLn(' Введите ',i+1,'-ую строку файла:');

ReadLn(st);

While st<>''

DO Begin

WriteLn(fisx,st);

Inc(i);

WriteLn(' Введите ',i+1,'-ую строку файла:');

ReadLn(st);

End;

WriteLn(' Введено ',i,' строк');

Close(fisx);

End;

{Заполнение исходного массива из файла}

Procedure SozdMas(Const fname:String;Var mas:TMas;n:TInd);

Var

fisx:Text;

ch:TElem;

i:TInd;

Begin

Assign(fisx,fname);

ReSet(fisx);

i:=1;

While (Not Eof(fisx))AND(i<=n)

DO Begin

Read(fisx,ch);

mas[i]:=ch;

i:=i+1;

End;

Close(fisx);

End;

{Сортировка массива по возрастанию методом быстрой сортировки}

Procedure QuickSort(Var mas:TMas;n:TInd);

Var

i,j,l,r:TInd;

middle,

temp:TElem;

top:TRef;

Begin

InitSt(top);

VStek(top,1,n);

While top<>NIL

Do Begin

IzSteka(top,l,r);

While l<r

Do Begin

i:=l; j:=r;

middle:=mas[(l+r)Div 2];

While i<j

Do Begin

While mas[i]<middle Do i:=i+1;

While middle<mas[j] Do j:=j-1;

If i<=j

Then Begin

temp:=mas[i];

mas[i]:=mas[j];

mas[j]:=temp;

i:=i+1; j:=j-1;

End;

End;

If i<r

Then VStek(top,i,r);

r:=j;

End;

End;

End;

{Вывод отсортированного массива}

Procedure Vivod(Const mas:TMas;n:TInd);

Var

i:TInd;

Begin

For i:=1 To n

Do Write(mas[i]:3);

WriteLn;

Write(' Для продолжения нажмите <Enter>');

ReadLn;

End;

{Основная программа}

Var

fname:String;

mas:TMas;

n:TInd;

Begin

TextBackGround(1);

ClrScr;

Dialog(42,1,80,25,13,10,'Результат:');

Dialog(1,17,40,25,2,15,'Описание задачи:');

WriteLn(' Дан текстовый файл с числами,');

WriteLn(' разделёнными пробелами.');

WriteLn(' Отсортировать числа, используя метод');

WriteLn(' быстрой сортировки и модуль работы');

Write(' со стеком.');

Dialog(1,1,40,16,14,10,'Ввод:');

WriteLn(' Создание исходного файла.');

WriteLn(' Введите имя исходного файла');

ReadLn(fname);

Exist(fname);

Make(fname);

Write(' Введите размер массива ->');

ReadLn(n);

SozdMas(fname,mas,n);

Dialog(42,1,80,25,13,10,'Результат:');

WriteLn(' Исходный массив:');

Vivod(mas,n);

WriteLn;

QuickSort(mas,n);

WriteLn(' Отсортированный массив:');

Vivod(mas,n);

End.

===============================================================

Unit M_Stek;

Interface

Const

R=100;

Type

TInd=1..R;

TElem=Integer;

TRef=^TStek;

TStek=Record

l,r:TInd;

sled:TRef;

End;

TMas=Array[TInd] Of TElem;

Procedure InitSt(Var head:TRef); {инициализация стека}

Function PuStek(head:TRef):Boolean; {проверка на пустоту}

Procedure VStek(Var head:TRef;Const l,r:TInd); {занесение в стек}

Procedure IzSteka(Var head:TRef;Var l,r:TInd); {извлечение из стека}

Implementation

{Процедура инициализации стека}

Procedure InitSt(Var head:TRef);

Begin

head:=NIL;

End;

{Проверка стека на пустоту}

Function PuStek(head:TRef):Boolean;

Begin

PuStek:=head=NIL;

End;

{Процедура занесения нового элемента в стек}

Procedure VStek(Var head:TRef;Const l,r:TInd);

Var

tec:TRef;

Begin

New(tec);

tec^.l:=l;

tec^.r:=r;

tec^.sled:=head;

head:=tec;

End;

{Процедура извлечения элемента из стека}

Procedure IzSteka(Var head:TRef;Var l,r:TInd);

Var

tec:TRef;

Begin

tec:=head;

l:=head^.l;

r:=head^.r;

head:=head^.sled;

Dispose(tec);

End;

End.