Добавление нового элемента в список
End.
Begin
Repeat
Begin
5 -3 -12
Begin
Begin
New(q);
q^.Inf := i*i;
q^.Next := head;
head := q;
End;
После создания этого списка значением переменной head будет являться ссылка на его первый элемент. Прочитаем созданный список – выведем на экран информационные поля его элементов, начиная с первого:
q := head; указатель – на первый элемент списка
While (q<>Nil) Do пока ссылка не пустая (последний элемент)
Write(q^.Inf:6); выводим значение очередного элемента
q := q^.Next; делаем шаг по списку – берем следующий элемент
End;
В данном случае при выполнении цикла While значением указателя q будут являться поочередно ссылки на первый, второй, третий и т.д. элементы списка, и, наконец, Nil. Это происходит потому, что после присваивания
q := q^.Next;
значением переменной q будет или ссылка на следующий элемент списка, хранящаяся в ссылочной части этого текущего элемента, или Nil, если достигнут конец списка.
Пользуясь этим способом перехода от предыдущего элемента к последующему, можно просмотреть или весь список от начала до конца, или его часть.
Пример: ввести с клавиатуры последовательность целых чисел (конец ввода – число 0), сформировать из них список, определить количество введенных чисел, вывести список на экран.
Интерфейс:
Первое число: -12
Следующее число: -3
Следующее число: 5
Следующее число: 0
Введено чисел: 3
Введенные числа:
Программа:
Program Spisok;
Uses CRT;
Type TPoint = ^TElement;
TElement = Record
Inf: Integer;
Next: TPoint;
End;
Var head, q : TPoint;
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 адрес головы списка
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пока не конец списка
Write(q^.Inf:5); выводим очередной элемент
q := q^.Next; ссылку – на следующий элемент
End;
WriteLn;
ReadLn;
Основное преимущество связных списков перед статическими структурами данных, например, массивами, заключается в том, что их можно изменять, включая в них новые элементы или исключая ненужные, причем эти операции могут производиться в любом месте списка.
Пусть имеется связный список из трех чисел: 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), каждый раз выводя новый список на экран.
Интерфейс: