Олимпиадные задачи по программированию (стр. 3 )

Линейные структуры

Представление любой структуры данных начинается с определения ее базового типа. Базовый тип выбирается таким образом, чтобы можно было организовать хранение данных и хранение ссылок на последующий и/или предыдущий элемент. При реализации списковых структур на языке программирования Паскаль за базовый тип принято брать тип-запись. Описание простейшего связанного списка будет выглядеть следующим образом:

Листинг 1.

Type

Point = ^Node; {указатель на элемент Node}

Node = Record {тип элемента структуры (Node)}

Data: Char;

Link: Point;

End;

Здесь Point является указателем на запись Node, состоящую из двух полей Data и Link, причем Data – это данные, которые будут храниться в данном узле списка символьного типа, а Link – это указатель на следующий элемент из списка (его тип – указатель). Нужно отметить, что данное описание подходит не только для связанных списков, но и для тех списковых структур, у которых есть одна ссылка на следующий элемент, т. е. стек, очередь, дек. Для таких структур как двухсвязный список в это описание базового типа следует добавить ссылку на предыдущий элемент, т. е.:

Листинг 2.

Type

Point = ^Node;

Node = Record

Data: Char;

Prev, Next: Point; {Prev –предыдущий,

Next – следующий элемент}

End;

Теперь, когда мы описали структуру узлов, необходимо (в соответствии с определением структуры данных) задать операции над этими узлами. Рассмотрим операции добавления и исключения узлов на примере односвязного списка.

Как и договорились, создадим связанный список при помощи описания, приведенного на листинге 1, и опишем операцию включения нового узла. Для того, чтобы присоединить новый узел, нам необходимо зарезервировать участок памяти для размещения новой динамической переменной. А затем установить соответствующие связи. Это можно сделать следующим образом (листинг 3).

Листинг 3.

В процедурах вставки и удаления узлов используются следующие параметры: x – данные, которые хранятся в поле data, PoE – указатель на конец списка.

procedure Ins_Node(x: char; var PoE: point);

var r: Point;

begin

new (r); {выделить память для нового узла}

r^.data:=x; {присваивается значение полю data}

r^.link:=PoE; {в поле связи заносится ссылка на

следующий узел}

PoE:=r; {указатель конца списка

устанавливается на новый элемент}

end;

procedure Del_Node(var x: char; var PoE: point);

var r:Point;

begin

if PoE^.Link<>Nil then

begin

r:=PoE^.link;

x:=PoE^.data;

dispose (PoE);

PoE:=r;

end

else writeln (' Список пуст ');

end;

Нужно отметить, что процедура Ins_Node позволяет нам вставлять новый узел только последним в списке. Чаще встречается задача, в которой требуется вставить узел не нарушая упорядоченности списка. В этом случае данная процедура становится не пригодной для использования. Рассмотрим пример, в котором данный недостаток устраняется.

Пример.

Дана последовательность натуральных чисел, расположенных в порядке возрастания. Требуется вставить новый элемент таким образом, чтобы он не нарушал порядка в списке. (Приведем полное решение этой задачи).

Листинг 4.

Program Spisok;

Type

Point=^Node;

Node=Record

Data: Integer;

Link: Point;

End;

Var

procedure Ins_Node(x: char; var PoE: point);

procedure Del_Node(var x: char; var PoE: point);

Begin

End.

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

Листинг 5.

unit Stack;

interface

type

Point=^noid;

noid=record

data: char;

link: point;

end;

procedure Push(x: char; var PoE: point);

procedure Pop(var x: char; var PoE: point);

function Empty (PoE: point): boolean;

implementation

procedure Push;

var r: Point;

begin

new (r);

r^.data:=x;

r^.link:=PoE;

PoE:=r;

end;

procedure Pop;

var r:Point;

begin

if not Empty (PoE) then

begin

r:=PoE^.link;

x:=PoE^.data;

dispose (PoE);

PoE:=r;

end

else writeln (' Стек пуст ');

end;

function Empty;

begin

if PoE=nil then Empty:=true else Empty:=false;

end;

end.

Нелинейные структуры (деревья)

Особенно интересными динамическими структурами данных являются упорядоченные двоичные деревья. Дерево состоит из узлов и ветвей, за которыми вновь следуют узлы. Узлы, в которые не входит ни каких ветвей, называются корневыми. Узлы, из которых не выходит ветвей, называют листьями. Тем самым можно строить иерархические отношения. Каждый узел состоит из части, содержащей данные (например, элемент Key, позволяющий однозначно идентифицировать узел), и указателя, показывающего на следующий узел.

