Файл: Технол_разраб_прогр_обесп_Гагарина_Кокарева.doc

Смещение (байт)

Представление байта в машинной памяти (номера разрядов)

> + 0

@S + 31

Рис. 3.7. Представление множества в памяти: @S — адрес данного типа множество

Размер памяти (в байтах), выделяемых под множество, вычисляется по формуле: 5= (max div 8) - (min div 8) + 1, где max и min — верхняя и нижняя границы базового типа данного множества, a div —- целочисленное деление.

Записи

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

Пример записи — набор сведений о сотруднике кафедры. Объект «сотрудник» может обладать следующими свойствами:

• табельный номер — целое положительное число;

• фамилия-имя-отчество — строка символов и т. д.;

• пол — символ;

• ученая степень — строка символов;

• заработная плата — вещественное число;

• и др.

В памяти эта структура может быть представлена в одном из двух видов:

• в виде последовательности полей, занимающих непрерывную область памяти (рис. 3.8). Чтобы получить доступ к любому элементу записи, нужно знать адрес начала записи и смещение относительно начала. При этом достигается экономия памяти компьютера, но затрачивается лишнее время на вычисление адресов полей;

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

Рис. 3.8. Представление в памяти переменной типа запись в виде последовательности полей

Дескриптор записи

Рис. 3.9. Размещение в памяти переменной типа запись в виде указателей

33.4. Полу статические структуры данных

Свойства полустатических структур данных:

• они имеют переменную длину и простые способы ее изменения;

• изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

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

К полустатическим структурам относятся стеки, очереди, деки,строки.

33.5. Динамические структуры данных

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

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

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

С помощью связного представления данных обеспечивается высокая изменчивость структуры. Достоинства динамических структур:

• размер структуры ограничивается только объемом памяти компьютера;

• при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей.

С другой стороны, такие структуры обладают рядом недостатков:

• работа с указателями требует высокой квалификации программиста;

• на указатели расходуется дополнительная память;

• дополнительный расход времени на доступ к элементам связной структуры.

Связные линейные списки

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

На рис. 3.10 приведена структура односвязного списка. Здесь поле INF — информационное поле, содержащее данные, NEXT — указатель на следующий элемент списка. Голова списка — указатель на начало списка. Указатель на следующий элемент последнего элемента списка содержит значение nil, это является признаком последнего элемента.

Рис. 3.10. Структура односвязного списка

Двусвязные списки

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

Модуль характеризуют:

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

• функциональная завершенность. Модуль выполняет набор определенных операций для реализации каждой отдельной функции, достаточных для завершения начатой обработки данных;

• логическая независимость. Результат работы данного фрагмента программы не зависит от работы других модулей;

• слабые информационные связи с другими программными модулями. Обмен информацией между отдельными модулями должен быть минимален;

• размер и сложность программного элемента в разумных рамках.

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

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

3.4.2. Основные характеристики программного модуля

Как разработать хороший модуль, который действительно будет способствовать упрощению программы?

В литературе приводятся различные критерии оценки приемлемости модуля. Были предложены следующие критерии:

• хороший модуль снаружи проще, чем внутри;

• хороший модуль проще использовать, чем построить. Предлагается использовать следующие характеристики программного модуля для оценки его приемлемости: размер модуля,

прочность модуля, сцепление с другими модулями и рутинность модуля.

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

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

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

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

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

• данным;

• образцу;

• управлению;

• внешним ссылкам;

• общей области данных;

• содержимому.

Худшим видом сцепления модулей является сцепление по содержимому. Таким является сцепление двух модулей, когда один из них имеет прямые ссылки на содержимое другого модуля (например, на константу, содержащуюся в другом модуле). Такое сцепление модулей недопустимо.

Не рекомендуется использовать также сцепление по общей области — это такое сцепление модулей, когда несколько модулей используют одну и ту же область памяти.

