- •ПРЕДИСЛОВИЕ
- •ВВЕДЕНИЕ
- •1.1. Технология программирования и основные этапы ее развития
- •1.2. Проблемы разработки сложных программных систем
- •1.3. Блочно-иерархический подход к созданию сложных систем
- •1.4. Жизненный цикл и этапы разработки программного обеспечения
- •1.5. Эволюция моделей жизненного цикла программного обеспечения
- •1.7. Оценка качества процессов создания программного обеспечения
- •2. ПРИЕМЫ ОБЕСПЕЧЕНИЯ ТЕХНОЛОГИЧНОСТИ ПРОГРАММНЫХ ПРОДУКТОВ
- •2.1. Понятие технологичности программного обеспечения
- •2.2. Модули и их свойства
- •2.3. Нисходящая и восходящая разработка программного обеспечения
- •2.4. Структурное и «неструктурное» программирование. Средства описания структурных алгоритмов
- •2.5. Стиль оформления программы
- •2.6. Эффективность и технологичность
- •2.7. Программирование «с защитой от ошибок»
- •2.8. Сквозной структурный контроль
- •3.1. Классификация программных продуктов по функциональному признаку
- •3.3. Предпроектные исследования предметной области
- •3.4. Разработка технического задания
- •3.5. Принципиальные решения начальных этапов проектирования
- •4. АНАЛИЗ ТРЕБОВАНИЙ И ОПРЕДЕЛЕНИЕ СПЕЦИФИКАЦИЙ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ СТРУКТУРНОМ ПОДХОДЕ
- •4.1. Спецификации программного обеспечения при структурном подходе
- •4.2. Диаграммы переходов состояний
- •4.3. Функциональные диаграммы
- •4.4. Диаграммы потоков данных
- •4.5. Структуры данных и диаграммы отношений компонентов данных
- •4.6. Математические модели задач, разработка или выбор методов решения
- •5. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ СТРУКТУРНОМ ПОДХОДЕ
- •5.1. Разработка структурной и функциональной схем
- •5.2. Использование метода пошаговой детализации для проектирования структуры программного обеспечения
- •5.3. Структурные карты Константайна
- •5.4. Проектирование структур данных
- •5.5. Проектирование программного обеспечения, основанное на декомпозиции данных
- •6. АНАЛИЗ ТРЕБОВАНИЙ И ОПРЕДЕЛЕНИЕ СПЕЦИФИКАЦИЙ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ ОБЪЕКТНОМ ПОДХОДЕ
- •6.1. UML - стандартный язык описания разработки программных продуктов с использованием объектного подхода
- •6.2. Определение «вариантов использования»
- •6.3. Построение концептуальной модели предметной области
- •6.4. Описание поведения. Системные события и операции
- •7. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ ОБЪЕКТНОМ ПОДХОДЕ
- •7.1. Разработка структуры программного обеспечения при объектом подхода
- •7.2. Определение отношений между объектами
- •7.3. Уточнение отношений классов
- •7.4. Проектирование классов
- •7.5. Компоновка программных компонентов
- •7.6. Проектирование размещения программных компонентов для распределенных программных систем
- •7.7. Особенность спиральной модели разработки. Реорганизация проекта
- •8. РАЗРАБОТКА ПОЛЬЗОВАТЕЛЬСКИХ ИНТЕРФЕЙСОВ
- •8.1. Типы пользовательских интерфейсов и этапы их разработки
- •8.2. Психофизические особенности человека, связанные с восприятием, запоминанием и обработкой информации
- •8.3. Пользовательская в программная модели интерфейса
- •8.4. Классификации диалогов и общие принципы их разработки
- •8.5. Основные компоненты графических пользовательских интерфейсов
- •8.6. Реализация диалогов в графическом пользовательском интерфейсе
- •8.8. Интеллектуальные элементы пользовательских интерфейсов
- •9. ТЕСТИРОВАНИЕ ПРОГРАММНЫХ ПРОДУКТОВ
- •9.1. Виды контроля качества разрабатываемого программного обеспечения
- •9.2. Ручной контроль программного обеспечения
- •9.3. Структурное тестирование
- •9.4. Функциональное тестирование
- •9.5. Тестирования модулей и комплексное тестирование
- •9.6. Оценочное тестирование
- •10. ОТЛАДКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
- •10.1. Классификация ошибок
- •10.2. Методы отладки программного обеспечения
- •10.3. Методы и средства получения дополнительной информации
- •10.4. Общая методика отладки программного обеспечения
- •11. СОСТАВЛЕНИЕ ПРОГРАММНОЙ ДОКУМЕНТАЦИИ
- •11.1. Виды программных документов
- •11.2. Пояснительная записка
- •11.3. Руководство пользователя
- •11.4. Руководство системного программиста
- •11.5. Основные правила оформления программной документации
- •11.6. Правила оформления расчетно-пояснительных записок при курсовом проектировании
- •СПИСОК ЛИТЕРАТУРЫ
•Разбор функции,
•Вычисление значений функции,
•Вывод таблицы,
•Расчет значений функции,
•Построение графика.
Структурные карты Джексона будут рассмотрены вместе с предложенной им методикой проектирования программ, основанной на декомпозиции данных в §5.5. .
5.4. Проектирование структур данных
Под проектированием структур данных понимают разработку их представлений в памяти. Основными параметрами, которые необходимо учитывать при проектировании структур данных, являются:
•вид хранимой информации каждого элемента данных;
•связи элементов данных и вложенных структур;
•время хранения данных структуры («время жизни»);
•совокупность операции над элементами данных, вложенными структурами и структурами в целом.
Вид хранимой информации определяет тип соответствующего поля памяти. В качестве элементов данных в зависимости от используемого языка 'программирования могут рассматриваться:
•целые и вещественные числа различных форматов;
•символы;
•булевские значения: true и false;
атакже некоторые структурные типы данных, например:
•строки;
•записи;
• специально объявленные классы. .
При этом для числовых полей очень важно правильно определить диапазон возможных значений, а для строковых данных - максимально возможную длину строки.
Связи элементов и вложенных структур, а также их устойчивость и совокупность операций
над элементами и вложенными структурами определяют структуры памяти, используемые для представления данных. Время жизни учитывают при размещении данных в статической или динамической памяти, а также во внешней памяти.
Рассмотрим существующие варианты внутреннего представления данных, их элементов и связей между ними более подробно.
Представление данных в оперативной памяти. Различают две базовые структуры организации данных в оперативной памяти: векторную и списковую.
Векторная структура представляет собой последовательность байт памяти, которые используются для размещения полей данных (рис. 5.14). Последовательное размещение организованных структур данных позволяет осуществлять прямой доступ к элементам: по индексу (совокупности индексов) - в массивах или строках или по имени поля - в записях или объектах.
Однако выполнение операций добавления и удаления элементов при использовании векторных структур для размещения элементов массивов может потребовать осуществления многократных сдвигов элементов.
Структуры данных в векторном представлении можно размещать как в статической, так и в динамической памяти. Расположение векторных представлений в динамической памяти иногда позволяет существенно увеличить эффективность использования оперативной памяти. Желательно размещать в динамической памяти временные структуры, хранящие промежуточные результаты, и структуры, размер которых сильно зависит от вводимых исходных данных.
Списковые структуры строят из специальных элементов, включающих помимо информационной части еще и один или несколько указателей-адресов элементов или вложенных структур, связанных с данным элементом. Размещая подобные элементы в динамической памяти можно организовывать различные внутренние структуры (рис. 5.15).
Однако при использовании списковых структур следует помнить, что:
•для хранения указателей необходима дополнительная память;
•поиск информации в линейных списках осуществляется последовательно, а потому требует больше времени;
•построение списков и выполнение операций над элементами данных, хранящимися в списках, требует более высокой квалификации программистов, более трудоемко, а соответствующие подпрограммы содержат больше ошибок и, следовательно, требуют более тщательного тестирования.
Обычно векторное представление используют для хранения статических множеств, таблиц (одномерных и многомерных), например, матриц, строк, записей, а также графов, представленных матрицей смежности, матрицей инцидентности или аналитически [55]. Списковое представление удобно для хранения динамических (изменяемых) структур и структур со сложными связями.
В наиболее ответственных случаях при выборе внутреннего представления целесообразно определять вычислительную сложность [24,55] выполнения наиболее часто встречающихся операций со структурой данных или ее элементами для различных вариантов. А также оценивать
их емкостную сложность. .
Пример 5.3. Разработать внутреннее представление неориентированного графа, над которым в основном выполняют операции определения смежности вершин, определения вершин, смежных данной, и удаления вершины.
В [27,55] предложены 10 вариантов внутреннего представления неориентированного графа, приведённого на рис. 5.16, а. Причем представление в виде матрицы смежности (рис. 5.16, б) использует табличный способ описания связности вершин. Комбинации векторов и односвязных списков (рис. 5.16, в-и) реализуют аналитическое задание графа, а вектор и список n-связных списков напрямую отображают связи вершин. Интересно также, что структуры, изображенные на рис. 5.16, б, в и д, могут быть размещены в статической памяти.
Для выбора структуры необходимы исследования. В табл. 5.2 приведены результаты расчета временной сложности указанных операций на уровне машинных команд в тактах микропроцессора для каждого представления и емкостной сложности этих представлений. (Оценка временной сложности выполнялась по методике, предложенной в [27, 55].)
Анализ результатов показывает, что, если число вершин n ≈ 100, то с точки зрения уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же существенно экономное использование оперативной памяти, то наиболее эффективное представление - массив динамических векторов.
Представление данных во внешней памяти. Современные операционные системы поддерживают два способа организации данных во внешней памяти: последовательный и с прямым доступом.