Лекции по программированию на Паскале. Часть 6

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; 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 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 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.

Часть 1 | Часть 2 | Часть 3 | Часть 4 | Часть 5 | Часть 6

Лекции по программированию на Паскале. Часть 6

Поиск по сайту