Сеть - часть 2

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

Рисунок 2.15. Представление сети матрицей инцидентности

Рисунок 2.16. Представление сети векторами смежности

Векторы смежности. Этот вариант представления также матричный (Рисунок 2.16). Все вершины пронумерованы. Каждой вершине соответствует строка матрицы, в которой перечислены номера вершин, смежных с данной.

В качестве примера рассмотрим фрагмент сканера для распознавания вещественных чисел в директивах ассемблера dd, dq, dt. Правило описания этих чисел в виде синтаксической диаграммы приведено в уроке 19 «Архитектура и программирование сопроцессора» учебника. Ему соответствует показанное ниже регулярное выражение и детерминированный конечный автомат (Рисунок 2.17):

(+|-)dd*.dd*e(+|-)dd*

Рисунок 2.17. Грамматика языка описания вещественных чисел в директиве dd и соответствующий ей детерминированный конечный автомат

Программа будет состоять из двух частей:

построение списка — здесь выполняется построение многосвязного списка по заданному регулярному выражению;

обработка входной строки на предмет выяснения того, является ли она правильной записью вещественного числа в директивах ассемблера dd, dq, dt.

При выполнении первого пункта возникает проблема — как задавать элемент многосвязного списка, если в общем случае различные элементы списка могут иметь разное количество связей? Как показано на рисунке, различные состояния имеют разное количество связей. Можно предложить разные подходы к выбору программной реализации этих связей. Выберем следующий. Организуем все исходящие связи каждого конкретного элемента в односвязный список. В этом случае многосвязный список будет содержать элементы двух типов:

описывающие состояния автомата — они организованы в двусвязный список;

описывающие ссылки или переходы от данного состояния к другим состояниям в зависимости от очередного входного символа — эти ссылки организованы в виде односвязных списков для каждого из состояний.

Содержание Назад Вперед