Динамический массив из 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).
Автоматические и динамические переменные
В некоторых случаях без динамических переменных не удается обойтись, но их
Количество можно уменьшить за счет тщательного проектирования структуры про-
Граммы и применения процедурной абстракции. Большинство переменных в про-
граммах из предыдущих лекций являются автоматическими переменными. Они ав-
Томатически создаются, когда начинает выполнятся блок (или функция), где эти пе-
Ременные объявлены. При выходе из блока (или функции) переменные автоматически
Уничтожаются. Поэтому в хорошо структурированной программе не слишком много
Операторов для создания и уничтожения переменных.
(ПРИМЕЧАНИЕ. В Си++, кроме автоматических и динамических, существуют статические пере-
Менные. Для объявления статической переменной в ее операторе описания надо перед названием ти-
па данных добавить служебное слово "static". Статические переменные существуют в течение все-
Го времени выполнения программы. Вместо статических переменных чаще используются глобальные
Константы, которые объявляются в заголовочных файлах или в начале исходных файлов.)
Связные списки
В этом параграфе кратко рассматривается одна из разновидностей абстракт-
|
|
ных типов данных (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;