Задачи включения элемента в линейный однонаправленный список без головного элемента.

Графическое представление выполняемых действий дано на рис. 21

Формирование пустого списка.

Procedure Create_Empty_List ( var first : el);

Begin

first = nil;

end;

Формирование очередного элемента списка.

Procedure Create_New_Elem(var p: el);

Begin

New (p);

Writeln ('введите значение первого информационного поля: ');

Readln ( p^.inf1 );

Writeln ('введите значение второго информационного поля:'); Readln ( p^.inf2 );

p^.next := nil;

{все поля элемента должны быть инициализированы}

end;

Подсчет числа элементов списка.

Function Count_el(First:el):integer;

Var

K : integer;

q : el;

Begin

If First = Nil then

k:=0 {список пуст}

Else

begin {список существует}

k:=1; {в списке есть хотя бы один элемент}

q:=First;

{перебор элементов списка начинается с первого}

While q^.Next <> Nil do

Begin

k:=k+1;

q:=q^.Next;

{переход к следующему элементу списка}

End;

End;

Count_el:=k;

End;

ПРИМЕЧАНИЕ: аналогично может быть написана процедура, например, печати списка, поиска адреса последнего элемента и др.

Вставка элемента в начало списка.

Procedure Ins_beg_list(P : el; {адрес включаемого элемента}

Var First : el);

Begin

If First = Nil Then

Begin

First := p;

P^.next := nil{ можно не делать, так как уже сделано при

формировании этого элемента}

End

Else

Begin

P^.Next:=First;{ссылка на бывший первым элемент}

First:=p;{ включаемый элемент становится первым }

End;

End;

Включение элемента в конец списка.

Procedure Ins_end_list(P : el; Var First : el);

Begin

If First = Nil Then

First:=p

Else

Begin

q:=First;{цикл поиска адреса последнего элемента}

While q^.Next <> Nil do

q:=q^.Next;

q^.Next:=p;{ссылка с бывшего последнего

на включаемый элемент}

P^.Next:=Nil;{не обязательно}

End;

End;

Включение в середину (после i-ого элемента).

Procedure Ins_after_I ( first : el; p : el; i : integer);

Var

t, q : el;

K ,n : integer;

Begin

n := count_el(first);{определение числа элементов списка}

if (i < 1 ) or ( i > n )then

Begin

writeln ('i задано некорректно');

exit;

End

Else

Begin

if i = 1 then

Begin

t := first;{адрес 1 элемента}

q := t^.next;{адрес 2 элемента}

t^.next := p;

p^.next := q;

End

Else

if i = n then

begin{ см. случай вставки после последнего

элемента}

. . .

End

else{вставка в «середину» списка}

Begin

t := first;

k := 1;

while ( k < i ) do

begin{поиск адреса i-го элемента}

k := k + 1;

t := t^.next;

end;

q := t^.next;

{найдены адреса i-го (t) и i+1 -го (q) элементов }

t^.next := p;

p^.next := q;

{элемент с адресом р вставлен}

end;

end;

end;

ПРИМЕЧАНИЕ: аналогично рассуждая и применяя графическое представление действия, можно решить задачу включения элемента перед i-ым. Строго говоря, такая задача не эквивалентна задаче включения элемента после (i-1)-го.

Задачи на удаление элементов из линейного однонаправленного списка без головного элемента.

Графическое представление выполняемых действий дано на рисунке 22.

Удаление элемента из начала списка.

ПРИМЕЧАНИЕ: перед выполнением операции удаления элемента или списка желательно запрашивать у пользователя подтверждение удаления.

Procedure Del_beg_list ( Var First : el);

Var

p : el;

answer : string;

Begin

If First <> Nil then

Begin { список не пуст }

writeln ('Вы хотите удалить первый элемент?(да/нет) ');

readln ( answer );

if answer = 'да' then

Begin

p:=First;

If p^.Next = Nil Then{в списке один элемент }

Begin

Dispose (p);{уничтожение элемента}

First:=Nil;{список стал пустым }

End

Else

Begin

P := first;{адрес удаляемого элемента }

First:=first^.Next;

{адрес нового первого элемента}

Dispose(p);

{удаление бывшего первого элемента }

End;

End

End

Else

writeln ('список пуст, удаление первого элемента невозможно');

End;

Удаление элемента из конца списка.

Нужен запрос на удаление

Procedure Del_end_list( Var First :el);

Begin

If First < > Nil then

Begin {список не пуст}

if fiRst^.next = nil then

begin{в списке - единственный элемент }

p := first;

dispose (p);

First := nil;

End

Else

begin{в списке больше одного элемента }

Q := First;

T := First;

{цикл поиска адреса последнего элемента}

While q^.Next < > Nil do

Begin

T := q;{запоминание адреса текущего элемента}

q:=q^.Next;{переход к следующему элементу}

end;

{после окончания цикла Т - адрес предпоследнего,

а Q - адрес последнего элемента списка}

dispose (q);{удаление последнего элемента}

t^.next := nil;{предпоследний элемент стал

последним}

End

End

Else

writeln ('список пуст, удаление элемента невозможно');

end;

ПРИМЕЧАНИЕ. После исключения элемента из списка этот элемент может не удаляться из памяти, а через список параметров передан на какую-либо обработку, если этого требует алгоритм обработки данных.

Удаление элемента из середины списка (i-ого элемента).

Procedure Del_I_elem ( first : el; i : integer);

Var

t, q, r : el;

K ,n : integer;

Begin

n := count_el(first);{определение числа элементов списка}

if (i < 1 ) or ( i > n ) then

Begin

writeln ('iзадано некорректно');

exit;

End

Else

Begin

{нужно добавить подтверждение удаления }

if i = 1 then

begin{удаляется 1 элемент}

t := first;

first:= first^.next;

dispose ( t);

End

Else

if i = n then

begin{ см. случай удаления последнего элемента}

. . .

End

else{удаление из «середины» списка}

Begin

t := first;

q := nil;

k := 1;

while ( k < i ) do

begin{поиск адресов (i-1)-го и i-го элементов}

k := k + 1;

q := t;

t := t^.next;

end;

r := t^.next;

{найдены адреса i-го (t), (i-1)-го (q) и (i+1)-го (r) элементов }

q^.next := r;

dispose ( t );{удален i-ый элемент }

end;

end;

end;

Не нашли, что искали? Воспользуйтесь поиском по сайту: