Среда программирования Turbo Pascal 7.1

Размещено на http://www.allbest.ru/

Постановка задачи

стек елемент вершина содержимое заполнение

Реализовать хранилище стеков, с операциями добавления, поиска, удаления стеков, а так же со всеми стандартными операциями внутри отдельного стека. Среда программирования Turbo Pascal 7. 1.

Ход решения

1. Реализовать стек в ООП со всеми стандартными операциями: добавление элемента, взятие вершины, проверки на пустоту и заполнение, вывод содержимого стека на экран.

2. Реализовать список, в каждом узле которого содержится стек.

3. В основной программе реализовать меню, для удобства работы.

Стек

Структура данных - это множество элементов данных и связей между ними. Они разделяются на статические и динамические. Статические формируются в памяти одномоментно до начала работы со структурами и во время своего существования не меняют свои размеры и место положения в памяти. Примерами являются массивы и записи. Динамические структуры данных могут менять свои размеры и расположение, их состав может постоянно меняться в ходе работы с программой. Они в свою очередь делятся на линейные (списки, стеки, очереди) и нелинейные (деревья, графы). В линейных структурах элементы идут один за другим, в нелинейных - возможно ветвление.

Рассмотрим подробнее линейные структуры данных, а именно списки. Списки бывают односвязными, двусвязными, циклическими. В каждом элементе односвязного списка содержится указатель на следующий элемент, двусвязного - на следующий и предыдущий, в циклическом последний элемент содержит указатель на первый.

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

Стек - это дисциплина обработки данных, имеющая линейную структуру, доступ в которой разрешается только к последнему добавленному элементу (вершине стека). Стек работает по принципу LIFO (Last In, First Out. Последний вошёл, первый вышел). Простым примером использования стека может послужить ситуация, когда мы просматриваем множество данных и составляем список особых данных, которые должны обрабатываться позднее. Когда первоначальное множество обработано, мы возвращаемся к этому списку и выполняем обработку, удаляя элементы, пока наш список не станет пустым. Например, рекурсивные функции, пока не обработан последний вызов, все предыдущие вызовы находятся в своеобразном стеке. Стек активно используется в архитектуре компьютера, в ней преобладает стековая адресация.

Рассмотрим основные функции обработки стека:

Push - добавление в вершину стека, в процедуру передаётся добавляемое значение.

Pop - взятие элемента из вершины стека, возвращает содержимое вершины

IsEmpty - проверка на пустоту, возвращает True или False.

IsFull - проверка на заполнение, максимальное число элементов в стеке определяет константа MaxStack, возвращает True или False.

Top - указатель на вершину стека

Рассмотрим структуру узла стека:

type

pStackEl = ^StackEl;

data = Integer;

StackEl = record

Value: data;

Prev: pStackEl;

End;

Value - значение узла стека (data = Integer; указывает, что стек числовой)

Prev - указатель на предыдущий элемент.

Для реализации хранилища стеков использован односвязный список с указателем на начало и конец. Рассмотрим узел списка:

type

pNode = ^listEl;

ListEl = record

Name: string;

Stack: StackOfData;

Next: pNode;

End;

Name - имя стека

Stack - непосредственно стек, описанный как объект в модуле UStack.

Next - указатель на следующий элемент списка.

Рассмотрим функции обработки данного списка:

AddNode - добавление узла, в процедуру передаётся имя нового стека.

DelNode - удаление узла, в процедуру передаётся указатель на удаляемый узел

Find - поиск стека, возвращает указатель на узел

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

Процедура ChangeStack вызывает соответствующие процедуры обработки стека из модуля со стеком, посредством активного меню:

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

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

Остальные функции обработки стеков и списка реализованы по стандартным алгоритмам.

Как работать с программой

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

Далее, чтобы добавить элементы в новый стек выбираем опцию CHANGE STACK:

Выбираем нужный стек и вносим изменения, как описано выше:

Наш стек пока ещё пуст, добавляем в него элементы опцией PUSH. Необходимо вводить число:

