Лекции по Turbo Pascal 7.0 (Лекции электронная версия), страница 8

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.

39. О Ч Е Р Е Д И

Очередью называется динамическая структура данных, добавление ком-

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

с другого конца. Очередь работает по принципу:

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); ¦ *--¦---¬ ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ ¦ pEnd

L=====-

г=====¬ г=====¬ г=====¬

pBegin^.pNext:=NIL; ¦ *--¦---¬ ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦ pEnd

L=====-

г=====¬ г=====¬ г=====¬

pBegin^.D:=D1; ¦ *--¦---¬ ¦ D1 ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦ pEnd

L=====-

г=====¬ г=====¬ г=====¬

pEnd:=pBegin; ¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd

L=====-

Добавление компоненты в очередь производится в конец очереди:

New(pAux);

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ ¦<--- pAux

L=====- L=====-

pAux^.pNext:=NIL;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

pBegin^.pNext:=pAux;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

pEnd:=pAux;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ L=====- ¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦ pEnd L-->¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

pEnd^.D:=D2;

г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦-------------------->¦ NIL ¦<--- pEnd

L=====- L=====-

Добавление последующих компонент производится аналогично.

Выборка компоненты из очереди осуществляется из начала очереди,

одновременно компонента исключается из очереди. Пусть в памяти ЭВМ

сформирована очередь, состоящая из трех элементов:

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦------>¦ *--¦------>¦ NIL ¦<--- pEnd

L=====- L=====- L=====-

Выборка компоненты выполняется следующими операторами:

D1:=pBegin^.D;

pBegin:=pBegin^.pNext;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin ¦ ¦ ¦ --->¦ *--¦------>¦ NIL ¦<--- pEnd

¦ L=====- ¦ L=====- L=====-

¦ ¦

L--------------

Пример. Составить программу, которая формирует очередь, добавляет

в нее произвольное количество компонент, а затем читает все компонен-

ты и выводит их на экран дисплея. В качестве данных взять строку сим-

волов. Ввод данных - с клавиатуры дисплея, признак конца ввода -

