Информатика

Оглавление Лекция.1. Язык Си 3 Технология разработки программ 3 Базовые элементы языка Си 4 Представление данных в Си 5 Лекция.2. Встроенные типы данных 6 Переменные 6 Операции и выражения 6 Функции 7 Лекция.3. Язык Си Обзор элементов языка Си 8 Типизированные константы 8 Область действия переменных 8 Управляющие конструкции С 10 Лекция.4. Циклы 13 Массивы и указатели 16 Типы, определяемые пользователем 19 Лекция.5. Препроцессор и отладка программ 23 Макроопределения 23 Условная компиляция 24 Лекция.6. Отладка программ 27 Элементы отладки 28 Лекция.7. Многомодульные программы 30 Деревья поиска 30 Динамическое двоичное дерево 31 Модификация типа значений в узлах 38 Лекция.8. Проектирование и тестирование программы 42 Список литературы 46 Лекция.1. Язык Си Язык программирования Си создан в 1972 г. сотрудником фирмы Bell Laboratories Деннисом Ритчи (Dennis M. Ritchie) при разработке операционной системы UNIX. Язык проектировался как инструмент для системного программирования с ориентацией на разработку хорошо структурированных программ. Удачное сочетание лаконичности конструкций и богатства выразительных возможностей позволило языку Си быстро распространиться и стать наиболее популярным языком прикладного и системного программирования. Компиляторы языка Си работают почти на всех типах современных ЭВМ в операционных системах UNIX, MS-DOS, Mac OS, OS/2, Windows, Windows NT, Solaris и др. С++ фактически по ряду аспектов является улучшенным Си. С++ предоставляет ряд совершенно новых возможностей, таких как объектно-ориентированное программирование, шаблоны, расширенная работа с пользовательскими типами и прочие. Технология разработки программ Разработка программ на языке C++ ведется с помощью специальных комплексов программ, которые называются системами программирования и позволяют создавать программы на определенной реализации языка. Системы программирования даже одного производителя имеют различные версии, которые отражают развитие технологии программирования и эволюцию среды выполнения программ. Это стимулирует стремление максимально использовать стандартные средства языка для того, чтобы снизить затраты на модификацию программ при изменении среды выполнения или при переходе на другую версию языка. Процесс создания программ включает четыре этапа: 1. Написание и редактирование исходного текста программы с сохранением ее в виде исходного файла или модуля. 2. Компиляция программы и получение ее на определенном промежуточном языке с сохранением виде объектного файла или модуля. 3. Построение исполнимого файла или модуля путем объединения (компоновки) полученного объектного модуля программы с другими объектными модулями стандартных и специальных библиотек. 4. Отладка программы, которую можно проводить с помощью специального средства (отладчика), облегчающего обнаружение ошибок. Соответственно, основными компонентами современных систем программирования являются: • интегрированная среда программирования; • редактор связей (компоновщик или линковщик); • библиотеки заголовочных файлов; • стандартные и специальные библиотеки; • библиотеки примеров программ; • программы-утилиты; • файлы документации. Интегрированная среда программирования (разработки) представляет собой приложение, которое имеет встроенный редактор текстов, подсистему работы с файлами, систему справочной помощи (Help-систему), встроенный отладчик, подсистему управления компиляцией и редактирования связей. Схема получения исполнимого модуля программы в интегрированной среде показана на рисунке (Рис. 1) Рис. 1 Схема получения исполняемого модуля Исходный модуль (ИМ) программы подготавливается с помощью встроенного или внешнего текстового редактора и размещается в файле с расширением *.срр. После этого ИМ обрабатывается препроцессором и, в случае необходимости, к исходному тексту программы присоединяются подключаемые файлы (ПФ). В дальнейшем модернизированный исходный модуль (ИМ*) обрабатывается компилятором. Выявленные синтаксические ошибки устраняются, и безошибочно откомпилированный объектный модуль (ОМ) помещается в файл с расширением obj. Затем ОМ обрабатывается компоновщиком, который дополняет программу нужными библиотечными функциями из библиотечных файлов (БФ). Полученный модуль называется исполнимым модулем (ИсМ) и помещается в файл с расширением ехе, который в дальнейшем исполняется. Базовые элементы языка Си Простейшее консольное приложение на языке Си имеет следующий вид: При запуске программа выдает сообщение Hello… и запрашивает нажатие любой кнопки, после чего выполнение программы завершается. Первые две строчки являются Си директивой (т.е. указанием) #include для препроцессора. Все строчки программы начинающиеся с символа # являются директивами для препроцессорной обработки. Директивы #include означают, что каждую из них следует заменить на содержимое файла, имя которого указано в угловых скобках. Это необходимо для проверки корректности вызова библиотечных функций printf и getch соответственно имеющих объявления в этих заголовочных файлах. Далее 3 троки являются просто комментариями заключенными между парами символов /* … */, которые служат для описание кода программы и полностью игнорируются компилятором. После директив и комментариев в программе расположено определение функции main (). Любая программа на Си содержит эту функцию, которая является ее входной точкой. В среде Windows вместо main () часто используется winMain ().Функция main () — это, конечно, частный случай функции вообще. Функции являются основными «строительными блоками» программ. Они, в свою очередь, строятся из операторов, составляющих тело функции. Каждый оператор оканчивается точкой с запятой (;). В общем виде функция определяется таким образом: возвращаемый_тип имя_функции(список_параметров) { // В фигурных скобках заключено тело функции, // составленное из отдельных операторов. тело_функции } Представление данных в Си Литералы Данные могут присутствовать непосредственно в тексте программы. В этом случае они представляются в виде литеральных констант. Литералы могут быть числовыми, символьными и строковыми. В приложении Hello мы пользовались строковыми литералами. Это — последовательность символов, заключенная в двойные кавычки. Символьный литерал служит для представления одиночного знака. Это символ, заключенный в одиночные кавычки (апострофы). Числовые литералы могут быть вещественными (с плавающей точкой) и целыми. В таблице 3.1 перечислены все упомянутые выше виды литеральных констант и даны соответствующие примеры (в листочке приложения). Можно дать литеральной константе некоторое имя, определив ее в качестве макроса препроцессора. После этого можно вместо литерала использовать указанное имя. Это особенно удобно в том случае, когда одна и та же константа встречается в различных частях программы; используя имя вместо литералов, вы гарантированы от опечаток и, кроме того, гораздо проще вносить в код изменения только в одном месте, если значение константы нужно модифицировать во всей программе. Лекция.2. Встроенные типы данных Любая информация рассматривается компилятором как принадлежащая к некоторому типу данных. В языке имеется несколько встроенных, или простых, типов (возможны и другие типы данных, например, определяемые пользователем). Простые типы перечислены в таблице 3.2. Размер и допустимый диапазон значений приведены здесь для 32-битной машины. Поэтому, например, тип int имеет размер 32 бита (4 байта) и эквивалентен типу long; на 16-разрядной машине int имел бы размер 2 байта. Но появившихся сравнительно недавно 64-х разрядных машинах int имеет размер 64 бита (8 байт). Это существенно если вы занимаетесь переносом программ на машину с другой разрядностью. Переменные Итак, отдельная единица данных должна обязательно иметь определенный тип. Именованная единица памяти для хранения данных называется переменной. Переменные создаются с помощью оператора объявления переменных, в котором указывается тип, имена переменных и (при необходимости) начальные значения, которыми переменные инициализируются. Вот несколько примеров: Операции и выражения Операции и выражения в C++ напоминают формулы в апгебре. Вот один пример выражения: aResult = (first - second * RATE) « 3 Операции характеризуются: 1. своим приоритетом, определяющим порядок, в котором производится оценка выражения, и 2. правилом ассоциации, задающим направление последовательных оценок идущих друг за другом операций одного приоритета. Как и в обычных формулах, для изменения порядка оценки выражения могут применяться круглые скобки (кстати, в приведенном выражении они излишни и введены только для наглядности). Знак равенства здесь также является операцией присваивания, которая сама (и, соответственно, все выражение в целом) возвращает значение. Оператором присваивания для переменной aResult выражение станет, если поставить после него точку с запятой. В таблице 3.3 дана сводка всех операций языка С в порядке убывания приоритета. Подробное описание операции дается в теоретической части лабораторной работы №1, там все должно быть понятно мы же пойдем далее. Функции Функция, как уже говорилось, является основным структурным элементом языка С. Выше мы уже показывали синтаксис определения функции (при рассмотрении функции main). Тело функции состоит из операторов, каждый из которых завершается точкой с запятой. Cам заголовок функции (его называют сигнатурой) не содержит точки с запятой. Помимо определения для функции обычно пишется также ее объявление, или прототип, который размещается в заголовочном файле с расширением .h и служит для проверки корректности обращений к функции при раздельной компиляции исходных файлов. возвращаемый_тип имя_функции (список_параметров) ; Вызов функции является выражением и принадлежит к типу, указанному в ее определении; он имеет вид: имя_функции (параметры); где параметры могут быть: пусто параметр[, параметр... ] Значение, возвращаемое функцией, можно игнорировать, т.е. использовать функцию в качестве процедуры: Мы так и поступали, когда выводили на экран сообщения функцией printf(). С другой стороны, возвращаемое функцией значение можно использовать в выражениях наряду с переменными и константами: Функция в С может иметь переменное или, точнее, неопределенное число параметров. В этом случае за последним обязательным параметром в заголовке функции следует многоточие (...). Подобным образом объявляется функция prtntf: int printf (const char *format, ...); Неопределенное число параметров означает, что количество и тип действительных аргументов в вызове должно так или иначе ей сообщаться, как это и происходит в случае printf ( )— там число аргументов определяется по числу спецификаторов в строке формата. С функциями ввода и вывода на практике вы познакомитесь на лабораторной работе №1. Лекция.3. Язык Си Обзор элементов языка Си Типизированные константы Разновидностью переменных являются типизированные константы. Это переменные, значение которых (заданное при инициализации) нельзя изменить. Для создания перед оператором объявления ставится ключевое слово const: const тип имя_константы = значение [, . . . ] ; Например: Область действия переменных Переменные в С могут быть локальными и глобальными, статическими и автоматическими, регистровыми, внешними и даже нестабильными. Они различаются областью действия, видимостью и временем жизни. Область действия Область действия — это та часть программы, где переменная в принципе доступна для программного кода (что означает это «в принципе», выяснится чуть позже). По своей области действия переменные делятся на локальные и глобальные. Локальные переменные объявляются внутри функции (или блока) и вне ее тела недоступны. К локальным переменным можно обращаться только в пределах объявляющей ее функции. Параметры в определении функции (формальные параметры) можно рассматривать как локальные переменные, инициализируемые значениями аргументов при вызове этой функции. Глобальные переменные не относятся ни к какой функции и объявляются совершенно независимо. В пределах текущего модуля имя глобальной переменной, естественно, должно быть уникальным. Областью действия глобальных переменных является по умолчанию вся программа. Если имя глобально и локальной переменной совпадают это допустимая ситуация.Но в этом случае локальная переменная скрывает глобальную с тем же именем. Тут речь идет о их области видимости которая не совпадает с областью действия. Время жизни Время жизни переменной определяется ее областью действия. Глобальная переменная существует все время, пока программа выполняется. Локальная переменная создается при входе в функцию и уничтожается при возврате из нее. Она является автоматической переменной. Нельзя ожидать, что локальная переменная будет сохранять свое значение в промежутках между вызовами объявляющей ее функции. Локальная переменная сохраняет значение между вызовами функции, если объявлена с модификатором static:: Статическая локальная переменная очень похожа на глобальную, память для нее отводится в той же области. Но областью действия локальная статической переменная является все-таки объявляющая функция; вне ее переменная недоступна. Модификаторы переменных static. Кроме сказанного следует добавить. Примененный к глобальной переменной, он ограничивает область ее действия текущим файлом (модулем компиляции). register. Этот модификатор рекомендует компилятору разместить локальную переменную в регистре процессора, если это возможно. extern. Модификатор говорит компилятору, что переменная является внешней, т.е. объявлена в другом файле. volatile. применяется для объявления переменных, которые можно назвать нестабильными. Значение такой переменной может изменяться само по себе, например, некоторым фоновым процессом или аппаратно. Компилятор не должен пытаться как-либо оптимизировать выражения, в которые входит переменная. Управляющие конструкции С Программа должна уметь «принимать решения», т.е. изменять последовательность исполнения своих операторов в зависимости от текущей ситуации – входных данных, результатов вычислений, действий пользователя и т.п. Существует три основных структуры потока управления, т.е. алгоритмов перехода от текущего оператора к следующему: • Последовательная структура — следующим исполняется оператор, расположенный непосредственно после текущего. • Структура выбора — имеется несколько операторов; в зависимости от оценки некоторого выражения для исполнения выбирается только один из них, остальные игнорируются. • Структура повторения — текущий оператор исполняется снова и снова до тех пор, пока не будет удовлетворено некоторое условие завершения. Из этих трех структур можно строить сколь угодно сложные управляющие конструкции, поскольку они подчиняются правилу суперпозиции: на место любого оператора некоторой структуры можно в свою очередь подставить любую структуру. Условный оператор if... else Графическое представление оператора показано на Рис. 2 Рис. 2 Условный оператор if... else Условный оператор реализует структуру выбора. Он имеет такой вид: if (условие) оператор1 else оператор2 Если условие оценивается как истинное (ненулевое), выполняется oпepaтop1, если как ложное (нулевое), выполняется oпepaтop2. Простейший пример: Вместо одиночного оператора всегда можно подставить блок из нескольких операторов, заключенный в фигурные скобки. Ключевое слово else и его операторы могут отсутствовать. В соответствии с правилом суперпозиции можно строить вложенные структуры if - else, например: Эта конструкция определяет наибольшее из трех чисел. Если убрать else в первом вложении If то конструкция может работать не так как надо пользователю…Чтоб этого избежать возможно использование фигурных скобок. Условие в операторе if Условие оператора if может быть сколь угодно сложным выражением, которое возвращает ненулевой целый результат. Например: Операции отношения (==, !=, <, >= и т.д.) возвращают ненулевой целый результат, если значения операндов удовлетворяют отношению. В большинстве реализаций С это 1, но полагаться на это не стоит. Если отношение не удовлетворяется, результатом операции будет нуль. Обратите внимание на три последних примера. В пятом примере вы можете видеть разницу между присваиванием (=) и отношением равенства (==). Не забывайте, что в С присваивание является операцией, возвращающей значение, В шестом примере вы видите поразрядную операцию AND, с помощью которой проверяется состояние отдельного бита переменной flags. В седьмом примере применена логическая операция AND, которая логически перемножает значения двух отношений. Оператор выбора switch Часто возникают ситуации, когда некоторая переменная может принимать несколько возможных значений- вариантов, и для каждого варианта требуется выполнить какие-то свои действия. Для подобных случаев в С существует специальная конструкция выбора switch. Выглядит она так: switch (выражение) { case константное_выражение: группа_операторов case константное_выражение: группа_операторов [default: группа_операторов] } Графическое представление оператора показано на Рис. 3 Рис. 3 Оператор выбора switch Рассмотрим пример: Если найдена метка case, совпадающая со значением проверяемого выражения, то выполняется группа операторов данного case. Однако дело на этом не заканчивается, поскольку, если не принять никаких дополнительных мер, управление «провалится» ниже, на следующую по порядку метку case и т.д., и в результате будут выполнены все операторы до самого конца блока switch. Если это нежелательно (как чаще всего и бывает), в конце группы операторов case нужно поставить оператор break. Он прерывает выполнение блока switch и передает управление оператору, непосредственно следующему за блоком. Лекция.4. Циклы В языке С структуры многократного повторения реализуются тремя разновидностями операторов цикла. Это циклы while, do...while и for. Цикл while Синтаксис имеет вид: while (условие_продолжения) { операторы тела цикла } Сначала оценивается условие_продолжения. Если оно истинно, выполняется оператор, после чего управление возвращается заголовку цикла, и все повторяется снова. Рис. 4 Цикл while Пример: Цикл do...while Этот цикл имеет такой вид: Рис. 5 Цикл do...while Цикл for Цикл for, наиболее универсальный из всех циклов языка С, выглядит так: Прежде всего выполняется инициализация цикла; секция инициализации может содержать любое выражение. Инициализация производится только один раз перед началом работы цикла. Оценивается выражение условия. Если оно истинно, выполняется оператор тела цикла; если условие ложно, происходит выход из цикла и управление передается следующему оператору. После исполнения тела цикла производится модификация, после чего управление возвращается заголовку цикла и все повторяется снова. Секция модификации может содержать любое выражение; обычно в ней изменяют значения управляющих переменных цикла. Простейшей и самой популярной конструкцией на основе цикла for является цикл с управляющей переменной-счетчиком: int i; for (i = 0; i < REPEAT; i++) doSomething(i); Альтернатива циклов рекурсия У структур повторения в ряде ситуаций есть альтернатива. Это рекурсия, заключающаяся в том, что функция вызывает саму себя. Естественно, такой вызов должен быть условным, т.е. обязательно должен наступить такой момент, когда на очередном шаге рекурсивного вызова не происходит. Есть классический пример рекурсии — 'вычисление факториала’: Не все языки программирования допускают рекурсию. Си — один из тех языков, в которых рекурсия возможна. Операторы прерывания блока Это операторы которые позволяют выйти из некоторого цикла досрочно, до выполнения условия его завершения: • Оператор break вызывает прерывание ближайшего (самого внутреннего) заключающего его блока switch, while, do. . .while или for. Управление немедленно передается следующему за блоком оператору. • Оператор continue воздействует только на блоки циклов. Он передает управление в конец тела цикла, пропуская, таким образом, все следующие за ним операторы блока. Здесь досрочно завершается не сам цикл, а его текущая итерация. • Оператор return прерывает выполнение текущей функции и возвращает ее значение в вызывающую программу. Он имеет вид: return [выражение]; Блоки и локальные переменные Поскольку при описании управляющих конструкций мы попутно ввели понятие блока, нужно сделать одно уточнение касательно объявлений и области действия локальных переменных. На самом деле локальные переменные могут объявляться не только в начале тела функции, но и в любом другом блоке (if, while и т.д.). Областью действия переменной является блок, в котором она объявлена; она скрывает любую переменную с тем же именем, объявленную вне данного блока. За пределами блока переменная недоступна. Массивы и указатели Массивы и указатели довольно тесно связаны между собой. Имя массива можно разыменовывать, как указатель. В свою очередь, указатель можно индексировать, как массив, если это имеет смысл. Массивы Массив по существу является совокупностью однотипных переменных (элементов массива), объединенных под одним именем и различающихся своими индексами. Массив объявляется подобно простой переменной, но после имени массива указывается число его элементов в квадратных скобках: Массив, как и переменную, можно инициализировать при объявлении. Значения для последовательных элементов массива отделяются друг от друга запятыми и заключаются в фигурные скобки: Обращение к отдельным элементам массива производится путем указания индекса элемента в квадратных скобках, например: Индекс должен быть целым выражением, значение которого не выходит за пределы допустимого диапазона. Поскольку индексация массивов начинается в С всегда с нуля (т.е. первый элемент имеет индекс 0), то, если массив состоит из N элементов, индекс может принимать значения от 0 до N—1. Указатели Указатель — это переменная, которая содержит адрес другого объекта. Этим объектом может быть некоторая переменная, динамический объект или функция. Говорят, что указатель ссылается на соответствующий объект. Адрес объекта,это 32-битное целое число, определяющее положение объекта в виртуальной памяти программы, указатель является не просто целым числом, а специальным типом данных. Он «помнит», на какого рода данные ссылается. Объявление указателя выглядит так: тип_указываемого_объекта *имя_указателя [= значение]; Вот примеры объявлений: Чтобы получить доступ к объекту, на который указатель ссылается, последний разыменовывают, применяя операцию-звездочку. Например, *pDouble будет представлять значение переменной, на которую ссылается pDouble: Указатели используются при обработке строк, а также для передачи функциям параметров, значения которых могут ими изменяться (передача по ссылке). Указатели позволяют создавать и обрабатывать динамические структуры данных. В языке С можно выделить память под некоторый объект не только с помощью оператора объявления, но и динамически, во время исполнения программы. Объект создается в свободной области виртуальной памяти функцией malloc (). Вот пример (предполагается, что переменные объявлены так, как выше): Аргументом malloc () является размер области памяти, которую нужно выделить; для этого можно применить операцию sizeof, которая возвращает размер (в байтах) переменной или типа, указанного в качестве операнда. Различия двух последних примеров - В первом из них указателю pDouble присваивается адрес переменной doubleVar. Во втором указателю присваивается адрес динамически созданного объекта типа double; после этого объекту, на который ссылается pDouble, присваивается значение переменной doubleVar. Т.о. создается новая динамическая копия значения переменной. Функция malloc () возвращает значение типа void* — «пустой указатель». Это указатель, который может указывать на данные любого типа. Такой указатель нельзя разыменовывать, поскольку неизвестно, на что он указывает — сколько байтов занимает его объект и как их нужно интерпретировать. В данном случае операция присваивания автоматически приводит значение malloc () к типу double*. Можно было бы написать в явном виде: Если выделение памяти по какой-то причине невозможно, malloc () возвращает NULL, нулевой указатель. NULL определяется в Windows как символьная константа в stdlib.h Указатель на функцию Можно объявить, инициализировать и использовать указатель на функцию. В вызовах API Windows часто применяют, например, «возвратно-вызываемые функции» - callback функции. В вызове API в качестве аргумента в этом случае употребляется указатель на соответствующую функцию. Соотношение между указателями и функциями примерно такое же, как между указателями и массивами, о чем говорится в следующем разделе. Отношения указателей и массивов Между указателями и массивами в С существует тесная связь. Имя массива без индекса эквивалентно указателю на его первый элемент. Последнее эквивалентно Наоборот, указатель можно использовать подобно имени массива, т.е. индексировать его. Например, piArr [3] представляет четвертый элемент массива iArray[ ]. Следует только помнить, что объявление массива выделяет память под соответствующее число элементов, а объявление указателя никакой памяти не выделяет, вернее, выделяет память для хранения значения указателя — некоторого адреса. Типы, определяемые пользователем Переименование типов Любому типу в С можно присвоить простое имя или переименовать его. Это делается с помощью ключевого слова typedef: typedef тип новое_имя_типа; Например Перечислимые типы Ключевое слово enum позволяет описать перечислимый тип, представляющий переменные, которые могут принимать значения из заданного набора целых именованных констант. Например: Обобщенная запись имеет вид: enum имя-этикетка {имя константы- [= значение] , . . . } переменная [, . . .]; В операторе еnum после закрывающей фигурной скобки можно сразу объявить несколько переменных данного типа:' Имя-этикетка не является настоящим именем типа. Именем типа будет в вышеприведенном примере enum Status. Но есть возможность воспользоваться ключевым словом typedef: Тогда Status будет полноценным именем перечислимого типа. (Обратите внимание, что для этикетки мы указали имя _status. Это обычная практика.) Структуры Массивы позволяют обращаться с набором логически связанных однотипных элементов как с единым целым. Если же требуется хранить набор разнородных, но логически связанных данных, описывающих, например, состояние некоторого объекта реального мира, используются структуры. Синтаксис структуры имеет такой вид: struct этикетка {список_элементов} [переменные]; Вот простой пример структуры, предназначенной для хранения основных сведений о человеке: Аналогично именем типа является struct этикетка (struct Person), и его можно сразу переопределить с помощью ключевого слова typedef. Для доступа к отдельным элементам структуры имеются две операции: точка и стрелка, за которыми следует имя элемента. С именем переменной структуры применяется точка, с указателем на переменную структуры используется стрелка: Битовые поля В качестве элементов структуры можно определять битовые поля. Для них задается ширина поля в битах, и компилятор отводит под элемент ровно столько бит, сколько указано. Несколько битовых полей может быть таким образом упаковано в одном слове (2 байта). Синтаксис битового поля: тип [имя_поля] : ширина поля; Тип поля может быть int или unsigned int. Доступ к битовым полям осуществляется так же, как и к регулярным элементам структуры. Если имя_поля отсутствует, место под поле отводится, но оно остается недоступным. Это будут просто «заполняющие» биты. Битовые поля применяются либо там, где необходима плотная упаковка информации (как это бывает при передаче функции некоторого набора логических флагов), либо, например, для отображения регистров внешнего устройства, которые часто бывают организованы как совокупность небольших полей и отдельных битов. Объединения Объединения, определяемые с помощью ключевого слова union, похожи по своему виду на структуры: union этикетка {список_элементов} [переменные]; Отличие состоит в том, что все элементы объединения занимают одно и то же место в памяти, они перекрываются. Компилятор отводит под объединение память, достаточную для размещения наибольшего элемента. О бъединения полезны, когда требуется обеспечить своего рода «полиморфное поведение» некоторого объекта. Например, вы хотите определить тип, реализующий представление различных геометрических фигур — прямоугольников, окружностей, линий, многоугольников. В зависимости от того, чем конкретно является данная фигура, для ее описания необходимы различные наборы значений. Использование переменных в функции Main например: Структура _GForm имеет, как таковая, три элемента: type, next (не используется) и data. Лекция.5. Препроцессор и отладка программ Препроцессорная обработка представляет собой первую фазу того процесса, что именуется компиляцией программы на C/C++. Макроопределения Макроопределения, называемые в просторечии макросами, определяются директивой препроцессора #define. Можно выделить три формы макросов #define: простое определение символа, определение символической константы и определение макроса с параметрами. Простое определение выглядит так: После такой директивы символ ndebug считается определенным Не предполагается, что он что-то означает; он просто — определен (как пустой). Можно было бы написать: Всякое вхождение в текст лексемы ndebug препроцессор заменил бы на "1". #define может определять не только константы. Поскольку препроцессор выполняет просто текстовую подстановку, можно сопоставить символу и любую последовательность операторов: Обратная дробная черта (\) означает, что макрос продолжается на следующей строчке. Определенный ранее макрос можно аннулировать директивой #undef: #undef NDEBUG После этого макрос становится неопределенным, и последующие ссылки на него будут приводить к ошибке при компиляции. Предопределенные макросы Компилятор С автоматически определяет некоторые макросы. Их можно разбить на две категории: макросы ANSI и макросы, специфические для конкретного компилятора. Сводка предопределенных макросов ANSI дана в таблице. Таблица 1 Предопределенные макросы ANSI Макрос Описание DATE Литеральная строка в формате "mmm dd yyyy". представляющая дату обработки данного файла препроцессором. FILE Строка имени текущего файла (в кавычках). LINE Целое, представляющее номер строки текущего файла. STDC Равно 1, если установлена совместимость компилятора со стандартом ANSI (ключ - А командной строки). В противном случае макрос не определен. TIME Строка в формате "hh:mm:ss", представляющее время препроцессорной обработки файла. Макросы с параметрами Макросы могут выполнять не только простую текстовую подстановку. Возможно определение макросов с параметрами, напоминающих функции языка С, например: Третье макроопределение показывает, что макросы могут быть вложенными. После каждого расширения макроса препроцессор снова сканирует полученный текст на предмет того, не содержит ли он идентификаторов, в свою очередь являющихся макросами. Исключением являются случаи, когда расширение содержит собственное имя макроса или является препроцессорной директивой. Директива #include Препроцессор заменяет директиву содержимым указанного в ней файла. Есть две ее формы: #include finclude "filename" В первом случае поиск нужного файла производится только в стандартных каталогах включаемых файлов; во втором случае — в текущем каталоге. Условная компиляция Можно производить выборочную компиляцию различных участков кода в зависимости от оценки некоторого константного выражения или определения идентификатора. Для этого служат директивы #if, #elif, #else и #endif. Общая форма применения директив условной компиляции следующая: #if выражение_1 , группа_операторов_1 [#elif выражение_2 группа_операторов_2 #elif выражение_3 группа рператоров_3 ...] [#else гpyппa_onepaтopoв_else] #endif Первая группа операторов компилируется, если выражение_1 истинно; в противном случае операторы ее опускаются. Вторая группа компилируется, если выражение_1 ложно и выражение_2 истинно и т.д. Группа #else компилируется только в том случае, если все условные выражения ложны. Конструкция условной компиляции должна заканчиваться директивой #endif. Разделы #elif и #else могут отсутствовать. Необходимыми элементами условной конструкции являются только директивы #if и #endif. Операции в условиях #if Выражения в директивах могут содержать обычные операции отношения <, >, <=, >= и ==. С их помощью можно проверять, например, значения предопределенных макросов или идентификаторов, определяемых директивой #define. В директивах препроцессора имеется также одна специальная операция defined. Она позволяет проверить, определен ли некоторый символ, например: Операция defined может комбинироваться с логическим отрицанием (!). будет истинным, если Sym не определен. Директивы #ifdef и #ifndef Эти две директивы эквивалентны соответственно #if defined и #if !defined. Типичное применение препроцессорных директив 1. Предотвращение включения файлов При использовании заголовков может происходить дублирование кода из-за повторного включения некоторого файла. (Допустим, у вас имеется исходный файл myprog.c, который подключает директивой #include два заголовка headerl.h и header2.h. Если, в свою очередь, оба этих файла подключают некоторый headerO.h, то последний будет дважды включен в исходный файл myprog.c. Чтобы предотвратить повторное включение кода заголовочного файла, можно организовать контроль следующим образом: Переключение разделов кода Директивы условной компиляции могут использоваться для простого переключения между двумя различными вариантами кода — старым и экспериментальным алгоритмом, например. Это можно сделать так: Макрос assert() В заголовочном файле assert.h определен макрос assert (), выполняющий примерно то же самое, что и показанный выше пример. Его «прототип» можно записать как void assert(int test); Макрос расширяется в оператор if, проверяющий условие test. Если его значение равно 0, печатается сообщение Assertion failed: с указанием имени файла и номера строки. Вот пример: Если перед включением файла assert.h определить символ ndebug, операторы assert( ) будут «закомментированы». Лекция.6. Отладка программ Отла́ дка — этап разработки компьютерной программы, на котором обнаруживают, локализуют и устраняют ошибки. Чтобы понять, где возникла ошибка, приходится : • узнавать текущие значения переменных; • и выяснять, по какому пути выполнялась программа. Существуют две взаимодополняющие технологии отладки. • Использование отладчиков — программ, которые включают в себя пользовательский интерфейс для пошагового выполнения программы: оператор за оператором, функция за функцией, с остановками на некоторых строках исходного кода или при достижении определённого условия. • Вывод текущего состояния программы с помощью расположенных в критических точках программы операторов вывода — на экран, принтер, громкоговоритель или в файл. Вывод отладочных сведений в файл называется журналированием. Программные ошибки Можно выделить две общих категории программных ошибок: времени компиляции и времени выполнения. Каждую из них, в свою очередь, можно разделить на две категории. В первом случае это ошибки компиляции (синтаксические) и ошибки компоновки; во втором — ошибки фатальные (условно назовем их так) и ошибки логические. Синтаксические ошибки Это самый безобидный вид программных ошибок.. Компилятор сразу обнаруживает синтаксические ошибки в собственном смысле и выдает сообщения об ошибках. К таким ошибкам относится, например, пропуск точки с запятой в конце оператора или непарные операторные скобки. Обычный компилятор печатает имя файла и номер строки, содержащей ошибку. Интегрированный компилятор сразу высвечивает в окне редактора соответствующую строку. Очень часто указанная строка не соответствует действительности, а лежит ниже в тексте программы, потому что, например, пропуск какой-нибудь за крывающей операторной скобки может обнаружиться только в той точке, где компилятору встретится определение следующей функции. Описание ошибки тоже может выглядеть странновато. Так что часто единственное, что молено сказать по сообщению об ошибке — это то, что ошибка есть и она локализована где-то не ниже указанной строки. Ошибки компоновки Эти ошибки обнаруживаются на этапе редактирования связей (компоновки) между объектными файлами программы и библиотеками, которые она использует. Как правило, компоновщик выдает сообщение о том, что отсутствует некоторый глобальный символ или, наоборот, таких символов слишком много. Дублирование глобальных символов может иметь место, например, когда забывают объявить некоторую глобальную переменную как extern (внешнюю) или static (с областью действия, ограниченной текущим файлом). Ошибки первого типа связаны с тем, что компоновщик не находит какую-то библиотеку. Она, конечно, может вообще отсутствовать в системе, но чаще это вопрос неправильной установки маршрутов системных библиотек или просто незнание программистом того, что та или иная библиотека обязательно должна быть указана в команде компоновщика (вспомните команду компоновки в make-файле из предыдущей главы). Иногда от программиста требуется незаурядное знание системы, чтобы определить причину таких ошибок. Фатальные ошибки времени выполнения К ним относятся ошибки, обнаруживаемые при запуске программы. Это может быть что-то вроде деления на ноль или нарушения защиты памяти. С помощью отладчика такие ошибки локализуются довольно просто, поскольку они, так сказать, «точечные». Правда, в эту же категорию можно отнести ошибки скорее логические, такие, как выход индекса за пределы массива или удаление элемента из пустой очереди. Они могут возникать не всегда, а зависеть от некоторого стечения обстоятельств. Сюда же можно отнести фатальные ошибки, связанные с неверным форматом ввода и т.п. Логические ошибки Эти ошибки локализовать наиболее трудно. Программа по видимости работает, но выдает совсем не те результаты, которых ожидает программист. Такого рода ошибки обычно коренятся в изначально неверном суждении относительно работы алгоритмов программы. Тут даже отладчик может принести лишь ограниченную пользу. Программист прежде всего должен «в уме», или на бумаге, проследить действия программы и определить критические участки кода, которые могут быть ответственны за отклонение ее поведения от ожидаемого. После этого уже можно пускать в ход отладчик и путем пошагового выполнения кода с контролем значения важнейших переменных выяснить, что же на самом деле в программе происходит. Элементы отладки Наиболее общими приемами отладки являются установка контрольных точек, наблюдение за переменными и пошаговое исполнение кода. Контрольные точки Программа, запущенная под управлением интегрированного отладчика, исполняется как обычно, т.е. с полной скоростью, пока не будет встречена контрольная точка (breakpoint). Тогда отладчик приостанавливает программу, и вы можете исследовать и изменять содержимое переменных, исполнять операторы в пошаговом режиме и т.д. Контрольные точки в C++Builder могут быть четырех видов: в исходном коде, на адресе, на данных и точки загрузки модуля. Мы рассмотрим только наиболее употребительные — в исходном коде. Контрольные точки в исходном коде Это самый распространенный вид контрольных точек. Точка представляет собой маркер, установленный на некоторой строке исходного кода. Когда управление достигает этой строки, программа приостанавливается. Проще всего установить контрольную точку такого типа прямо в редакторе кода, щелкнув кнопкой мыши на пробельном поле редактора (слева от текста) рядом со строкой, на которой требуется приостановить программу. Контрольные точки могут быть также условными, со счетчиком проходов или комбинированного типа. Контрольные точки данных Контрольная точка на данных вызывает остановку программы, если в указанный элемент данных производится запись. Можно указать либо адрес, либо имя переменной. Можно указать также размер объекта, определяющий диапазон адресов, обращение к которым будет вызывать остановку. Для переменных встроенных типов размер устанавливается автоматически. Как и в предыдущем случае, для контрольных точек данных можно задать условие и счетчик. Наблюдение за переменными Итак, вы остановили программу в контрольной точке. Обычно затем смотрят, каковы значения тех или иных переменных. Это называется наблюдением переменных (watching variables). В отладчике имеется специальное окно списка наблюдаемых переменных. Его можно открыть командой View | Debug Windows | Watches и ввести в него любое число переменных. Проще всего добавить переменную в список наблюдения можно, поместив курсор редактора кода на ее имя и выбрав в контекстном меню редактора Add Watch at Cursor. В окне наблюдений будет показано имя переменной и ее текущее значение либо сообщение, показывающее, что переменная в данный момент недоступна или наблюдение отключено (). Можно ввести в список и целое выражение, если выделить его в редакторе и вызвать контекстное меню. Альтернативным методом добавления переменных или выражений является выбор в контекстном меню окна наблюдений пункта Add Watch... (пункт Edit Watch... служит для редактирования свойств уже имеющегося в списке наблюдения). Будет открыт диалог, позволяющий задать, помимо выражения, которое будет наблюдаться, также и формат представления его значения. Помимо окна Watch, показывающего значения явно заданных переменных, в отладчиках, как правило, имеется окно, автоматически отображающее все локальные переменные и параметры текущей функции (окно Local Variables). Пошаговое исполнение кода Одной из важнейших и самых очевидных операций при отладке является пошаговое исполнение кода. Когда программа приостановлена в контрольной точке, вы можете наблюдать значения различных переменных. Но чтобы найти конкретный оператор, ответственный за неправильную работу программы, нужно видеть, как эти значения меняются при исполнении отдельных операторов. Таким образом, выполняя операторы программы по одному, можно определить момент, когда значения каких-то переменных оказываются совсем не теми, что ожидались. После этого уже можно подумать, почему это происходит и как нужно изменить исходный код, чтобы устранить обнаруженную ошибку. Отладчик имеет две основных команды, позволяющие исполнять операторы программы по одному, с остановкой после каждого оператора. Это Step Over и Trace Into. Эти команды могут выполняться из главного меню Run или с помощью кнопок инструментальной панели. Step Over (F8) Команда Step Over выполняет оператор, на котором приостановлено выполнение, и останавливается на следующем по порядку операторе. Текущий оператор выделяется в редакторе кода синим фоном и помечается зеленой стрелкой в пробельном поле. Если текущий оператор содержит вызов функции, она выполняется без остановок, и текущим становится первый оператор, следующий за возвратом из функции. Step Over «перешагивает» через вызов функции. Trace Into (F7) Команда Trace Into эквивалентна Step Over в случае, когда текущий оператор не содержит вызовов функций. Если же оператор вызывает некоторую функцию, то отладчик по команде Trace Into переходит на строку ее заголовка (заголовок при желании тоже можно рассматривать как исполняемый оператор, ответственный за инициализацию локальных переменных-параметров). При следующей команде (все равно — Step Over или Trace Into) текущим станет первый исполняемый оператор тела функции. Trace Into «входит внутрь» функции. Run Until Return (Shift+F8) Команда Run Until Return в известном смысле дополняет предыдущую. Когда дальнейшее пошаговое исполнение функции (в которую мы вошли командой Trace Into) нецелесообразно, данная команда позволяет быстро выйти из ' нее. Применение команды Run в данном случае привело бы к «прогону» программы, после выхода из функции, до следующей контрольной точки или до завершения. Команда Run Until Return останавливает программу на операторе, следующем за оператором вызова функции. Лекция.7. Многомодульные программы Представим развернутый пример программы из нескольких исходных модулей. Это позволит: 1. Показать полный цикл сборки программы из нескольких модулей; 2. Показать некоторые приемы программирования связанные указателями, рекурсией и прочей спецификой языка. Построим библиотеку для создания и использования деревьев поиска, а затем протестируем ее в различных вариантах с помощью пробных программ. Это типично «алгоритмически насыщенная» задача, из тех, что любят программисты. Деревья поиска Деревья поиска являются разновидностью двоичных деревьев. Вообще двоичное дерево представляет собой динамическую связанную структуру данных, состоящую из узлов, которые содержат значения того или иного типа. Дерево имеет единственный корневой узел. Каждый узел дерева может быть непосредственно связан с двумя потомками, или дочерними узлами (левым и правым), по отношению к которым он является родительским узлом. Узел может иметь двух потомков, одного потомка или ни одного потомка. В последнем случае он называется листом. Структура, образуемая всеми потомками данного узла слева или справа, называется соответственно его левым или правым поддеревом. Вот как может выглядеть двоичное дерево с целыми узлами: Рис. 6 Двоичное дерево Здесь 9 — корневой узел, 8, 2, 4, 0, 3 — листы. Узлы 9, 5, 7 и 6 имеют по два дочерних узла, 1 — один дочерний узел. Произвольное двоичное дерево становится деревом поиска, если значение любого узла больше любого значения из его левого поддерева и меньше любого значения из правого поддерева. Например, можно перераспределить значения в узлах показанного выше дерева так, что оно станет деревом поиска: Рис. 7 Дерево поиска Дерево поиска, как и следует из названия, при определенных условиях позволяет очень быстро найти в дереве нужное значение. Число сравнений, которое для этого требуется выполнить, имеет порядок логарифма числа узлов по основанию 2. Такое же число сравнений требуется для двоичного поиска в сортированном массиве значений, поскольку принцип поиска в обоих случаях по сути один и тот же. Различия структур дерева поиска и сортированного массива проявляются, когда требуется ввести в структуру новый элемент или удалить один из имеющихся элементов. В случае массива придется перемещать его элементы, чтобы освободить позицию для нового элемента или ликвидировать «дырку» на месте удаленного. Дерево поиска не требует перемещения узлов, а только реорганизации их связей. Динамическое двоичное дерево Программное динамическое двоичное дерево реализуется довольно просто. Определяется структурный тип узла, в котором действительно необходимы только три элемента — указатель- связка левого потомка, указатель правого потомка и элемент, представляющий значение узла. Это может быть целое, строка, указатель на некоторый динамический объект и т.д. Для удобства мы ввели дополнительно в структуру узла указатель на родительский узел. Память для узлов выделяется динамически. Определение типа узла и определения функций, осуществляющих элементарные операции с узлами, мы выделили в модули node.h и node.с. Мы будем пока работать с узлами, которые содержат целые значения. Однако мы определили тип значения обобщенно, как val_t. Это позволит в дальнейшем использовать процедуры библиотеки деревьев для других типов, переопределив тип значения и переписав функции модуля node.c. Эти функции выполняют создание нового узла (newNode ()), удаление узла (delNode ()), сравнение «меньше» и проверку на равенство двух значений (lessNode() и eqlsNode()) и распечатку значения в узле (printNode ()). Функции сравнения и печати тривиальны. Функция создания узла выделяв! память вызовом malloc() , которая возвращает указатель на блок памяти с размером, соответствующим структуре Node. Связкам нового узла присваивается нулевой указатель NULL, а полю значения — значение параметра функции. Директива #pragma hdrstop в разделе включаемых заголовков связана с особенностями компилятора и его структуры стандартных заголовочных файлов. Многие компиляторы используют т н. прекомпиляцию заголовочных файлов, позволяющую представить их информацию в виде, обеспечивающем максимально быстрый к ней доступ. Однако иногда случается так что.из-за каких-то конфликтов в макроопределениях (а полный набор заголовочных файлов воистину необозрим) компилятор отказывается включать в прекомпилируемый файл некоторый заголовок и выдает об этом предупреждение обрабатывая его как обычно. Ничего страшного, однако, можно заранее запретить прекомпиляцию заголовков, вызывающих нарекания. Это самый простои способ избежать предупреждающих сообщении, хотя как правило, удается достичь этого и более «грамотными» методами, разобравшись, из-за чего все таки возникают конфликты. Теперь мы напишем модуль btree.c (с заголовком btree.h), функции го будут работать уже не с отдельными узлами, а с деревом. Если 3^°™ поменять тип значения, которое содержится в узле, то переписывать эти функции не понадобится, хотя их, возможно, потребуется заново компилировать. Переписать придется только node.h и node.с. Btree.h — заголовок функций для деревьев: Btree.c — определения функций библиотеки деревьев: if(root->left != NULL) delSubtree(root->left); /*Рекурсия*/ if(root->right!=NULL) delSubtree (root->nght) ;/*Рекурсия*/ if(which(root)==LEFT) root->parent->left = NULL; if(which (root)==RIGHT) root->parent->right = NULL, delNode(root); ) void delTree()/*Удалить дерево */ /* (Нерекурсивный интерфейс delSubtree */ { delSubtree(treeRoot); treeRoot = NULL; } Node* addNode(val_t val) /* Добавить новый узел */ { Node* tn; *, if (treeRoot == 0) { /* Пустое дерево */ newRoot(val); /* создать новый корень */ return treeRoot;} tn = treeRoot; while (leqlsNode(tn->value, val)) { if (lessNode(val, tn->value)) /* Идем влево */ if (tn->left == NULL) { /* Левого потомка нет / tn->left = newNode (val); /* Добавить как левый лист */ tn->left->parent = tn; return tn->left; } else tn = tn->left; /* Новый текущий узел */ else/* Идем вправо */ if (tn->right == NULL) { /* Правого потомка нет */ tn->right = newNode(val); /* Добавить как правый лист */ tn->right->parent = tn; return tn->right; } else tn = tn->right; /* Новый текущий узел */ } /* Значение уже имеется в дереве */ return NULL; } void printlnOrder(Node* tn) /* Распечатка с порядковой выборкой */ { if (tn == NULL) return; /* Конечная точка рекурсии */ printlnOrder(tn->left); /* Рекурсия по левому поддереву */ printNode(tn); /* Текущий узел / printlnOrder(tn->right); /* Рекурсия по правому поддереву */ } /* Вспомогательная */ void print(Node* tn, int lvl) { int i; if (tn == NULL) return; print(tn->right, lvl + 1); /* Распечатать правое поддерево */ for (i = 0; i < lvl; i++) printf(" ") ; printNode(tn); /* Напечатать текущий узел */ printf("\n"); print(tn->left, lvl + 1); /* Распечатать левое поддерево */ } void printTree() /* Распечатать дерево графически */ { /* (Нерекурсивный интерфейс print) */ printf("\n"); print(treeRoot, 0); printf("\n"); ) Обратите внимание на строку с объявлением extern в btree.h. Это объявление внешней глобальной переменной — указателя на корневой узел дерева. Объявление находится в файле заголовка, так что любой исходный файл, включающий данный заголовок, будет содержать это объявление. Файл btree.c включает btree.h, но в нем производится также повторное объявление глобальной treeNode с инициализацией нулевым указателем. Именно это объявление является определением глобальной переменной, которое отводит под нее реальную память, и оно не вступает в конфликт с объявлением extern в том же файле. Функция newRoot () инициализирует дерево, создавая корневой узел. Функция printlnOrder () совершает рекурсивный обход дерева с порядковой выборкой, распечатывая значения в узлах. Сначала происходит обход левого поддерева (рекурсивный вызов), затем печатается текущее значение и, наконец, делается второй рекурсивный вызов для обхода правого поддерева. Значения в дереве, таким образом, распечатываются в восходящем порядке. Функция print () печатает в псевдографическом виде дерево, повернутое «набок», с корнем слева. По сути она выполняет обратный порядковый обход, делая при печати отступы для каждого уровня рекурсии. Ее нерекурсивным интерфейсом является printTree(). Функция addNodeO, выполняющая вставку в дерево нового узла, более сложна. Она совершает проход по дереву от корня вниз, сравнивая переданное ей значение (val) со значениями встреченных узлов. Если val меньше значения текущего узла, происходит переход к левому потомку, если больше — к правому. Если данный потомок отсутствует, нм становится новый узел. Если встречается значение, равное val, функция ничего не делает и возвращает NULL, так как структура дерева не допускает повторяющихся значений. Функция delSubtree () выполняет удаление всех узлов дерева, совершая рекурсивный обход с отложенной выборкой (сначала удаляются поддеревья, затем — текущий узел). Нерекурсивная delTree() является ее интерфейсом. Напишем тестовую программу, проверяющую все функции, созданные к данному моменту: Btest.c — проверка функций дерева поиска: Функция fillTree() заполняет дерево 13-ю значениями, после чего производится распечатка дерева двумя способами. Чтобы компилировать всю программу, нужно ввести команду gсс btest.c btree.c node.с Компилятор транслирует нее три файла и передает полнившиеся объектные файлы компоновщику, который создает исполняемый файл btest.exe. Результат запуска программы показан на рис. 8. Рис. 8 Распечатка дерева поиска с целыми значениями Распечатка показывает, что дерево строится правильно. Следует заметить, что в целях максимальной компактности и ясности кода мы не делаем никаких проверок на ошибки (например, на ошибку выделения памяти или попытку сделать что-то некорректное с пустым деревом). В реальном приложении это было бы недопустимо! Модификация типа значений в узлах Сейчас мы проверим, будут ли процедуры из btree.c работать с другим типом значений в узлах. Мы возьмем строковые данные. Для простоты мы будем хранить короткие строки, не более 15 символов, прямо в узлах дерева (технически более целесообразным решением было бы хранение указателей на динамически выделяемые строки произвольной длины). В node.h нам потребуется только переопределить тип val_t: Модифицированный файл node.h В node.с мы соответствующим образом реализуем новые функции выделения, сравнения и печати узлов: Наконец, мы модифицируем функцию fillTree() тестовой программы, чтобы она помещала в дерево не целые, а строковые значения: Stest.c — модификация тестовой программы Файл btree.c, как уже говорилось, модификаций не требует. Программа stest.exe компилируется той же командой: gcc stest.c btree.c node.с Результат ее работы представлен на рис. 9. Как видите, строки распечатываются в алфавитном порядке и дерево выглядит правильно, как и должно выглядеть дерево поиска. Хоть и немного криво. Скажем пару слов относительно функции в node.с. Функция newNode() выделяет память и копирует в узел переданную ей строку функцией strncpy () . Копируется не более 15 символов. Вспомогательная функция cmpNode() сравнивает строки (без различения регистра) с помощью стандартной stricmp(), которая возвращает -1, если первая строка (первый аргумент) по алфавитному порядку предшествует второй, 0, если строки равны, и 1, если первая строка идет по алфавиту после второй. Рис. 9 Распечатка дерева с узлами, содержащими строки Лекция.8. Проектирование и тестирование программы Профессионал отличается тем, что может достаточно точно оценить, сколько времени у него займет написание программы, которая будет работать в полном соответствии с поставленной задачей. Кроме «ума, вкуса и терпения», для этого требуется опыт, а также знание основных принципов, выработанных программистами в течение более чем полувека развития этой дисциплины. Даже к написанию самых простых программ нужно подходить последовательно, соблюдая определенную дисциплину. Структурный подход к программированию, охватывает все стадии разработки проекта: спецификацию, проектирование, собственно программирование и тестирование. Задачи, которые при этом ставятся, — уменьшение числа возможных ошибок за счет применения только допустимых структур, возможно более раннее обнаружение ошибок и упрощение процесса их исправления. Ключевыми идеями структурного подхода являются нисходящая разработка, структурное программирование и нисходящее тестирование. Приведенные ниже этапы создания программ рассчитаны на достаточно большие проекты, разрабатываемые коллективом программистов. Для программы небольшого объема каждый этап упрощается, но содержание и последовательность этапов не изменяются. I этап. Создание любой программы начинается с постановки задачи. Изначально задача ставится в терминах предметной области, и необходимо перевести ее в термины, более близкие к программированию. Поскольку программист редко досконально разбирается в предметной области, а заказчик — в программировании (простой пример: требуется написать бухгалтерскую программу), постановка задачи может стать весьма непростым итерационным процессом. Кроме того, при постановке задачи заказчик зачастую не может четко и полно сформулировать свои требования и критерии. В качестве иллюстрации приведу карикатуру «Качели» (Рис. 10), которая появилась 1973 году в информационном бюллетене вычислительного центра Лондонского университета и сразу стала широко известной, поскольку очень точно отражала процесс создания программы. Рис. 10 «Качели» Постановка задачи завершается созданием технического задания, а затем внешней спецификации программы, включающей в себя: ◦ описание исходных данных и результатов (типы данных, форматы, точность, способ передачи, ограничения); ◦ описание задачи, реализуемой программой; ◦ способ обращения к программе; ◦ описание возможных аварийных ситуаций и ошибок пользователя. Таким образом, программа рассматривается как черный ящик, для которого определена функция и входные и выходные данные. II этап. Разработка внутренних структур данных. Большинство алгоритмов зависит от того, каким образом организованы данные, поэтому интуитивно ясно, что начинать проектирование программы надо не с алгоритмов, а с разработки структур, необходимых для представления входных, выходных и промежуточных данных. При этом принимаются во внимание многие факторы, например, ограничения на размер данных, необходимая точность, требования к быстродействию программы. Структуры данных могут быть статическими или динамическими (динамические структуры рассматриваются в следующем разделе). III этап. Проектирование (определение общей структуры и взаимодействия модулей). На этом этапе применяется технология нисходящего проектирования программы, основная идея которого теоретически проста: разбиение задачи на подзадачи меньшей сложности, которые можно рассматривать раздельно. При этом используется метод пошаговой детализации. Можно представить себе этот процесс так, что сначала программа пишется на языке некоторой гипотетической машины, которая способна понимать самые обобщенные действия, а затем каждое из них описывается на более низком уровне абстракции, и так далее. Очень важной на этом этапе является спецификация интерфейсов, то есть способов взаимодействия подзадач. Для каждой подзадачи составляется внешняя спецификация, аналогичная приведенной выше. На этом же этапе решаются вопросы разбиения программы на модули, главный критерий — минимизация их взаимодействия. Одна задача может реализовываться с помощью нескольких модулей и наоборот, в одном модуле может решаться несколько задач. На более низкий уровень проектирования переходят только после окончания проектирования верхнего уровня. Алгоритмы записывают в обобщенной форме — например, словесной, в виде обобщенных блок-схем или другими способами. Если возникают трудности с записью алгоритма, он, скорее всего, плохо продуман. На этапе проектирования следует учитывать возможность будущих модификаций программы и стремиться проектировать программу таким образом, чтобы вносить изменения было возможно проще. Поскольку неизвестно, какие изменения придется выполнить, это пожелание напоминает создание «общей теории всего»; на практике надо ограничиться разумными компромиссами. Программист, исходя из своего опыта и здравого смысла, решает, какие именно свойства программы может потребоваться изменить или усовершенствовать в будущем. Процесс проектирования является итерационным, поскольку в программах реального размера невозможно продумать все детали с первого раза. IV этап. Структурное программирование. Процесс программирования также организуется по принципу «сверху вниз»: вначале кодируются модули самого верхнего уровня и составляются тестовые примеры для их отладки, при этом на месте еще не написанных модулей следующего уровня ставятся «заглушки» — временные программы. «Заглушки» в простейшем случае просто выдают сообщение о том, что им передано управление, а затем возвращают его в вызывающий модуль. В других случаях «заглушка» может выдавать значения, заданные заранее или вычисленные по упрощенному алгоритму. Таким образом, сначала создается логический скелет программы, который затем обрастает плотью кода. Казалось бы, более логично применять к процессу программирования восходящую технологию — написать и отладить сначала модули нижнего уровня, а затем объединять их в более крупные фрагменты, но этот подход имеет ряд недостатков. Во-первых, в процессе кодирования верхнего уровня могут быть вскрыты те или иные трудности проектирования более низких уровней программы (просто потому, что при написании программы ее логика продумывается более тщательно, чем при проектировании). Если подобная ошибка обнаруживается в последнюю очередь, требуются дополнительные затраты на переделку уже готовых модулей нижнего уровня. Во-вторых, для отладки каждого модул'я, а затем более крупных фрагментов программы требуется каждый раз составлять свои тестовые примеры, и программист часто вынужден имитировать то окружение, в котором должен работать модуль. Нисходящая же технология программирования обеспечивает естественный порядок создания тестов — возможность нисходящей отладки, которая рассмотрена далее. Рекомендации по записи алгоритмов на C++ (большинство из этих рекомендаций справедливы и для других языков высокого уровня) приведены в предыдущем разделе. Напомню, что главные цели — читаемость и простота структуры программы в целом и любой из составляющих ее функций. При программировании следует отделять интерфейс (функции, модуля, класса) от его реализации и ограничивать доступ к ненужной информации. Небрежное даже в мелочах программирование может привести к огромным затратам на поиск ошибок на этапе отладки. Этапы проектирования и программирования совмещены во времени: в идеале сначала проектируется и кодируется верхний уровень, затем — следующий, и так далее. Такая стратегия применяется потому, что в процессе кодирования может возникнуть необходимость внести изменения, отражающиеся на модулях нижнего уровня. V этап. Нисходящее тестирование. Этот этап записан последним, но это не значит, что тестирование не должно проводиться на предыдущих этапах. Проектирование и программирование обязательно должны сопровождаться написанием набора тестов — проверочных исходных данных и соответствующих им наборов эталонных реакций. Необходимо различать процессы тестирования и отладки программы. Тестирование — процесс, посредством которого проверяется правильность программы. Тестирование носит позитивный характер, его цель — показать, что программа работает правильно и удовлетворяет всем проектным спецификациям. Отладка — процесс исправления ошибок в программе,при этом цель исправить все ошибки не ставится. Исправляют ошибки, обнаруженные при тестировании. При планировании следует учитывать, что процесс обнаружения ошибок подчиняется закону насыщения, то есть большинство ошибок обнаруживается на ранних стадиях тестирования, и чем меньше в программе осталось ошибок, тем дольше искать каждую из них. Для исчерпывающего тестирования программы необходимо проверить каждую из ветвей алгоритма. Общее число ветвей определяется комбинацией всех альтернатив на каждом этапе. Это конечное число, но оно может быть очень большим, поэтому программа разбивается на фрагменты, после исчерпывающего тестирования которых они рассматриваются как элементарные узлы более длинных ветвей. Кроме данных, обеспечивающих выполнение операторов в требуемой последовательности, тесты должны содержать проверку граничных условий (например, переход по условию х>10 должен проверяться для значений, больших, меньших и равных 10). Отдельно проверяется реакция программы на ошибочные исходные данные. Идея нисходящего тестирования предполагает, что к тестированию программы приступают еще до того, как завершено ее проектирование. Это позволяет раньше опробовать основные межмодульные интерфейсы, а также убедиться в том, что программа в основном удовлетворяет требованиям пользователя. Только после того как логическое ядро испытано настолько, что появляется уверенность в правильности реализации основных интерфейсов, приступают к кодированию и тестированию следующего уровня программы. Естественно, полное тестирование программы, пока она представлена в виде скелета, невозможно, однако добавление каждого следующего уровня позволяет постепенно расширять область тестирования. Этап комплексной отладки на уровне системы при нисходящем проектировании занимает меньше времени, чем при восходящем, и приносит меньше сюрпризов, поскольку вероятность появления серьезных ошибок, затрагивающих большую часть системы, гораздо ниже. Кроме того, для каждого подключаемого к системе модуля уже создано его окружение, и выходные данные отлаженных модулей можно использовать как входные для тестирования других, что облегчает процесс тестирования. Это не значит, что модуль надо подключать к системе совсем «сырым» — бывает удобным провести часть тестирования автономно, поскольку сгенерировать на входе системы все варианты, необходимые для тестирования отдельного модуля, трудно. Список литературы 1. Т. А. Павловская C/C++. Программирование на языке высокого уровня, — СПб.:Питер, 2003. —461 с: ил. ISBN 5-94723-568-4 2. Лаптев В. В. C++. Экспресс-курс. - СПб.: БХВ-Петербург, 2004. - 512 с.: ил. ISBN 5-94157- 358-8 3. В.П.Аверкин, А.И.Бобровский, В.В.Веснич, В.Ф.Радушинский, А.Д.Хомоненко Программирование на C++, уч. пособие под ред. проф. А. Д. Хомоненко 4. Б.И. Березин, С.Б. Березин, Начальный курс С и С++. – М.: ДИАЛОГ-МИФИ, 2001. – 288 с. ISBN 5-86404-075-4 5. Харви Дейтел, Пол Дейтел Как программировать на С++. – М.: Бином, 2006 , - 1007 с. ISBN: 5-9518-0160-5