Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil).
Схематически это выглядит так:
Попробуем вместе сформировать небольшой список путем добавления элементов в конец списка.
Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.
Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5, 1 и 9), а в другом поле будет находится адрес следующего за ним элемента.
Примечание. Нужно понимать, что поле данных вообще говоря может содержать в себе сколько угодно полей; это зависит от конкретно поставленной задачи.
Type
Ukazatel = ^S;
S = Record
Data: integer;
Next: Ukazatel;
End;
Таким образом, мы описали ссылочный тип, с помощью которого можно создать наш связанный однонаправленный список.
|
|
Заметим, что все элементы списка взаимосвязаны, т. е. где находится следующий элемент, "знает" только предыдущий. Поэтому самое главное в программе, это не потерять, где находится начало списка. Поэтому на начало списка будем ставить указатель с именем Head и следить за тем, чтобы на протяжении выполнения программы значение этого указателя не менялось.
А теперь опишем переменные для решения нашей задачи:
Var
Head, {указатель на начало списка}
x {вспомогательный указатель для создания очередного элемента списка}
: Ukazatel;
Создадим первый элемент:
New(x); {выделим место в памяти для переменной типа S}
x^.Data:= 3; {заполним поле Data первого элемента}
x^.Next:= Nil; {заполним поле Next первого элемента: указатель в Nil}
Head:= x; {поставим на наш первый элемент указатель головы списка}
Таким образом, к выделенной области памяти можно обратиться через два указателя.
Продолжим формирование списка, для этого нужно добавить элемент в конец списка. Поэтому вспомогательная переменная указательного типа х будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом.
Поэтому можно записать равенства:
Head^.Next = x^.Next;
Head^.Data = x^.Data;
Head = x;
Выделим область памяти для следующего элемента списка.
New(x^.Next);
Присвоим переменной х значение адреса выделенной области памяти, иначе, переставим указатель на вновь выделенную область памяти:
x:= x^.Next;
Определим значение этого элемента списка, иначе, заполним поля:
x^.Data:= 5;
x^.Next:= Nil;
Итак, теперь у нас список содержит два элемента. Понятно, чтобы создать третий и четвертый элементы, нужно проделать те же самые операции.
|
|
Задание. Запишите в тетрадь ответы на вопросы:
1. Какие операции требуется выполнить для вставки в список его элемента?
2. Можно ли для построения списка обойтись одной переменной?
3. Сколько элементов может содержать список?
4. Когда прекращать ввод элементов списка?
5. Запишите в тетрадь рассмотренные операторы и дополните их операторами, создающими третий и четвертый элементы списка (1, 9).
Теперь попробуем подытожить наши рассуждения.Оформим создание списка в виде процедуры, в которой его элементы вводятся с клавиатуры.
Procedure Init(Var u: Ukazatel);
Var
x: Ukazatel;
Digit: integer; {Значение информационной части элемента списка}
Begin
Writeln('Введите список ');
Head:= Nil; {Список пуст}
Writeln ('Введите элементы списка. Конец ввода 0');
Read (Digit);
if Digit <> 0
then {Формируем и вставляем первый элемент списка}
Begin
New(x);
x^.Next:= Nil;
x^.Data:= Digit;
Head:= x
Read (Digit);
while Digit<>0 do
Begin
New(x^.Next); {Формируем и вставляем элемент в конец списка}
x:= x^.Next;
x^.Next:= Nil;
x^.Data:= Digit;
Read(Digit);
End;
Writeln;
End;
Рассмотрите формирование списка несколько другим способом.
Procedure Init(Var u: Ukazatel);
Var
x, y: Ukazatel;
Digit: integer;
Begin
Writeln('Введите список ');
Head:= Nil;
Writeln ('Введите элементы списка. Конец ввода 0');
Read (Digit);
while Digit<>0 do
Begin
New(y);
y^.Next:= Nil;
y^.Data:= Digit;
if u=Nil
then
u:= y
else
x^.Next:= y;
x:= y;
Read(Digit);
End;
Writeln;
End;
Задание. Перепишите эту процедуру в тетрадь, дополните ее комментарием, составьте чертеж и приготовьте учителю подробное объяснение работы данной процедуры.
Просмотр списка
Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть
while p<>Nil do
Begin
Write(p^.Data, ' ');
p:= p^.Next;
End;
Задание. Составьте программу, содержащую процедуру создания списка путем вставки элементов в конец списка и процедуру просмотра списка и вывода на экран его элементов. Процедуры должны содержать параметр, в который передается начало списка. Покажите протестированную программу и листинг учителю для оценки.