Організація стека за допомогою списку

Мета роботи: Метою роботи є вивчення логічної структури стеку, важливих операцій доступу до стека, очищення стека та перевірки стека.

 

Завдання

Модифікувати програму таким чином, щоб данi, які зберігаються в стеку, були типу запису (RECORD), складеного з двох полів. Вивід полів запису повинен здійснюватися в один рядок.

Тип даних узгодити з викладачем.

Program siod_1_1; {тип вказівника на елемент стеку}

Uses Crt; {тип елементу стеку}

Type {рядок даних елементу}

spis = "el; {вказiвник на наступний елемент}

el = record

inf: string;

next: spis;

end;

Var

key: char; {символ, введенний з клавіатури за допомогою}

{небуферованого вводу}

tek: spis; {вказiвник вершини стеку}

och: spis; {вказiвник на доданий або виключений елемент стеку}

 

Procedure clear_m(n: integer): {процедура очищення частини экрану}

{n=1 очищується половина екрану ліворуч (стовбці 1-40)}

{n=2 очищується права половина екрану (стовбці 41-80)}

Var

i: integer; {координата курсора по вертикалi}

Begin

n:=(n-1)*39+1; {визначення координати курсора по горизонталi}

for i:=3 to 23 do {цикл очищення частини екрану}

begin

gotoXY(n,i);

wrileln.(' ');

end;

end;

 

Procedure Instek; {процедура додання елементу в стек}

Begin

clear_m(l);

new(och); {утворення елементу}

och^.next:=tek; {додання утвореного елементу в стек}

tek:=och; {встановлення вказiвника вершини стеку на}

{доданий елемент}

gotoxy(l,3);

writeln('Введите новий елемент:');

readln(tek^.inf); {ввод рядка даних елементу}

End;

 

Змiст звіту

6.2.1 Мета роботи.

6.2.2 Блок - схема алгоритму з пояснювальними коментаріями.

6.2.3 Схема фізичної структури стеку.

6.3 Контрольнi запитання

6.3.1 Що називається стеком?

6.3.2 Якi основнi операцiї над стеком?

6.3.3 Що називається вершиною стеку? Як вона адресується?

6.3.4 Як зберігається стек в пам’ятi ЕОМ?

Лабороторна робота №6

Реалізація двунаправленого циклічного списку

Мета роботи: Метою роботи є вивчення основних операцій над списковою структурою - двунаправленим кільцевим списком: включенря нового елементу, виключення елементу, переміщення по списку.

Завдання до лабораторної роботи одержати у викладача.

ЗАВДАННЯ

Program spis_2c;

Uses Crt,Graph;

Const.

Pi=3.1415826535;

Type

el = ^spis; {вказiвник на елемент списку}

spis = record {тип елементу списку}

x,y: integer;{координати центру кола, відповідні елем-ту списку}

inform: string; {рядок даних елементу списку}

{(суть елементу)}

pred: el; вказiвник на попередній елемент списку}

posi: el; {вказiвник на наступний елемент списку}

end;

Var

Driver_Mode: integer; {перемiщення, використані для iнiцiалiзацiї}

{графічного режиму дисплея}

main: el;

numb: integer; {кiлькiсть елементів списку}

key: char;

st: integer; {символ, відповідний натиснутій клавіші}

 

Procedure Beep;

Begin {процедура подачи звукового сигналу}

Sound(1000); {включення звукового сигналу}

delay(128); {затримка}

Nosound; {виключення звукового сигналу}

End;

 

Procedure Clr(xl,yl,x2,y2:integer);

{процедура очищення частини екрану, заданої у вигляді} {прямокутника}

{х1,у1 - координати верхнього кута прямокутника ліворуч}

{х2,у2 - координати правого нижнього кута прямокутника}

Begin

SetFillStyle(0,l);

Ваr(х1,у1,х2,у2);

End;

 

Procedure Setscr; {процедура вивода інструкції по роботі з програмою}

Begin

Cleardevice; {очищення екрана}

OutTextXY(10,10,' ПРОГРАМА РЕАЛІЗУЄ ДВУНАПРАВЛЕНИЙ ЦИКЛІЧНИЙ СПИСОК');

OutTextXY(20,20,'i-додати елемент d-знищити елемент 1-перейти на елемент по ч.с.');

OutTextXY(20,30,' г - перейти на елемент проти ч.с. Enter - ввести суть елемента');

OutTеxtXY(410.60,'Cyть елемента:');

End:

 

Procedure Inp_inf; {процедура ввода сутi елементу}

Begin

ОutТехtХУ(410,120,'Введіть суть елемента:'); {вивод запрошення}

GotoXY(55,17); {позиціонування курсору} readln(main^.inform); {ввод суті елементу} сlr(410.120,640,135); {витирання запрошення і введеної суті}

{елементу}

End;

 

Procedure Out_inf; {процедура виводу суті елементу}

Begin

сlr(410,70,640.80); {підготовка экрану до виводу}

OutTxtXY(410,70,main^. inform); {вивод суті елементу}

End;

 

Procedure Ch_inf; {процедура ввода суті елементу и виводу її на екран}

Begin

inp_uif;

out_mf;

End;

 

Procedure Mal_sp;

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

{Список поданий у вигляді кільця, елементи списку - у вигляді }

{кіл, які лежать на кільці. Поточний елемент позначається }

{символом '*' - міткою поточного елементу}

Var

tek: el; {вказiвник на поточний елемент списку}

st: real; {величина кута між сусідніми колами,}

{якими позначені елементи списку}

