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

Вид материала

Содержание

Подобный материал:

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

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

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

нент.

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

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

ся оттуда.

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

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

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

поля записи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^ Примеры программ

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

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

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

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

клавиатуры дисплея, признак конца ввода - строка символов 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.

Пример2

Написать программу посещения студентами дисплейного класса. Учесть приход и уход студентов в течение занятий. Данные представить в виде линейного списка.

TYPE

Link=^data; {указатель на тип данных }

data=record {описание самого типа данных }

FIO:string[50]; {ФИО }

timeStart,timeEnd:string[5]; {время нчала и конца (15:03) }

next:Link; {указатель на следующую запись}

end;

VAR

P,First:Link; {указатели на запись: текущую, первую}

m:byte; {для меню }

{добавление новой записи в список}

PROCEDURE addFirst(a:Link);

BEGIN

a^.next:=First;

First:=a;

END;

{ввод данных в текущую запись}

PROCEDURE InputData;

BEGIN

P:=new(Link);

write('Введите ФИО: ');

readln(P^.FIO);

write('Введите время начала: ');

readln(P^.timeStart);

write('Введите время окончания: ');

readln(P^.timeEnd);

addFirst(P);

END;

{вывод на экран}

PROCEDURE Print;

var

curr:Link; {указатель на очередную запись }

count:integer; {счетчик }

BEGIN

count:=0;

curr:=First; {установить указатель на первую запись}

while curr<>nil do

begin

inc(count);

writeln(count,') ',curr^.FIO:55,curr^.timeStart:10,curr^.timeEnd);

curr:=curr^.next; {перейти к очередной записи }

end;

readln;

END;

{===== основная программа =====}

BEGIN

new(P); {создать новую динамическую переменную и установить на нее указатель}

{цикл меню}

repeat

InputData; {ввод данных }

writeln;

writeln('1 - добавить в список');

writeln('2 - распечатать весь список и выйти');

write('=>');

readln(m);

until m=2;

Print; {вывод на экран}

END.

Пример3

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

TYPE

Link=^data; {указатель на тип данных }

data=record {описание самого типа данных }

FIO:string[50]; {ФИО }

Tel:string[10]; {телефон }

next:Link; {указатель (адрес) на следующую запись}

end;

VAR

P,First:Link; {указатели на запись: текущую, первую }

BEGIN

writeln('Число свободных блоков в динамически распределяемой области памяти:');

writeln('До загрузки данных = ',memavail);

P:=new(Link); {=1= выделить память и адрес записать в P}

P^.FIO:='Шабаров П.С'; {=2= выделенную память заполнить данными }

P^.Tel:='93-2-46';

P^.next:=nil;

First:=P;

P:=new(Link); {=3=}

P^.FIO:='Соловьев А.А.'; {=4=}

P^.Tel:='3-12-41';

P^.next:=First;

First:=P;

P:=new(Link); {=5=}

P^.FIO:='Липовский Р.Е.'; {=6=}

P^.Tel:='3-32-17';

P^.next:=First;

First:=P;

writeln('После загрузки данных = ',memavail);

while P<>nil do

begin

First:=P^.next; {сохранить адрес указывающий на следующую запись}

dispose(P); {=7= освободить память по текущему адресу }

P:=First; {сохраненный адрес записать в P }

end;

writeln('После удаления данных = ',memavail);

readln;

END.

Вообщем, после переработки предыдущей задачи, оказалось что там много чего лишнего. Данная программа показывает: как создать простой свзанный список, что происходит с динамической памятью и как освободить память занимаемую списком.

Для создания списка сначала создаем тип - какие данные будут в памяти.
Тип берем RECORD (запись). Основной переменной любого связанного списка является - переменная-указатель, которая указывает на следующую запись.
Переменная-указатель - занимает 4 байта и хранит в себе какой-либо адрес.
В данной программе переменная-указатель это: next, P, First.
Необходимо указать на какой тип указывает переменная-указатель.
В данной программе тип указателя это: Link.
Выделяем новую динамическую память и сохраняем адрес (где рассположена выделенная память).

P:=new(Link);

Заполняем нужными данными переменную-указатель.
P^.FIO:='Шабаров П.С';
P^.Tel:='93-2-46';
Заполняем нужными данными переменную-указатель: записываем адрес для следующей записи.

P^.next:=nil;

Если запись первая, то переменная-указатель следующей записи должен указывать на пустой указатель - nil.

