2.3. Как строить структуры данных

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

Определенные и описанные в разд. 2.2 три конструкции данных можно комбинировать бесчисленными способами, формируя полные структуры данных. Например, рассмотрим файл данных, представленный на рис. 2.13.

Рис. 2.13. Файловая структура данных.

ФАЙЛ Г - это последовательность, которая представляет собой ЗАГОЛОВОК, за которым следует ТЕЛО ФАЙЛА, а затем ЗАВЕРШИТЕЛЬ строго в указанном порядке. ЗАГОЛОВОК представляет собой выбор из либо компонента Н1 типа ЗАГОЛОВОК, либо компонента Н2 типа ЗАГОЛОВОК. Повторение ТРАНЗАКЦИИ (нуль или более транзакций) образует ТЕЛО ФАЙЛА и аналогично ЗАВЕРШИТЕЛЬ является повторением компонента Z. Автор использовал свою личную нотацию в виде числа 8 в круглых скобках рядом с повторяемым блоком, чтобы указать, что ЗАВЕРШИТЕЛЬ фактически состоит из восьми символов 2. ТРАНЗАКЦИЯМИ являются все выборы из вклада и изъятия.

Все компоненты самого низкого уровня, которые не разлагаются на подкомпоненты, считаются ЭЛЕМЕНТАРНЫМИ. на рис. 2.13 это компоненты НІ, Н2, ВКЛАД, ИЗЪЯТИЕ и 2.

Конечно, каждый из этих компонентов вполне может обладать своей собственной детальной структурой, которую можно было бы представить комбинацией из одной или более основных конструкций. Например, компонент «ВКЛАД» можно составить так, как показано на рис. 2.14.

Рис. 2.14. Структура вклада.

Поскольку все вклады всегда будут иметь одинаковую структуру и каждый вклад будет трактоваться одинаковым образом, может оказаться несущественным описывать ВКЛАД подробнее, чем на рис. 2.13. В другом случае проектировщик структуры данных может просто дойти до нижнего края своего листа бумаги, решит остановиться здесь и перенести подробности ВКЛАДА на следующую страницу. Итак, ЭЛЕМЕНТАРНЫЙ компонент может оказаться таким, потому что его на самом деле нельзя полезным образом разложить дальше или же потому, что с практической или проектной точки зрения оказывается удобным воздержаться от его разложения. Позже мы покажем, как проектные требования к программе приводят к решению, какие компоненты данных можно считать элементарными. Читатель может удивиться, зачем на рис. 2.13 присутствует компонент ТЕЛО ФАЙЛА. Почему бы, например, не изобразить структуру ФАЙЛА ? так, как показано на рис. 2.15?

Это выглядит похоже на последовательность, но не может ею быть, потому что компонент ТРАНЗАКЦИЯ может появиться много раз. Между тем очередные части последовательности должны появляться только по одному разу. Поэтому корректным вариантом структуры данных ФАЙЛ Г является тот, который показан на рис. 2.13. Такое правило применяется из практических соображений. Как мы покажем позже, структуры, данных образуют основу для структур программ.