Проектирование программ по структурам данных - раздел Программирование, Основы алгоритмизации и Программирование
Проектирование Программ По Структурам Данных Можно Считать Од...
Проектирование программ по структурам данных можно считать одним из самых зрелых и продвинутых направлений в индустриальном отношении.
Использование диаграмм Варнье, Джексона и МЭСИД для проектирования программ уже упоминалось ранее, а здесь остановимся несколько подробнее на использовании подхода МЭСИД для задач, относимых обычно к классу экономических.
Все эти подходы основываются на создании диаграмм структур выходных и входных данных, определении несоответствий в них и путей устранения этих несоответствий через диаграмму структуры программы, составление списков операций и написание псевдокода (текста) программы.
Одним из принципов в этих методологиях является упреждающее чтение записей. В языках программирования, в которых при N записях в последовательном файле об окончании записей становится известно при N + 1 чтении, такое программирование является более удобным. В этом случае чтение первой записи выполняется по началу программы, а остальные чтения осуществляются в блоках, где производится их обработка. Для языков, в которых признак окончания файла устанавливается для последней прочитанной записи, то есть требуется N чтений при N записях упомянутое неудобство устраняется чтением первой записи по началу программы и использованием дополнительно условного оператора для установки флага завершения файла в блоках, где производится их обработка. Другим способом является написание специальной подпрограммы, к которой производится N+1 обращение с получением флага завершенности файла и записи в целом или только необходимых полей. При использовании ряда языков четвертого поколения (4 GL) эта проблема решается автоматически.
Одним из вариантов в подходе МЭСИД является следующая последовательность шагов с преобладающим направлением от выхода к входу и от физического к логическому:
1. Составление диаграммы структуры выходных данных.
2. Составление диаграммы структуры входных данных.
3. Составление диаграммы структуры программы с матрицей операций.
4. Заполнение матрицы операций.
5. Составление текста программы на языке программирования
В основе составления спецификации помимо графических средств лежит активный контроль речевой деятельности, направленный на выделение сходных подмножеств и их синхронизацию и/или отношений 1:1, 1:M, M:N.
Пусть имеется условный макет отчета (сводки) о начислении заработной платы рабочим-сдельщикам (рис. 1), в котором для каждого табельного номера (рабочего, исполнителя) выводится одна строка. Кроме итогов по табельным номерам выводятся итоги для участков, цехов и общий итог. Заголовок и «шапка» выводятся один раз в начале отчета. Обрабатываются все записи входного набора данных с последовательной организацией, упорядоченного по шифру цеха, шифру участка и табельному номеру. Кроме упомянутых элементов каждая запись включает шифр детали, номер операции, единицу измерения, нормированное время на единицу, расценку и количество.
Сначала произведем описание структуры выходных данных. Глядя на макет отчета, можно видеть, что самая частая строка отчета относится к табельному номеру (рабочему, исполнителю). Полями (элементами) всех этих строк являются шифр цеха, шифр участка, табельный номер и начислено. Низшим уровнем в иерархии является рабочий, а шифр цеха и шифр участка повторяются для разных рабочих в пределах участков и цехов. Таким образом, можно выделить (рис.2а) конструкцию повторения «табельный номер», в тело которой входят элементы шифр цеха, шифр участка, табельный номер и начислено.
Зададим вопросы: «Что предшествует этой конструкции, что следует за ней, во что она входит?». Отвечая на эти вопросы, можно получить диаграмму (рис. 2б), затем диаграмму (рис.2в) и, наконец, диаграмму (рис.2г) которую можно прочитать примерно следующим образом:
1. Печать отчета начинается с вывода заголовка и шапки.
2. Производится вывод информации по цехам, по участкам, по табельным номерам.
3. При завершении участка выводится итог по участку.
4. При завершении цеха выводится итог по цеху.
5. При завершении файла (всей информации) выводится общий итог.
Построение диаграммы выходных данных настраивает на более внимательный анализ структуры входных данных. Возвращаясь к описанию входных данных, можно отметить, что упорядоченность последовательного файла по шифру цеха, шифру участка и табельному номеру соответствует порядку выделения подмножеств выходных данных. Отметим, однако, что упорядоченность по табельному номеру служит не только, и не столько, удобству чтения информации отчета, а формированию итоговой строки отчета для табельного номера, то есть одному полю «начислено» может соответствовать несколько записей входного файла об операциях, выполненных над определенными деталями. Кроме того, запись входного файла может содержать разнообразные поля, которые могут не иметь непосредственного отношения к формируемому отчету. В рассматриваемой задаче можно предположить, что для вычисления «начислено» будут значения расценки и количества (в случае неуверенности необходимо согласовать с постановщиком задачи). Таким образом, диаграмму входных данных (рис. 3) можно прочитать следующим образом:
1. Файл состоит из подмножеств записей, соответствующих цехам.
2. Эти подмножества состоят из подмножеств записей, соответствующих участкам.
3. Эти подмножества состоят из подмножеств записей, соответствующих табельным номерам.
4. Эти подмножества состоят из подмножеств записей, соответствующих обработанным деталям.
5. Каждая такая запись содержит информацию об обработанной детали, включая данные, необходимые для вычислений и идентификации подмножеств.
Сравнив иерархии в диаграммах выходных и входных данных, мы не видим существенных противоречий (например, различий в упорядоченности), что позволяет перейти к составлению диаграммы структуры программы. За основу этой структуры берется структура входных данных, каждое повторение и развилка которой наращиваются соответствующими началами и окончаниями (рис. 4). Диаграмма структуры программы является достаточно компактной, и ее можно дополнить матрицей операций, определяющей порядок действий программы на уровне псевдокода. Столбцы матрицы соответствуют категориям операций:
1. Чтение с прямым доступом.
2. Подготовка переходов.
3. Подготовка вычислений и вычисления.
4. Подготовка вывода, вывод и очистка.
5. Чтение с последовательным доступом.
6. Переходы.
Категория «Чтение с прямым доступом» предназначена главным образом для извлечения данных из файлов прямого доступа для расширения состава полей записей последовательного файла. В нашем примере при необходимости работы с наименованиями цеха и участка после последовательного чтения основного файла мы могли бы задать чтение соответствующих справочников по началу цеха и по началу участка.
Категория «Подготовка переходов» связана в значительной степени с определением однородных в определенном смысле подмножеств записей входного файла. Так, например, печать итога по участку должна производиться, когда начинается другой участок или когда заканчивается файл. С этой целью определяется значение флажка окончания файла и фиксируется код участка.
Категория «Подготовка вычислений и вычисления» связана главным образом с обнулением счетчиков и их наращиваем.
Категория «Подготовка вывода, вывод и очистка» связана главным образом с выводом значений идентификации подмножества по его началу или/и окончанию. Так, при детальной печати распечатывается каждая запись входного файла, а при итоговой печати выводятся итоги для подмножеств и идентификаторы. В нашем примере на нижнем уровне выводится строка для табельного номера, когда это подмножество завершено и уже известны идентификаторы для следующего подмножества. По это причине необходимо запоминать эти идентификаторы на соответствующем уровне для последующего вывода. Этот процесс похож на подготовку переходов, и в ряде случаев поля подготовки переходов можно использовать и для вывода.
Существует еще вид отчетов с индикацией группы, когда идентификаторы подмножеств и сопутствующие элементы выводятся в более детальной строке только при смене подмножества, а после этого в детальной строке остаются пробелы. В этом случае в поле(я) вывода по началу подмножества помещаются его идентификаторы, а после первого же вывода поля вывода заполняются пробелами.
Категория «Чтение с последовательным доступом» обычно связана с основным файлом, исчерпание которого приводит к завершению программы.
Категория «Переходы» в явном виде, в отличие от метода Варнье, может не использоваться, поскольку в диаграмме структуры программы имеются строки для соответствующих операторов управления.
Возникает, однако, вопрос, как связать эти диаграммы структур данных и программы на уровне полей. Допишем с этой целью на диаграммах достаточно короткие наименования полей записей и дополнительных переменных (рис.5).
Запись операций в матрице (рис.6) должна производиться с учетом различия частот выполнения блоков программы. Так, задавая вопросы, как часто и когда должно выполняться то или иное действие, можно определить его место в матрице. Например, операция ввода должна выполняться для каждой детали и еще один раз по началу программы, операция вывода заголовка и шапки должна выполняться один раз по началу программы и т.д.
Московский государственный университет экономики... Статистики и информатики...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Проектирование программ по структурам данных
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Москва 2003
УДК 004.42
ББК -018*32.973
К 174
Калмыкова О.В., Грибанов В.П., Сорока Р.И. Основы программирования. /Моск. гос. ун-т экономики, статистики и информа
Основные определения и понятия.
Алгоритмизация – это процесс построения алгоритма решения задачи, результатом которого является выделение этапов процесса обработки данных, формальная запись со
Средства изображения алгоритмов.
Основными изобразительными средствами алгоритмов являются следующие способы их записи:
- словесный;
- формульно-словесный;
- блок-схемный;
- псев
Базовые канонические структуры алгоритмов.
Доказано, что любую программу можно написать, используя комбинации трех управляющих структур:
- следования или последовательности операторов;
- развилки или условн
While P do A ;
Действие А будет повторяться до тех пор, пока значение предиката будет оставаться истинным. Поэтому в действии А должно изменяться значение переменных, от которых зависит Р. В противном случае прои
Repeat A until P;
Повторение типа Repeat until всегда выполняется хотя бы 1 раз. Действие А перестает выполняться, как только предикат становится истинным.
4) выбор
Вопросы к главе 1.
1. Что такое данные?
2. Что такое программа?
3. Что такое алгоритм?
4. Что такое алгоритмический процесс?
5. Перечислить свойства алгоритмов.
6. Чем отл
Общая характеристика языка Паскаль.
Язык Паскаль был разработан Никласом Виртом первоначально для целей обучения программированию. В настоящее время он получил широкое распространение по ряду объективных причин.
Алфавит языка.
Язык Турбо Паскаль допускает использование прописных и строчных букв латинского алфавита, знака подчеркивания, арабских цифр и ограничителей.
Элементарные конструкции.
Из основных символов непосредственно образуются элементарные конструкции языка, которые являются минимальными неделимыми синтаксическими единицами. К ним относятся: идентификаторы,
Типы данных.
Каждая переменная и константа в программе на языке Паскаль имеет свой тип данных. Тип определяет набор операций, которые могут быть к ней применимы, а также тип результата выполнени
WRITELN( SIM);
…
Если телом цикла является другой цикл, то циклы называются вложенными или сложными. Цикл, содержащий в себе другой цикл, называют внешни
Вопросы к главе 2.
1. Дать определение языка программирования.
2. Дать классификационную характеристику языков программирования.
3. Определить особенности языков высокого уровня.
Структурированные типы данных.
Данные одинакового простого типа (кроме вещественного) могут объединяться в множество.
В общем виде тип множество описывается:
Свойства множеств.
1) Если все элементы одного множества совпадают с элементами другого множества, то они (множества) считаются равными.
Множества [1..5] и [1,2,3,4,5] равны.
2) Если
Описание записи (RECORD).
Запись – это структура данных, состоящая из фиксированного числа компонент, называемых полями. Каждое поле имеет свой идентификатор и тип. К компонентам запи
Структура программы на языке Паскаль.
Синтаксически программа на языке Паскаль делится на 2 части: заголовок и программный блок.
Общий вид заголовка:
PROGRAM<имя про
Описание и вызов процедур.
Для реализации многократно повторяющихся участков вычислений и для обеспечения модульности программ в языке Турбо Паскаль предусмотрена возможность использования процедур и функций.
PR1 (A,B,C,S);
Формат списка параметров в заголовке процедуры и при вызове процедуры отличаются. При вызове переменные, константы или выражения следуют через запятую, а в заголовке запись переменных напоминает об
Описание функции.
Функция предназначена для вычисления какого-либо одного значения и используется в выражениях аналогично стандартным функциям.
Синтаксис заголовка фу
Формальные и фактические параметры.
При описании процедуры (функции) в ее заголовке могут быть указаны параметры следующих видов:
- параметры-значения;
- параметры-переменные;
- параметры-ко
Параметры-значения.
При передаче параметров по значению в стеке, в котором осуществляется выделение памяти под внутренние (локальные) переменные подпрограммы, выделяется дополнительная память, в которую копируются зна
Параметры-переменные.
При вызове по ссылке в подпрограмме память под передаваемые переменные не отводится. В подпрограмму передается не значение переменной, а ссылка на место в памяти соответствующего фактического парам
Uses crt;
Type tmas=array[1..100,1..100] of word;
tvect=array[1..100] of word;
Var a:tmas;
v:tvect;
Параметры-константы.
Так как аргументы, передаваемые в процедуру или функцию , размещаются в стеке, то в случае передачи значением массива большого размера, может произойти переполнение стека. В языке Турбо Паскаль 7.0
Область действия имен.
Любая подпрограмма представляет собой блок со своей областью описаний. Она может содержать внутри этого блока описания других процедур и функций, а также обращения к ним. Объекты, о
Процедуры и функции без параметров.
В случае использования процедур и функций без параметров связь данных осуществляется через глобальные переменные.
Подпрограммы должны быть, по возмож
Рекурсивные процедуры и функции.
Рекурсия- это способ организации вычислительного процесса, при котором процедура или функция в процессе выполнения входящих в ее состав операторов обращается са
Предварительно-определенные процедуры.
При косвенной рекурсии одна подпрограмма вызывает другую, которая либо сама, либо посредством других подпрограмм вызывает исходную. В этом случае используется предварительное
Модули.
Процедуры и функции могут быть сгруппированы в отдельный модуль. Модуль (unit)- это программная единица, текст которой компилируется автономно (незави
INTERFACE
USES<список подключаемых модулей>;
TYPE<описание типов, определенных в данном модуле
и доступных для других модулей
IMPLEMENTATION
USES<список подключаемых модулей>;
TYPE<описание типов, определенных в данном модуле
и недоступных для других модулей
Вопросы к главе 4.
1. Назначение процедур и функций.
2. Возможность подключения процедур и функций с помощью опции компилятора.
3. Описание заголовка процедуры.
4. Описание
Стандартные процедуры и функции.
В языке программирования Турбо Паскаль все используемые процедуры и функции объединены в стандартные модули. К основным модулям можно отнести следующие:
· SYSTEM –
Математические функции.
Имя функции
Назначение функции
Tип результата
Abs(X)
Абсолютное значение (модуль) аргумента
Abs(-3.5)=3.5
Функции порядкового типа.
Имя функции
Назначение функции
Odd(X)
Проверяет, является ли аргумент нечетным числом
Odd(0)=false
Odd(1)=true
Процедуры порядкового типа.
Имя процедуры
Назначение процедуры
Dec(X [,dx])
Уменьшает значение переменной Х на величину dx (если параметр dx не
Строковые функции.
Имя функции
Назначение функции
Concat(<строка1>,<строка2>,..)
Сцепление строк
Сoncat(‘A’,’BC’,’_1’)=’A
Строковые процедуры.
Имя процедуры
Назначение процедуры
Delete(<строка>,<позиция>,<количество>)
Удаление части строки с
Прочие процедуры и функции.
Имя функции
Модуль
Назначение процедуры или функции
Keypressed
Crt
Функция. Возвращает зна
Процедуры ввода данных.
Ввод данных в языке Турбо Паскаль выполняется стандартными процедурами (операторами) READ или READLN, вывод - процедурами WRITE ил
Процедуры вывода данных.
Процедура (оператор) WRITEпредназначена для вывода выражений следующих типов: Integer, Byte, Real, Char, String, Boolean и др.
WRIT
Особенности вывода вещественных значений.
Если описать переменную вещественного типа, то возможны следующие варианты вывода этой переменной:
1) Write(R); Вывод осуществляется в норм
Вопросы к главе 5.
1. Общая классификация стандартных процедур и функций.
2. Назначение основных стандартных модулей.
3. Особенности математических функций.
4. Особенности использования про
Особенности обработки типизированных файлов.
Файл с типом (типизированный файл) состоит из последовательности записей одинаковой длины и одинакового внутреннего формата. Записи следуют непрерывно друг за другом. Первые 4 байта
Особенности обработки текстовых файлов.
Текстовые файлы состоят из символов. Каждый текстовый файл разделяется на строки неопределенной длины, которые заканчиваются символом конец строки. Весь файл заканчивается символом
Файлы без типа.
Любой файл может быть представлен в виде последовательности символов кода ASCII. Турбо Паскаль позволяет рассматривать файл с любой организацией как бы состоящим из блоков по 128 байт.
Фай
Постановка задачи.
Пусть для системы обработки данных требуется написать программу одновременного формирования трех ведомостей о начислении заработной платы для рабочих-сдельщиков на основе пооперацио
Проектирование программы.
Для проектирования программы будем использовать подход МЭСИД. Процесс проектирования начинается с составления диаграмм структур выходных данных. Они представлены на рис.12. После со
Кодирование программы.
Текст программы помимо тела, соответствующего матрице операций, должен содержать объявления файлов и структур данных. Для решения данной задачи используются не все поля записей основного и справочн
Вопросы к главе 6.
1. Как можно описать файлы ?
2. Какие типы файлов существуют в Турбо Паскале ?
3. Как организовать прямой доступ к типизированным файлам ?
4. Особенности работы с типизир
Динамическая память.
В предшествующих разделах использовались переменные, память под которые выделялась статически, то есть на стадии компиляции. Эти области памяти (для переменных из раздела VA
Указатель.
Обращение к участку динамической памяти в программе осуществляется с помощью специальной ссылочной переменной, которая называется указателем (ссылкой).
Переменная типа «ука
New (P);
где р - переменная типа «типизированный указатель».
Эта процедура создает новую динамическую переменную (выделяет под нее участок памяти) и устанавливает на нее указатель
Dispose (P);
где P - переменная типа «указатель» (типизированный).
В результате работы процедуры Dispose(P) участок памяти, связанный с указателем P,
Release (P);
где P - переменная типа «указатель»;
Mark - запоминает состояние динамической области в переменной-указателе р;
Release
New(i4);
i4^:=4; (*1*)
Disроsе (i2);{освобождается второе размещение}
New (i); {память нужного размера (в данном случае два байта) выделя
Организация списков.
Преимущества динамической памяти становятся особенно очевидными при организации динамических структур, элементы которых связаны через адреса (стеки, очереди, деревья, сети и т.д.).
Стеки, деки, очереди.
Одной из важных концепций в программировании является концепция стека. Стеком называется упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих
Использование рекурсии при работе со списками.
Рекурсия является одним из удобнейших средств при работе с линейными списками. Она позволяет сократить код программы и сделать алгоритмы обхода узлов деревьев и списков более понятн
Бинарные деревья.
Кроме линейных структур существуют и нелинейные, при помощи которых задаются иерархические связи данных. Для этого используются графы, а среди них сетевые и древовидные структуры. Р
Действия с бинарными деревьями.
Рассматривая действия над деревьями, можно сказать, что для построения дерева необходимо формировать узлы, и, определив предварительно место включения, включать их в дерево. Количес
Построение бинарного дерева.
Важным понятием древовидной структуры является понятие двоичного дерева поиска. Правило построения двоичного дерева поиска: элементы, у которых значение некоторого признака меньше,
Решение задач работы с бинарным деревом.
Элемент дерева используется для хранения какой-либо информации, следовательно, он должен содержать информационные поля, возможно разнотипные. Элемент двоичного дерева связан в общем
Вопросы к главе 7.
1. Особенности использования статической и динамической памяти.
2. Описание динамических переменных.
3. Использование указателей и ссылочных переменных.
4
Понятие жизненного цикла программного продукта
Программное изделие проходит в своем развитии целый ряд этапов, начиная от возникновения потребности в программном продукте и заканчивая снятием программы с эксплуатации. Рассмотрение полного жизне
Нисходящее проектирование.
Нисходящее проектирование строится на вышеперечисленных принципах. При нисходящем проектировании происходит анализ задачи с целью определения возможности разбиения ее на ряд подзада
Структурное кодирование.
Структурное кодирование - это метод кодирования (программирования), предусматривающий создание понятных, простых и удобочитаемых программных модулей и программных комплексов на треб
Модульное программирование.
Модульное программирование - это организация программы как совокупности небольших независимых блоков, модулей, структура и поведение которых подчиняется определенным правилам. Следу
Вопросы к главе 8.
1. Понятие жизненного цикла программного продукта.
2. Основные этапы разработки программного обеспечения.
3. Дать определение технологии программирования.
4. Цели структу
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов