Список. Создание списка путем добавления элементов в конец списка. Просмотр списка
Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Из определения следует, что каждый элемент списка содержит поле данных (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; |
Выделим область памяти для следующего элемента списка.
Присвоим переменной х значение адреса выделенной области памяти, то есть, переставим указатель на вновь выделенную область памяти:
Определим значение этого элемента списка, то есть, заполним поля:
x^.Data := 5;
x^.Next := Nil; |
Итак, теперь у нас список содержит два элемента. Для того, чтобы создать третий и четвертый элементы, нужно проделать те же самые операции.
Задание. Ответьте на вопросы:
- Какие операции требуется выполнить для вставки в список его элемента?
- Можно ли для построения списка обойтись одной переменной?
- Сколько элементов может содержать список?
- Когда прекращать ввод элементов списка?
- Запишите операторы, создающие третий и четвертый элементы списка (1, 9).
Теперь попробуем подытожить наши рассуждения. Оформим создание списка в виде процедуры, в которой его элементы вводятся с клавиатуры.
|
Procedure Init(Var u : Ukazatel);
Var
x : Ukazatel;
Digit : integer; {Значение информационной части элемента списка}
Begin
Writeln('Введите список ');
u := Nil; {Список пуст}
Writeln ('Введите элементы списка. Конец ввода 0');
Read (Digit);
if Digit <> 0
then {Формируем и вставляем первый элемент списка}
Begin
New(x);
x^.Next := Nil;
x^.Data := Digit;
u := x;
Read (Digit);
while Digit<>0 do
Begin
New(x^.Next); {Формируем и вставляем элемент в конец списка}
x := x^.Next;
x^.Next := Nil;
x^.Data := Digit;
Read(Digit);
End;
End;
Writeln;
End;
|
Рассмотрите формирование списка несколько другим способом.
Procedure Init(Var u : Ukazatel);
Var
x, y : Ukazatel;
Digit : integer;
Begin
Writeln('Введите список ');
u := 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 |
|
