57. Представление данных в оперативной памят

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

Однако выполнение операций добавления и удаления элементов при использовании векторных структур для размещения элементов массивов может потребовать осуществления многократных сдвигов элементов.

Структуры данных в векторном представлении можно размещать как в статической, так и в динамической памяти. Расположение векторных представлений в динамической памяти иногда позволяет существенно увеличить эффективность использования оперативной памяти. Желательно размещать в динамической памяти временные структуры, хранящие промежуточные результаты, и структуры, размер которых сильно зависит от вводимых исходных данных.

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

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

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

58. Представление данных во внешней памяти

Современные операционные системы поддерживают два способа организации данных во внешней памяти: последовательный и с прямым доступом.

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

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

При выборе типа памяти для размещения структур данных следует иметь в виду, что:

• в оперативной памяти размещают данные, к которым необходим быстрый доступ как для чтения, так и для их изменения;

• во внешней – данные, которые должны сохраняться после завершения программы.

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

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

59. Проектирование программного обеспечения, основанное на декомпозиции данных Методикой Джексона

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

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

Разработка структуры программы в соответствии с методикой выполняется следующим образом:

• строят изображение структур входных и выходных данных;

• выполняют идентификацию связей обработки (соответствия) между этими данными;

• формируют структуру программы на основании структур данных и обнаруженных соответствий;

• добавляют блоки обработки элементов, для которых не обнаружены соответствия;

• анализируют и обрабатывают несоответствия, т.е. разрешают «столкновения»;

• добавляют необходимые операции (ввод, вывод, открытие/закрытие файлов и т. п.);

• записывают программу в структурной нотации (псевдокоде).