Основные понятия алгоритмического языка
компонент производится аналогично.
Выборка компоненты из очереди осуществляется из начала очереди,
одновременно компонента исключается из очереди. Пусть в памяти ЭВМ
сформирована очередь, состоящая из трех элементов:
г=====¬ г=====¬ г=====¬ г=====¬ г=====¬
¦ *--¦---¬ ¦ 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===- ¦ ¦===¦ ¦==
| |  скачать работу |
Основные понятия алгоритмического языка |
