СОДЕРЖАНИЕ

ЛИНЕЙНЫЕ ОДНОСВЯЗНЫЕ СПИСКИ

1 Линейные односвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . .	4
2 Создание, просмотр и уничтожение списка . . . . . . . . . . . . . . . . .	6
3 Добавление элемента в список. . . . . . . . . . . . . . . . . . . . . . . . . . . .	10
4 Перемещение элементов списка . . . . . . . . . . . . . . . . . . . . . . . . . .	11
5 Вставка и удаление элементов списка . . . . . . . . . . . . . . . . . . . . . .	13
6 Поиск элемента в списке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	18
7 Вставка и удаление элемента . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	19
8 Сортировка списка . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	22
9 Рекурсивные подпрограммы обработки списка . . . . . . . . . . . . . .	24
10 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	31
10.1 Нерекурсивные подпрограммы. . . . . . . . . . . . . . . . . . . . . . . .	31
10.2 Рекурсивные подпрограммы. . . . . . . . . . . . . . . . . . . . . . . . . .	33
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	35

1 Линейные односвязные списки

Линейный список – последовательность, состоящая из линейно упорядоченных элементов, каждый из которых характеризуется одним и тем же набором полей.

В односвязном линейном списке каждый элемент (звено списка) содержит поле (или поля) с информацией и поле указателя со значением адреса следующего элемента. Одно из информационных полей или единственное поле информации играет роль идентифицирующего ключа (key). Поле указателя последнего элемента содержит значение nil. Стандартная константа nil означает, что эта ссылка не указывает ни на какую память.

Список определяется указателем списка – указателем на начало списка (первое звено списка).

Основные операции над списками будут рассмотрены на примере списка целых чисел. Звено списка имеет тип rec , а указатель на звено – тип link:

type link=^rec;

rec=record

inf:integer; {поле информации}

next:link {указатель на следующий элемент}

end;

Указатель start типа link содержит адрес начала списка (первого звена).

Основные операции над списками:

– создание пустого списка;

– добавление элемента в начало списка;

– добавление элемента в конец списка;

– построение списка добавлением элемента в начало списка (порядок элементов в списке будет обратным порядку их добавления в список);

– построение списка добавлением элемента в конец списка (порядок элементов в списке будет соответствовать порядку их добавления в список);

– просмотр списка ( проход по списку с выдачей значений информационных полей списка );

– уничтожение списка ( проход по списку с удалением элемента списка );

– перемещение элементов списка;

– вставка (включение) элементов в заданное место списка;

– удаление из списка элементов с заданными свойствами;

– поиск в списке элемента с заданным свойством;

– упорядочение элементов списка (сортировка списка).

Все операции над списками реализуются в виде подпрограмм (процедур или функций). Параметр подпрограммы start (указатель списка) задается как параметр–значение в тех случаях, когда адрес первого элемента списка остается неизменным (хотя внутри списка ссылки могут меняться, как и значения полей первого и остальных элементов списка). Параметр start задается как параметр–переменная (с ключом var), если в подпрограмме значение указателя start может меняться и это изменение должно быть передано в вызывающую программу.

2 Создание, просмотр и уничтожение списка

Пример 2.1 Создать (построить) список добавлением элементов в начало списка. Информация вводится с клавиатуры.

Выдать значения информационного поля списка.

program List;

type link=^rec;

rec=record

inf:integer;

next:link;

end;

var start:link;

procedure Create_1(var start:link); {создание списка}

var p:link; {указатель на текущий элемент списка}

i,n:integer;

begin

start:=nil;

write('Число элементов списка =');

readln(n);

writeln('Введите значения элементов списка:');

for i:=1 to n do

begin

new(p);

read (p^.inf);

p^.next:=start;

start:=p

end

end;

procedure View(start:link); {просмотр списка}

begin

while start<>nil do

begin

write(start^.inf,' ');

start:=start^.next

end;

writeln

end;

procedure Del_List(var start:link); {уничтожение списка}

var p:link; {указатель на текущий элемент списка}

begin

while start<>nil do

begin

p:=start;

start:=start^.next;

dispose(p)

end

end;

begin

Create_1(start);

writeln('Список:');

View (start);

Del_List(start);

if start=nil then {проверка списка на пустоту}

writeln('Список удален')

end.

Пример 2.2 Создать (построить) список добавлением элементов в конец списка. Информация содержится в текстовом файле.

procedure Create_2(var start:link; var f:text);

var p, {указатель на текущий элемент списка}

q:link; {указатель на новый элемент}

begin

start:=nil;

while not eof (f) do

begin

new(q);

read(f,q^.inf);

if start = nil then

start:=q

else p^.next:=q;

p:=q

end;

if start <> nil then

p^.next:=nil

end;

Другой вариант создания списка добавлением элементов в конец списка реализован в виде процедуры Create_3.

procedure Create_3(var start:link; var f:text);

var p, {указатель на текущий элемент списка}

q:link; {указатель на новый элемент}

begin

if eof (f) then start:=nil

else

begin

new(start);

read(f, start^.inf);

p:=start;

while not eof (f) do

begin

new(q);

read(f,q^.inf);

p^.next:=q;

p:=q

end;

p^.next:=nil

end

end;

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