Сохраняем адрес P в First (можно было сохранить сразу после 3-го действия).

First:=P;

Если нужны еще записи, то переходим к действию 3.
Связанный список готов. Далее делаем что хотим...
Освобождаем динамическую память.
while P<>nil do
begin
First:=P^.next;
dispose(P);
P:=First;
end;

Для обхода всех записей списка делаем вот такой цикл:

P:=First; {начать с первой записи }

while P<>nil do {выполняем пока не дошли до конца}

begin

... {что-то делаем }

...

P:=P^.next; {переходим к следующей записи }

end;

Так, это еще не все. Обязательно скачайте файлик - там исходник программы и графическое пояснение что и как происходит при выполнении этой программы.
Внимательно прочитайте этот материал, затем разберитесь с помощью графического пояснения как работает программа, и вы поймете, как работать со связа

Пример4н

ПП

Сортировка связанного списка.

TYPE

Link=^data; {указатель на тип данных }

data=record {описание самого типа данных }

FIO:string[50]; {ФИО }

N:integer; {номер }

next:Link; {указатель (адрес) на следующую запись}

end;

VAR

P,First:Link; {указатели на запись: текущую, первую }

m:byte; {для меню }

{процедура - добавление новой записи в список}

PROCEDURE AddData;

BEGIN

P:=new(Link); { выделить память и адрес записать в P}

P^.next:=First; { адрес на следующую запись }

First:=P; { сохраняем адрес первой записи }

{здесь заполняйте запись данными в соответствии с вашим типом }

write('Введите ФИО: ');

readln(P^.FIO);

write('Введите номер: ');

readln(P^.N);

END;

{вывод на экран}

PROCEDURE Print;

var

count:integer; {счетчик для нумерации }

BEGIN

count:=0;

P:=First; {начать с первой записи }

while P<>nil do

begin

inc(count); {увеличить счетчик }

writeln(count,') ',P^.FIO,' ',P^.N);

P:=P^.next; {перейти к очередной записи }

end;

readln;

END;

{процедура - удаление всего списка, освобождение динамической памяти}

PROCEDURE DelData;

BEGIN

P:=First;

while P<>nil do

begin

First:=P^.next; {сохранить адрес указывающий на следующую запись}

dispose(P); {освободить память по текущему адресу }

P:=First; {сохраненный адрес записать в P }

end;

END;

{процедура - сортировки списка по возрастанию}

PROCEDURE Sort;

var

P1,P2,TMP:Link; {P1,P2 - адрес записи для циклов, TMP - временно}

BEGIN

new(TMP); {выделим память для TMP }

P1:=First; {начать цикл 1 с первой записи }

while P1<>nil do {выполняем пока не дошли до конца цикла 1}

begin

P2:=First; {начать цикл 2 с первой записи }

while P2<>nil do {выполняем пока не дошли до конца цикла 2}

begin

if P1^.N

begin

{сохраняем данные в временную переменную}

{адрес на следующую запись не изменяем! }

TMP^.FIO:=P1^.FIO;

TMP^.N:=P1^.N;

{делаем обмен данными по адресу P1 }

P1^.FIO:=P2^.FIO;

P1^.N:=P2^.N;

{делаем обмен данными по адресу P2 }

P2^.FIO:=TMP^.FIO;

P2^.N:=TMP^.N;

end;

P2:=P2^.next; {переходим к следующей записи цикла 2}

end;

P1:=P1^.next; {переходим к следующей записи цикла 1}

end;

dispose(TMP); {освобождаем память, занимаемую TMP }

END;

{==== основная программа ====}

BEGIN

First:=nil; {нет записей в списке, адрес пустой }

repeat { меню }

AddData;

writeln('1 - добавить новую запись');

writeln('2 - выйти и далее...');

write('=>');

readln(m);

until m=2; {end меню}

writeln('== До сортировки ==');

Print;

Sort;

writeln('== После сортировки ==');

Print;

DelData;

END.

{Примечание: First - первая запись с конца!}

Данный пример показывает: как вводить данные в список с помощью меню, как вывести список на экран, как отсортировать список, как освободить пямять занимаемую списком. ным списком!

Пример5. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компонен- ты и выводит их на экран дисплея. В качестве данных взять строку сим- волов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов 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.

Пример6. Составить программу, которая формирует список, добавляет в него произвольное количество компонент, выполняет вставку и удаление компоненты по ключу, а затем читает и выводит весь список на экран дисплея. В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов 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;

Blog

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

Содержание