...
...
ChangeToUpperCase( a_string );
3. Динамические массивы
Правила создания и уничтожения динамических переменных типов "int",
"char", "double" и т.п. (см. п.1.3) распространяются и на динамические массивы. По
отношению к массивам динамическое распределение памяти особенно полезно, по-
скольку иногда бывают массивы больших размеров.
Динамический массив из 10-ти целых чисел можно создать следующим обра-
зом:
int* number_ptr;
number_ptr = new int[10];
Переменные-массивы в Си++ являются указателям, поэтому к 10-ти элементам
динамического массива допускается обращение:
number_ptr[0] number_ptr[1] ... number_ptr[9]
или:
number_ptr *(number_ptr + 1) ... *(number_ptr + 9)
Для уничтожения динамического массива применяется оператор "delete" c
квадратными скобками "[]":
delete[] number_ptr;
Скобки "[]" играют важную роль. Они сообщают оператору, что требуется
уничтожить все элементы массива, а не только первый.
Работа с динамическими массивами показана в программе 3.1. В приведенном
фрагменте программы у пользователя запрашивается список целых чисел, затем вы-
числяется и выводится на экран их среднее значение.
...
...
int no_of_integers, *number_ptr;
cout << "Введите количество целых чисел в списке: ";
cin >> no_of_integers;
number_ptr = new int[no_of_integers];
if ( number_ptr == NULL )
{
cout << "Извините, недостаточно памяти.\n";
exit(1);
}
cout << "Наберите " << no_of_integers;
cout << " целых чисел, разделяя их пробелами:\n";
for ( int count = 0; count < no_of_integers; count++ )
cin >> number_ptr[count];
cout << "Среднее значение: ";
cout << average( number_ptr, no_of_integers );
delete[] number_ptr;
...
82
...
Фрагмент программы 3.1.
Динамические массивы, как и обычные, можно передавать в качестве парамет-
ров функций. Поэтому в программе 3.1 без изменений будет работать функция
"average()" из предыдущей лекции (лекция 6, п. 2).
4. Автоматические и динамические переменные
В некоторых случаях без динамических переменных не удается обойтись, но их
количество можно уменьшить за счет тщательного проектирования структуры про-
граммы и применения процедурной абстракции. Большинство переменных в про-
граммах из предыдущих лекций являются автоматическими переменными. Они ав-
томатически создаются, когда начинает выполнятся блок (или функция), где эти пе-
ременные объявлены. При выходе из блока (или функции) переменные автоматически
уничтожаются. Поэтому в хорошо структурированной программе не слишком много
операторов для создания и уничтожения переменных.
(ПРИМЕЧАНИЕ. В Си++, кроме автоматических и динамических, существуют статические пере-
менные. Для объявления статической переменной в ее операторе описания надо перед названием ти-
па данных добавить служебное слово "static". Статические переменные существуют в течение все-
го времени выполнения программы. Вместо статических переменных чаще используются глобальные
константы, которые объявляются в заголовочных файлах или в начале исходных файлов.)
5. Связные списки
В этом параграфе кратко рассматривается одна из разновидностей абстракт-
ных типов данных (abstract data type, ADT) –связный список. Связный список интере-
сен тем, что при его реализации применяются указатели. О других абстрактных типах
данных более подробно будет говориться в последующих лекциях.
Связный список состоит из узлов. В каждом узле хранятся некоторые данные и
указатель на следующий узел списка (рис. 9). В программе, работающей со списком,
обычно есть еще один отдельный указатель, ссылающийся на первый узел списка
("pointer" на рис. 9). В указатель последнего узла принято записывать значение
"NULL".
Размер связных списков, в отличие от массивов, можно изменять динамически
(во время выполнения программы можно добавлять/удалять отдельные узлы в любом
месте списка).
Рис. 9.. Структура связного списка.
Далее будем рассматривать реализацию на Си++ связного списка для хранения
символьных строк. Сначала определим на Си++, из чего состоит "узел" нашего спи-
ска. Для этого надо объединить строку и указатель в тип данных "узел". Это делается
с помощью оператора описания структуры. Оператор "struct" позволяет создать
новый тип данных, в отличие от оператора "typedef", который, по существу, предна-
значен для присвоения нового имени уже существующему типу данных.
83
Структура –это набор разнотипных переменных (в противоположность масси-
ву, состоящему из элементов одного типа). Применительно к нашей задаче, тип "node"
–это структура, состоящая из символьного массива размером
MAX_WORD_LENGTH и указателя на такую же структуру:
struct node
{
char word[MAX_WORD_LENGTH];
node* ptr_to_next_node;
};
Обратите внимание на точку с запятой после закрывающей фигурной скоб-
ки "}". Слово "struct" является служебным словом Си++ (это аналог "record" в Пас-
кале). Возможно описание узла с применением нового типа данных "указатель на
узел":
struct node;
typedef node* node_ptr;
struct node
{
char word[MAX_WORD_LENGTH];
node_ptr ptr_to_next_node;
};
В строке "struct node;" имя "node" является пустым описанием. Оно напоми-
нает прототип (описание) функции –детали структуры "node" определяются в после-
дующих строках. Пустое определение позволяет в следующей строке с помощью опе-
ратора "typedef" объявить новый тип данных "указатель на структуру node".
5.1 Операторы "." и "->"
После определения структуры "node (узел)" в программе можно объявлять пе-
ременные этого типа:
node my_node, my_next_node;
Для доступа к полям (внутренним переменным) структуры "my_node" надо
пользоваться оператором "." (точка):
cin >> my_node.word;
my_node.ptr_to_next_node = &my_next_node;
Допустим, что в программе были объявлены указатели на узлы, а сами узлы
списка были созданы динамически:
node_ptr my_node_ptr, another_node_ptr;
my_node_ptr = new node;
another_node_ptr = new node;
В таком случае для доступа к полям узлов можно пользоваться совместно опе-
раторами "звездочка" и "точка":
cin >> (*my_node_ptr).word;
(*my_node_ptr).ptr_to_next_node = another_node_ptr;
Более кратко эти выражения записываются с помощью специального операто-
ра "->", который предназначен для доступа к полям структуры через указатель:
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 ".
5.2 Создание связного списка
Ниже приведена функция создания связного списка для хранения символьных
строк, которые пользователь вводит с клавиатуры. Указатель "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.