Использование рекурсивных вызовов в программах на языке Си. Лясин Д.Н - 8 стр.

UptoLike

ВУЗ: 

ВПИ ВолгГТУ | Волжский

Составители: 

Рубрика: 

8
Действительно, объявление узла включает в себя указатели на
узлы, корневые для левого и правого поддерева, то есть дерево
самоподобно. Не случайно алгоритмы обработки в бинарных деревьях
преимущественно рекурсивны. Рассмотрим, например, функцию вывода
на экран всех элементов бинарного дерева:
void walkTree(node * p)
{
if(p)
{
walkTree(p->left); //обойти левое поддерево
cout << p->value << ' '; //вывод информационной
части узла
walkTree(p->right); //обойти правое поддерево
}
}
Рассмотрим алгоритм, реализация которого без использования
рекурсии будет неэффективной. Очень популярный алгоритм быстрой
обменной сортировки по Хоару, который используется в том числе в
стандартной библиотеке языка Си (функция qsort), имеет рекурсивную
природу.
Описание работы алгоритма быстрой обменной сортировки:
1. Выбираем в массиве некоторый элемент, который будем
называть опорным элементом.
2. Выполняем операцию разделения массива: реорганизуем массив
таким образом, чтобы все элементы, меньшие или равные опорному
элементу, оказались слева от него, а все элементы, большие опорного —
справа от него. Это можно сделать за один проход по массиву.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа
от опорного элемента.
Рассмотрим пример работы алгоритма. Сначала разберемся с
алгоритмом разделения массива. Пусть задан массив M:
40 80 30 50 60 20 10
Назначим разделитель, например, первый элемент. Будем двигаться
от начала массива направо, пока не найдем числа, больше разделителя.
Будем двигаться от конца массива влево, пока не найдем числа, меньше
разделителя. Отметим разделитель красным цветом, метку движения
справа налево - фиолетовым, а слева направо – зеленым. Нашли первые
числа, удовлетворяющие условиям поиска:
40 80 30 50 60 20 10
Поменяем их местами:
40 10 30 50 60 20 80
Продолжим движение, находим еще одну удовлетворяющую
условиям поиска пару чисел:
40 10 30 50 60 20 80
Меняем их местами: 
      Действительно, объявление узла включает в себя указатели на
узлы, корневые для левого и правого поддерева, то есть дерево
самоподобно. Не случайно алгоритмы обработки в бинарных деревьях
преимущественно рекурсивны. Рассмотрим, например, функцию вывода
на экран всех элементов бинарного дерева:
     void walkTree(node * p)
     {
       if(p)
        {
          walkTree(p->left);  //обойти левое поддерево
          cout << p->value << ' '; //вывод информационной
части узла
          walkTree(p->right);   //обойти правое поддерево
        }
     }
      Рассмотрим алгоритм, реализация которого без использования
рекурсии будет неэффективной. Очень популярный алгоритм быстрой
обменной сортировки по Хоару, который используется в том числе в
стандартной библиотеке языка Си (функция qsort), имеет рекурсивную
природу.
      Описание работы алгоритма быстрой обменной сортировки:
      1. Выбираем в массиве некоторый элемент, который будем
называть опорным элементом.
      2. Выполняем операцию разделения массива: реорганизуем массив
таким образом, чтобы все элементы, меньшие или равные опорному
элементу, оказались слева от него, а все элементы, большие опорного —
справа от него. Это можно сделать за один проход по массиву.
      3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа
от опорного элемента.
      Рассмотрим пример работы алгоритма. Сначала разберемся с
алгоритмом разделения массива. Пусть задан массив M:
        40 80 30 50 60 20 10
      Назначим разделитель, например, первый элемент. Будем двигаться
от начала массива направо, пока не найдем числа, больше разделителя.
Будем двигаться от конца массива влево, пока не найдем числа, меньше
разделителя. Отметим разделитель красным цветом, метку движения
справа налево - фиолетовым, а слева направо – зеленым. Нашли первые
числа, удовлетворяющие условиям поиска:
      40 80 30 50 60 20 10
      Поменяем их местами:
      40 10 30 50 60 20 80
      Продолжим движение, находим еще одну удовлетворяющую
условиям поиска пару чисел:
      40 10 30 50 60 20 80
      Меняем их местами:


                                  8

Страницы