Обработка деревьев с помощью рекурсивного обхода



 

Задача 1. Найти количество четных элементов в дереве.

Для решения этой задачи необходимо перебрать все элементы дерева и проверить информационные поля на четность. Для перебора будем использовать обход дерева слева направо. Результат запоминаем в специальной переменной, которую передаем по ссылке.

 

//количество четных элементов в дереве

void kol(Point *p, 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);

}

}

 

Препроцессорные средства

 

Стадии и команды препроцессорной обработки

 

Назначение препроцессора – обработка исходного текста программы до ее компиляции (можно назвать первой фазой компиляции). Инструкции препроцессора называют директивами. Они начинаются с символа #.

На стадии обработки директив препроцессора возможно выполнение следующих действий:

1. Замена идентификаторов заранее подготовленными последовательностями символов (#define).

2. Включение в программу текста из указанных файлов (#include).

3. Исключение из программы отдельных частей (условная компиляция).

4. Макроподстановка, т. е. замена обозначения параметризируемым текстом.

 

Директива #define

 

Директива #define имеет несколько модификаций. Они предусматривают определение макросов или препроцессорных идентификаторов, каждому из которых ставится в соответствие некоторая последовательность символов. В последующем тексте программы препроцессорные идентификаторы заменяются на заранее оговоренные последовательности символов.

#define идентификатор строка_замещения

Таблица 2. Пример работы директивы define

До обработки После обработки
#define begin { #define end } void main() begin операторы end   void main() { операторы }  

С помощью #define удобно определять размеры массивов

Таблица 3. Пример работы директивы define

 

До обработки После обработки
#define N 10 #define M 100 void main() { int matr[N][N]; double mas[M] …. } void main() { int matr[10][10]; double mas[100]   }  

 

Те же возможности в С++ обеспечивают константы, определенные в тексте программы. Поэтому в С++ по сравнению с классическим С #define используется реже.

 

void main() //использование констант в С++

{

const int N=10;

const int M=100;

int matr[N][N];

double mas[M]

 

}

 

Включение текстов из файлов

 

Для включения текста из файла используется команда #include. Она имеет две формы записи:

#include <имя_файла>

#include “имя_файла”

В первом случае препроцессор разыскивает файл в стандартных системных каталогах. Во втором случае препроцессор сначала обращается к текущему каталогу и только потом к системному.

По принятому соглашению к тем файлам, которые надо помещать в заголовке программы приписывается расширение h (заголовочные файлы). 

Заголовочные файлы оказываются эффективным средством при модульной разработке крупных программ, в которых используются внешние объекты (переменные, массивы, структуры), глобальные для нескольких частей программы. Описание таких объектов помещается в одном файле, который с помощью директивы include включается во все модули, где необходимы эти объекты.

 

//файл tree. h

//дерево и функции для его формирования и печати

#include <iostream.h>

struct Point

{

int key;

Point*left,*right;

};

 

Point* first(int d)//формирование первого элемента дерева

{

Point* p=new Point;

p->key=d;

p->left=0;

p->right=0;

return p;

}

Point* Add(Point*root,int d)//добавление элемента d в дерево поиска

{

Point*p=root,*r;

bool ok=false;

while(p&&!ok)

{

  r=p;

  if(d==p->key)ok=true;

  else

       if(d<p->key)p=p->left;//пойти в левое поддерево

       else p=p->right;//пойти в правое поддерево

}

if(ok) return p;//найдено, не добавляем

//создаем узел

Point* New_point=new Point();//выделили память

New_point->key=d;

New_point->left=0;

New_point->right=0;

if(d<r->key)r->left=New_point;

else r->right =New_point;

return New_point;

}

void Show(Point*p,int level)

{

if(p)

{

  Show(p->left,level+5);

  for(int i=0;i<level;i++)cout<<" ";

  cout<<p->key<<"\n";

  Show(p->right,level+5);

}

}

//Файл с основной программой

#include <iostream.h>

#include "tree.h"

 

void main()

{

 

int n,k;

cout<<"n?";

cin>>n;

Point *root=first(10);//первый элемент

for(int i=0;i<n;i++)

{

  cout<<"?";

  cin>>k;

  Add(root,k);

}

Show(root,0);

}

Препроцессор добавляет текст файла tree.h в файл, в котором расположена основная программа и как единое целое передает на компиляцию.

 

Условная компиляция

 

Для условной компиляции используются следующие команды:

#if константное_выражение #ifdef препроцессорный идентификатор #ifndef препроцессорный идентификатор   позволяют выполнить проверку условий  
#else #endif   позволяют определить диапазон действия проверяемого условия.  

 

Общая структура применения директив условной компиляции следующая:

# if условие текст1

#else текст2

#endif

Конструкция #else текст2 необязательна. текст1 включается в компилируемый текст только при истинности проверяемого условия. Если условие ложно – то при наличии директивы else на компиляцию передается текст2, если эта директива отсутствует, то при ложном условии текст1 просто опускается.

Различие между форматами команд #if следующее:

1. Директива #if константное_выражение проверяет значение константного выражения. Если оно отлично от нуля, то считается, что проверяемое условие истинно.

2. В директиве #ifdef препроцессорный идентификатор проверяется, определен ли с помощью директивы #define идентификатор, помещенный после #ifdef. Если идентификатор определен, то текст1 используется компилятором.

3. В директиве #ifndef препроцессорный идентификатор проверяется обратное условие: истинным считается неопределенность идентификатора. Если идентификатор не определен, то текст1 используется компилятором.

Файлы, которые предназначены для препроцессорного включения, обычно снабжают защитой от повторного включения. Такое повторное включение может произойти, если несколько модулей, в каждом из которых подключается один и тот же файл, объединяются в общий текст программы. Такими средствами защиты снабжены все заголовочные файлы стандартной библиотеки (например, iostream.h).

Схема защиты от повторного включения:

//Файл с именем filename включается в другой файл

#ifndef _FILE_NAME

….//включаемый текст файла filename

#define _FILE_NAME 1

#include <…>//заголовочные файлы

<текст модуля>

#endif

_FILE_NAME – зарезервированный для файла filename препроцессорный идентификатор, который не должен встречаться в других текстах программы.

 


Дата добавления: 2018-04-04; просмотров: 405; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!