Программа создания и обработки линейного списка

Линейный список – это структура данных, представляющая собой последовательность компонент, связанных между собой адресами, как показано на рис. 1.

PN

………..

На рис. 10.1 используются следующие обозначения:

PN – адрес первого элемента списка, который запоминается для работы со списком при его создании;

nil - признак последнего элемента списка.

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

- создание пустого списка;

- последовательный просмотр списка и поиск заданного элемента;

- добавление нового элемента в упорядоченный список;

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

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

- удаление заданного элемента из списка.

В программе на языке Паскаль элемент линейного списка объявляется с помощью типа «запись» следующего вида:

Туре TElem = recodrd

Inf: integer; {информационное поле}

Next: TPtr { поле связи (адрес следующего элемента списка) }

End;

TPtr – тип «указатель», который объявляется следующим образом:

Type TPtr=^ TElem;

Указательный тип используется для определения переменных, значением которых являются адреса размещенных в памяти переменных, тип которых совпадает с типом указателя. Для размещения в памяти элементов списка используется стандартная процедура динамического распределения памяти; в языке Паскаль эта процедура имеет имя New. Для удаления элемента из списка служит стандартная процедура освобождения памяти Dispose. Адресное поле последнего элемента списка содержит значение nil, специальный, пустой адрес, который является признаком конца списка.

Пример программы создания и обработки линейного списка.

program Project2;

{$APPTYPE CONSOLE}

uses

Windows;

type TPtr=^TElem;

TElem=record

Inf:integer;

Next:TPtr;

end;

Var Beg: TPtr; Value: integer; Rejim: byte;

Procedure Init_list(Var P: TPtr);

Begin P:=nil; end;

Procedure Add_list(Var P: TPtr);

Var PT,TPR,Prev:TPtr; Prizn: byte;

begin

write('Input Value: '); read(Value);

if P=nil then begin New(TPR); P:=TPR;

TPR^.Inf:=Value; TPR^.Next:=nil;

write('First element of list is created - ',Value);

end

else begin PT:=P; PREV:=nil; Prizn:=0;

while PT<>nil do

begin if Value<PT^.Inf then begin

if PREV=nil then begin

New(TPR); P:=TPR; TPR^.Inf:=Value;

TPR^.Next:=PT;

write('Element ',Value,' added before first element'); end

else begin

New(TPR); PREV^.Next:=TPR; TPR^.Inf:=Value;

TPR^.Next:=PT;

Write('Element ',Value, ' is added between two other elements ');

end;

Prizn:=1; break;

end;

PREV:=PT; PT:=PT^.Next;

end;

if Prizn=0 then begin

New(TPR); TPR^.Inf:=Value;

TPR^.Next:=nil; PREV^.Next:=TPR;

write('Element ',Value, ' is added after last element');

end; end;

end;

Procedure Del_Elem(Var P: TPtr);

Var

PT,TPR,Prev:TPtr; Prizn: byte;

begin

if P=nil then write('list is empty!!!')

else begin write('Input value: '); read(Value);

PT:=P; PREV:=nil; Prizn:=0;

while PT<>nil do begin

writeln(PT^.Inf);

if Value=PT^.Inf then begin

if PREV<>nil then begin

PREV^.Next:=PT^.Next; Prizn:=1;

write('Element is deleted '); break;

end

else begin P:=PT^.Next; Prizn:=1;

write('Element is deleted '); break;

end;

Dispose(PT);

end;

PREV:=PT; PT:=PT^.Next;

end;

if Prizn=0 then write('Element is not founded ' );

end;

end;

Procedure Display_list(P: TPtr);

Var

PT:TPtr; i: byte;

begin

i:=0; PT:=P;

if P=nil then begin write('list is empty!!!'); exit; end;

Writeln; write(' List =[');

while PT<>nil do

begin i:=i+1;

write(PT^.Inf,' '); PT:=PT^.Next;

end;

write(']'); write(' Number of elements = ',i);

end;

begin

while True do

begin

writeln;

write('0 -- Exit; '); write('1 -- Create; '); write('2 -- Display; ');

write('3 -- Add; '); writeln('4 -- Delete; '); writeln('Input option (0 -- 4)');

readln(Rejim);

case(Rejim) of

0: begin readln; exit; end;

1: Init_list(Beg);

2: Display_list(Beg);

3: Add_list(Beg);

4: Del_Elem(Beg)

else write('Error!!! ')

end; end; end.