2020-01-14
97
Введите следующее слово (или '.' для завершения списка): тестовое
Введите следующее слово (или '.' для завершения списка): сообщение
Введите следующее слово (или '.' для завершения списка): из
Введите следующее слово (или '.' для завершения списка): нескольких
Введите следующее слово (или '.' для завершения списка): слов
Введите следующее слово (или '.' для завершения списка): на
Введите следующее слово (или '.' для завершения списка): русском
Введите следующее слово (или '.' для завершения списка): языке
Введите следующее слово (или '.' для завершения списка):.
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
Это тестовое сообщение из нескольких слов на русском языке
ПОСЛЕ КАКОГО СЛОВА ВЫ ХОТИТЕ ВСТАВИТЬ НОВОЕ СЛОВО? это
КАКОЕ СЛОВО ВЫ ХОТИТЕ ВСТАВИТЬ? небольшое
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
Это небольшое тестовое сообщение из нескольких слов на русском языке
КАКОЕ СЛОВО ВЫ ХОТИТЕ УДАЛИТЬ? тестовое
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
|
|
|
Это небольшое сообщение из нескольких слов на русском языке
СОДЕРЖИМОЕ СПИСКА ПОСЛЕ СОРТИРОВКИ:
Из на небольшое нескольких русском слов сообщение это языке
Подсказки. Основные черты алгоритма добавления нового узла заключаются в сле-
дующем:
Для поиска и запоминания узла, после которого надо вставить новый
Узел, применяется дополнительный указатель.
Для создания нового узла применяется еще один дополнительный указа-
Тель.
После выполнения действий 1) и 2) следует модифицировать соответ-
Ствующие указатели.
Возможный алгоритм удаления узла:
Заведите дополнительный указатель на узел перед удаляемым узлом и указатель
На удаляемый узел.
Измените указатель внутри узла, расположенном до удаляемого узла, так, чтобы
Он указывал на узел, расположенный после удаляемого.
Удалите лишний узел.
Для сортировки связного списка несложно адаптировать алгоритм сортиров-
Ки массива из 6-й лекции.
89
ЛЕКЦИЯ 8. Рекурсия
Понятие рекурсии
В хорошо спроектированной программе на Си++ в определениях функций час-
то встречаются вызовы других функций этой же программы или библиотеки Си++.
Например, в предыдущей (7-й) лекции, в определении функции "assign_list(...)"
есть вызов "assign_new_node(...)". Если в определении функции содержится вызов ее
самой, то такая функция называется рекурсивной.
Понятие рекурсии хорошо известно в математике и логике. Например, можно
привести следующее рекурсивное определение натуральных чисел:
• 1 является натуральным числом
|
|
|
• целое число, следующее за натуральным, есть натуральное число.
В данном контексте понятие рекурсии тесно связано с понятием математиче-
ской индукции. Обратите внимание, что в приведенном определении натуральных чи-
Сел есть нерекурсивная часть (базовое утверждение о том, что 1 является натураль-
Ным числом).
Еще одним известным примером рекурсивного определения является опреде-
ление функции факториала "!" для неотрицательных целых чисел:
• 0! = 1
• если n>0, то n! = n*(n-1)!
В этом определении факториала "!" есть базовое утверждение (определение 0!)
И рекурсивная часть. Согласно определению, факториал 6 вычисляется следующим
образом:
6! = 6*5! = 6*5*4! = 6*5*4*3! = 6*5*4*3*2! = 6*5*4*3*2*1! = 6*5*4*3*2*1*1 = 720
Простой пример рекурсии
Рассмотрим рекурсивную функцию "print_backwards()" из программы 2.1. Эта
Функция предназначена для ввода с клавиатуры последовательности символов. Для
Прекращения ввода пользователь должен напечатать специальный символ (точку).
После этого функция печатает введенные символы в обратном порядке.
#include<iostream.h>
void print_backwards();
Int main()
{
print_backwards();
cout << "\n";
return 0;
}
Void print_backwards()
{
char character;
cout << "Введите символ (или '.' для завершения ввода): ";
cin >> character;
if (character!= '.')
{
90
print_backwards();
cout << character;
}
}
Программа 2.1.
Программа 2.1 печатает на экране подобные сообщения:
Введите символ (или '.' для завершения ввода): H
Введите символ (или '.' для завершения ввода): i
Введите символ (или '.' для завершения ввода):.
iH
Порядок выполнения функции "print_backwards()" подробно описан в сле-
дующем параграфе. Пока обратите внимание на то, что вызов "print_backwards()" (в
ее собственном определении) находится внутри оператора "if".
В определениях рекурсивных функций обычно есть некоторый оператор ветв-
ления, у которого, как минимум, одна нерекурсивная ветвь, реализующая "базовое
утверждение" определения функции. Если такой ветви нет, то функция будет вызы-
Вать себя бесконечно (в действительности, до тех пор, пока не будет занята вся па-
Мять).
В программе 2.1 базовое утверждение реализовано неявно – это возврат из
функции, если был введен символ "." (точка).
Как выполняется рекурсивный вызов
Порядок выполнения программы 2.1 легко понять с помощью нескольких схем.
Главная функция начинается с вызова "print_backwards()". Для выполнения вы-
Зова функции в памяти компьютера выделяется некоторое количество памяти (необ-
Ходимое для запоминания адреса возврата, для создания копий параметров по значе-
Нию и для передачи параметров-указателей). Свободная область памяти в момент
первого вызова "print_backwards()" на рис. 1 изображена в виде пустого прямо-
Угольника. Внутри прямоугольника показано содержимое экрана в соответствующие
моменты времени (на схемах считается, что направление "сверху-вниз" соответствует
Увеличению времени, прошедшему с момента запуска программы).
Рис. 1.. Свободная область памяти перед
первым вызовом "print_backwards()"
Рис. 2. Свободная область памяти перед
вторым вызовом "print_backwards()".
Выполнение функции "print_backwards()" начинается со ввода символа, а за-
тем происходит второй вызов "print_backwards()" (в этот момент программа еще не
91
Начинала обратную печать символов). Для второго вызова также выделяется некото-
Рое количество памяти, поэтому объем свободной памяти уменьшается (рис. 2).
Далее процесс повторяется, но, допустим, при третьем вызове
"print_backwards()" пользователь ввел завершающий символ (точку). Поэтому после
