Порядок действий функции "assign_list(...)" поясняется на рис. 10-16. На
рис. 10 показано состояние программы после выполнения вызова:
assign_new_node( a_list );
85
Рис. 10.. Состояние программы 5.1 после создания нового списка.
Предположим, что пользователь напечатал слово "мой". Тогда после 13-й стро-
ки программа окажется в состоянии, показанном на рис. 11.
Рис. 11.. Состояние программы после заполнения данными первого узла.
После первой строки в теле цикла "while" программа перейдет в состояние,
показанное на рис. 12.
Рис. 12.. В хвост списка был добавлен новый узел.
Далее, если пользователь напечатал слово "список", то после итерации цикла
"while" программа будет в состоянии, как на рис. 13.
Рис____________. 13. Последний узел списка заполнен данными и в предыдущий узел по-
мещен соответствующий указатель.
После выполнения первой строки во второй итерации цикла "while" состояние
программы см. рис. 14.
Рис. 14.. В хвост списка был добавлен новый узел.
Допустим, в ответ на следующий запрос пользователь напечатает ".". Тогда
после завершения цикла "while" программа будет в состоянии, как на рис. 15.
86
Рис. 15.. Был удален последний узел списка.
Символ "." сигнализирует о том, что пользователь захотел прекратить ввод
данных для списка. Поэтому функция "assign_list(...)" завершается и при выходе
из нее автоматически уничтожаются локальные переменные-указатели "current_node"
и "last_node" (которые были объявлены в теле функции). После возврата из функции
состояние программы будет таким, как на рис. 16.
Рис. 16.. Состояние программы 5.1 после выхода из функции ввода списка с
клавиатуры.
5.3 Печать связного списка
Напечатать содержимое связного списка на экране несложно. Ниже приведена
функция для печати строк, хранящихся в узлах списка:
void print_list( node_ptr a_list )
{
while ( a_list != NULL )
{
cout << a_list->word << " ";
a_list = a_list->ptr_to_next_node;
}
}
Фрагмент программы 5.1.
6. Сводка результатов
В лекции описаны способы динамического распределения оперативной памяти
и работа с динамическими переменными с помощью указателей. В Си++ имена мас-
сивов можно рассматривать как указатели. Поэтому массивы можно создавать и
уничтожать динамически. В выражениях с указателями можно применять арифмети-
ческие операции сложения и вычитания. В конце лекции кратко рассмотрены основ-
ные свойства связного списка и приведен пример реализации этого абстрактного типа
данных с помощью указателей.
87
7. Упражнения
Упражнение 1
Не запуская приведенную далее программу, определите, какие сообщения она
выводит на экран. Для проверки своего ответа запустите программу.
#include <iostream.h>
#include <stddef.h>
typedef int* IntPtrType;
int main()
{
IntPtrType ptr_a, ptr_b, *ptr_c;
ptr_a = new int;
*ptr_a = 3;
ptr_b = ptr_a;
cout << *ptr_a << " " << *ptr_b << "\n";
ptr_b = new int;
*ptr_b = 9;
cout << *ptr_a << " " << *ptr_b << "\n";
*ptr_b = *ptr_a;
cout << *ptr_a << " " << *ptr_b << "\n";
delete ptr_a;
ptr_a = ptr_b;
cout << *ptr_a << " " << *&*&*&*&*ptr_b << "\n";
ptr_c = &ptr_a;
cout << *ptr_c << " " << **ptr_c << "\n";
delete ptr_a;
ptr_a = NULL;
return 0;
}
Упражнение 2
Напишите логическую функцию с двумя параметрами-строками. Функция
должна возвращать "true", если ее первый параметр-строка по алфавиту расположе-
на раньше, чем вторая строка. В противном случае функция должна возвращать
"false". Можете считать, что обе строки содержат только строчные буквы, и в них
нет ни пробелов, ни служебных символов. Проверьте работу функции с помощью
тестовой программы. После отладки функции напишите ее вариант с применением
арифметических выражений с указателями. Убедитесь, что функция работает так же,
как и первый вариант.
Упражнение 3
В программу 5.1 добавьте 3 новых функции и измените программу так, чтобы
проверить их действие.
•Функция
void add_after(node_ptr& list, char a_word[], char word_after[])
Вставляет в связный список "list" после первого встретившегося узла со
словом "a_word" новый узел со словом "word_after". Если в списке "list"
88
нет узла со словом "a_word", то функция не должна модифицировать спи-
сок.
•Функция
void delete_node(node_ptr& a_list, char a_word[])
Удаляет в связном списке "a_list" первый встретившийся узел
со словом "a_word".
•Функция
void list_selection_sort(node_ptr& a_list)
Выполняет сортировку узлов списка в алфавитном порядке (см. Упражне-
ние 2).
Пример экранного ввода/вывода текстовой программы в типичном сеансе работы:
1
Введите первое слово (или '.' для завершения списка): это
Введите следующее слово (или '.' для завершения списка): тестовое
Введите следующее слово (или '.' для завершения списка): сообщение
Введите следующее слово (или '.' для завершения списка): из
Введите следующее слово (или '.' для завершения списка): нескольких
Введите следующее слово (или '.' для завершения списка): слов
Введите следующее слово (или '.' для завершения списка): на
Введите следующее слово (или '.' для завершения списка): русском
Введите следующее слово (или '.' для завершения списка): языке
Введите следующее слово (или '.' для завершения списка): .
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
это тестовое сообщение из нескольких слов на русском языке
ПОСЛЕ КАКОГО СЛОВА ВЫ ХОТИТЕ ВСТАВИТЬ НОВОЕ СЛОВО? это
КАКОЕ СЛОВО ВЫ ХОТИТЕ ВСТАВИТЬ? небольшое
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
это небольшое тестовое сообщение из нескольких слов на русском языке
КАКОЕ СЛОВО ВЫ ХОТИТЕ УДАЛИТЬ? тестовое
ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:
это небольшое сообщение из нескольких слов на русском языке
СОДЕРЖИМОЕ СПИСКА ПОСЛЕ СОРТИРОВКИ:
из на небольшое нескольких русском слов сообщение это языке
Подсказки. Основные черты алгоритма добавления нового узла заключаются в сле-
дующем:
1) Для поиска и запоминания узла, после которого надо вставить новый
узел, применяется дополнительный указатель.
2) Для создания нового узла применяется еще один дополнительный указа-
тель.
3) После выполнения действий 1) и 2) следует модифицировать соответ-
ствующие указатели.
Возможный алгоритм удаления узла:
1) Заведите дополнительный указатель на узел перед удаляемым узлом и указатель
на удаляемый узел.
2) Измените указатель внутри узла, расположенном до удаляемого узла, так, чтобы
он указывал на узел, расположенный после удаляемого.
3) Удалите лишний узел.
Для сортировки связного списка несложно адаптировать алгоритм сортиров-
ки массива из 6-й лекции.
89
ЛЕКЦИЯ 8. Рекурсия
1. Понятие рекурсии
В хорошо спроектированной программе на Си++ в определениях функций час-
то встречаются вызовы других функций этой же программы или библиотеки Си++.
Например, в предыдущей (7-й) лекции, в определении функции "assign_list(...)"
есть вызов "assign_new_node(...)". Если в определении функции содержится вызов ее
самой, то такая функция называется рекурсивной.
Понятие рекурсии хорошо известно в математике и логике. Например, можно
привести следующее рекурсивное определение натуральных чисел:
•1 является натуральным числом
•целое число, следующее за натуральным, есть натуральное число.
В данном контексте понятие рекурсии тесно связано с понятием математиче-
ской индукции. Обратите внимание, что в приведенном определении натуральных чи-
сел есть нерекурсивная часть (базовое утверждение о том, что 1 является натураль-
ным числом).
Еще одним известным примером рекурсивного определения является опреде-
ление функции факториала "!" для неотрицательных целых чисел:
•0! = 1
•если n>0, то n! = n*(n-1)!
В этом определении факториала "!" есть базовое утверждение (определение 0!)