i: integer; {керуюча змінна циклу}

Begin

сlr(1,60,400,200);

Circle(150,130,118); {вичерчування кільця}

Circle(150,130,142);

st:=2*Pi/numb;

tek:=maili;{встановлення вказівника tek на поточний елем-т списку}

for i:=l to numb do {цикл вичерчування кола - елементів списку}

begin

tek^.x:=Trunc(130*cos((i-l)*st)+150);

{обчислювання координат по горизонталі та вертикалі}

tek^:y:=Trunc(54*sin((i-l)*st)+130);

Circlc(tclt^.x,tek^.y,10); {вичерчування кола елементу}

tck:=tck^.posl; {перехід до наступного елементу}

end;

OutTextXY(main^.x-3,main^.y-3,'*'); {виведення мітки поточного}

End; {елементу}

 

Procedure Left_right(napr:char); {процедура переміщення за списком}

Begin

SetColor(0); {зтирання мітки поточного елементу}

OutTextXY(main^Jt-3,main^.y-3,'*’);

SеtColor(l);

if napr=T {вибір напрямку руху за списком}

then

main:=main^.posi; {перехід до наступного елементу}

else

main:=main^.pred; {перехід до попереднього елементу} OutTextXY(main^.x-3,main^ -y-3,’*’);

{виведення мітки поточного eлементу}

cild;

 

Procedure Plus_l;

{процедура включення нового елемента між поточним та наступним}

Var

r:el; {вказiвник на наступний елемент списку}

n:el; {вказiвник на новий елемент списку}

Begin

r:=main^.posl; {встановлення вказівника r на наступний елемент} {списку}

new(n); {утворення нового елементу списку}

main^.posl:=n; {формування зв’язку поточного елементу з новим}

n^.pгed:=main;

n^.posi:=r; {формування зв’язку нового елементу з наступним}

r^.pred:=n;

n^.inform:="; {інiцiалiзація рядка даних нового елементу списку}

main:=n.; {призначення включеного елементу списку наступним}

mal_sp; {виведення на екран поточного стану списку}

End;

 

Procedure Minus_l;

{процедура знищення поточного елементу з списка}

Var

l: el; {вказiвник на попередній елемент списку}

r: el; {вказiвник на наступний елемент списку}

Begin

l:=main^.pred; {встановлення вказiвника 1 на попередній елемент}

{списку}

r:=main^.posi; {встановлення вказівника r на наступний елемент}

{списку}

Dispose (main); {знищення поточного елементу}

l^.posl:=r; {формування зв’язку мiж попереднім та наступним}

r^.pred:=l; { елементами списку}

main:=l; {призначення попереднього елемента поточним}

mal_sp; {виведення на екран поточного стану списку}

End;

 

BEGIN

Driver:=Dctect;

Initgraph(Driver_Mode,' '); {ініціалізація графічного режиму}

{роботи екрану}

setscr;

numb:=l; {похідна кiлькiсть елементів списка}

new(main); {утворення першого елементу списка}

main^.posl:=main; {утворення циклічного списку}

main^.pred:=main;

main^.inform:=' '; {iнiцiалiзацiя рядка даних елементу}

mal_sp; {виведення поточного стану списку}

key:=' ':

while kеy<>chr(27) do {цикл обробки натиснутої клавіші, вихід}

begin {з циклу при натисненні клавіші <КЛЮЧ>}

out_inf;

while not KeyPressed do {очікування натиснення клавіші}

key:=ReadKey;

if key=chr(0) then {ввод символа, відповідного}

begin

key:=ReadKey; {натиснутій клавіші}

case key of {вибір виду обробки}

'r': left_right('r'); {переміщення за списком проти г.с.}

‘l': left_right(T); {переміщення за списком за г.с.}

#13: ch_inf; {ввод суті елементу}

'd': if numb<>l {перевірка кількості елементів}

then

begin {якщо кiлькiсть елементів більше 1,то}

numb:=numb-l;

{зменшення кількості елементів на 1}

minus^l; {усування поточного елементу}

end

else {якщо список складається з 1 елементу, то}

beep;

{подання звукового сигналу про помилку}

'i': begin {додаток елементу}

numb:=numb+l;

{збiльшення кількості елементiв на 1}

plus_l; {включенння нового елементу}

end;

#27:;

else

beep; {подання звукового сигналу у випадку}

end; {натиснення невикористаної клавіші}

end;

CloseGraph: {знищення графічного режиму роботи экрану}

End.

 

Змiст звіту

 

7.2.1 Мета роботи.

7.2.2 Блок-схема алгоритму з коментаріями

7.2.3 Схема фізичної структури двунаправленого кільцевого

списку.

 

7.3 КонтрольнІ запитання

 

7.3.1 Що називається списком?

7.3.2 Що називається двунаправленим кільцевим списком?

7.3.3 Як включається новий елемент до списку?

7.3.4 Як виключається елемент зі списку?

 

ЛАБОРАТОРНА РОБОТА №7

Застосування бiнарних дерев

Мета роботи: метою роботи є вивчення методiв знаходження одного рiшення з двох можливих із застосуванням бiнарних дерев.

ЗАВДАННЯ

8.1.1 Вивчити операції над бінарними деревами.

8.1.2 Розробить програму знаходження усiх дублiкатiв у списку чисел.

8.1.3 Розробить програму знаходження бiнарних дерев.

8.1.4 Pозробить програму подання виразу, утримуючого операнди та бінарні оператори у виді строго бiнарного дерева.

Варіанти завдання отримати у викладача.