Сцепление по образцу предполагает, что модули обмениваются данными, объединенными в структуры. Этот тип обеспечивает неплохие характеристики по сравнению с предыдущими. Недостаток заключается в том, что конкретные передаваемые данные «спрятаны» в структуры, и потому уменьшается «прозрачность» связи между модулями. Кроме того, при изменении структуры передаваемых данных необходимо модифицировать все использующие ее модули.

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

Сцепление по внешним ссылкам предполагает, что модули ссылаются на один и тот же глобальный элемент данных [1].

Единственным видом сцепления модулей, который рекомендуется для использования современной технологией программирования, является сцепление по данным (параметрическое сцепление) — это случай, когда данные передаются модулю либо при обращении к нему как значения его параметров, либо как результат его обращения к другому модулю для вычисления некоторой функции. Такой вид сцепления модулей реализуется на языках программирования при использовании обращений к процедурам (функциям).

Рутинность модуля — это его независимость от предыстории обращений к нему. Модуль будем называть рутинным, если ре-

7888

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

• всегда следует использовать рутинный модуль, если это не приводит к плохим сцеплениям модулей;

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

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

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

Различают следующие виды связности (в порядке убывания уровня) [1]:

• функциональную;

• последовательную;

• информационную (коммуникативную);

• процедурную;

• временную;

• логическую;

• случайную.

При функциональной связности модуль предназначен для выполнения одной функции. Его исходные данные и операции предназначены для решения одной конкретной задачи. Такой _модуль имеет максимальную связность и, как следствие, хорошую технологичность (простота компиляции, тестирования, со-_провождения).

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

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

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

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

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

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

В табл. 3.1 представлены характеристики различных видов связности по экспертным оценкам [1, 62, 63].

Таблица 3.1. Сравнительные характеристики различных видов связности

Анализ табл. 3.1 показывает, что при проектировании программных модулей лучше всего использовать функциональную, последовательную и информационную связности.

3-4.3. Модульная структура программных продуктов

Модульная структура программы представляет собой древовидную структуру, в узлах которой размещаются программные модули, а направленные дуги показывают статическую подчиненность модулей. Если в тексте модуля имеется ссылка на другой модуль, то их на структурной схеме соединяет дуга, которая исходит из первого и входит во второй модуль. Другими словами, каждый модуль может обращаться к подчиненным ему модудям. При этом модульная структура программной системы, кро-структурной схемы, должна включать в себя еще и совокупность спецификаций модулей, образующих эту систему [37].

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

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

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

2. принятие основных решений в алгоритме выносится на максимально высокий по иерархии уровень;

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

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

Например, при разработке СУБД используются следующие программные модули:

1) экранные формы ввода и/или редактирования информа-
ции базы данных;

2. отчеты;

3. макросы;

4. стандартные средства для обработки информации;

5. меню для выбора функции обработки и др.

3.4.4, Методы разработки при модульном программировании

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

Существуют разные методы разработки модульной структуры Программы, в зависимости от которых определяется порядок программирования и отладки модулей, указанных в этой структуре. Обычно в литературе обсуждаются два метода [42, 46]: метод восходящей разработки и метод нисходящей разработки.

Метод восходящей разработки

Сначала строится древовидная модульная структура программы. Затем поочередно проектируются и разрабатываются модули программы, начиная с модулей самого нижнего уровня, затем предыдущего уровня и т. д. То есть модули реализуются в таком порядке, чтобы для каждого программируемого модуля были уже запрограммированы все модули, к которым он может обращаться. После того как все модули программы запрограммированы, производится их поочередное тестирование и отладка в таком же восходящем порядке. Достоинство метода заключается в том, что каждый модуль при программировании выражается через уже запрограммированные непосредственно подчиненные модули, а при тестировании использует уже отлаженные модули. Недостатки метода восходящей разработки заключаются в следующем:

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

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

• головной модуль проектируется и реализуется в последнюю очередь, что не дает продемонстрировать его заказчику для уточнения спецификаций.

Метод нисходящей разработки

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

