...
Процедури обробки черг і стеків PDF Печать E-mail

Процедури обробки черг і стеків

Д И Н А М І Ч Н І    С Т Р У К Т У Р И
Д А Н И Х
Структуровані типи даних,  такі, як масиви, множини, записи, являють   собою статичні структури,  тому що їхні розміри незмінні протягом усього часу виконання програми.
Часто потрібно, щоб структури даних змінювали свої розміри в ході рішення задачі.   Такі структури даних називаються динамічними,  до  них відносяться стеки,  черги, списки, дерева й інші.
Опис динамічних структур  за допомогою масивів,  записів і
файлів приводить до нераціонального використання пам'яті ЕОМ і збільшує час рішення задач.
Кожний компонент будь-якої динамічної структури являє  собою запис, що містить   принаймні два полю чи:  одне поле типу вказівник, а  друге - для розміщення даних.  У загальному випадку запис може містити не   один,  а декілька вказівників і кілька полів даних.
Поле даних може бути змінною,  масивом, множиною або записом.
Опис цього компонента дамо в такий спосіб:
type
Pointer = ^Comp;
Comp = record
D:T;
pNext:Pointer
end;
тут T - тип даних.
Розглянемо основні правила  роботи  з  динамічними  структурами даних типу стек, черга.

С Т Е К И
Стеком називається динамічна структура даних, додавання компонента в яку і виключення компонента з  якої відбувається  з одного кінця, який називається вершиною стека. Стік працює за принципом
LIFO (Last-In, First-Out) – останнім прийшов, першим пішов.
Звичайно над стеками виконується три операції:
-початкове формування стеку (запис першого компонента);
-додавання компонента в стек;
-вибірка компонента (вилучення).
Для формування стека і роботи з ним необхідно мати  два  перемінні типу вказівник,  перша з яких визначає вершину стека, а друга - допоміжна. Нехай опис цих перемінних має вигляд:
var pTop, pAux: Pointer;
де pTop - покажчик вершини стека; pAux - допоміжний покажчик. Початкове формування стека виконується наступними операторами:
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC

Останній оператор або група операторів записує вміст поля чи даних першого компонента.   Додавання компонента в стек відбувається з використанням допоміжного вказівника:
Додавання наступних компонентів виробляється аналогічно.
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
Розглянемо процес вибірки компонент зі стека.
sC:=pTop^.sD;
pTop:=pTop^.pNext

Приклад. Скласти програму,  що формує стек, додає в нього довільну кількість компонентів, а потім читає усі компоненти і виводить їх на екран,  як дані взяти рядок символів. Введення даних - з клавіатури , ознака кінця введення – рядок символів END.

Program STACK;
uses Wincrt;
type  Alfa= String[10];
PComp= ^Comp;
Comp= Record
sD: Alfa;
pNext: PComp
end;
var pTop: PComp; sC: Alfa;

Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC
end;

Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
end;
Procedure DelComp(var pTop: PComp; var sC:ALFA);
begin
sC:=pTop^.sD;
pTop:=pTop^.pNext
end;
begin
Clrscr;
writeln('  ВВЕДІТЬ РЯДОК ');
readln(sC);
CreateStack(pTop,sC);
repeat
writeln('  ВВЕДІТЬ РЯДОК ');
readln(sC);
AddComp(pTop,sC)
until sC='END';
writeln('****** РЕЗУЛЬТАТИ ВИКОНАННЯ ******');
repeat
DelComp(pTop,sC);
writeln(sC);
until pTop = NIL
end.

Ч Е Р Г И
Чергою називається динамічна структура даних, додавання компонента в яку здійснюється в кінець, а вибірка здійснюється з іншого кінця. Черга працює за принципом:
FIFO (First-In, First-Out) – першим прийшов – першим пішов.
Для формування черги і роботи з нею необхідно мати три змінні типу вказівник,  перша з яких  вказує на початок  черги, друга – на кінець черги, третя - допоміжна.
Опис компоненти черги і змінних типу вкзівник дамо в такий спосіб:
type
PComp=^Comp;
Comp=record
D:T;
pNext:PComp
end;
var
pBegin, pEnd, pAux: PComp;

де pBegin - вказівник початку черги, pEnd - вказівник кінця  черги, pAux - допоміжний вказівник.
Тип Т визначає тип даних компоненту черги.
Початкове формування черги виконується наступними операторами:
New(pBegin);
pBegin^.pNext:=NIL;
pBegin^.sD:=sC;
pEnd:=pBegin
Додавання компонента в чергу відбувається в кінець черги:
New(pAux);
pAux^.pNext:=NIL;
pEnd^.pNext:=pAux;
pEnd:=pAux;
pEnd^.s:=s
Додавання наступних компонентів  відбувається
аналогічно.
New(pAux);
pAux^.pNext:=NIL;
pEnd^.pNext:=pAux;
pEnd:=pAux;
pEnd^.sD:=sC

Вибірка компонента  з  черги  здійснюється з початку черги, одночасно компонента виключається з черги. 
Вибірка компонента виконується наступними операторами:
sC:=pBegin^.sD;
pBegin:=pBegin^.pNext

 

 

 

 


Приклад. Скласти програму,  що формує чергу, додає в неї довільна кількість компонентів, а потім читає усі компоненти і виводить їх на екран дисплея. Як дані взяти рядок символів. Уведення    даних  - із клавіатури дисплея,  ознака кінця введення - рядок символів END.
Program QUEUE;
uses Wincrt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= record
sD:Alfa;
pNext:PComp
end;
var
pBegin, pEnd: PComp;
sC: Alfa;

Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);
begin
New(pBegin);
pBegin^.pNext:=NIL;
pBegin^.sD:=sC;
pEnd:=pBegin
end;
Procedure AddQueue(var pEnd:PComp; var sC:Alfa);
var pAux: PComp;
begin
New(pAux);
pAux^.pNext:=NIL;
pEnd^.pNext:=pAux;
pEnd:=pAux;
pEnd^.sD:=sC
end;

Procedure DelQueue(var pBegin: PComp; var sC: Alfa);
begin
sC:=pBegin^.sD;
pBegin:=pBegin^.pNext
end;
BEGIN
Clrscr;
writeln(' УВЕДИ РЯДОК ');
readln(sC);
CreateQueue(pBegin,pEnd,sC);
repeat
writeln(' УВЕДИ РЯДОК ');
readln(sC);
AddQueue(pEnd,sC)
until sC='END';
writeln(' ***** ВИСНОВОК РЕЗУЛЬТАТІВ *****');
repeat
DelQueue(pBegin,sC);
writeln(sC);
until pBegin=NIL
end.

 

Яндекс.Метрика >