- •Конспект лекций
- •Раздел 1. Задача проектирования программных систем Введение. Содержание и задачи курса
- •Задачи и этапы проектирования сложных программных средств
- •Тема 1.1. Технология программирования и основные этапы ее развития
- •1.1.1. Стихийное программирование.
- •1.1.2. Структурное программирование.
- •1.1.3. Объектно-ориентированное программирование.
- •1.1.4. Компоненты и case-технология.
- •1.1.5. Платформа .Net.
- •Тема 1.2. Организация процесса проектирования программного обеспечения (по)
- •1.2.1. Проблемы разработки сложных программных систем.
- •1.2.2. Блочно-иерархический подход к проектированию по.
- •1.2.3. Жизненный цикл по.
- •1.2.4. Процессы жизненного цикла.
- •1.2.5. Модели жизненного цикла по.
- •1.2.6. Оценка качества процессов разработки по.
- •1.2.7. Технология rad.
- •Тема 1.3. Технологичность программных продуктов
- •1.3.1. Понятие технологичности по.
- •1.3.2. Модульное программирование.
- •1.3.3. Нисходящая и восходящая разработка по.
- •1.3.4. Стиль оформления программы.
- •1.3.5. Эффективность и технологичность.
- •Тема 1.4. Определение требований к по
- •1.4.1. Классификация программных систем.
- •1.4.2. Эксплуатационные требования к по.
- •1.4.3. Исследование предметной области.
- •1.4.4. Разработка технического задания.
- •Тема 1.5. Начальный этап проектирования
- •1.5.1. Выбор архитектуры по.
- •1.5.2. Выбор типа пользовательского интерфейса.
- •1.5.3. Выбор подхода к разработке.
- •1.5.4. Выбор средств разработки.
- •1.5.5. Стандарты разработки.
- •Раздел 2. Использование декомпозиции и абстракции при структурном подходе к анализу и проектированию по Тема 2.1. Анализ требований к по и декомпозиция системы при структурном подходе
- •2.1.1. Спецификация процедур и данных при структурном подходе.
- •2.1.2. Диаграммы переходов состояний.
- •2.1.3. Функциональные диаграммы.
- •2.1.4. Диаграммы потоков данных.
- •2.1.5. Абстрактные структуры данных.
- •2.1.6. Математические модели задач.
- •Тема 2.2. Методы проектирования структуры по
- •2.2.1. Структурная схема по.
- •2.2.2. Функциональная схема по.
- •2.2.3. Метод пошаговой детализации.
- •2.2.4. Проектирование по, основанное на декомпозиции данных.
- •2.2.5. Case-технологии на основе структурного подхода.
- •Тема 2.3. Проектирование структур данных
- •2.3.1. Векторная структура.
- •2.3.2. Списковые структуры.
- •2.3.3. Представление данных во внешней памяти.
- •Раздел 3. Использование декомпозиции и абстракции при объектно-ориентированном подходе к анализу и проектированию по Тема 3.1. Анализ требований к по и декомпозиция системы при объектном подходе
- •3.1.1. Язык uml.
- •3.1.2. Диаграммы вариантов использования.
- •3.1.3. Диаграммы классов.
- •3.1.4. Диаграмма последовательностей.
- •3.1.5. Диаграмма деятельностей.
- •Тема 3.2. Проектирование по при объектном подходе
- •3.2.1. Типы классов объектов.
- •3.2.2. Отношения между объектами.
- •3.2.3. Интерфейсы.
- •3.2.4. Проектирование классов.
- •3.2.5. Компоновка программных компонентов.
- •Раздел 4. Разработка по Тема 4.1. Проектирование интерфейса с пользователем
- •4.1.1. Типы пользовательских интерфейсов.
Тема 2.3. Проектирование структур данных
Под проектированием структур данных понимают разработку их представлений в памяти. Основными параметрами, которые необходимо учитывать при проектировании структур данных, являются:
вид хранимой информации каждого элемента данных;
связи элементов данных и вложенных структур;
время хранения данных структуры («время жизни»);
совокупность операций над элементами данных, вложенными структурами и структурами в целом.
Вид хранимой информации определяет тип соответствующего поля памяти. В качестве элементов данных в зависимости от используемого языка программирования могут рассматриваться:
целые и вещественные числа различных форматов;
символы;
булевские значения: true и false;
а также некоторые структурные типы данных, например:
строки;
записи;
специально объявленные классы.
При этом для числовых полей очень важно правильно определить диапазон возможных значений, а для строковых данных - максимально возможную длину строки.
Связи элементов и вложенных структур, а также их устойчивость и совокупность операций над элементами и вложенными структурами определяют структуры памяти, используемые для представления данных. Время жизни учитывают при размещении данных в статической или динамической памяти, а также во внешней памяти.
Различают две базовые структуры организации данных в оперативной памяти: векторную и списковую.
2.3.1. Векторная структура.
Однако выполнение операций добавления и удаления элементов при использовании векторных структур для размещения элементов массивов может потребовать осуществления многократных сдвигов элементов.
Структуры данных в векторном представлении можно размещать как в статической, так и в динамической памяти. Расположение векторных представлений в динамической памяти иногда позволяет существенно увеличить эффективность использования оперативной памяти. Желательно размещать в динамической памяти временные структуры, хранящие промежуточные результаты, и структуры, размер которых сильно зависит от вводимых исходных данных.
2.3.2. Списковые структуры.
Списковые структуры строят из специальных элементов, включающих помимо информационной части еще и один или несколько указателей - адресов элементов или вложенных структур, связанных с данным элементом. Размещая подобные элементы в динамической памяти можно организовывать различные внутренние структуры (рис. 5,15).
Однако при использовании списковых структур следует помнить, что:
для хранения указателей необходима дополнительная память;
поиск информации в Линейных списках осуществляется последовательно, а потому требует больше времени;
построение списков и выполнение операций над элементами данных, хранящимися в списках, требует более высокой квалификации программистов, более трудоемко, а соответствующие подпрограммы содержат больше ошибок и, следовательно, требуют более тщательного тестирования.
Обычно векторное представление используют для хранения статических множеств, таблиц (одномерных и многомерных), например, матриц, строк, записей, а также графов, представленных матрицей смежности, матрицей инцидентности или аналитически [55]. Списковое представление удобно для хранения динамических (изменяемых) структур и структур со сложными связями.
В наиболее ответственных случаях при выборе внутреннего представления целесообразно определять вычислительную сложность [24, 55] выполнения наиболее часто встречающихся операций со структурой данных или ее элементами для различных вариантов. А также оценивать их емкостную сложность.
Например, предложены 10 вариантов внутреннего представления неориентированного графа. Для выбора структуры необходимы исследования - расчет временной сложности указанных операций на уровне машинных команд в тактах микропроцессора для каждого представления и емкостной сложности этих представлений. Анализ результатов показывает, что, если число вершин n<=100, то с точки зрения уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же существенно экономное использование оперативной памяти, то наиболее эффективное представление - массив динамических векторов.