Информатика и информационные технологии: конспект лекций

1) начальное формирование стека (запись первой компоненты);

2) добавление компоненты в стек;

3) выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа «указатель», первая из которых определяет вершину стека, а вторая – вспомогательная.

Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных – с клавиатуры, признак конца ввода – строка символов END.

Program STACK;

uses Crt;

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('****** ВЫВОД РЕЗУЛ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, называемых поддеревьями.

Далее дадим определения, используемые при оперировании древовидными структурами.