nextupprevious

Next:.4.2 Язык описания алгоритмов
Up:4 Разработка алгоритмов
Previous:4 Разработка алгоритмов

4.1 Основные типы данных, возникающие при выполнении заданий

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

Определение некоторого абстрактного структурного типа данных предполагает фиксацию всех операций, которые можно использовать для обработки значений данного типа, и всех типов тех компонент структурного типа, которые являются аргументами или результатами указанных операций. Такие операции и типы компонент в дальнейшем будем называть базисными для данного абстрактного типа данных. Реализация абстрактного типа данных состоит в совместном решении задач отображения его на типы данных языка Zonnon и реализации на языке Zonnon его базисных операций. Причем если определяемый тип связан с входными (выходными) данными программы, то дополнительно требуется отобразить его на входной (выходной) файл в естественной для человека форме и реализовать операции во вводу (выводу) значений данного типа.

Например, в алгоритме вхождения всех возможных размещений на шахматной доске не атакующих друг друга восьми ферзей выделенный тип данных состоит из всех таких размещений $N$ ферзей на шахматной доске, что $1 \leq N \leq 8$ и для любого $i, 1 \leq i \leq N, i$-й ферзь находится на $i$-й вертикали. Набор базисных операций этого типа состоит из трех операций проверки (наличия ферзей на доске, наличия атакующих ферзей и возможности перемещения $N$-го ферзя вверх на следующую горизонталь), трех операций получения по имеющемуся размещению ферзей некоторого нового (за счет перемещения $N$-го ферзя на одну горизонталь вверх, за счет снятия с доски $N$-го ферзя и за счет установки $(N+1)$-го ферзя на первую горизонталь), а также операции распечатки доски с размещенными на ней ферзями. Такой тип данных может быть реализован внутри программы с помощью двух переменных: переменной целого типа, хранящей количество ферзей в конфигурации, и переменной типа

array 8 of integer,

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

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

Для списка определены понятия начального, конечного и текущего элементов, а также следующего и предыдущего элементов по отношению к текущему. Текущий элемент -- это тот единственный элемент списка, который в данный момент доступен для обработки.

Базисными операциями над списками являются: создание пустого списка; проверка списка на пустоту; проверка существования предыдущего или следующего элемента (т.е. проверка того, является ли текущий элемент соответственно первым или последним); взятие в качестве текущего первого, последнего, предыдущего или следующего элемента списка; выборка значения текущего элемента; замена текущего элемента на некоторое значение базисного типа; удаление текущего элемента из списка с взятием в качестве текущего предыдущего или следующего элемента; занесение некоторого значения базисного типа в список перед или после текущего элемента.

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

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

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

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

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

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

Рис. 17. Дерево с вершинами $A, B, C, D,$$E, F, G,$$H, I, J, K, L$
($A$ -- корень дерева, $B, D, E, F, G, J, K, L$ -- его листья)

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

Рис. 18. Отношения между вершинами дерева, изображенного на рис. 17 (сплошные линии связывают братьев, волнистые -- отца с сыном, пунктирные -- сына с отцом)

Очень часто используют тип деревьев с более ограниченным набором базисных операций, формулируемых в терминах отношений, определяющих для каждой вершины дерева $p$ не более трех вершин (рис. 17 и 18): отца (если $p$ не корень), старшего сына (если $p$ не лист) и брата (если $p$ не является ни младшим сыном, ни корнем). Этот набор включает операции по проверке, является ли текущая вершина корнем, листом или младшим сыном, и по переходу от текущей вершины к ее отцу, (старшему) сыну и брату, а также операции по изменению текущей вершины, подключению нового или удалению старого отца, сына и брата.

Тип орграфов над некоторыми базисными типами $T$ и $Q$ определяет множество структур, состоящих из списка элементов типа $T$, называемых вершинами, и списка элементов типа $Q$, называемых дугами. Для каждой вершины имеется список всех дуг, исходящих из этой вершины, и список всех дуг, заходящих в эту вершину.

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

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

Тип графов над некоторыми базисными типами $T$ и $Q$ определяет множество структур, состоящих из списка элементов типа $T$, называемых вершинами, и списка элементов типа $Q$, называемых ребрами. Для каждой вершины определен список инцидентных ей ребер, а для каждого ребра -- двухэлементный список из вершин, которые это ребро соединяет.

Набор базисных операций для графов аналогичен соответствующему набору для орграфов.

Типы графов, без кратных ребер, определяемые только над типом вершин $T$, образуют важный подкласс типов графов. Граф такого типа состоит из списка вершин, для каждой из которых определен список вершин графа, смежных с данной.

Next:4.2 Язык описания алгоритмов
Up:4 Разработка алгоритмов
Previous:4 Разработка алгоритмов

© В.Н. Касьянов, Е.В.Касьянова,2004