Inf: Integer;

Next: TPoint;

End;

Var head, q : tPoint;

Begin

ClrScr;

New(head); head - указатель на голову списка

head^.Inf := 0; количество элементов в списке

head^.Next := Nil; списка еще нет

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

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

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

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

Then Exit; то выходим из программы

head^.Inf := 1; в списке один элемент

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

WriteLn(‘Введено чисел: ’, head^.Inf);

WriteLn(‘Введенные числа:’);

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

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

Begin

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

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

End;

WriteLn;

ReadLn;

End.

Основное преимущество связных списков перед статическими структурами данных, например, массивами, заключается в том, что их можно изменять, включая в них новые элементы или исключая ненужные, причем эти операции могут производиться в любом месте списка.

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

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

Добавим в описание переменных переменную ссылочного типа r:

Var head, q, r: tPoint;

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

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

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

1.создается новый элемент и заполняется его информационное поле:

New(r);

r^.Inf := 17;

2.в списке находится элемент,послекоторого должен стоять новый, в данном случае элемент-3; для этого используем переменнуюq:

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

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

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

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

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

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

r^.Next := q^.Next;

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

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

q^.Next := r;

Пример: сформировать список из элементов5, -3, 17, -12и вывести его на экран. Добавлять с клавиатуры новые элементы после заданных (конец ввода – число0), каждый раз выводя новый список на экран.

Интерфейс:

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

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

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

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

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

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

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

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

5 -3 17 -12

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

Новый элемент: -2

После какого: -3

Новый список:

5 -3 -2 17 -12

Новый элемент: 15

После какого: -12

Новый список:

5 -3 -2 17 -12 15

Новый элемент: 9

После какого: 5

Новый список:

5 9 -3 -2 17 -12 15

Новый элемент: 20

После какого: 10

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

Список:

5 9 -3 -2 17 -12 15

Новый элемент: 0

Список:

5 9 -3 -2 17 -12 15

Программа:

Program Spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record