2020-01-14
107
ра "->", который предназначен для доступа к полям структуры через указатель:
84
cin >> my_node_ptr->word;
my_node_ptr->ptr_to_next_node = &my_next_node;
Другими словами, имена "my_node_ptr->word" и "(*my_node_ptr).word" обозна-
чают одно и то же – поле "word" структуры типа "node", на которую ссылается указа-
тель "my_node_ptr ".
Создание связного списка
Ниже приведена функция создания связного списка для хранения символьных
строк, которые пользователь вводит с клавиатуры. Указатель "a_list" ссылается на
первый узел нового списка (на "голову" списка). Для завершения ввода данных поль-
Зователь должен ввести специальный завершающий символ (точку).
void assign_list(node_ptr& a_list)
{
node_ptr current_node, last_node;
assign_new_node(a_list);
cout << "Введите первое слово";
cout << "(или '.' для завершения списка): ";
cin >> a_list->word;
if (!strcmp(".", a_list->word))
{
delete a_list;
a_list = NULL;
}
current_node = a_list; /* СТРОКА 13 */
while (current_node!= NULL)
{
assign_new_node(last_node);
cout << "Введите следующее слово";
cout << "(или '.' для завершения списка): ";
|
|
|
cin >> last_node->word;
if (!strcmp(".", last_node->word))
{
delete last_node;
last_node = NULL;
}
current_node->ptr_to_next_node = last_node;
current_node = last_node;
}
}
Фрагмент программы 5.1.
Функция "assign_new_node(...)" для создания нового узла аналогична
функции "assign_new_int(...)" из программы 1.5.
Порядок действий функции "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 после выхода из функции ввода списка с
Клавиатуры.
Печать связного списка
Напечатать содержимое связного списка на экране несложно. Ниже приведена
функция для печати строк, хранящихся в узлах списка:
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.
Сводка результатов
В лекции описаны способы динамического распределения оперативной памяти
и работа с динамическими переменными с помощью указателей. В Си++ имена мас-
Сивов можно рассматривать как указатели. Поэтому массивы можно создавать и
Уничтожать динамически. В выражениях с указателями можно применять арифмети-
Ческие операции сложения и вычитания. В конце лекции кратко рассмотрены основ-
Ные свойства связного списка и приведен пример реализации этого абстрактного типа
Данных с помощью указателей.
87
Упражнения
Упражнение 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