Мы рассмотрим наиболее часто используемые – бинарные деревья. Подобное дерево можно описать, например, таким образом:

type BTree=^Node;

Node= record

Left: BTree;

Key: integer;

Right: BTree;

end;

Если для каждого узла выполняется правило, что все левые примыкающие к этому узлу узлы меньше (то есть имеют меньший ключ), а все правые узлы больше, то такое бинарное дерево называют упорядоченным. В силу своего свойства упорядоченности применение подобных деревьев для поиска исключительно удобно. Их также называют поисковыми деревьями или деревьями поиска.

Как было описано выше, существует три способа просмотра всех узлов дерева: Preorder, Inorder, Endorder. Программирование всех трех способов требует знания рекурсии, так, например, для того чтобы просмотреть дерево в обратном порядке (Inorder), нам понадобится следующая процедура (листинг 6.).

Листинг 6.

procedure Inorder (b: BTree; t: integer);

begin

if b=Nil then writeln (' Дерево пусто ')

else with b^ do

begin

t:=t+1;

if left<>Nil then Inorder (left, t);

writeln (' ':4*t, key:4);

if right<>Nil then Inorder (right, t);

t:=t-1;

end;

end;

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

В заключение рассказа о реализации деревьев, приведем листинг исходного кода модуля TREES. TPU, в котором собраны несколько функций для работы с деревьями (листинг 7.).

Листинг 7.

unit Trees;

interface

type BTree=^Node;

Node= record

Left: BTree;

Key: integer;

b: integer;

Right: BTree;

end;

Procedure Inorder (b: BTree; t: integer);

Procedure Del_tree (var b: Btree);

Procedure Print_tree(b: BTree; t: integer);

procedure Zapoln(var b: BTree; k: integer);

implementation

procedure Inorder;

begin

if b=Nil then writeln (' Tree is empty ')

else with b^ do

begin

t:=t+1;

if left<>Nil then Inorder (left, t);

writeln (' ':4*t, key:4);

if right<>Nil then Inorder (right, t);

t:=t-1;

end;

end;

procedure Del_tree;

begin

if b<>Nil then

begin

if b^.right<>Nil then Del_tree(b^.right);

if b^.left<>Nil then Del_tree(b^.left);

dispose (b);

end;

end;

procedure Print_tree;

var i: integer;

begin

if b<>Nil then

with b^ do

begin

Print_tree (left, t+1);

writeln (' ':t*4, key:4);

Print_tree (right, t+1);

end;

end;

procedure Zapoln;

begin

if b=Nil then

begin

new (b);

with b^ do

begin

left:=Nil; key:=k; right:=Nil;

end;

end

else

with b^ do

begin

if key<k then Zapoln(left, k);

if key>k then Zapoln(right, k);

end;

end;

end.

Двоичные деревья являются хорошими структурами данных для получения упорядоченных множеств данных, поскольку позволяют хранить их отсортированными, а также для проведения поиска. В данной работе не будут описываться реализация алгоритмов поиска на языке программирования Pascal, т. к. их реализация представляется очень простой и легкодоступной даже для начинающего программиста.

Метод динамического программирования

Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач с меньшей размерностью и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. Преимущество динамического программирования заключается в том, что любая подзадача решается один раз, ее решение сохраняется и никогда не вычисляется заново.

В том случае, когда исходная задача определяется одним параметром N, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение Fk задачи размерности k для всех k, меньших N, и хотим получить решение для k, равного N. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N. В частности, зная решения задач F0, F1, …, Fs, вычисляем в цикле решения Fs+1, Fs+2 и т. д. до искомого решения FN.

Задачи, решение которых основано на использовании метода динамического программирования, зачастую требуют только правильного применения основной идеи этого метода. После этого нужна только аккуратная реализация алгоритма. Сложно выделить какие-то общие ошибки или проблемы, возникающие в таких задачах. Все же отметим, что часто «лобовое» применение принципа динамического программирования не укладывается в ограничения, например, по памяти (такие задачи требовательны к памяти, ведь мы экономим время работы, в том числе за счет хранения промежуточных результатов). Поэтому, возможно, потребуется аккуратная реализация хранения большого количества данных (динамическая память, структуры данных).

Сортировка и ее виды. Применимость алгоритмов к различным входным данным

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