нисходящем порядке. При таком порядке разработки программы вся необходимая глобальная информация формируется своевременно, т. е. ликвидируется весьма неприятный источник просчетов при программировании модулей. Существенно облегчается и тестирование модулей, производимое при нисходящем тестировании программы. Первым тестируется головной модуль программы, который представляет всю тестируемую программу, при этом все модули, к которым может обращаться головной, заменяются их имитаторами (так называемыми «заглушками» [45]). Каждый имитатор модуля является простым программным фрагментом, реализующим сам факт обращения к данному модулю с необходимой для правильной работы программы обработкой значений его входных параметров и с выдачей, если это необходимо, подходящего результата. Далее производится тестирование следующих по уровню модулей. Для этого имитатор выбранного для тестирования модуля заменяется самим модулем, и добавляются имитаторы модулей, к которым может обращаться тестируемый модуль. При таком подходе каждый модуль будет тестироваться в «естественных» состояниях информационной среды, возникающих к моменту обращения к этому модулю при выполнении тестируемой программы. Таким образом, большой объем «отладочного» программирования заменяется программированием достаточно простых имитаторов используемых в программе модулей.

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

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

Спецификация программы (головного модуля)

Текст головного модуля

Спецификация 3-й подзадачи

Текст головного

модуля 1-й подзадачи

Текст головного

модуля 3-й подзадачи

Спецификация 2-й подзадачи

Текст головного

модуля 2-й подзадачи

Спецификация 2.1-й подзадачи

Спецификация 2.2-й подзадачи

Рис. 3.13. Второй шаг формирования модульной структуры программы при конструктивном подходе

вом. В результате к дереву добавляются очередные уровни, как показано на рис. 3.13.

Архитектурный подход

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

Нисходящая реализация

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

Целенаправленная конструктивная реализация

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

Подводя итог сказанному, на рис. 3.14 представлена общая схема классификации рассмотренных методов разработки структуры программы.

Методы разработки структуры программ

Нисходящие

Восходящие

Классический подход

Классический подход

Классическая нисходящая разработка

Классическая восходящая разработка (не рекомендуется)

Классическая нисходящая реализация

Классическая восходящая реализация (не рекомендуется)

Конструктивный подход

Архитектурный подход

Конструктивная разработка

Архитектурная разработка

Конструктивная реализация

Архитектурная реализация

Рис. 3.14. Классификация методов разработки структуры программ

3.5. Анализ требований и определение спецификаций при структурном подходе

На этом этапе необходимо построить модели ПО во взаимодействии с окружающей средой. Поскольку разные модели описывают проектируемое программное обеспечение с разных сторон, рекомендуется использовать сразу несколько моделей и сопровождать их описаниями. Структурный подход к проектированию программных продуктов предполагает разработку следующих моделей [1, 53]:

• диаграмм потоков данных (DFD — Data Flow Diagrams), описывающих взаимодействие источников и потребителей информации через процессы, которые должны быть реализованы в системе;

• диаграмм «сущность—связь» (ERD Entity-Relationship Diagrams), описывающих базы данных разрабатываемой системы;

• диаграмм переходов состояний (STD — State Transition Diagrams), характеризующих поведение системы во времени;

• функциональных диаграмм (методология SADT);

• спецификаций процессов;

• словаря терминов.

3-5./. Спецификации процессов

Спецификации процессов могут быть представлены в виде псевдокодов, блок-схем алгоритмов, Flow-форм, диаграмм Насей — Шнейдермана или просто краткого текстового описания [1].

При структурном программировании различают три вида вычислительного процесса: линейный, разветвленный и циклический.

Линейная структура — выполнение операторов последовательно.

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

Циклическая структура — многократное выполнение одинаковой последовательности операторов.

Схемы алгоритмов

Для изображения схем алгоритмов разработан ГОСТ 19.701—90 (табл. 3.2).

Действие 1

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

• выбор. Обозначает выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 3.16, а);

• цикл-до. Обозначает повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 3.16, б)',

• цикл с заданным числом повторений (счетный цикл). Обозначает повторение некоторых действий указанное количество раз (рис. 3.16, в).

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