Автор: Пользователь скрыл имя, 27 Марта 2013 в 11:59, лекция
СОСТАВ ЯЗЫКА. Обычный разговорный язык состоит из четырех основных
элементов: символов, слов, словосочетаний и предложений. Алгоритми-
ческий язык содержит подобные элементы, только слова называют элемен-
тарными конструкциями, словосочетания-выражениями, предложения-опера-
торами.
число, либо строка символов. Ключ располагается в поле данных компо-
ненты, он может занимать как отдельное поле записи, так и быть частью
поля записи.
Основные отличия связного списка от стека и очереди следующие:
-для чтения доступна любая компонента списка;
-новые компоненты можно добавлять в любое место списка;
-при чтении компонента не удаляется из списка.
Над списками выполняются следующие операции:
-начальное формирование списка (запись первой компоненты);
-добавление компоненты в конец списка;
-чтение компоненты с заданным ключом;
-вставка компоненты в заданное место списка (обычно после компо-
ненты с заданным ключом);
-исключение компоненты с заданным ключом из списка.
Для формирования списка и работы с ним необходимо иметь пять пере-
менных типа указатель, первая из которых определяет начало списка,
вторая - конец списка, остальные- вспомогательные.
Описание компоненты списка и переменных типа указатель дадим сле-
дующим образом:
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 ║ ┌─║──* ║
╚═════╝ │ ║═════║ ║═════║ ║═════║ ║═════║ │ ╚═════╝
pBegin └──>║ *──║───>║ *──║─....─>║ *──║───>║ NIL ║<─┘ pEnd
╚═════╝ ╚═════╝ ╚═════╝ ╚═════╝
Для чтения и вставки
компоненты по ключу
иск компоненты с заданным ключом:
pCKey:=pBegin;
while (pCKey<>NIL) and (Key<>pCKey^.D) DO
pCKey:=pCKey^.pNext;
Здесь Key - ключ, тип которого совпадает с типом данных компоненты.
После выполнения этих операторов указатель pСKey будет определять
компоненту с заданным ключом или такая компонента не будет найдена.
Пусть pCKey определяет компоненту с заданным ключом. Вставка новой
компоненты выполняется
New(pAux); ╔═══╗
pAux^.D:= DK1; ┌──║─* ║
│ ╚═══╝
│ pCKey
│
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗
║ *─║──┐ ║D1 ║ ║Key║ ║KK1║ ║DN ║ ┌──║─* ║
╚═══╝ │ ║═══║ ║═══║ ║═══║ ║═══║ │ ╚═══╝
pBegin └─>║ *─║─...─>║ *─║────>║ *─║─...─>║NIL║<─┘ pEnd
╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝
║ ║<─┘ pAux
pAux^.pNext:=pCKey^.pNext;
pCKey^.pNext:=pAux;
╔═══╗
┌──║─* ║
│ ╚═══╝
│ pCKey
│
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗
║ *─║──┐ ║D1 ║ ║Key║ ║KK1║ ║DN ║ ┌──║─* ║
╚═══╝ │ ║═══║ ║═══║ ║═══║ ║═══║ │ ╚═══╝
pBegin └─>║ *─║─...─>║ * ║ ║ *─║─...─>║NIL║<─┘ pEnd
╚═══╝ ╚═══╝ ╚═══╝ ╚═══╝
│ ^
│ │ ╔═══╗ ╔═══╗
│ │ ║DK1║ ┌──║-* ║
│ └──────────║═══║ │ ╚═══╝
└───────────────────>║─* ║<─┘ pAux
Для удаления компоненты с заданным ключом необходимо при поиске
нужной компоненты помнить адрес предшествующей:
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
╔═══╗ ╔═══╗
║ * ║ ║ * ║
╚═══╝ ╚═══╝
│ │
│ │
│ │
╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗ ╔═══╗
║ *─║──┐ ║D1 ║ ║KK1║ ║Key║ ║KK2║ ║DN ║ ┌──║─* ║
╚═══╝ │ ║═══║ ║═══║ ║═══║ ║═══║ ║═══║ │ ╚═══╝
pBegin └─>║ *─║─...─>║ *─║─┐ ║ *─║───>║ *─║─...─>║NIL║<─┘ pEnd
╚═══╝ ╚═══╝ │ ╚═══╝ ╚═══╝ ╚═══╝
│ ^
│ │
└──────────────┘
Пример. Составить программу, которая формирует список, добавляет в
него произвольное количество компонент, выполняет вставку и удаление
компоненты по ключу, а затем читает и выводит весь список на экран
дисплея. В качестве данных взять строку символов. Ввод данных - с
клавиатуры дисплея, признак конца ввода - строка символов 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;
bCond: Boolean;
Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa);
begin
New(pBegin);
pBegin^.pNext:=NIL;
pBegin^.sD:=sC;
pEnd:=pBegin
end;
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
end;
Procedure InsComp(var sKey,sC: Alfa);
var pAux:PComp;
begin
Find(sKey,pBegin,pCKey,
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^.pNext:=pCKey^.pNext
end;
begin
ClrScr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateLL(pBegin,pEnd,sC);
repeat
writeln('ВВЕДИ СТРОКУ ');
readln(sC);
AddLL(pEnd,sC)
until sC='END';
writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****');
pAux:=pBegin;
repeat
writeln(pAux^.sD);
pAux:=pAux^.pNext;
until pAux=NIL;
writeln;
writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ');
readln(sKey);
writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ');
readln(sC);
InsComp(sKey,sC);
writeln;
writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ');
readln(sKey);
DelComp(sKey,pBegin);
writeln;
writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****');
pAux:=pBegin;
repeat
writeln(pAux^.sD);
pAux:=pAux^.pNext;
until pAux=NIL
end.
Информация о работе О с н о в н ы е п о н я т и я ал г о р и т м и ч е с к о г о я з ы к а