230 I |
Часть 1 # Введение в протратмшроваишв на С^-^ |
Но программа из листинга 6.12 не многим лучше. Конечно, она работает, и не зацикливается (как кажется), однако тип переменной oh в ней определен как char, а затем эта переменная сравнивается с EOF (отрицательным значением). Такое сравнение будет работать только в том случае, если char по умолчанию определя ется как signed (переменная со знаком). На моей машине это так, но на другой необязательно. Замена определения oh на следуюш,ее позволит посмотреть, что происходит в этом случае:
unsigned char oh = cin.peekO; |
/ / конец файла, 255 |
|
|
|
|
|
1 Наберите текст |
(или просто нажмите |
Enter, |
1 чтобы закончить |
ввод): First |
line |
| |
1 Выделено 8: First 1 |
|
|
1 Выделено 11 |
: First line |
|
|
строка 1: First 1^лв |
|
|
This is the last line |
|
|
Выделено 8: This is |
|
|
Выделено 15 |
This is the la |
|
|
Выделено 22 |
This is the last line |
1 |
строка 2: This is the last |
line |
Выделено 1:
Рис. 6.14. Вывод программы из листинга 6.12 (с отладочными сообщениями)
Запустив программу из листинга 6.12, можно видеть, что она действительно зацикливается.
Это обш.ая проблема переносимости. Хорошим ре шением будет использование типа int:
int oh = Cin.peekO; |
/ / конец файла, |
Для программы из листинга 6.12 этого достаточно. Выполнение программы показано на рис. 6.14.
Итак, примеры становятся все более сложными, настало время подумать о других методах управления памятью. Если данная тема кажется вам слишком сложной, переходите сразу к главе 7, где рассказыва ется о функциях С4- + , но не забудьте вернуться сюда и прочитать разделы, посвяш.енные динамическим структурам.
Динамические структуры
в предыдущем разделе рассматривалось применение динамически распределя емой памяти для массивов, что позволяет определять размеры массивов на этапе выполнения, а не на этапе компиляции. Такой метод работы с указателями намно го полезнее, чем методы, обсуждавшиеся в начале главы (ссылки на переменные в стеке или распределение в динамической памяти отдельных переменных).
Применение динамических массивов устраняет опасность порчи содержимого памяти или непроизводительного расходования доступного пространства. За это приходится расплачиваться дополнительной сложностью программы и возможностью "утечки памяти", если программист работает с ее распределением некорректно. Следует принимать во внимание и производительность программы. Управление динамически распределяемой памятью требует времени. Для большинства прило жений такое влияние на производительность несуш,ественно, но если память вы деляется и освобождается слишком часто, возможно снижение быстродействия программы.
Для всех массивов (фиксированного размера и динамических) характерно, что добавление и удаление элементов выполняется быстро и просто, только когда это последний действительный элемент массива. Если элементы добавляются или удаляются в середине массива, то все происходит гораздо сложнее и медленнее. Динамически распределяемые структуры — хорошая альтернатива применению массивов с часто включаемыми и удаляемыми элементами.
Определяемые программистом структуры можно распределять как отдельные узлы и соединять в связанные списки (сети узлов). Чтобы можно было включить узел в связный список, он должен представлять собой структуру, содержащую по крайней мере два компонента: информационный элемент и адрес следующего узла (указатель на следующий узел в связанном списке). Информационный эле мент может быть отдельным значением или структурой с несколькими полями (в соответствии с требованиями приложения). Чтобы сконцентрироваться на во просах программирования, а не на деталях приложения, будем рассматривать очень простую структуру, в которой информационный элемент содержит только одно значение (например, сумму транзакции).
Глава 6 ® Управление памятью |
231 |
При определении типа узла можно свободно выбирать имя поля с адресом следуюндего узла. Назовем его next. А вот его тип свободно выбрать нельзя:
struct Node { |
|
|
double amount; |
/ / |
информационный элемент |
Node* next; } |
/ / |
связь со следующим узлом |
Какое бы имя типа для узла ни использовалось, имя типа поля next будет таким же — добавляется лишь обозначение указателя, поскольку поле next представля ет собой указатель на структуру типа Node. Хорошо бы также использовать один и тот же тип узла в разных контекстах, при необходимости меняя тип информаци онного поля. Один из способов сделать это — ввести другой тип Item и опреде лить его с помош^ью typedef. (Другой способ заключается в применении шаблонов
С+Н |
они более гибкие, но при этом сложнее.) |
typedef |
double |
Item; |
/ / |
Item - синоним double |
struct |
Node { |
|
|
|
Item |
item; |
|
/ / |
информационный элемент |
Node* |
next; } |
; |
/ / |
ссылка на следующий узел |
Выделять узлы в динамической области можно в любое время. Идея исполь зования узлов состоит в создании узла только тогда, когда программе нужно сохра нить информацию в новом элементе (например, после чтения данных с клавиатуры, из файла или из сети). Следовательно, нет необходимости резервировать память заранее, т. е. нет нужды в массивах, а потому отсутствует опасность переполнения и непроизводительного расходования памяти, не нужно сдвигать элементы для вставки или после удаления.
Динамическое управление памятью со связанными узлами сложнее, чем при использовании динамических массивов, но это очень важный навык программиро вания. Указатели, применяемые для операций с узлами, являются именованными переменными. Память для них выделятся в стеке, как для глобальных или локаль ных (в некоей области действия — функции или блоке) переменных. Указатели должны: правильно определяться, инициализироваться и обрабатываться.
Программистов редко интересует значение самого адреса. Указатель исполь зуется не для определения храняш,егося в нем адреса, а для доступа к объекту, на который данный указатель ссылается. Для этого имя указателя применяется с име нем объекта или без него (поскольку распределяемый в динамической области объект имени не имеет).
Следуюш^ий фрагмент программы показывает типичную ошибку программиро вания: здесь определяются два указателя-переменных, которые не инициализиру ются:
Node *р, *q; |
/ / |
область действия * - одно имя |
q->item = amount; |
/ / |
портит содержимое ячейки, |
|
/ / |
на которую ссылается q |
Неинициализированный указатель может ссылаться на что угодно. Если программа не использует данную область памяти, то результаты могут быть корректными. Если эта область задействована ОС или другой программой, возможны проблемы.
Нельзя путать терминологию или обозначения. У программиста на это должна быть своего рода интуиция. До сих пор нам приходилось иметь дело только с нуждаюш,имися в инициализации г-значениями. В следуюш^ем примере с целыми ясно, что переменную х перед использованием в присваивании нужно инициализировать (как г-значение), но переменная у в инициализации не нуждается, поскольку она применяется как 1-значение:
int х; int у; |
/ / |
определение неинициализируемых переменных |
у = х; |
/ / |
X требует инициализации, у - нет |
232Чость I • Введение в программирование на C^^-i^
Вприведенном выше примере q->item используется как 1-значение и не требует предварительной инициализации, однако q применяется как г-значение и должно что-то содержать перед доступом к полю item.
Когда указатель (например, q) правильно инициализируется, его содержимым
будет адрес структуры типа Node. Неизвестно, что именно содержит q: адрес поля item или поля next, начало структуры или что-то среднее. Не стоит пытаться вы яснить это и использовать для оптимизации программы. Адрес указателя должен оставаться абстракцией адреса. Каково бы ни было содержимое q, *q есть зна чение, на которое ссылается указатель. В данном случае — неименованная структура типа Node. Доступ к данному значению называется разыменованием указателя. Аналогично, q->item — значение поля next в той же структуре. До ступ к полям неименованной структуры через указатель, ссылающийся на эту структуру (q->item и q->next) называется разыменованием указателя.
Некоторые программисты не любят работать с двумя операторами указания — стрелкой и звездочкой. Можно использовать и единообразную запись: (*q). item вместо q->item и (*q).next вместо q->next. Скобки здесь необходимы, так как операция указания имеет более высокий приоритет, чем операция разыменования. Следовательно, *q. item означает *(q. next), а это синтаксическая ошибка — опе рация указания может применяться здесь только к структурной переменной, а не к указателю.
Таким образом, программа не должна разыменовывать неинициализированный указатель. Если указатель глобальный, то по умолчанию он имеет значение NULL, и разыменование такого указателя даст ошибку этапа выполнения (обычно про грамма прекрандает работу). Если указатель локальный, его значением будут просто произвольные данные. Интерпретируемое как адрес, такое значение может указывать на любое место в памяти (в динамически распределяемой области или нет). Нужно следить за тем, чтобы не запортить содержимое памяти из-за получе ния подобных некорректных значений.
Установить значение указателя можно несколькими способами. Один из них состоит в присваивании ему адреса именованной переменной с помош.ью операции получения адреса q = &count, но это не особенно полезный способ. Остаются еш,е два способа присваивания значения указателю:
•Выделение новой неименованной переменной в динамически распределяемой области и присваивание указателю значения, возвраш,аемого операцией new (в действительности, неизвестно, на что она ссылается — на начало или конец динамически распределяемой памяти).
•Поиск указателя, который уже ссылается на интересующую нас область памяти, и использование его как источника в присваивании. Этот указатель может быть переменной в стеке или полем переменной в динамически распределяемой области.
Это все, что касается инициализации и присваивания указателей. В следующем фрагменте применяются оба метода:
Node *р, *q = new No'de; q->item = amount;
q->next = NULL;
P = q;
/ / |
q инициализирован, а р - нет |
/ / |
сохраняет значение amount |
/ / |
в динамической области |
/ / |
популярное контрольное значение |
/ / |
для связанных списков . |
/ / |
р ссылается на тот же узел, что и q |
Во многих алгоритмах возникает необходимость перебирать связанную струк туру, т. е. проходить каждый узел и выполнять некоторые операции (получение значения элемента, проверка достижения последнего узла и т. д.). Один из спосо бов сделать это состоит в ведении счетчика узлов (подобно массиву). Другой —
Глава 6 « У п р а в л е н и е памятью |
| 233 Щ |
в переборе узлов до обнаружения контрольного значения в списке. Обычно в ка честве контрольного значения используется содержимое поля next последнего узла, которому присваивается NULL. Преимущество такого подхода в том, что дан ное значение нельзя спутать с другими возможными значениями указателя. Как уже говорилось выше, обычный О для этого также подходит, но многие програм мисты предпочитают применять определенное в библиотеке значение NULL, указы вая тем самым на то, что программа имеет дело с указателями.
C++ не позволяет присваивать адрес переменной одного типа указателю дру гого типа. В этом смысле С+Н язык со строгим контролем типов. В следую щем примере исходного кода программист пытается вывести содержимое каждого байта переменной node (на которую ссылается указатель q) в виде символов ASCII. Обратите внимание, что не все содержимое двоичных полей Node может выводиться, как отображаемые символы. Именно такого рода злоупотребления и не допускает строгий контроль типов:
char |
*с |
= q; |
|
/ / |
нет, это синтаксическая ошибка |
for |
(int |
i = 0; i |
< sizeof(Node); i++) |
/ / |
проход каждого байта |
cout « |
*c++ « |
' '; |
/ / |
вывод каждого байта как символа |
C++ позволяет делать то, что, по мнению программиста, должно быть сделано. Ведь это свободная страна, в конце концов. Если требуется распечатать каждый байт структуры, то такое возможно, следует лишь указать компилятору (и сопро вождающему приложение программисту), что применяется другой тип указателя и что вы знаете, что делаете). Механизм уже известен — приведение типа в C+ + . Вот пример:
char |
с = char*) |
q; |
for |
( i n t |
i = О, |
i < sizeof(Node); i++) |
cout « |
( i n t ) |
(*c++) « ' '; |
/ / |
нет, это синтаксическая ошибка |
/ / |
перебор каждого байта |
/ / |
вывод каждого байта как символа |
Обратите внимание, что типы char и Node несовместимы. Значение одного типа нельзя преобразовать в значение другого даже с помощью приведения типа. Это еще один пример строгого контроля типов в C+ + . Значения указателей разных типов нельзя присваивать друг другу непосредственно, но можно преобразовать их через приведение типа. Почувствуйте разницу. И не злоупотребляйте преобра зованием указателей.
Если программа формирует связанную структуру (в цикле), каждый узел созда ется в динамически распределяемой памяти, заполняется данными (вводимыми с клавиатуры или из файла) и добавляется к связанной структуре. Есть несколько видов связанных структур. Мы рассмотрим простой связанный список, в котором новый узел добавляется к концу списка.
При наличии такой структуры, как связанный список, программа может пооче редно обращаться к каждому узлу, начиная с первого и до узла, содержащего в поле next контрольное значение. Проблема в том, как добраться до конца списка при включении новых узлов. Перебор каждого узла от начала до контрольного значения — дело слишком сложное и дорогое в смысле времени выполнения, особенно, если список разрастается в размере.
Одно из решений данной проблемы состоит во введении указателя на послед ний узел списка. При создании нового узла он добавляется к списку без перебора других узлов. Что означает в этом случае "добавление"? То, что поле next послед него узла (которое содержало адрес NULL) будет ссылаться на новый последний узел. Следовательно, нужно найти имена для поля next последнего узла (1-значе- ние в присваивании) и адрес нового узла (г-значение в присваивании). Между тем оба узла распределяются в динамической области — имен они не имеют! Это означает, что нужно найти указатели, ссылающиеся на эти два узла (послед ний и новый). В следующем фрагменте указатель, ссылающийся на последний узел, называется last, а имя указателя, ссылающегося на новый узел — q. Таким
234 |
Часть I • Введение в програг^1мирование на C++ |
|
образом, присваиванием, добавляющим новый узел в конце связанного списка, |
|
будет last->next = q. В контексте это выглядит так: |
|
Node *last; |
/ / |
указатель на последний узел |
|
do { |
/ / |
до EOF |
|
Node* q = new Node; |
/ / |
создает новый узел в динамической области |
|
i f (q == 0) |
/ / |
проверка на успешное выполнение запроса |
{cout « "Нет памяти: ввод прекращен" << endl;
break; |
} |
/ / |
корректно завершить, если неудача |
q->item |
= amount; |
/ / |
заполнить узел данными программы |
q->next |
= NULL; |
/ / |
контрольное значение для конца списка |
last->next |
= q; |
/ / |
добавить как последний узел в список |
|
|
|
/ / |
другие необходимые операции |
} while (true);
Хорошее решение. Оно показывает, как можно быстро добавить к связанному списку новый узел, не перебирая в списке все имеющиеся узлы. Не указаны лишь две важные вещи: как начать и как закончить, т. е. как подсоединить к пустому списку самый первый узел и как убедиться, что на следующей итерации цикла указатель последнего узла действительно ссылается на последний узел в списке, а не на бывший последний (предшествующий вновь добавленному).
При добавлении к списку самого первого узла выражение last > next не имеет смысла, так как в списке нет узлов и, следовательно, next не может принадлежать выделенному ранее узлу. Это означает, что при добавлении к списку самого пер вого узла нужно обойти данное присваивание и делать что-то еще. Например, присоединить первый узел к "голове" списка.
Обычно "голова" списка просто представляет собой еще один указатель. Назо вем его data. Один из способов сообщить об отсутствии присоединенных к списку узлов состоит в ведении счетчика узлов списка. Когда счетчик count равен О, новый узел нужно добавлять к указателю списка data. Когда счетчик не равен О, новый узел слелует добавлять к концу списка, т. е. list->next:
Node *last, *data; int count=0 |
|
/ / |
указатель первый/последний, |
|
|
/ / |
счетчик узлов |
do { |
|
/ / |
до конца данных |
|
|
/ / |
получение значения amount |
Node* q = new Node; |
/ / |
создание нового узла в динамической области |
i f (q == 0) |
/ / |
проверка на успешное выполнение запроса |
{cout « "Нет памяти: ввод прекращен" « endl;
break; |
} |
/ / |
корректно завершить, если неудача |
q->item = amount; |
/ / |
заполнить узел данными программы |
q->next = NULL; |
/ / |
контрольное значение для конца списка |
i f (count == 0) |
/ / |
только для первого узла |
data = q; |
|
/ / |
добавить первый узел в список |
else |
|
|
|
last->next |
= q; |
/ / |
добавить как последний узел в список |
|
|
/ / |
другие необходимые операции |
} while (true);
Помните об условном операторе? Это как раз та ситуация, когда данный опера тор очень удобен. В зависимости от значения count, выражение возвращает data или last->next. Затем указатель q присваивается соответственно либо указателю data, либо las ->next.
(count == О ? data : last->next) = q; |
/ / хорошая запись |
Глава 6 # Управление памятью |
235 |
Еш.е один способ начать список состоит в инициализации указателя списка data значением NULL. В цикле после распределения и инициализации нового узла можно проверить, содержит ли указатель списка NULL. Если да, то новый узел — это первый узел в списке, который следует присоединить к data. Если он не NULL, то новый узел не является первым и его следует добавить к list->next.
i f (data == |
NULL) |
/ / |
это значит, |
что узлов |
еще нет |
|
data = q; |
|
/ / |
устанавливает указатель |
списка на первый |
узел |
else |
|
|
|
|
|
|
|
l a s t - > n e x t |
= q; |
/ / |
новый узел |
добавляется |
к |
последнему узлу |
списка |
Если предпочитаете условный оператор, можно использовать его:
(data == О ? data : last->next) = q; |
// эффектный код |
Все это проиллюстрировано на рис. 6.15. На рис. 6.15а — начальное состояние списка, когда указатель data инициализирован значением О, а указатель last пока может ссылаться на что угодно. Рис. 6.15Ь демонстрирует состояние списка после добавления первого узла (когда значение amount равно 22). Инициализируется новый узел, на него ссылается указатель q, а указатели data и last ссылаются на следующий узел. Обратите внимание, что next имеет тот же размер, что и указа тели data и last, поскольку все они одного типа — Node*. Из рис. 6.15с видно, как выглядит список после добавления еще одного узла (на него ссылается указа тель q). Рис. 6.15d демонстрирует первый шаг добавления к концу списка: поле next последнего узла (last->next) устанавливается на новый узел (куда ссылается q). На рис. 6.15е показан второй шаг добавления: указатель last устанавливается на новый узел.
* ' & |
|
D |
data |
|
last |
в,Ц |
> 22 |
|
data |
у |
last |
[Г |
|
|
='•-^03* |
•0 |
data |
a Нзз 0 |
last |
Node *data = О, *last;
Node *q = new Node; q->item = amount; q->next = 0;
data = q; last = q;
Node *q = new Node; q->item = annount; q->next = 0;
D) |
a-- • 2 2 |
N |
•a |
last->next = q; |
|
|
|
|
data |
Q |
last |
|
|
|
|
33 |
|
|
|
|
|
|
|
|
E) |
D- > |
22 |
К |
|
|
last = q; |
|
|
|
|
|
|
|
|
data |
D- |
33 |
last |
|
Рис. 6 . 1 5 . Диаграмма указателей для включения нового узла в конец связанного списка
236 |
Часть I # Введение в nporpoivii^HpOBaHHe на С^^ |
|
Как видно, после добавления нового узла в конце списка следует переместить |
|
указатель |
last, так как он |
ссылается на узел, предшествуюидий последнему, |
|
и присваивание last->next |
на следующей итерации было бы некорректно. Для |
|
перемеидения указателя last |
нужно записать оператор присваивания, где указа |
|
тель last |
находится слева. Что же будет справа? Чтобы ответить на данный |
|
вопрос, нужно найти указатель, уже ссылаюидийся на цель присваивания, т. е. |
|
указатель на новый узел. |
|
|
Посмотрите на рис. 6.15d. Ссылаются ли какие-нибудь указатели на вновь |
|
добавленный узел? Да. Даже два. Один из них — указатель q, который использо |
|
вался ддя распределения нового узла. Другой — указатель last->next, который |
|
использовался для добавления этого узла в список. Подойдет любой. |
|
last = q; |
/ / |
переустановить указатель снова на последний узел |
Используя второй указатель для ссылки на новый узел, можно получить:
last = last->next; |
/ / перемещение указателя к следующему узлу списка |
Это вторая форма перемещения указателя last на самом деле представляет собой обобнденный метод установки указателя на следующий узел в связанном списке. Такой метод очень популярен в алгоритмах обработки списков. Он эквивалентен оператору i++ при переборе элементов массива, перемещающему индекс на следующий элемент.
Влистинге 6.13 приведена программа, аналогичная приведенной в листингах 6.9
и6.10. Данные транзакций считываются с клавиатуры. Вместо выделения фикси рованного массива в стеке (как в листинге 6.9) или распределения массива в ди намической области памяти программа выделяет память для каждого узла и каждого получаемого значения. Затем узел добавляется в конец связанного списка.
Листинг 6.13. Использование связанного списка узлов в динамически распределяемой памяти
#inclucie |
<iostream> |
|
|
|
|
#inclucle |
<iomanip> |
|
|
|
|
using |
namespace std; |
|
|
|
|
typedef |
double |
Item; |
|
|
|
|
struct |
Node { |
|
|
|
|
|
Item |
item; |
|
|
|
|
|
Node* next; |
} ; |
|
|
|
|
int main |
() |
|
|
|
|
|
{ int |
count = 0; |
|
/ / |
счетчик amount |
|
Node *data=0, |
*last; |
' |
/ / |
указатели на начало и конец списка |
do { |
|
|
|
|
|
/ / |
пока не встретится EOF |
double amount; |
|
/ / |
локальная переменная для ввода |
cout |
« |
" Введите сумму (или О для завершения): "; |
|
i f |
(amount == 0) break; |
|
|
|
|
cin |
» |
amount; |
|
/ / |
получить следующее значение double |
i f |
(amount==0) break; |
|
/ / |
остановить ввод, |
если более нет данных |
Node* q = new Node; |
|
/ / |
создать в динамической области новый узел |
i f |
(q == 0) |
|
|
/ / |
проверка на успешное выполнение запроса |
{ cout « |
"Нет памяти в динамической |
области" « endl; break; |
} |
q->item |
= amount; |
|
/ / |
заполнить узел данными программы |
q->next |
= NULL; |
|
/ / |
контрольное значение для конца списка |
(data |
== О ? data : last->next) ^ q; |
|
|
|
|
last |
= q; |
|
|
/ / |
last=last->next; |
также годится |
count++;
} while (true);
|
|
|
|
|
|
|
Глава 6 ^ Уоровление паллятью |
237 |
cout « |
"\пВсего загружено " « |
count |
« |
значений\п"; |
|
|
|
if (count == 0) return 0; |
|
|
|
итог\п\п" |
/ / |
нет вывода, если нет ввода из файла |
cout « |
"\пНомер Сумма Промежуточный |
/ / |
печать |
заголовка |
|
cout.setf(ios::fixecl); |
|
|
|
|
|
/ / |
фиксированный формат для double |
cout.presicion(2); |
|
|
|
|
|
/ / |
цифры после десятичной |
точки |
double |
t o t a l = 0; |
|
|
|
|
|
/ / |
сумма для ввода значений |
Node *q = data; |
|
|
|
|
|
/ / |
старт в начале списка |
|
for |
(int |
i = 0; i < count; i++) |
|
|
|
/ / |
перебор данных списка |
|
|
{ |
t o t a l += q->item; |
|
|
|
|
/ / |
накопление итоговой суммы |
|
|
cout.width(3); cout « i+1; |
|
|
/ / |
номер транзакции |
|
|
|
cout.width(IO); |
cout |
« |
q->item; |
|
/ / |
значение |
транзакции |
|
|
|
cout.width(11); |
cout |
« |
total « |
endl |
/ / |
текущий |
итог |
|
|
|
q = q->next; } |
|
|
|
|
|
/ / |
перемещение указателя на след. узел |
Node *p = data, *r = data; |
|
|
|
|
/ / |
инициализация перебора |
указателей |
while |
(p != NULL) |
/ / |
пока не кончится список |
{ |
p = p->next; |
/ / предотвращение "зависания" последнего узла |
|
delete r; r = p; } |
/ / |
удаление узла, переход к следующему |
return 0;
После чтения всех данных программа перебирает связанный список. Для каждого узла она выводит сумму транзакции и текущий промежуточный итог. Вывод программы представлен на рис. 6.16.
Код прохода по связанному списку инициализирует локальный указатель q, ссылающийся на начало спис ка (q = data). Затем он делает count шагов по списку и на каждом шаге обращается к узлу по указателю q (в данном случае накапливает total, выводит Number, Amount и Subtotal). После этого установкой q в q->next выполняется переход к следующему узлу. Когда q ста новится равным NULL, найден последний узел (его поле next содержит NULL) и цикл завершается.
Еще одна форма этого цикла для перебора списка переустанавливает указатель в заголовке цикла for:
1 |
Введите сумму |
(или 0 длязавершения): 22 |
1 |
1 |
Введите сумму |
(или 0 длязавершения): 33 |
|
1 |
Введите |
сумму |
(или 0 длязавершения): 44 |
|
1 |
Введите |
сумму |
(или 0 длязавершения): 55 |
|
1 |
Введите |
сумму |
(или 0 длязавершения): 66 |
|
1 |
Введите |
сумму |
(или 0 длязавершения): 0 |
|
Всего |
загружено |
5 значений |
Номер |
Сумма |
Промежуточный итог |
1 |
22.00 |
22.00 |
2 |
33.00 |
55.00 |
3 |
44.00 |
99.00 |
4 |
55.00 |
154.00 |
5 |
66.00 |
220.00 |
Рис. 6.16. Вывод программы из листинга 6.13
double t o t a l = 0; |
|
/ / |
сумма для вводимых величин |
int |
i = 0; |
|
/ / |
старт в начале списка |
for |
(Node* q=data; q!=NULL; |
q=q->next) |
/ / |
проход по списку |
{ |
t o t a l |
+= q->iteni; |
|
/ / |
накопление total |
|
cout.width(3); cout « i+1; |
/ / |
номер транзакции |
|
cout.width(IO); cout « |
q->item; |
/ / |
значение |
транзакции |
|
cout.width(11); cout « |
t o t a l « endl; |
/ / |
текущий |
итог |
|
i++; |
} |
|
/ / |
увеличение счетчика |
|
|
|
|
/ / |
обработанных узлов |
Обратите внимание, что имя q уже было ранее в программе. Оно было локаль ным в цикле ввода, а потому допускается повторное использование данного имени в программе без какого-либо анализа. Если бы оно определялось в области дейст вия функции main О, подобно data, то для дальнейшего применения данного имени нужно было бы анализировать, можно ли использовать его для других целей, или потребуется другое имя. Это еще один пример уменьшения зависимости между от дельными частями программы за счет корректного применения области действия. Тем самым уменьшается сложность программы и упроидается ее сопровождение.
238 |
Часть I • Введение в программирование на C-f-f |
Последний цикл в программе из листинга 6.13 показывает еш.е один вид про хода по списку. Здесь цель состоит в возврате списка узлов в динамически распре деляемую область, чтобы избежать "утечки памяти". В данном простом примере, когда программа распределяет узлы, поочередно перебирая их, а потом завершает работу, это не так важно. О динамически распределяемой памяти позаботится ОС. Это важно для программ, где выделение и освобождение памяти для узлов проис ходит многократно в процессе выполнения (иногда в течение очень долгого време ни). Ясно, что в таких программах неосвобождение выделяемой для узлов памяти приведет к проблемам.
Следуюш.ий цикл включен в программу для демонстрации еш.е одного способа перебора списка. Цикл должен проходить каждый узел списка и удалять его. Здесь также нужно инициализировать указатель для ссылки на первый узел и перемеш,е- ния к следуюи;ему узлу. При достижении последнего узла переход к следуюш^ему узлу приведет к тому, что указатель примет значение NULL. Популярным вариантом перебора списка является применение цикла for:
for |
(Node *q = data; |
q != NULL; q = q->next) |
/ / |
просмотр каждого узла |
{ |
delete q; } |
|
/ / |
освобождение памяти в |
|
|
/ / динамически распределяемой области |
Хороший цикл. Его заголовок почти стандартен и может применяться во многих контекстах. Проблема здесь в том, что выражение инкремента q = q->next выпол няется после тела цикла и перед проверкой условия завершения цикла. Между тем в теле цикла освобождается память, на которую ссылается указатель q. Эта память может использоваться для других целей, и данная программа никоим образом не должна на нее ссылаться. После delete q данный цикл ссылается на q->next.
Кстати, это вовсе не означает, что программа выполняется некорректно. На одной из моих машин она работала правильно, так как память, на которую ссылал ся указатель q, была помечена как свободная и не использовалась для других целей. Поэтому выражение q->next действительно давало адрес следуюш,его узла правильно. Однако не нужно полагаться на это и считать допустимым ссылки на чью-то память. На другой машине данная программа аварийно завершалась. Так что корректность результатов программы С+4- вовсе не означает, что программа работает правильно.
Программа из листинга 6.13 использует более сложную, но более надежную форму цикла. Указатели риг ссылаются здесь на один узел. Затем р перемеш.а- ется на следуюш,ий узел, а узел, на который ссылается г, удаляется. После этого р и г снова ссылаются на один узел:
Node *р = data, *г = data; |
/ / |
инициализация перебора указателей |
while (р != NULL) |
/ / |
пока не кончится список |
{ р = p->next; |
/ / |
предотвращение |
"зависания" последнего узла |
delete г; г = р; } |
/ / |
удаление узла, |
переход к следующему |
Обратите внимание, что "delete г" здесь следует читать как "удален узел, на который ссылается г", а не "узел г удален". Не стоит верить в то, что удаляется сам указатель. Это весьма далеко от истины. Указатель имеет имя, и, следователь но, память для него выделяется в стеке. Таким образом, он удаляется согласно правилам языка при достижении закрываюш.ей фигурной скобки области дейст вия, где указатель определен. Операция delete удаляет только неименованные переменные в динамически распределяемой области.
И еш,е одно, последнее предупреждение. Когда данная программа работает со связанными узлами в динамически распределяемой области памяти, ее корректная компиляция и правильное выполнение для всех наборов данных не означает, что программа действительно корректна. Это справедливо лишь для алгоритмов, не работаюи|их с динамически распределяемой памятью. Поэтому никогда не стоит применять более сложных решений, чем того действительно требует приложение.
Глава 6 • Управление памятью |
239 |
Обмен данными с файлами на диске
Во всех предыдундих примерах программа считывала данные с клавиатуры и выводила их на экран. Это позволяло нам сконцентрироваться на других момен тах, но в реальных приложениях все иначе. Программа должна иметь возможность получать данные, созданные другими приложениями, и сохранять результаты для будундего использования. В этом разделе кратко рассматриваются файлы — как еще один способ работы с большими наборами данных.
Как и другие современные языки, C++ не имеет встроенных операций вводавывода. Они вынесены из самого языка в библиотеку. Программы C++ могут использовать две библиотеки: стандартную библиотеку ввода-вывода stdio, унаследованную из языка С, и более новую библиотеку lost ream, разработанную специально для C++.
Обе библиотеки поддерживают файловый ввод и вывод. Библиотека С сложна и порождает ошибки.
Это важно знать программистам, поддерживаюш,им унаследованные програм мы на С. Библиотека C++ способствуют снижению количества ошибок в про граммах, но более сложна и громоздка. Часто одно и то же действие можно выполнить двумя способами. Чтобы понять, как работает библиотека C+ + , нуж но знать об использовании классов C+ + , о наследовании, множественном насле довании и другие концепции, которые пока не обсуждались. Вот почему в данном разделе описываются лишь базовые средства, позволяюш^ие считывать данные из файлов на диске и записывать их в файл.
Вывод в файл
Начнем с записи в файл, поскольку это в чем-то прош^е, чем чтение из файла. На самом деле запись данных в файл на диске аналогична выводу данных на
экран монитора, но вместо предопределенного объекта cout используется опреде ляемый программистом объект библиотечного класса ofst ream (output file stream — поток вывода в файл). Этот класс определен в библиотечном заголовочном файле fSt ream, который нужно включить в исходный код.
Как говорилось в главе 2, объект представляет собой экземпляр класса, комбинируюш,ий данные и поведение, т. е. структуру, компоненты которой включают в себя функции. Библиотечный класс ofstream сконструирован так, что все до ступные для стандартного объекта cout функции доступны и для определяемых программистом объектов класса ofstream.
Это очень удобно. Все, что нужно сделать,— направить вывод программы вместо экрана в файл на диске, для чего определяется объект класса ofstream, подставляемый в программе вместо объекта cout. Операторы вывода (включая операторы форматирования) выполняют те же действия^что и для объекта cout. Они преобразуют последовательности битов в переменных программы в последо вательности записываемых символов, но выводятся они не на экран, а в файл на диске.
В листинге 6.14 показана программа из листинга 6.12, считывающая набор строк произвольной длины и сохраняюш,ая их в файле data. out. Для этого потре бовались минимальные изменения.
Как видно, здесь определяется объект f класса ofstream. В качестве аргумента при создании файлового объекта задается имя физического файла на диске:
ofstreamf("data.out"); / / открыть файл для вывода
Этот оператор связывает объект f с физическим файлом data, out в том же ката логе, что и выполняемый файл программы. Если нужно задать файл в другом каталоге, то используется соответствуюш.ий маршрут (не забывайте только о ' \\'
