Учебные материалы к элективным курсам по информатике дляклассов, выпуск 1 (стр. 3 )

Списки можно применять для решения различных задач. Конечно, можно использовать в качестве альтернативной структуры данных массив. Но когда дело касается необходимости вставки элемента в середину такой структуры или же исключения среднего элемента из массива, возникает необходимость смещения других элементов, что требует затрат времени. Кроме того, на основе связных списков можно строить и другие структуры данных. Рассмотрим еще одну задачу.

Задача 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.

Двусвязные списки

Кроме односвязных списков, можно строить также и двусвязные. В такой структуре данных каждый элемент имеет указатели на оба соседних. То есть в описании типа элемента добавляется еще одно поле. Например, описание может выглядеть следующим образом:

Type

list=^element;

element=record

inf:string[20];

ukl, ukr:list

end;

У первого элемента указатель ukl будет равен nil, а у последнего элемента значение nil будет иметь указатель ukr.

Эту структуру даны можно применить, например, к решению задачи «Считалка-маятник».

Стеки и очереди

Стек и очередь являются структурами данных, широко применяемыми в стандартных алгоритмах, а также для построения моделей. Эти структуры также как списки являются линейными и определения типов данных для них также совпадают с теми, что применяются для односвязных списков.

Стек или магазин – линейная структура данных, имеющая одно «окно», применяемое для включения в него данных или «вталкивания» и для извлечения данных или «выталкивания». Устройство стека похоже на устройство патронного магазина для пистолета или автомата. Патроны (данные) вталкиваются в магазин при его снаряжении и выталкиваются при перезарядке оружия. При этом первым извлекается патрон, который был вставлен в магазин последним. Таким образом, стек или магазин представляет собой такую структуру, в которой для данных применяется правило «Последний вошел – первый вышел». По-английски это же будет звучать «Last In – Fist Out» или LIFO.

В отличие от стека, очередь следует понимать в обычном бытовом смысле. Очередь – это такая структура, в которой для данных применяется правило «Первый вошел – первый вышел» или по-английски «First In – Fist Out», сокращенно FIFO. Элемент добавляется в хвост очереди, а извлекается из начала.

Рассмотрим простой пример, иллюстрирующий применение стека для вычислений. Пусть нужно вычислить N! – факториал числа N. По определению . Для выполнения вычислений сначала поместим все значения N>0 в стек, а потом вычислим каждое промежуточное значение факториала, умножая предыдущее значение на извлекаемый из стека множитель.

Для работы с данными используем процедуры push – для проталкивания значения в стек и pop – для выталкивания из стека.

Программа	Комментарии
program stekfactorial;
type
stek=^element;	Описание типа указателя на элемент стека
element=record	Описание типа элемента стека
fn:real;	Информационное поле
down:stek	Указатель на предыдущий элемент
end;
Var
b, c:stek;	Описание статических указателей, b – вершина стека
n, i:integer;
nf, g:real;
procedure pop(var x:real);	Процедура выталкивания значения из стека в переменную x
Begin
c:=b;	Запомнили позицию верхнего элемента
x:=b^.fn;	Считали значение из стека
b:=b^.down;	Сместили указатель на следующий элемент в стеке
dispose(c);	Уничтожили извлеченный элемент
end;
procedure push(x:real);	Процедура помещения в стек значения x
Begin
new(c);	Создали новую переменную
c^.fn:=x;	Записали значение в новый элемент стека
c^.down:=b;	Установили указатель на предшествующий элемент
b:=c	Сдвинули указатель вершины стека
end;
Begin
readln(n);	Ввод значения переменной
i:=n;
b:=nil;
while i>=0 do	Цикл «пока» для помещения значений в стек.
Begin
if i=0 then push(1)	Поместить в стек 0!
else push(i);	Проталкивание значения множителя
i:=i-1;	Переход к следующему значению
end;
pop(nf);	Выталкивание значения 0! в переменную nf
while b<>nil do	Пока стек не пуст
Begin
pop(g);	Выталкиваем значение множителя в переменную g
nf:=nf*g	Находим следующее значение факториала
end;
writeln(nf)	Печатаем значение результата
end.

Двоичные деревья