Учебник Технология программирования. Технология программирования
 Скачать 7.85 Mb.
|
|
5.4. Проектирование структур данных Под проектированием структур данных понимают разработку их представлений в памяти. Основными параметрами, которые необходимо учитывать при проектировании структур данных, являются: • вид хранимой информации каждого элемента данных; • связи элементов данных и вложенных структур; • время хранения данных структуры («время жизни»); • совокупность операций над элементами данных, вложенными структурами и структурами в целом. Вид хранимой информации определяет тип соответствующего поля памяти. В качестве элементов данных в зависимости от используемого языка программирования могут рассматриваться: • целые и вещественные числа различных форматов; • символы; • булевские значения: true и false; а также некоторые структурные типы данных, например: • строки; • записи; • специально объявленные классы. При этом для числовых полей очень важно правильно определить диапазон возможных значений, а для строковых данных - максимально возможную длину строки. Связи элементов и вложенных структур, а также неустойчивость и совокупность операций над элементами и вложенными структурами определяют структуры памяти, используемые для представления данных. Время жизни учитывают при размещении данных в статической или динамической памяти, а также во внешней памяти. Рассмотрим существующие варианты внутреннего представления данных, их элементов и связей между ними более подробно. Представление данных в оперативной памяти. Различают две базовые структуры организации данных в оперативной памяти: векторную и списковую. 155 Векторная структура представляет собой последовательность байт памяти, которые используются для размещения полей данных (рис. 5.14). Последовательное размещение организованных структур данных позволяет осуществлять прямой доступ к элементам: по индексу (совокупности индексов) - в массивах или строках или по имени поля - в записях или объектах. Однако выполнение операций добавления и удаления элементов при использовании векторных структур для размещения элементов массивов может потребовать осуществления многократных сдвигов элементов. Структуры данных в векторном представлении можно размещать как в статической, так и в динамической памяти. Расположение векторных представлений в динамической памяти иногда позволяет существенно увеличить эффективность использования оперативной памяти. Желательно размещать в динамической памяти временные структуры, хранящие промежуточные результаты, и структуры, размер которых сильно зависит от вводимых исход- ных данных. Списковые структуры строят из специальных элементов, включающих помимо информационной части еще и один или несколько указателей - адресов элементов или вложенных структур, связанных с данным элементом. Размещая подобные элементы в динамической памяти можно организовывать различные внутренние структуры (рис. 5.15). 156 Однако при использовании списковых структур следует помнить, что: • для хранения указателей необходима дополнительная память; • поиск информации в линейных списках осуществляется последовательно, а потому требует больше времени; • построение списков и выполнение операций над элементами данных, хранящихся в списках, требует более высокой квалификации программистов, более трудоемко, а соответствующие подпрограммы содержат больше ошибок и, следовательно, требуют более тщательного тестирования. Обычно векторное представление используют для хранения статических множеств, таблиц (одномерных и многомерных), например, матриц, строк, записей, а также графов, представленных матрицей смежности, матрицей инцидентности или аналитически [55]. Списковое представление удобно для хранения динамических (изменяемых) структур и структур со сложными связями. В наиболее ответственных случаях при выборе внутреннего представления целесообразно определять вычислительную сложность [24, 55] выполнения наиболее часто встречающихся операций со структурой данных или ее элементами для различных вариантов. А также оценивать их емкостную сложность. Пример 5.3. Разработать внутреннее представление неориентированного графа, над которым в основном выполняют операции определения смежности вершин, определения вершин, смежных данной, и удаления вершины. В [27, 55] предложены 10 вариантов внутреннего представления неориентированного графа, приведенного на рис. 5.16, а. Причем представление в виде матрицы смежности (рис. 5.16, б) использует табличный способ описания связности вершин. Комбинации векторов и односвязных списков (рис. 5.16, в-г) реализуют аналитическое задание графа, а вектор и список n-связных списков напрямую отображают связи вершин. Интересно также, что структуры, изображенные на рис. 5.16. б, в и д, могут быть размещены в статической памяти. Для выбора структуры необходимы исследования. В табл. 5.2 приведены результаты расчета временной сложности указанных операций на уровне машинных команд в тактах микропроцессора для каждого представления и емкостной сложности этих представлений. (Оценка временной сложности выполнялась по методике, предложенной в [27, 55].) Анализ результатов показывает, что, если число вершин n < 100, то с точки зрения уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же существенно экономное использование оперативной памяти, то наиболее эффективное представление - массив динамических векторов. Представление данных во внешней памяти. Современные операционные системы поддерживают два способа организации данных во внешней памяти: последовательный и с прямым доступом. 157 158 159 При последовательном доступе к данным возможно выполнение только последовательного чтения элементов данных или последовательная их запись. Такой вариант предполагается при работе с логическими устройствами типа клавиатуры или дисплея, при обработке текстовых файлов или файлов, формат записей которых меняется в процессе работы. Прямой доступ возможен только для дисковых файлов, обмен информацией с которыми осуществляется записями фиксированной длины (двоичные файлы С или типизированные файлы Pascal). Адрес записи такого файла можно определить по ее номеру, что и позволяет напрямую обращаться к нужной записи. При выборе типа памяти для размещения структур данных следует иметь в виду, что: • в оперативной памяти размещают данные, к которым необходим быстрый доступ как для чтения, так и для их изменения; • во внешней - данные, которые должны сохраняться после завершения программы. Возможно, что во время работы данные целесообразно хранить в оперативной памяти для ускорения доступа к ним, а при ее завершении - переписывать во внешнюю память для длительного хранения. Именно этот способ используют большинство текстовых редакторов: во время работы с текстом он весь или его часть размещается в оперативной памяти, откуда по мере надобности переписывается во внешнюю память. В подобных случаях разрабатывают два представления данных: в оперативной и во внешней памяти. Правильный выбор структур во многом определяет эффективность разрабатываемого программного обеспечения и его технологические качества, поэтому данному вопросу должно уделяться достаточное внимание независимо от используемого подхода. 5.5. Проектирование программного обеспечения, основанное на декомпозиции данных В § 4.5 уже упоминалось, что практически одновременно были предложены методики проектирования программного обеспечения Джексона и Варнье-Орра, основанные на декомпозиции данных. Обе методики предназначены для создания «простых» программ, работающих со сложными, но иерархически организованными структурами данных. При необходимости разработки программных систем в обоих случаях предлагается вначале разбить систему на отдельные программы, а затем использовать данные методики. Методика Джексона. При создании своей методики М. Джексон исходил из того, что структуры исходных данных и результатов определяют структуру программы. 160 Методика основана на поиске соответствий структур исходных данных и результатов. Однако при ее применении возможны ситуации, когда на каких-то уровнях соответствия отсутствуют. Например, записи исходного файла сортированы не в том порядке, в котором соответствующие строки должны появляться в отчете. Такие ситуации были названы «столкновениями». Выделяют несколько типов столкновений, которые разрешают по- разному. При различной последовательности записей их просто сортируют до обработки. Более подробно способы разрешения столкновений изложены в [33]. Разработка структуры программы в соответствии с методикой выполняется следующим образом: • строят изображение структур входных и выходных данных; • выполняют идентификацию связей обработки (соответствия) между этими данными; • формируют структуру программы на основании структур данных и обнаруженных соответствий; • добавляют блоки обработки элементов, для которых не обнаружены соответствия; • анализируют и обрабатывают несоответствия, т.е. разрешают «столкновения»; • добавляют необходимые операции (ввод, вывод, открытие/закрытие файлов и т. п.); • записывают программу в структурной нотации (псевдокоде). Пример 5.4. Разработать структуру программы, которая читает записи об успеваемости студентов и формирует список неуспевающих студентов группы. На рис. 5.17 представлены структуры входных и выходных данных программы. Анализ этих структур показывает, что между ними есть соответствия (на рис. 5.17 эти соответствия показаны полужирными дугами). Помимо полного соответствия, имеет место еще частичное соответствие - соответствие, отмечаемое только, если студент имеет задолженности (на рис. 5.17 оно отмечено полужирным пунктиром). Используя найденные полные и неполные соответствия, строим «каркас» программы (затемненные блоки на рис. 5.18). Согласно методике добавляем блоки, которые позволят разрешить «столкновения» (светлые блоки на рис. 5.18). Далее строим полный список операций, которые должна выполнять программа, учитывая, что не каждой записи исходного файла соответствует строка отчета (признак «формировать запись вывода» установлен), и выводить надо названия только тех предметов, по которым у студента есть задолженности (признак «задолженность» установлен): 1 - завершить работу; 2 - открыть входной файл; 3 - открыть выходной файл; 161 4 - закрыть входной файл; 5 - закрыть выходной файл; 6 - вывести заголовок; 7 - вывести завершитель; 8 - ввести запись входного файла; 9 - вывести строку отчета (при включенном состоянии признака «формировать запись вывода»); 10 - очистить буфер вывода; 11 - установить признак «формировать запись вывода»; 12 - сбросить признак «формировать запись вывода»; 13 - поместить в строку вывода ФИО; 14 - установить признак «задолженность»; 15 - сбросить признак «задолженность»; 162 16 - занести название предмета в строку вывода; 17 - стереть название предмета из буфера. Затем определяем местоположение операций обработки (на рис. 5.18 они показаны кружочками с номерами). Результатом является полная структура разрабатываемой программы в нотации Джексона. Далее в соответствии с методикой следует записать алгоритм программы на псевдокоде. 163 Вметодике Джексона предлагается псевдокод, точно соответствующий графической нотации. Он использует следующие конструкции. Последовательность: <Имя> Посл. Выполнить <деиствие 1> Выполнить <деиствие 2> <Имя> конец Выбор: <Имя> Выбор <условие действия 1> Выполнить <действие 1> <Имя> или <условие действия 2> Выполнить <действие 2> <Имя> конец Повторение. <Имя> Повт, пока не <условие действия> Выполнить <действие 1> <Имя> конец С применением этого псевдокода запись алгоритма программы выглядит следующим образом: Составление отчета посл. Открыть входной файл Открыть выходной файл Вывести заголовок отчета Формирование тела отчета повт. пока не конец входного файла. Ввести запись Очистить буфер вывода Сбросить признак «формировать запись вывода» Сбросить признак «задолженность» Вывести в буфер ФИО Обработка данных повт, пока не конец записи Обработка предмета посл. Занести название предмета в строку вывода Обработка предмета конец Обработка оценки выбор если оценка положительна Стереть название предмета из буфера Обработка оценки или если оценка пропуск Установить признак «задолженность» Обработка пропуска выбор если не установлен признак «формировать запись вывода» 164 Установить признак «формировать запись вывода» Обработка пропуска конец Обработка оценки конец Обработка конца записи выбор если установлен признак «формировать запись вывода» Вывести строку отчета Обработка конца записи конец Обработка данных конец Формирование тела отчета конец Вывести завершитель Закрыть входной файл Закрыть выходной файл Завершить работу Составление отчета конец Методика Варнье-Орра. Методика Варнье-Орра базируется на том же положении, что и методика Джексона, но основными при построении программы считаются структуры выходных данных и, если структуры входных данных не соответствуют структурам выходных, то их допускается менять. Таким образом, ликвидируется основная причина столкновений. В примере 5.4 целесообразно поменять местами оценки и названия предметов, чтобы упростить обработку. Однако на практике не всегда существует возможность пересмотра структур входных данных: эти структуры уже могут быть строго заданы, например, если используются данные, полученные при выполнении других программ, поэтому данную методику применяют реже. Как следует из вышеизложенного, методики Джексона и Варнье-Орра могут использоваться только в том случае, если данные разрабатываемых программ могут быть представлены в виде иерархии или совокупности иерархий. 5.6. Case-технологии, основанные на структурных методологиях анализа и проектирования К нашему времени накоплен опыт успешного использования большинства известных методологий структурного анализа и проектирования в соответствующих CASE-средствах. Наибольшее распространение получили методологии [30]: SADT (3,3%), структурного системного анализа Гейна-Сарсона (20,2%), структурного анализа и проектирования Йордана-Де Марко (36,5%), развития систем Джексона (7,7%), развития структурных схем DSSD (Data Structured System Development), Варнье-Oppa (5,8%), анализа и проектирования систем реального времени Уорда-Меллора и Хатли, информационного моделирования Мартина (22,1%). 165 Как видно из приведенных статистических данных, наибольшее применение нашли структурные методологии, использующие диаграммы потоков данных. Это вызвано двумя причинами: • диаграммы потоков данных более детально по сравнению с функциональными диаграммами отображают специфику многочисленных в настоящее время информационных систем: не требуют строгой типизации обрабатываемой информации, предусматривают возможность хранения данных, конкретизируют взаимодействие с внешним миром, предусматривают получение комплексной модели программного обеспечения и т. п.; • разработан метод построения проектных спецификаций (структурных карт Джексона или Костантайна) по диаграммам потоков данных, что позволяет автоматически создавать такие спецификации. В табл. 5.3 представлены данные о моделях, поддерживающих соответствующий пакет, а в табл. 5.4 - нотации представления соответствующей информации. Несмотря на то, что последнее время все большее распространение получают объектно- ориентированные средства разработки программного обеспечения, структурные методологии продолжают совершенствовать. Их ус- Таблица 5.3 Название Фирма Функции Данные События BPWin Logic Works + - - CASE Аналитик Эйтекс + + + CASE/4/0 MicroTOOL + + + DatabaseDesigner Oracle - + - Design/IDEF Meta Software + + - Designer/2000 Oracle + + - EasyCASE Evergreen CASE + + + ERWin Logic Works - + - I-CASE Yourdan CAYENNE + + + Prokit*WORK BENCHMDIS + + - S-Designer Sybase/Powersoft + + - SILVERRun CSA + + + Visible Analyst Workbench Visible Systems + + _ 166 Таблица 5.4 Название Нотация DFD Спецификации Поведение Структурные карты CASE Аналитик Гейн-Сарсон Структурный язык Управляющ ие потоки CASE/4/0 Иордан (расширен- ная) - Уорд- Меллор (c STD) Джексон Designer/2000 Гейн-Сарсон - - Джексон I-CASE Yourdan Гейн- Сарсон, Иордан Структурный язык Уорд- Меллор (c STD) Константайн EasyCASE Иордан 3GL STD Константайн Prokit* WORKBENCH Гейн-Сарсон - - Константайн S-Designer Гейн- Сарсон, Иордан - - Константайн SILVERRun произвольная - Управляющ ие потоки — Visible Analyst WORK BENCH Гейн- Сарсон, Иордан - - Константайн пешно применяют при разработке многих программных продуктов, например, для уточнения требований к системам, основной частью которых являются базы данных, очень часто используют диаграммы потоков данных. |