Главная страница
Навигация по странице:

  • Программа. Инициализировать глобальные значения Вывести заголовок и меню Выполнять Если

  • Шаг 2.

  • Программа. Вывод заголовка и меню Выполнять Если

  • Разбор формулы (Fat; Var Tree)

  • Расчет значений функции (xl, х2, h, Tree; Var X,Y,n) Если

  • 5.3. Структурные карты Константайна

  • 5.4. Проектирование структур данных

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

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

  • 5.5. Проектирование программного обеспечения, основанное на декомпозиции данных

  • Технология программирования - Иванова Г.С.. Г. С. Иванова Технология программирования


    Скачать 9.91 Mb.
    НазваниеГ. С. Иванова Технология программирования
    АнкорТехнология программирования - Иванова Г.С..pdf
    Дата01.02.2017
    Размер9.91 Mb.
    Формат файлаpdf
    Имя файлаТехнология программирования - Иванова Г.С..pdf
    ТипДокументы
    #1685
    КатегорияИнформатика. Вычислительная техника
    страница14 из 28
    1   ...   10   11   12   13   14   15   16   17   ...   28
    Шаг 1. Определяем структуру управляющей программы, которая для нашего случая реализует работу с меню через клавиатуру:
    Программа.
    Инициализировать глобальные значения
    Вывести заголовок и меню
    Выполнять
    Если выбрана Команда
    то Выполнить Команду
    иначе Обработать нажатие клавиш управления
    Все-если
    до Команда=Выход
    Конец.
    Очистка экрана, вывод заголовка и меню, а также выбор Команды - операции сравнительно простые, следовательно, их можно не детализировать.
    Шаг 2. Детализируем операцию Выполнить команду:
    Выполнить Команду:
    Выбор Команда
    Функция:
    Ввести или выбрать формулу Fun
    Выполнить разбор формулы
    Отрезок:
    Ввести значения xl,x2
    Шаг:
    Ввести значения h
    Вид результата:
    Ввести вид_результата
    Выполнить:
    Рассчитать значения функции
    Если Вид_результата=График
    то Построить график
    иначе Вывести таблицу
    Все-если
    Bee-выбор
    Определим, какие фрагменты имеет смысл реализовать в виде подпрограмм. Во-первых, фрагмент Вывод заголовка и меню, так как это достаточно длинная линейная последовательность
    операторов и ее выделение в отдельную процедуру позволит сократить управляющую программу.
    Во-вторых, фрагменты Разбор формулы, Расчет значений функции, Построение графика и Вывод таблицы, так как это достаточно сложные операции. Это - подпрограммы первого уровня, которые определяют структуру программы (рис. 5.5). Определим для этих подпрограмм интерфейсы по данным с основной программой, т. е. списки параметров.
    Подпрограмма Вывод заголовка и меню параметров не предполагает.
    Подпрограмма Разбор формулы должна иметь два параметра: Fun - аналитическое задание функции, Tree - возвращаемый параметр - адрес дерева разбора.
    Подпрограмма Расчет значений функции должна получать адрес дерева разбора Tree, отрезок: значения
    ,
    2 1
    x
    и
    x
    а также шаг h. Обратно в программу она должна возвращать таблицу значений функции Х(n) и Y(n), где n - количество точек функции.
    Подпрограммы Вывода таблицы и Построения графика должны получать таблицу значений функции и количество точек.
    После уточнения имен переменных алгоритм основной программы будет выглядеть следующим образом:
    Программа.
    Вывод заголовка и меню
    Выполнять
    Если выбрана Команда
    то
    Выбор Команда
    Функция:
    Ввести или выбрать формулу Fun
    Разбор формулы (Fat; Var Tree)
    Отрезок:
    Ввести значения xl,x2
    Шаг:
    Ввести значения h
    Вид результата:
    Ввести вид_результата
    Выполнить:
    Расчет значений функции (xl, х2, h, Tree; Var X,Y,n)

    Если Вид_резулытата=График
    то Построение графика(Х, Y, n)
    иначе Вывод та6лицы(Х, Y, n)
    Все-если
    Bсe-выбор
    иначе Обработать нажатие клавиш управления
    Все-если
    до Команда=Выход
    Конец.
    На следующих шагах необходимо выполнить детализацию алгоритмов подпрограмм.
    Детализацию выполняют, пока алгоритм программы не станет полностью понятен. Один из возможных вариантов полной структурной схемы данной программы показан на рис. 5.6.
    Как уже упоминалось в § 2.4, использование метода пошаговой детализации обеспечивает высокий уровень технологичности разрабатываемого программного обеспечения, так как он позволяет использовать только структурные способы передачи управления.
    Разбиение на модули при данном виде проектирования выполняется эвристически, исходя из рекомендуемых размеров модулей (20-60 строк) и сложности структуры (две-три вложенных управляющих конструкции). В принципе в качестве модуля (подпрограммы) можно реализовать решение подзадач, сформулированных на любом шаге процесса детализации, однако определяющую роль при разбиении программы на модули играют принципы обеспечения технологичности модулей, рассмотренные в § 2.2.
    Для анализа технологичности полученной иерархии модулей целесообразно использовать структурные карты Константайна или Джексона.

    5.3. Структурные карты Константайна
    На структурной карте отношения между модулями представляют в виде графа, вершинам которого соответствуют модули и общие области данных, а дугам - межмодульные вызовы и обращения к общим областям данных.
    Различают четыре типа вершин (рис. 5.7):
    • модуль - подпрограмма,
    • подсистема - программа,
    • библиотека - совокупность подпрограмм, размещенных в отдельном модуле,
    • область данных - специальным образом оформленная совокупность данных,, к которой возможно обращение извне.
    При этом отдельные части программной системы (программы, подпрограммы) могут вызываться последовательно, параллельно или как сопрограммы (рис. 5.8).
    Чаще всего используют последовательный вызов, при котором модули, передав управление, ожидают завершения выполнения вызванной программы или подпрограммы, чтобы продолжить прерванную обработку.
    Под параллельным вызовом понимают распараллеливание вычислений на нескольких вычислителях, когда при активизации другого процесса данный процесс продолжает работу (рис.
    5.9, а). На однопроцессорных компьютерах в мультипрограммных средах в этом случае начинается попеременное выполнение соответствующих программ. Параллельные процессы бывают синхронные и асинхронные. Для синхронных процессов определяют точки синхронизации
    - моменты времени, когда производится обмен информацией между процессами. Асинхронные процессы обмениваются информацией только в момент активизации параллельного процесса.
    Под вызовом сопрограммы понимают возможность поочередного выполнения двух одновременно запущенных программ, например, если одна программа подготовила пакет данных для вывода, то вторая может ее вывести, а затем перейти в состояние ожидания следующего
    пакета. Причем в мульпрограммных системах основная программа, передав данные, продолжает работать, а не переходит в состояние ожидания, как изображено на рис. 5.9, б.
    Если стрелка, изображающая вызов, касается блока, то обращение происходит к модулю целиком, а если входит в блок, то - к элементу внутри модуля.
    При необходимости на структурной карте можно уточнить особые условия вызова (рис. 5.10): циклический вызов, условный вызов и однократный вызов - при повторном вызове основного модуля однократно вызываемый модуль не активизируется!
    Связи по данным и управлению обозначают стрелками, параллельными дуге вызова, направление стрелки указывает направление связи (рис. 5.11).
    Структурные карты Константайна позволяют наглядно представить результат декомпозиции программы на модули и оценить ее качество, т. е. соответствие рекомендациям структурного программирования (сцепление и связность).

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

    Модули Расчет значений функции, Вывод таблицы и Построение графика связаны с основной программой по образцу, так как параметры X и Y структурные (массивы), следовательно программа считается сцепленной по образцу.
    Анализ показывает, что количество сцеплений по образцу в программе можно уменьшить, если подпрограмму Расчет значений функции перенести на следующий уровень (рис. 5.13).
    Однако в этом случае при смене вида результата таблица значений будет рассчитываться заново.
    Аналогично можно перенести подпрограмму Разбор функции на более низкий уровень и вызывать ее, например, из подпрограммы Расчет значений функции, но поскольку велика вероятность многократного вычисления значений одной функции на разных интервалах, вряд ли это целесообразно.
    После внесения соответствующих изменений в алгоритм следует определить полную спецификацию модулей. Спецификация должна включать: имя, краткое описание назначения, перечень входных и выходных параметров с указанием типа и области допустимых входных и выходных значений. Затем можно приступать к реализации модулей.
    В соответствии с требованиями нисходящей разработки (комбинированный подход) можно предложить следующий порядок реализации модулей:
    • Основная программа,
    • Вывод окна с текстом,
    • Вывод заголовка и меню,

    • Разбор функции,
    • Вычисление значений функции,
    • Вывод таблицы,
    • Расчет значений функции,
    • Построение графика.
    Структурные карты Джексона будут рассмотрены вместе с предложенной им методикой проектирования программ, основанной на декомпозиции данных в §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, то с точки зрения уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же существенно экономное использование оперативной памяти, то наиболее эффективное представление - массив динамических векторов.
    Представление данных во внешней памяти. Современные операционные системы поддерживают два способа организации данных во внешней памяти: последовательный и с прямым доступом.

    Примечание. В таблице использованы следующие обозначения: n – размерность задачи (количество вершин графа);
    p
    и max
    p
    - среднее и максимальное количество вершин, смежных данной.
    В круглых скобках под выражениями приведены результаты расчета по ним – для n=100,
    10
    ,
    5
    max
    =
    =
    p
    и
    p
    При последовательном доступе к данным возможно выполнение только последовательного чтения элементов данных или последовательная их запись. Такой вариант предполагается при работе с логическими устройствами типа клавиатуры или дисплея, при обработке текстовых файлов или файлов, формат записей которых меняется в процессе работы.
    Прямой доступ возможен только для дисковых файлов, обмен информацией с которыми осуществляется записями фиксированной длины (двоичные файлы С или типизированные файлы
    Pascal). Адрес записи такого файла можно определить по ее номеру, что и позволяет напрямую обращаться к нужной записи.
    При выборе типа памяти для размещения структур данных следует иметь в виду, что:
    • в оперативной памяти размещают данные, к которым необходим быстрый доступ как для чтения, так и для их изменения;
    • во внешней - данные, которые должны сохраняться после завершения программы.
    Возможно, что во время работы данные целесообразно хранить в оперативной памяти для ускорения доступа к ним, а при ее завершении - переписывать во внешнюю память для длительного хранения. Именно этот способ используют большинство текстовых редакторов: во время работы с текстом он весь или его часть размещается в оперативной памяти, откуда по мере надобности переписывается во внешнюю память. В подобных случаях разрабатывают два представления данных: в оперативной и во внешней памяти.
    Правильный выбор структур во многом определяет эффективность разрабатываемого программного обеспечения и его технологические качества, поэтому данному вопросу должно уделяться достаточное внимание независимо от используемого подхода.
    5.5. Проектирование программного обеспечения,
    основанное на декомпозиции данных
    В § 4.5 уже упоминалось, что практически одновременно были предложены методики проектирования программного обеспечения Джексона и Варнье-Орра, основанные на декомпозиции данных. Обе методики предназначены для создания «простых» программ, работающих со сложными, но иерархически организованными структурами данных. При необходимости разработки программных систем в обоих случаях предлагается вначале разбить систему на отдельные программы, а затем использовать данные методики.
    Методика Джексона. При создании своей методики М. Джексон исходил из того, что структуры исходных данных и результатов определяют структуру программы.
    Методика основана на поиске соответствий структур исходных данных и результатов. Однако при ее применении возможны ситуации, когда на каких-то уровнях соответствия отсутствуют.
    Например, записи исходного файла сортированы не в том порядке, в котором соответствующие строки должны появляться в отчете. Такие ситуации были названы «столкновениями». Выделяют несколько типов столкновений, которые разрешают по-разному.
    При различной последовательности записей их просто сортируют до обработки. Более подробно способы разрешения столкновений изложены в [33].
    Разработка структуры программы в соответствии с методикой выполняется следующим образом:
    • строят изображение структур входных и выходных данных;
    • выполняют идентификацию связей обработки (соответствия) между этими данными;
    • формируют структуру программы на основании структур данных и обнаруженных соответствий;

    добавляют блоки обработки элементов, для которых не обнаружены соответствия;
    • анализируют и обрабатывают несоответствия, т.е. разрешают «столкновения»;
    • добавляют необходимые операции (ввод, вывод, открытие/закрытие файлов и т. п.);
    • записывают программу в структурной нотации (псевдокоде).
    1   ...   10   11   12   13   14   15   16   17   ...   28
    написать администратору сайта