- •О.Л. Викентьева, А.Н. Гусин, O.A. Полякова
- •ПРОЕКТИРОВАНИЕ ПРОГРАММ И ПРОГРАММИРОВАНИЕ НА C++
- •1. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
- •10.1. Базовые конструкции структурного программирования
- •10.3. Составные операторы
- •10.4. Операторы выбора
- •10.5. Операторы циклов
- •10.6. Операторы перехода
- •11. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ОСНОВНЫХ ОПЕРАТОРОВ C++
- •11.2. Программирование арифметических циклов
- •11.3. Программирование итерационных циклов
- •11.4. Программирование вложенных циклов
- •12. МАССИВЫ
- •12.1. Определение массива в C/C++
- •12.2. Примеры решения задач с использованием массивов
- •13. УКАЗАТЕЛИ
- •13.1. Понятие указателя
- •13.2. Динамическая память
- •13.3. Операции с указателями
- •14. ССЫЛКИ
- •15.3. Динамические массивы
- •СИМВОЛЬНАЯ ИНФОРМАЦИЯ И СТРОКИ
- •16.1. Представление символьной информации
- •16.2. Библиотечные функции для работы со строками
- •16.3. Примеры решения задач с использованием строк
- •17. ФУНКЦИИ В C++
- •17.1. Объявление и определение функций
- •17.2. Прототип функции
- •17.3. Параметры функции
- •17.4. Локальные и глобальные переменные
- •17.5. Функции и массивы
- •17.5.1. Передача одномерных массивов как параметров функции
- •17.5.2. Передача строк в качестве параметров функций
- •17.5.3. Передача многомерных массивов в функцию
- •17.6. Функции с начальными значениями параметров (по умолчанию)
- •17.7. Подставляемые (inline) функции
- •17.8. Функции с переменным числом параметров
- •17.9. Рекурсия
- •17.11. Шаблоны функций
- •17.12. Указатель на функцию
- •17.13. Ссылки на функцию
- •18. ТИПЫ ДАННЫХ, ОПРЕДЕЛЯЕМЫЕ ПОЛЬЗОВАТЕЛЕМ
- •18.1. Переименование типов
- •18.2. Перечисления
- •18.3. Структуры
- •18.3.1. Работа со структурами
- •18.3.2. Битовые поля
- •18.3.3. Объединения
- •19. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
- •19.1. Создание элемента списка
- •19.2. Создание списка из п элементов
- •19.3. Перебор элементов списка
- •19.4. Удаление элемента с заданным номером
- •19.5. Добавление элемента с заданным номером
- •19.6. Двунаправленные списки
- •19.7. Очереди и стеки
- •19.8. Бинарные деревья
- •19.9. Обход дерева
- •19.10. Формирование дерева
- •19.11. Удаление элемента из дерева
- •19.12. Обработка деревьев с помощью рекурсивного обхода
- •20. ПРЕПРОЦЕССОРНЫЕ СРЕДСТВА
- •20.1. Стадии и команды препроцессорной обработки
- •20.2. Директива #define
- •20.3. Включение текстов из файлов
- •20.4. Условная компиляция
- •20.5. Макроподстановки средствами препроцессора
- •21.1. Проектирование программы
- •21.2. Кодирование и документирование программы
- •СПИСОК ЛИТЕРАТУРЫ
- •ПРОЕКТИРОВАНИЕ ПРОГРАММ И ПРОГРАММИРОВАНИЕ НА C++
19.12. Обработка деревьев с помощью рекурсивного обхода
Задача № 1. Найти количество четных элементов в дереве.
Для решения этой задачи необходимо перебрать все элементы дерева и проверить информационные поля на четность. Для перебора будем использовать обход дерева слева направо. Результат запомина ем в специальной переменной, которую передаем по ссылке,
//количество четных элементов в дереве void kol(Point *р, int &rez)
{
if (p)
{
kol(p->left,rez);
if(p->key%2==0)rez++;
kol(p->right, rez);
Задача № 2. Найти количество отрицательных элементов в де
реве. Решается аналогично предыдущей.
//количество отрицательных элементов в дереве void quantity_otr(int a,int &k)
{
if (a<0)k++;
}
void kol(Point *p,void (*ptr)(int,int&), int
&rez)//итератор
{
if (p)
{
kol(p->left,quantity_otr,rez); ptr(p->key,rez);
kol(p->right, quantity_otr,rez);
}
20.ПРЕПРОЦЕССОРНЫЕ СРЕДСТВА
20.1.Стадии и команды препроцессорной обработки
Назначение препроцессора - обработка исходного текста про
граммы до ее компиляции (можно назвать первой фазой компиля ции). Инструкции препроцессора называют директивами. Они начи наются с символа #.
На стадии обработки директив препроцессора возможно выпол нение следующих действий:
1. Замена идентификаторов заранее подготовленными последо вательностями символов ( # d e f i n e ) .
2. Включение в программу текста из указанных файлов (# i n c l u d e ).
3.Исключение из программы отдельных частей (условная компиляция).
4.Макроподстановка, т.е. замена обозначения параметризируемым текстом.
20.2. Директива #define
Директива # d e f in e имеет несколько модификаций. Они преду сматривают определение макросов или препроцессорных идентифи каторов, каждому из которых ставится в соответствие некоторая последовательность символов. В последующем тексте программы препроцессорные идентификаторы заменяются на заранее оговорен ные последовательности символов.
# d e f in e и дентиф икатор строка_ зам ещ ени я Пример работы директивы define:
До обработки |
|
|
# d e fin e |
b e g in |
{ |
# d e fin e |
end |
} |
v o id m ain() b e g in операторы end
После обработки
v o id m a in ()
{
операторы
}
С помощью # d e f in e удобно определять размеры массивов
Пример работы директивы define:
До обработки
# d e fin e |
N |
10 |
id e f in e |
М |
100 |
v o id m a in ()
{
in t m a tr [N ][N ]; d ou b le mas [M]
}
После обработки
v o id m a in ()
{
i n t m a tr [ 1 0 ] [ 1 0 ] ; d o u b le m a s[100]
}
Те же возможности в C++ обеспечивают константы, определен ные в тексте программы, поэтому в C++ по сравнению с классиче ским С #d e f in e используется реже.
v o i d m a i n ( ) / / и с п о л ь з о в а н и е к о н с т а н т в C++
{
c o n s t |
i n t |
N=10; |
c o n s t |
i n t |
M=100; |
i n t m a t r [ N ] [ N ] ; |
||
d o u b l e |
mas[M] |
|
} |
|
|
20.3. Включение текстов из файлов
Для включения текста из файла используется команда
#i n c l u d e . Она имеет две формы записи:
#i n c l u d e <имя_ файла>
#i n c l u d e "имя_ файла"
В первом случае препроцессор разыскивает файл в стандартных системных каталогах. Во втором случае препроцессор сначала обра щается к текущему каталогу и только потом к системному.
По принятому соглашению к тем файлам, которые надо поме щать в заголовке программы, приписывается расширение h (заголо вочные файлы).
Заголовочные файлы оказываются эффективным средством при модульной разработке крупных программ, в которых используются внешние объекты (переменные, массивы, структуры), глобальные для нескольких частей программы. Описание таких объектов помещается
в одном файле, который с помощью директивы i n c l u d e включается во все модули, где необходимы эти объекты.
/ / ф а й л t r e e , h
/ / д е р е в о и функции для е г о формирования / / и п е ч а т и
# i n c l u d e < i o s t r e a m . h > s t r u c t P o i n t
{
i n t k e y ;
P o i n t * l e f t , * r i g h t ;
};
P o i n t * f i r s t ( i n t d ) / / ф о р м и р о в а н и е п е р в о г о
/ / э л е м е н т а д е р е в а
{
P o i n t * p=new P o i n t ;
p - > k e y = d ; p - > l e f t = 0 ;
p - > r i g h t = 0 ; r e t u r n p;
}
P o i n t * A d d ( P o i n t * r o o t , i n t d ) / / д о б а в л е н и е / / э л е м е н т а d в д е р е в о п о и с к а
{
P o i n t * p = r o o t , * r ; b o o l o k = f a l s e ;
w h i l e ( p & & ! ok)
{
r = p ;
i f ( d = = p - > k e y ) o k = t r u e ; e l s e
i f ( d < p - > k e y ) p = p - > l e f t ; / / п о й т и / / в л е в о е п о д д е р е в о
e l s e p = p - > r i g h t ; / / п о й т и в п р а в о е
/ / п о д д е р е в о
}
i f ( o k ) r e t u r n р ; / / н а й д е н о , не д о б а в л я е м / / с о з д а е м у з е л
P o i n t * N ew _ p oin t= n e w P o i n t ( ) ; //в ы д е л и л и память
New_point->key=d;
N e w _ p o i n t - > l e f t = 0 ;
N e w _ p o i n t - > r i g h t = 0 ;
i f ( d < r - > k e y ) r - > l e f t = N e w _ p o i n t ; e l s e r - > r i g h t = N e w _ p o i n t ;
r e t u r n N e w _ p o i n t ;
}
v o i d S h o w ( P o i n t * p , i n t l e v e l )
{
i f (P)
{
S h o w ( p - > l e f t , l e v e l + 5 ) ;
f o r ( i n t i = 0 ; i < l e v e l ; i + + ) c o u t < < " c o u t < < p - > k e y < < " \ n " ;
S h o w ( p - > r i g h t , l e v e l + 5 ) ;
}
}
/ / Ф а й л с о с н о в н о й п р о г р а м м о й
# i n c l u d e < i o s t r e a m . h >
#include "tree.h"
v o i d m a i n ()
{
i n t n , k ; c o u t « " n ? " ;
c i n > > n ;
P o i n t * r o o t = f i r s t ( 1 0 ) ; / / п е р в ы й э л е м е н т f o r ( i n t i = 0 ; i < n ; i + + )
{
c o u t « ,,? M; c i n > > k ;
A d d ( r o o t , k ) ;
}
S h o w ( r o o t , 0 ) ;
}
Препроцессор добавляет текст файла t r e e . h в файл, в котором расположена основная программа, и, как единое целое, передает на компиляцию.