Удаление из стека осуществляет опция DELETE STACK:

Чтобы завершить работу с программой выбираем EXIT.

Программа написана в Turbo Pascal 7. 1, чтобы подключить модули, нужно скопировать файлы UList. TPU и UStack. TPU в директорию компилятора BIN\.

Код программы

Модуль «Стек»

Unit UStack;

Interface

Const

MaxStack = 7;

type

pStackEl = ^StackEl;

data = Integer;

StackEl = record

Value: data;

Prev: pStackEl;

End;

StackOfData = object

public

procedure Create;

function IsEmpty: boolean;

function IsFull: boolean;

procedure Push (val: data) ;

function Pop: data;

procedure Print;

private

Top: pStackEl;

End;

Implementation

Var

i: Integer;

stack1: stackOfData;

{///////////////////////////////////////////////}

procedure StackOfData. Create;

Begin

Top: =Nil;

End;

{///////////////////////////////////////////////}

function StackOfData. IsEmpty: boolean;

Begin

If Top = Nil Then

IsEmpty: =True

Else

IsEmpty: =False;

End;

{///////////////////////////////////////////////}

function StackOfData. IsFull: boolean;

Var

count: Integer;

PSE: PstackEl;

Begin

PSE: =Top;

count: =0;

While PSE<>Nil Do

Begin

count: =count+1;

PSE: =PSE^. Prev;

End;

If count>=MaxStack Then

IsFull: =True

Else

IsFull: =False;

End;

{///////////////////////////////////////////////}

procedure StackOfData. Push (val: data) ;

Var

NewStackEl: pStackEl;

Begin

New (NewStackEl) ;

NewStackEl^. value: =val;

NewStackEl^. prev: =Top;

Top: =NewStackEl;

End;

{///////////////////////////////////////////////}

function StackOfData. Pop: data;

Var

PSE: pStackEl;

Begin

Pop: =Top^. value;

PSE: =Top;

Top: =Top^. prev;

Dispose (PSE) ;

End;

{////////////////////////////////////////////}

procedure StackOfData. Print;

Var

PSE: PstackEl;

Begin

PSE: =Top;

While PSE<>Nil Do

Begin

Write (PSE^. Value, ' ') ;

PSE: =PSE^. Prev;

End;

End;

{///////////////////////////////////////////////}

Begin

End.

Модуль «Список стеков»

Unit UList;

Interface

Uses UStack, crt;

type

pNode = ^listEl;

ListEl = record

Name: string;

Stack: StackOfData;

Next: pNode;

End;

ListOfStack = object

public

procedure Create;

procedure AddNode (klox: string) ;

procedure DelNode (var delEl: pNode) ;

function Find: pNode;

procedure ChangeStack (var ple: pNode) ;

private

head: pNode;

tail: pNode;

End;

Implementation

{////////////////////////////////////////////}

procedure ListOfStack. Create;

Begin

head: =Nil;

tail: =Nil;

End;

{////////////////////////////////////////////}

procedure ListOfStack. AddNode (klox: string) ;

var

NewNode: pNode;

Begin

If head<>Nil Then

Begin

New (NewNode) ;

NewNode^. name: =klox;

NewNode^. Stack. Create;

NewNode^. next: =Nil;

tail^. next: =NewNode;

tail: =NewNode;

End

Else

Begin

New (head) ;

head^. name: =klox;

head^. Stack. Create;

Head^. next: =Nil;

tail: =head; ;

End;

End;

{////////////////////////////////////////////}

procedure ListOfStack. DelNode (var delEl: pNode) ;

var

ple: pNode;

Begin

If delEl<>Nil Then

Begin

If delEl=head Then

Begin

head: =head^. next;

Dispose (delEl) ;

End

Else

Begin

ple: =head;

While ((ple^. next<>delEl) and (ple <> Nil)) Do ple: =ple^. next;

If delEl=tail Then tail: =ple;

ple^. next: =delEl^. next;

Dispose (delEl) ;

End;

End;

End;

{////////////////////////////////////////////}

function ListOfStack. Find: pNode;

Var

ple: pNode;

c: char;

count, m: Integer;

Begin

ple: =head;

count: =0;

m: =0;

writeln ('->BACK') ;

While ple<>Nil Do

Begin

writeln (' ', ple^. name) ;

ple: =ple^. next;

count: =count+1;

End;

writeln;

repeat

c: = readkey;

if ((c=#72) and (m>0)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m-1;

GoToXY (1, m+1) ;

write ('->') ;

End;

if ((c=#80) and (m<count)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m+1;

GoToXY (1, m+1) ;

Write ('->') ;

End;

until c=#13;

If m = 0 Then

Find: =Nil

Else

Begin

ple: =head;

While m>1 Do

Begin

ple: =ple^. next;

m: =m-1;

End;

Find: =ple;

End;

clrscr;

End;

{////////////////////////////////////////////}

procedure ListOfStack. ChangeStack (var ple: pNode) ;

var

m: Integer;

c: char;

val: data;

Begin

If ple<>Nil Then

Begin

m: =1;

While m<>0 Do

Begin

clrscr;

Writeln ('->BACK') ;

Writeln (' Push') ;

Writeln (' Pop') ;

Writeln (' Print') ;

m: =0;

repeat

c: = readkey;

if ((c=#72) and (m>0)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m-1;

GoToXY (1, m+1) ;

write ('->') ;

End;

if ((c=#80) and (m<3)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m+1;

GoToXY (1, m+1) ;

Write ('->') ;

End;

until c=#13;

clrscr;

If m=1 Then

Begin

If Not ple^. Stack. IsFull Then

Begin

write ('Please enter value: ') ;

readln (Val) ;

ple^. Stack. Push (val) ;

End

Else

Begin

Writeln ('Stack is full! ') ;

readln;

End;

End;

If m = 2 Then

If Not ple^. Stack. IsEmpty Then

Begin

Writeln (ple^. Stack. Pop) ;

readln;

End

Else

Begin

write ('Stack is empty! ') ;

readln;

End;

If m = 3 Then

Begin

ple^. Stack. Print;

readln;

End;

End;

End;

End;

{////////////////////////////////////////////}

Begin

End.

Главное меню

Program Multistack;

Uses UList, crt;

var

i, m: Integer;

c: char;

klox: string;

Node: pNode;

List: ListOfStack;

Begin

clrscr;

List. Create;

m: =1;

While m<>0 Do

Begin

clrscr;

Writeln ('->EXIT') ;

Writeln (' ADD STACK') ;

Writeln (' DELETE STACK') ;

Writeln (' CHANGE STACK') ;

Writeln (' INFORMATION') ;

m: =0;

repeat

c: = readkey;

if ((c=#72) and (m>0)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m-1;

GoToXY (1, m+1) ;

write ('->') ;

End;

if ((c=#80) and (m<4)) Then

Begin

GoToXY (1, m+1) ;

write (' ') ;

m: =m+1;

GoToXY (1, m+1) ;

Write ('->') ;

End;

until c=#13;

clrscr;

Case m Of

1:

Begin

Writeln ('Please enter name: ') ;

readln (klox) ;

List. AddNode (klox) ;

writeln ('Stack is added! ') ;

readln;

End;

2:

Begin

clrscr;

Node: =List. Find;

List. DelNode (Node) ;

End;

3:

Begin

Node: =List. Find;

If Node<>Nil Then

List. ChangeStack (Node) ;

End;

4:

Begin

Writeln ('MultiStack') ;

Writeln ('Chelyabinsk State University') ;

Writeln ('Faculty of Mathematics') ;

Writeln ('Orynbaev Ruslan') ;

Writeln ('MP-101') ;

Writeln ('2010') ;

readln;

End;

End;

End;

End.

Заключение

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

Размещено на Allbest.ru

...