строка символов 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(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');

repeat

DelQueue(pBegin,sC);

writeln(sC);

until pBegin=NIL

end.

40. Л И Н Е Й Н Ы Е С П И С К И

В стеки или очереди компоненты можно добавлять только в какой -

либо один конец структуры данных, это относится и к извлечению компо-

нент.

Связный (линейный) список является структурой данных, в произволь-

но выбранное место которого могут включаться данные, а также изымать-

ся оттуда.

Каждая компонента списка определяется ключом. Обычно ключ - либо

число, либо строка символов. Ключ располагается в поле данных компо-

ненты, он может занимать как отдельное поле записи, так и быть частью

поля записи.

Основные отличия связного списка от стека и очереди следующие:

-для чтения доступна любая компонента списка;

-новые компоненты можно добавлять в любое место списка;

-при чтении компонента не удаляется из списка.

Над списками выполняются следующие операции:

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

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

-чтение компоненты с заданным ключом;

-вставка компоненты в заданное место списка (обычно после компо-

ненты с заданным ключом);

-исключение компоненты с заданным ключом из списка.

Для формирования списка и работы с ним необходимо иметь пять пере-

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

вторая - конец списка, остальные- вспомогательные.

Описание компоненты списка и переменных типа указатель дадим сле-

дующим образом:

type

PComp= ^Comp;

Comp= record

D:T;

pNext:PComp

end;

var

pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

где pBegin - указатель начала списка, pEnd - указатель конца списка,

pCKey, pPreComp, pAux - вспомогательные указатели.

Начальное формирование списка, добавление компонент в конец списка

выполняется так же, как и при формировании очереди.

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦-¬ ¦ D1 ¦ ¦ D2 ¦ ¦ DN1 ¦ ¦ DN ¦ --¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦--->¦ *--¦-....->¦ *--¦--->¦ NIL ¦<-- pEnd

L=====- L=====- L=====- L=====-

Для чтения и вставки компоненты по ключу необходимо выполнить по-

иск компоненты с заданным ключом:

pCKey:=pBegin;

while (pCKey<>NIL) and (Key<>pCKey^.D) DO

pCKey:=pCKey^.pNext;

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

После выполнения этих операторов указатель pСKey будет определять

компоненту с заданным ключом или такая компонента не будет найдена.

Пусть pCKey определяет компоненту с заданным ключом. Вставка новой

компоненты выполняется следующими операторами:

New(pAux); г===¬

pAux^.D:= DK1; ---¦-* ¦

¦ L===-

¦ pCKey

¦

г===¬ г===¬ г===¬ г===¬ г===¬ г===¬

¦ *-¦--¬ ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ *-¦---->¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- L===- L===-

г===¬ г===¬

¦DK1¦ ---¦-* ¦

¦===¦ ¦ L===-

¦ ¦<-- pAux

L===-

pAux^.pNext:=pCKey^.pNext;

pCKey^.pNext:=pAux;

г===¬

---¦-* ¦

¦ L===-

¦ pCKey

¦

г===¬ г===¬ г===¬ г===¬ г===¬ г===¬

¦ *-¦--¬ ¦D1 ¦ ¦Key¦ ¦KK1¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ * ¦ ¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- L===- L===-

¦ ^

¦ ¦ г===¬ г===¬

¦ ¦ ¦DK1¦ ---¦-* ¦

¦ L----------¦===¦ ¦ L===-

L------------------->¦-* ¦<-- pAux

L===-

Для удаления компоненты с заданным ключом необходимо при поиске

нужной компоненты помнить адрес предшествующей:

pCKey:=pBegin;

while (pCKey<>NIL) and (Key<>pCKey^.D) do

begin

pPreComp:=pCKey;

pCKey:=pCKey^.pNext

end;

Здесь указатель pCKey определяет компоненту с заданным ключом, указа-

тель pPreComp содержит адрес предидущей компоненты.

Удаление компоненты с ключом Key выполняется оператором:

pPreComp^.pNext:=pCKey^.pNext;

pPreComp pCKey

г===¬ г===¬

¦ * ¦ ¦ * ¦

L===- L===-

¦ ¦

¦ ¦

¦ ¦

г===¬ г===¬ г===¬ г===¬ г===¬ г===¬ г===¬

¦ *-¦--¬ ¦D1 ¦ ¦KK1¦ ¦Key¦ ¦KK2¦ ¦DN ¦ ---¦-* ¦

L===- ¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦===¦ ¦ L===-

pBegin L->¦ *-¦-...->¦ *-¦-¬ ¦ *-¦--->¦ *-¦-...->¦NIL¦<-- pEnd

L===- L===- ¦ L===- L===- L===-

¦ ^

¦ ¦

L---------------

Пример. Составить программу, которая формирует список, добавляет в

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

компоненты по ключу, а затем читает и выводит весь список на экран

дисплея. В качестве данных взять строку символов. Ввод данных - с

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

Program LISTLINKED;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;

Comp= record

sD:Alfa;

pNext:PComp

end;

var

pBegin, pEnd, pAux, pCKey, pPreComp: PComp;

sC, sKey: Alfa;

Procedure AddLL(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 Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp;

var bCond: Boolean);

begin

pCKey:=pBegin;

while (pCKey <> NIL) and (sKey <> pCKey^.D) do

begin

pPreComp:=pCKey;

pCKey:=pCKey^.pNext

end;

if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE

else bCond:=TRUE

end;

Procedure InsComp(var sKey,sC: Alfa);

var pAux:PComp;

begin

Find(sKey,pBegin,pCKey,pPreComp,bCond);

New(pAux);

pAux^.sD:=sC;

pAux^.pNext:=pCKey^.pNext;

pCKey^.pNext:=pAux

end;

Procedure DelComp(var sKey: Alfa; var pBegin: PComp);

begin

Find(sKey,pBegin,pCKey,pPreComp,bCond);

pPreComp^.pNext:=pCKey^.pNext

end;

begin