Добавление нового элемента в список

Var head, q, r: TPoint;

Список сформирован, и значениями переменных head и q является ссылка на первый элемент списка:

Необходимо после элемента - 3вставить элемент с информационной частью, равной 17.

Для включения нового элемента в готовый список выполняются следующие действия:

r^.Inf:= 17;

сейчас ссылка q указывает на элемент -3, то есть q^.Inf = -3, а поле q^.Next содержит адрес элемента -12:

Программа:

Program Spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q, r: TPoint;

posle: Integer;

flag: 0..1; флаг поиска (0 – элемент не найден)

New(q); формируем первый элемент

Write(‘Первое число: ’);

q^.Next:= head^.Next; помещаем его в голову списка

head^.Next:= q; в head^.Next адрес головы списка

Repeat

New(q); формируем очередной элемент

Write(‘Очередное число: ’);

ReadLn(q^.Inf); вводим его информационную часть

If (q^.Inf=0) если ввели 0,

Then Break; то выходим из цикла ввода

head^.Inf:= head^.Inf + 1; увеличиваем счетчик элементов на 1

q^.Next:= head^.Next; вставляем элемент в голову списка

head^.Next:= q; в head^.Next адрес головы списка

Until (q^.Inf = 0);

Procedure Vyvod_spisok; процедура вывода списка

q:= head^.Next; текущую ссылку – на первый элемент

While (q <> Nil) Do пока не конец списка

Begin

Write(q^.Inf:5); выводим очередной элемент

q:= q^.Next; ссылку – на следующий элемент

End;

WriteLn;

End;

Begin головная программа

Formir_spisok; обращение к процедуре создания списка

Vyvod_spisok; обращение к процедуре вывода списка

ReadLn(r^.Inf); информационная часть нового элемента

If (r^.Inf = 0) если она равна нулю,

Then Break; то выходим из цикла ввода

Write(‘После какого: ’);

ReadLn(posle);

flag:= 0; флаг поиска равен нулю – элемент пока не найден

q:= head^.Next; поисковый указатель q – в голову списка

While (q <> Nil) Do пока не конец списка

If (q^.Inf = posle) ищем нужный элемент

Then

Begin

flag:= 1; если элемент найден:

Break; выходим из цикла поиска

End

Else q:= q^.Next; иначе делаем шаг по списку

If (flag = 0) Then если элемент не найден:

Begin

WriteLn(‘Такого элемента в списке нет’);

WriteLn(‘Список:’);

Vyvod_spisok; выводим список

Continue; и продолжаем цикл ввода

End;

r^.Next:= q^.Next; если элемент найден,

q^.Next:= r; то вставляем его в список

head^.Inf:= head^.Inf + 1; увеличиваем счетчик элементов на единицу

Vyvod_spisok; выводим новый список

Until (r^.Inf = 0); окончание цикла ввода

WriteLn(‘Список:’);

Vyvod_spisok; выводим окончательный список

ReadLn;

End.

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

Пусть имеется связный список из трех чисел : 5, -3, -12.

Список сформирован, и значениями переменных head и q является ссылка на первый элемент списка:

Необходимо удалить из списка элемент - 3.

Для удаления (исключения) существующего элемента из списка выполняются следующие действия:

1. указатели q (поисковый) и r (отстает от поискового на шаг) ставим в голову списка:

q:= head^.Next; на первый элемент списка

r:= head; на указатель на голову списка

2. в списке отыскивается удаляемый элемент, для этого используем поисковый указатель q:

While (q <> Nil) Do пока не дошли до конца списка

If (q^.Inf = -3) если нашли нужный элемент,

Then Break то выходим из цикла поиска,

r:= q; иначеподтягиваем r к q

q:= q^.Next; и делаем шаг по списку указателем q

End;

сейчас ссылка q указывает на элемент -3, то есть q^.Inf = -3, а поле q^.Next содержит адрес элемента -12. Ссылка r указывает на предыдущий элемент списка, то есть на 5, а в r^.Next содержится адрес удаляемого элемента - r^.Next = q:

3. в ссылочное поле r^.Next помещается адрес, хранящийся в q^.Next, то есть адрес элемента -12:

r^.Next:= q^.Next;

Сейчас оба элемента (5 и -3) будут соединены с элементом -12,

4. освобождаем память от удаленного элемента -3 и возвращаем указатели q и r в голову списка:

Dispose(q); удаляем из памяти элемент -3

q:= head^.Next; на первый элемент списка

Интерфейс:

Создание списка

Первое число: -12

Следующее число: 17

Следующее число: -3

Следующее число: 5

Следующее число: 0

Введено чисел: 4

Введенные числа:

5 -3 17 -12