Автоматы как структуры данных

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

Возможные операции над доступными вершинами:

Чтение атрибутов вершины и исходящих из неё стрелок.
Запись новых атрибутов.
Добавить/удалить вершину (стрелку) (с пустыми атрибутами).

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

Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.

До сих пор в реализации абстрактных типов мы старались жёстко зафиксировать некоторую нумерацию компонентов этого типа, связав её с естественной нумерацией самого массива. Такой подход не позволяет эффективно реализовать характерные для динамических типов операции вставки и удаления компонентов. Это хронический дефект массивов даже в их основной роли – хранение последовательностей.

Упражнение. Написать процедуры вставки и удаления символа и слова в тексте.

Дилемма: Либо тратить на не имеющие логического смысла технические сдвиги – дефрагментацию памяти, либо мириться с дырками фрагментированной памяти.

Начальная идея проста – ставить новые компоненты не в конец или начало памяти (массива), а на первое попавшее свободное место.

a₅

a₄

a₁

a₂

a₃

a₆

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

1 2 3 4 5 6 7 8

‘а’

‘н’

‘б’

‘а’

‘н’

2 7 1 8 

5 – индекс 1-й буквы

 - специальное значение – признак конца списка.

Второй вариант – функция предшествования. Получаем понятия прямого, обратного и двукратного списков.

succ succ

последовательность одна, но автоматы разные.