Списки формируются из динамических переменных, которые являются их элементами. Приведем пример описания односвязного списка и выполнения некоторых действий с ним. Опишем типы данных:
Type
list=^element;
element=record
inf:string[20];
next:list
end;
Здесь тип list – является указателем на переменные типа element. Тип element определяет структуру элемента списка, состоящую из информационного поля inf и поля-указателя на следующий элемент next.
Опишем несколько статических переменных типа list, которые будем использовать для того, чтобы зафиксировать первый и последний элементы, а также как вспомогательные:
Var a, b,c:list;
Создадим первый элемент списка и зафиксируем его переменной a – начало списка, переменная b пусть указывает на конец списка:
new(a);
b:=a;
a^.inf:=’perviy’;
a^.next:=nil;
Последняя команда показывает, что элемент является последним, поскольку указатель на следующий элемент – поле next, устанавливается пустым – nil. Добавим к списку еще один элемент, следующий за первым:
new(b^.next);
b:=b^.next;
b^.inf:=’vtoroy’;
b^.next:=nil;
Вторая команда в этой серии выполняет сдвиг указателя b на следующий элемент списка (на него был установлен указатель текущего элемента).
Теперь вставим еще один элемент списка между первым и вторым, для этого используем переменную c:
new(c);
c^.inf:=’poltora’;
c^.next:=a^.next;
a^.next:=c;
Здесь была создана новая динамическая переменная, присвоено значение ее информационному полю, затем был установлен ее указатель на следующий элемент и, наконец, указатель первого элемента передвинут на вновь созданный.
Добавим элемент в начало списка:
new(c);
c^.inf:=’nulevoy’;
c^.next:=a;
a:=c;
Таким образом, мы рассмотрели операции добавления элемента в начало и в конец списка, а также вставку нового элемента между двумя соседними. Кроме того, выяснили, что для движения по списку можно выполнять операции вида b:=b^.next.
Описанные выше структуру данных и операции над ней можно применить при решении следующей задачи.
Задача 1. В текстовом файле содержатся значения вещественных чисел. Сформировать и распечатать список этих значений в порядке их возрастания.
Решение. Будем формировать список из элементов, аналогичных описанным в предыдущем примере. Поместим первое значение из файла в начало списка. Затем, пока файл не закончился будем читать из него следующее значение и выполнять действия в соответствии с условиями: Если первый элемент больше, чем считанный, то поместим считанный элемент в начало списка. В противном случае будем перемещаться по списку пока не найдем элемент больший, чем считанный или не закончится список. Вставим новый элемент в найденную позицию.
Программа | Комментарии |
program sortlist; | |
uses crt; | |
Type | Описание типов данных |
list=^element; | |
element=record | |
fn:real; | |
next:list | |
end; | |
Var | |
f:text; | Описание файловой переменной |
a, b,c:list; | Описание переменных |
n:real; | |
begin | |
clrscr; | Очистка экрана |
assign(f,'infile1.txt'); | Отождествление файловой переменной с файлом |
reset(f); | Открытие файла |
readln(f, n); | Чтение первого значения |
new(b); | Создание первого элемента списка |
c:=b; | |
b^.next:=nil; | |
b^.fn:=n; | |
while not eof(f) do | Чтение данных пока файл не закончился |
begin | |
readln(f, n); | |
b:=c; | b-установлен на начало списка |
new(a); | Создание элемента для включения в список |
a^.fn:=n; | |
if n>c^.fn then | Проверка позиции нового элемента |
begin | |
a^.next:=b; | Добавление элемента в начало списка |
c:=a | |
end | |
else | |
begin | |
while (b^.next^.fn>n)and(b^.next<>nil) do | Пока не найдена позиция или список не кончился |
b:=b^.next; | Двигаемся по списку |
a^.next:=b^.next; | Вставляем новый элемент в найденную для |
b^.next:=a | него позицию |
end | |
end; | |
b:=c; | b-установлен на начало списка |
while b<>nil do | Пока список не закончился |
begin | |
writeln(b^.fn:10:2); | Печатаем значение элемента |
b:=b^.next | Переходим к следующему элементу |
end | |
end. |
Замкнутые списки
Списки можно применять для решения различных задач. Конечно, можно использовать в качестве альтернативной структуры данных массив. Но когда дело касается необходимости вставки элемента в середину такой структуры или же исключения среднего элемента из массива, возникает необходимость смещения других элементов, что требует затрат времени. Кроме того, на основе связных списков можно строить и другие структуры данных. Рассмотрим еще одну задачу.
Задача 2. Круговая считалка. Во входном текстовом файле содержится список имен участников игры, более 6 человек. Игроки становятся в круг. Ведущий читает считалку, состоящую из 24 слов и на каждом 4 слове выводит игрока из круга. Расчет продолжается со следующего игрока. Нужно напечатать имена тех игроков, которые остались в круге.
Решение. Будем формировать список из элементов, аналогичных описанным в предыдущей задаче. Поместим первое значение из файла в начало списка. Затем, пока файл не закончился, будем читать из него следующее значение, и добавлять в конец списка. После завершения данных в файле установим указатель последнего элемента на первый элемент списка. Формирование структуры данных завершено. Она будет выглядеть примерно, так как на рисунке. ‘Ваня’ был первым в файле, а ‘Алена’ – последней.
 |
