Занятие 1. Список. Создание списка путем добавления элементов в конец списка. Просмотр списка.

 

Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (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;

 

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