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('****** ВЫВОД РЕЗУЛbТАТОВ ******');
repeat
DelComp(pTop, sC);
writeln(sC);
until pTop = NIL;
end.
3. Очереди
Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) – «Поступивший первым, обслуживается первым».
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая – конец очереди, третья – вспомогательная.
Пример. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных – с клавиатуры, признак конца ввода – строка символов END.
Program QUEUE;
uses Crt;
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(' ***** ВЫВОД РЕЗУЛbТАТОВ *****');
repeat
DelQueue(pBegin, sC);
writeln(sC);
until pBegin = NIL;
end.
ЛЕКЦИЯ № 9. Древовидные структуры данных
1. Древовидные структуры данных
Древовидной структурой данных называется конечное множество элементов-узлов, между которыми существуют отношения – связь исходного и порожденного.
Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t – это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.
Далее дадим определения, используемые при оперировании древовидными структурами.
Если узел у находится непосредственно под узлом х, то узел у называется непосредственным потомком узла х, а х – непосредственным предком узла у, т. е., если узел х находится на i-ом уровне, то соответственно узел у находится на (i + 1) – ом уровне.
Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева – его корень.
Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.
Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в