Для обработки данных установим указатель b на первый элемент списка. Организуем цикл «для», изменяя значение параметра i от 1 до 24. Если i будет кратно 4, то исключим следующий элемент командой b^.next:=b^.next^.next, в противном случае будем передвигать указатель b на следующего участника, выполнив команду b:=b^.next. По завершению цикла «для» в замкнутом списке останется на 6 элементов меньше чем было сначала.
На рисунке ниже показано, как исключается из списка первый элемент – ‘Юра’. Для этого указатель элемента ‘Рома’ переставляется с ‘Юра’ на элемент ‘Миша’.
Распечатаем оставшиеся элементы. Очевидно, что нельзя использовать указатель на первый элемент списка, который был установлен при начале его формирования. Этот элемент мог быть исключен. Будем распечатывать имена участников, начиная с того, на котором закончен расчет. Чтобы не ходить по кругу предварительно установим указатель начала списка на участника, оказавшегося последним при выполнении расчета. Ниже приведен текст программы для этой задачи и комментарии к ней.
Программа | Комментарии |
program ringlist; | |
uses crt; | |
type | |
list=^element; | Описание типа указателя на следующий элемент |
element=record | Описание типа динамических переменных |
fn:string[20]; | Информационное поле – имя |
next:list | Поле – указатель на следующий элемент |
end; | |
var | |
f:text; | Описание файловой переменной |
b, c:list; | Описание статических указателей |
n:string[20]; | |
i:integer; | |
begin | |
clrscr; | |
assign(f,'infile2.txt'); | Отождествление переменной с файлом |
reset(f); | Открытие файла для чтения |
readln(f, n); | Чтение первого значения |
new(b); | Создание первого элемента списка |
c:=b; | Указатель c устанавливается на начало списка |
b^.fn:=n; | Присваивание значения элементу |
while not eof(f) do | Пока файл не закончился |
begin | |
readln(f, n); | Чтение следующего значения |
new(b^.next); | Создание нового элемента |
b:=b^.next; | Перемещение указателя b на новый элемент |
b^.fn:=n; | Присваивание значения новому элементу |
end; | |
b^.next:=c; | Замыкание списка в круг |
b:=c; | Установка b на начало списка |
for i:=1 to 24 do | Цикл «для» |
begin | |
if i mod 4 =0 then b^.next:=b^.next^.next | Исключение 4 элемента |
else b:=b^.next | Смещение на следующий элемент |
end; | |
c:=b; | Указатель c устанавливается на текущий элемент |
repeat | |
writeln(b^.fn); | Печать значения элемента списка |
b:=b^.next | Перемещение на следующий элемент |
until b=c | Проверка возвращения к началу списка |
end. |
Двусвязные списки
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
