Связный список – это динамическая структура, имеющая вид цепочки связанных между собой элементов, причем каждый предыдущий элемент в ней хранит информацию о месте (адресе ячейки памяти), где расположен следующий за ним элемент.
Такая ситуация напоминает очередь к врачу в приемной: каждый пациент знает, за кем он занимал очередь, хотя все посетители могут сидеть в каком угодно порядке на свободных стульях.
Связанный список состоит из элементов типа запись, причем каждый элемент имеет два поля – информационное и ссылочное. В информационном поле (полях) хранится значение элемента списка – числа, строки и т.д., а в ссылочном – ссылка (адрес ячейки памяти) на следующий за ним элемент:
Type TPoint = ^TElement;
TElement = Record
Inf: Integer;
Next: TPoint;
Var head, q : TPoint;
Определен новый тип TPoint – ссылка на объекты типа TElement, причем TElement – это запись, имеющая два поля: Inf - целого типа и Next - типа TPoint. Здесь мы впервые сталкиваемся с ситуацией, когда в правой части определения для типа TPoint встречается имя типа TElement, который определен позже. В Паскале разрешается такое рекурсивное определение типов, если один из них является ссылочным.
Таким образом, переменные head и q типа TPoint являются записями, одно из полей которых содержит ссылку на адрес ячейки памяти, отводимой для переменной этого же типа. Значит, каждый элемент создаваемого списка будет содержать ссылку на такой же элемент списка. Признаком того, что данный элемент является последним в списке, является равенство поля ссылки этого элемента значению Nil – пустой ссылки. На каждый элемент списка, кроме первого, имеется ссылка от предыдущего элемента. Поэтому при формировании любого списка необходимо вводить переменную, значение которой является ссылка на текущий первый элемент списка – голову списка. Такой переменной у нас является head. Если список еще не сформирован, то есть в нем нет ни одного элемента (пустой список), то значение этой переменной должно равняться Nil.
Построим список из трех элементов, содержащих числа 5, -3, -12 (причем 5 - голова, а -12 - хвост). Пусть в ссылочном поле переменной head всегда хранится адрес текущего первого элемента списка. Переменную q будем использовать для выделения с помощью оператора New(q) места в памяти для размещения очередного элемента списка.
В начале построения списка ни одного элемента в нем нет – список пуст, поэтому нет и его начала:
New(head);
Head := Nil;
Список начнем строить с последнего элемента, равного -12 : определим для него место в памяти и информационную часть:
q^.Inf := -12;
Сейчас этот элемент является первым (и пока единственным), поэтому одновременно и последним элементом списка. Поэтому ссылочная часть его должна быть равна head, имеющему значение Nil – за этим элементом других элементов нет:
q^.Next := head;
а переменная head должна уже содержать ссылку на этот первый созданный элемент списка:
head := q;
Таким образом, переменная head сейчас хранит адрес ячейки памяти, созданной операцией New(q), в которой записан первый элемент списка -12.
Вставим перед ним элемент, равный -3: определим для него место в памяти и информационную часть:
New(q);
q^.Inf := -3;
При этом в памяти сохраняется уже созданный элемент списка, ссылка на который хранится в head :
Вновь созданный элемент будет первым элементом списка, поэтому ссылку head на последний (старый первый) элемент поместим в его ссылочную часть:
q^.Next := head;
а в освободившуюся переменную head поместим ссылку на него – новый первый элемент списка (эта переменная всегда должна указывать на голову списка):
head := q;
Наконец, создадим первый (в порядке следования) элемент списка, равный 5:
New(q);
q^.Inf := 5;
Поместим в его ссылочную часть ссылку на ранее созданный (следующий за ним в списке) элемент, равный -3, а в переменную head – ссылку на него самого:
q^.Next := head;
head := q;
В результате создан связный список, в каждом элементе которого хранится адрес (ссылка) следующего за ним элемента, а ссылка на первый элемент списка находится в переменных head и q.
Ссылочное поле (в нашем случае .Next) само является указателем, поэтому, например, значением переменной head^.Next^.Inf будет являться информационное поле второго по списку элемента, т.е. -3, а значением переменной head^.Next^.Next - ссылочное поле этого элемента, т.е. ссылка на третий элемент списка. Так, наращивая переменную head, можно добраться до конца списка.
Таким образом, рассмотренный способ построения списка “с хвоста” заключается в создании пустого списка и повторяющемся выполнении ряда однотипных шагов, добавляющих в начало списка новые элементы.
Например, программа построения списка, элементами которого являются квадраты целых чисел от 1 до n, имеет вид (воспользуемся имеющимся описанием переменных):
head := Nil;
For i:=n DownTo 1 Do
q^.Inf := i*i;
q^.Next := head;
head := q;
После создания этого списка значением переменной head будет являться ссылка на его первый элемент. Прочитаем созданный список – выведем на экран информационные поля его элементов, начиная с первого:
q := head; указатель – на первый элемент списка
While (q<>Nil) Do пока ссылка не пустая (последний элемент)
Write(q^.Inf:6); выводим значение очередного элемента
q := q^.Next; делаем шаг по списку – берем следующий элемент
В данном случае при выполнении цикла While значением указателя q будут являться поочередно ссылки на первый, второй, третий и т.д. элементы списка, и, наконец, Nil. Это происходит потому, что после присваивания
q := q^.Next;
значением переменной q будет или ссылка на следующий элемент списка, хранящаяся в ссылочной части этого текущего элемента, или Nil, если достигнут конец списка.
Пользуясь этим способом перехода от предыдущего элемента к последующему, можно просмотреть или весь список от начала до конца, или его часть.
Пример: ввести с клавиатуры последовательность целых чисел (конец ввода – число 0), сформировать из них список, определить количество введенных чисел, вывести список на экран.
Интерфейс:
Первое число: -12
Следующее число: -3
Следующее число: 5
Следующее число: 0
Введено чисел: 3
Введенные числа:
Программа:
Type TPoint = ^TElement;
TElement = Record
Inf: Integer;
Next: TPoint;
Var head, q : TPoint;
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; ссылку – на следующий элемент
Основное преимущество связных списков перед статическими структурами данных, например, массивами, заключается в том, что их можно изменять, включая в них новые элементы или исключая ненужные, причем эти операции могут производиться в любом месте списка.
Пусть имеется связный список из трех чисел: 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), каждый раз выводя новый список на экран.
New(head);
Список начнем строить с последнего элемента, равного -12 : определим для него место в памяти и информационную часть:
Сейчас этот элемент является первым (и пока единственным), поэтому одновременно и последним элементом списка. Поэтому ссылочная часть его должна быть равна head, имеющему значение Nil – за этим элементом других элементов нет:
а переменная head должна уже содержать ссылку на этот первый созданный элемент списка:
New(q);
При этом в памяти сохраняется уже созданный элемент списка, ссылка на который хранится в head :
q^.Next := head;
а в освободившуюся переменную head поместим ссылку на него – новый первый элемент списка (эта переменная всегда должна указывать на голову списка):
New(q);
New(r);
r^.Next := q^.Next;
q^.Next := r;