Сеть

Неважно, что кто-то идет неправильно,

возможно, это хорошо выглядит...

Первый закон Скотта (Прикладная Мерфология)

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

Сетью называется кортеж G — (V,E), где V — конечное множество вершин, Е -^ конечное множество ребер, соединяющих пары вершин из множества V. Две вершины и и v из множества V называются смежными, если в множестве Е существует ребро (u, v), соединяющее эти вершины. Сеть может быть ориентированной и неориентированной. Это зависит от того, считаются ли ребра (u, v) и (v, u) разными. В практических приложениях часто ребрам приписываются веса, то есть некоторые численные значения. В этом случае сеть называется взвешенной. Для каждой вершины v в сети есть множество смежных вершин, то есть таких вершин Uj (i = l..n), для которых существуют ребра (v, и:). Это далеко не все определения, касающиеся сети, но для нашего изложения их достаточно, так как его цель — иллюстрация средств ассемблера для работы с различными структурами данных. Поэтому рассмотрим варианты представления сетей в памяти компьютера в виде, пригодном для обработки. Какой из этих вариантов лучше, зависит от конкретной задачи. Мы также не будем проводить оценку эффективности того или иного вида представления.

Матрица смежности. Сеть, имеющую М вершин, можно представить в виде матрицы размерностью МхМ. При условии, что вершины помечены v,, v2,..., vm, значение матрицы ау = 1 говорит о существовании ребра между вершинами v, и v,. Иначе говоря, эти вершины являются смежными. Для ориентированной сети матрица смежности будет симметричной.

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

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

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

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

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

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

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

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

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

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

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

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

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

В случае нелинейной организации двусвязного списка его построение таит ряд проблем. Часть из них снимается при статическом способе построения списка, который для конечных автоматов является наилучшим. При необходимости, используя приведенные ниже структуры, читатель может самостоятельно описать такой список в своем сегменте данных. Далее мы займемся динамическим, более сложным вариантом организации нелинейного списка, реализующим конечный автомат. Напомним, что его задачей является распознавание лексемы — описания шестнадцатеричного числа в директивах ассемблера dd, dq, dt. Для построения нелинейного многосвязного списка разработаем ряд макрокоманд. С их помощью построение проводится в два этапа:

создание двусвязного списка состояний конечного автомата;

создание односвязных списков переходов.

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

;но при необходимости можно создать и доп. кучу с помощью HeapCreate :HANDLE GetProcessHeap (VOID);

call GetProcessHeap

mov Hand_Head.eax :сохраняем дескриптор .запрашиваем и инициализируем блоки памяти из кучи:

xorebx.ebx :здесь будут указатели на предыдущ. элементы

xorecx.ecx ;dl - номер элемента состояния (двоичный) rept N_state

push ecx :LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes);

push type descr ;размер структуры

push 0 :флаги не задаем

push HandJHead ;описатель кучи

call HeapAlloc

mov [eax].prev_state.ebx запоминаем адрес предыдущ. (if ebx=0. то это первый)

movebx.eax запоминаем адрес текущего в ebx

raov [eax].current_state,eax (И в descr.current_state

pop ecx

mov [eax].id_state_state,cl

inc cl endm

указатель на последний элемент списка состояний в поле-указатель на начало списка head

mov head.ebx .восстанавливаем регистры

pop ebx

pop eax endm

Содержание раздела