- •1 Линейные односвязные списки
- •2 Создание, просмотр и уничтожение списка
- •3 Добавление элемента в список
- •4 Перемещение элементов списка
- •Упражнения
- •5 ВсТаВка и удаление элементов списка
- •Упражнение
- •6 Поиск элемента в списке
- •7 Вставка и удаление элемента
- •Упражнение
- •Упражнения
- •8 Сортировка списка
- •9 Рекурсивные подпрограммы обработки списка
- •Упражнение
- •Упражнения
- •Упражнение
- •10 ЗаДаЧи
- •10.1 Нерекурсивные подпрограммы
- •10.2 Рекурсивные подпрограммы
- •Литература
СОДЕРЖАНИЕ
ЛИНЕЙНЫЕ ОДНОСВЯЗНЫЕ СПИСКИ
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;
Замечание. Проверку файла на пустоту в теле процедуры можно опустить, если известно или проверяется в вызывающей программе, что файл не пуст.