Файл: Think likea programmer.pdf

Решение задач с указателями и динамической памятью 127
averageReord
Функция получает указатель на коллекцию студенческих карто- чек и возвращает среднее значение баллов студентов этой коллекции в формате double.
Коллекция может быть любого размера. Предполагается, что функция addRecord бу- дет использоваться часто, следовательно, она должна быть реализована наиболее эффективным способом.
Из всего многообразия методов, соответствующих техническому заданию, мы выберем связные списки , которые позволят попракти- коваться в работе с указателями. Вы, должно быть, уже сталкивались со связными списками раньше, а если нет, то знайте, что создание связного списка представляет собой нечто радикально отличающее- ся от всего, что мы обсуждали раньше в этой книге. Хороший специ- алист по решению задач мог бы прийти к любому из предыдущих ре- шений, потратив достаточное количество времени и тщательно все обдумав. Большинство программистов, однако, не смогли бы разра- ботать концепцию связных списков без посторонней помощи. Тем не менее, однажды увидев и овладев основами, вы сможете придумы- вать другие связные структуры по накатанной. Связный список яв- ляется по-настоящему динамической структурой. Наши строковые массивы хранились в динамически выделенной памяти, но, будучи однажды созданными, они становились статическими структурами, которые не меняли своего размера и только иногда перемещались. В отличие от них, связный список постепенно увеличивается звено за звеном, как гирлянда.
Построение списка узлов
Давайте создадим простейший связный список студенческих кар- точек. Для объявления связного списка вам понадобится создать структуру с помощью ключевого слова struct, которая содержит указатель на такую же структуру вдобавок к тем данным, которые вы хотите сохранить в коллекции, реализованной с помощью связного списка. В нашем случае структура struct будет содержать номер сту- дента и его балл.
struct
XlistNode {
Yint studentNum;
int grade;
ZlistNode * next;
};
[ typedef listNode * studentCollection;
Мы создали структуру listNode
X
. Структуры, которые создают- ся для реализации связного списка, всегда называются узлами . Мож- но предположить, что они получили это название по аналогии с бо- таническим термином, обозначающим точку на стволе, из которой растут новые ветви. Узел содержит номер студента
Y
и его балл, кото- рые составляют полезное содержимое узла. Также узел содержит ука- затель на ту же структуру, которую мы только что описали
Z
. Когда

128 Глава 4
большинство программистов видит эту конструкцию в первый раз, они не могут понять, как же можно создать структуру, ссылающую- ся на саму себя. Но все это вполне законно, и скоро вы поймете это.
Обратите внимание, что указатели, ссылающиеся на самих себя, но- сят названия типа next (от англ. следующий), nextPtr и тому подобные.
И наконец, в коде объявляется указатель на список узлов
[
. Это улуч- шит читаемость наших функций. Теперь давайте создадим пробный связный список с использованием этих типов:
X studentCollection sc;
Y listNode * node1 = new listNode;
Z node1->studentNum = 1001; node1->grade = 78;
listNode * node2 = new listNode;
node2->studentNum = 1012; node2->grade = 93;
listNode * node3 = new listNode;
[ node3->studentNum = 1076; node3->grade = 85;
\ sc = node1;
] node1->next = node2;
^ node2->next = node3;
_ node3->next = NULL;
` node1 = node2 = node3 = NULL;
Вначале мы объявляем структуру studentCollection, sc
X
, кото- рая в конечном счете станет названием нашего связного списка. Затем мы объявляем переменную node1
Y
, которая является указателем на listNode
. Еще раз повторю, studentCollection — синоним listNode *, но для лучшей читаемости я использую тип studentCollection только для переменной, которая будет ссылаться на весь список студенческих карточек. После объявления указателя node1 и его инициализации с помощью динамически созданного в куче узла
Y
мы присваиваем зна- чение полям studentNum и grade в узле
Z
. В этот момент следующее поле не определено. У нас не справочник по синтаксису, но если вы раньше не встречали нотацию -> , то поясню, что она используется для обращения к полям (свойствам) структуры (или класса). Таким образом, запись node1->studentNum означает «поле studentNum в пере- менной типа struct, на которую указывает node1» и эквивалентна за- писи (*node1).studentNum. Потом мы повторяем ту же процедуру для узлов node2 и node3. На рис. 4–9 можно увидеть состояние памяти по- сле присвоения значений полям последнего узла. Чтобы показать узел struct
, на этой схеме мы используем метод разделенных ящиков, ко- торый мы уже применяли раньше для массивов.
Рис. 4.9. На полпути к построению связного списка

Решение задач с указателями и динамической памятью 129
Теперь, когда у нас уже есть все узлы, мы можем выстроить их между собой в связный список. Это как раз то, что делает оставший- ся код из предыдущего листинга. Во-первых, мы направляем указа- тель studentCollection на первый узел
\
. Затем мы направляем поле next первого узла на второй узел
]
, а после этого направляем поле next второго узла на третий узел
^
. На следующем шаге мы присваи- ваем значение NULL (еще раз уточню, что это всего лишь псевдоним нуля) полю next третьего узла
_
. Мы делаем это по тем же причи- нам, по которым ставили нулевой символ в конце массивов в пре- дыдущей задаче: чтобы обозначить окончание структуры. Точно так же, как нам был необходим специальный символ для обозначения за- вершения массива, нам нужен ноль в поле next последнего узла наше- го связного списка, чтобы мы точно знали, что это последний узел.
Наконец, чтобы подчистить хвосты и избежать возможной пробле- мы перекрестных ссылок, мы присваиваем значение NULL каждому из индивидуальных указателей на узлы
`
. Конечное состояние памя- ти можно увидеть на рис. 4.10.
Рис. 4.10. Завершенный связный список
Глядя на рисунок, легко понять, почему структура называется связным списком: каждый узел списка связан со следующим узлом.
Вы будете часто встречать линейное изображение связных списков, но я предпочитаю распределенный по памяти вид этой схемы, так как он подчеркивает, что эти узлы не имеют никакого отношения друг к другу, кроме ссылок. Каждый из них может храниться в любом уголке кучи. Удостоверьтесь, что вы разобрались с кодом, перед тем как согласиться со схемой.
Обратите внимание, что в конечном состоянии остался только один указатель на стек переменная типа studentCollection sc, ко- торая указывает на первый узел. Указатель, внешний для списка (не является полем next в узле списка), который указывает на первый узел связного списка, называется головной указатель . Чисто символи- чески эта переменная представляет список целиком, но, конечно, по факту она указывает только на первый узел. Чтобы достичь второ- го узла, нам нужно идти через первый, а чтобы добраться до третье- го – через первый и второй и т.д. Это значит, что связный список допускает только последовательный доступ , в отличие от произволь- ного доступа, который предоставляют массивы. Последовательный доступ является слабым местом связного списка. А сильная сторона

130 Глава 4
связного списка, как уже обсуждалось раньше — это способность уве- личиваться или уменьшаться в размерах путем добавления или уда- ления узлов, без создания абсолютно новых структур и копирования данных, как мы это делали при работе с массивами.
Добавление узлов в список
Теперь давайте перейдем к реализации функции addRecord. Эта функция будет создавать новый узел и добавлять его к существующе- му связному списку. Мы будем пользоваться той же техникой, что и при решении предыдущей задачи. Во-первых, заготовка и пробный вызов. Для тестирования мы будем дорабатывать код предыдущего листинга, таким образом, sc уже существует в качестве головного указателя на связный список с тремя узлами.
void addRecord(studentCollection& sc, int stuNum, int gr) {
}
X addRecord(sc, 1274, 91);
Еще раз повторю, что
X
вызов функции произойдет в конце пре- дыдущего листинга. Раз у нас теперь есть заготовка функции с пара- метрами, то мы можем нарисовать схему состояния «до» вызова, как это показано на рис. 4.11.
Рис. 4.11. Состояние «до» вызова функции
addRecord
Что касается состояния «после», то у нас есть выбор. Нетрудно догадаться, что нам нужно создать новый узел, хранящийся в куче, и скопировать в него параметры stuNum и gr. Но открытым остается вопрос о позиции, на которую новый узел будет добавлен в список.
Наиболее очевидный выбор — это добавление в конец: тогда просто нужно направить нулевой указатель в поле next на новый узел. Это будет соответствовать рис. 4.12.
Рис. 4.12. Предполагаемое состояние «после» вызова функции
addRecord

Решение задач с указателями и динамической памятью 131
Но если мы предполагаем, что порядок записей не имеет значе- ния (нам не нужно поддерживать записи в определенном порядке, в котором они были добавлены в коллекцию), то это неверный выбор.
Чтобы понять, почему, давайте рассмотрим коллекцию не из трех студенческих карточек, а из 3000. Чтобы добраться до последней за- писи нашего связного списка с целью изменить ее поле next, требу- ется пройти через все 3000 узлов. Это непозволительно неэффектив- но, так как мы можем добраться до нового узла и не проходя через
каждый из существующих узлов. На рис. 4.13 можно увидеть, как это сделать. После создания нового узла он добавляется в начало списка, а не в конец. В состоянии «после» наш головной указатель sc указы- вает на новый узел, в то время как поле next нового узла указывает на бывший первый узел списка, тот, в котором хранится запись о сту- денте с номером 1001. Стоит отметить, что, пока мы присваиваем значение полю next нового узла, изменяется только один указатель sc и ни одно из значений в существующих узлах не меняется и даже не проверяется. Напишем код, ориентируясь на схему:
void addRecord(studentCollection& sc, int stuNum, int gr) {
X listNode * newNode = new listNode;
Y newNode->studentNum = stuNum;
newNode->grade = gr;
Z newNode->next = sc;
[ sc = newNode;
}
Рис. 4.13. Приемлемое состояние «после» вызова функции
addRecord. Пунктирная стрелка
указывает на предыдущее значение указателя
sc
Еще раз подчеркиваю, что разобраться со схемой и этим кодом намного проще, чем пытаться представить и понять все это у себя в голове. Код напрямую вытекает из иллюстрации. Мы создаем но- вый узел
X
и копируем номер студента и его балл из параметров
Y
Затем привязываем новый узел к списку первым, направив указа- тель его поля next на бывший первый узел (копируя значение указа- теля sc)
Z
, а далее перенаправляем указатель sc на новый узел
[
Стоит отметить, что два последних шага происходят именно в этом порядке. Мы должны использовать первоначальное значение указа- теля sc, перед тем как изменить его. Также стоит отметить, что раз

132 Глава 4
мы меняем значение указателя sc, то он должен быть ссылочным па- раметром.
Как всегда после написания кода для типичного примера, мы долж- ны проверить возможные специальные случаи. В этом примере мы бу- дем проверять, что функция работает в ситуации с пустым списком.
В примере со строковым массивом пустая строка была также и указа- телем, так как у нас по-прежнему был массив, на который можно было указывать и который содержал только нулевой завершающий байт.
Здесь же количество узлов совпадает с количеством студенческих кар- точек, и поэтому пустой список будет головным указателем, содержа- щим NULL. Будет ли наш код по-прежнему работать, если мы попыта- емся соединить типичный пример с нулевым указателем? На рис. 4.14 представлены состояние «до» и желаемое со стояние «после».
Запустив этот пример с кодом, мы видим, что все прекрасно ра- ботает. Новый узел создается, как и раньше. Так как указатель sc со- держит NULL перед началом работы функции, то именно это значе- ние копируется в поле next нового узла
Z
. Это соответствует нашим ожиданиям, и список, содержащий один узел, получает корректное окончание. Стоит отметить, что, если мы продолжим реализовы- вать другую идею – добавление нового узла в конец связного списка – изначально пустой список станет специальным случаем, так как это будет единственный случай, когда указатель sc будет меняться.
Рис. 4.14. Состояния «до» и «после» вызова функции
addRecord в случае нулевого списка
Обход списка
И вот наконец настало время для того, чтобы разобраться с функци- ей averageRecord. Как и раньше, мы начнем с заготовки и схемы. Рас- смотрим заготовку функции и вызов типичного примера. Полагаю, что типичный вызов
X
происходит после создания нашего первона- чального типичного списка, как показано на рис. 4.10.
double averageRecord(studentCollection sc) {
}
X int avg = averageRecord(sc);

Решение задач с указателями и динамической памятью 133
Как вы видите, я решил вычислять среднее значение в формате int
, как мы делали это с массивами в предыдущей главе. В зависи- мости от задачи, однако, может быть лучше рассчитывать среднее как значение с плавающей точкой. Сейчас нам нужна схема, но мы уже рассматривали примерно то же самое состояние «до» на рис. 4.9.
Нам не нужна схема состояния «после», потому что эта функция не вносит никаких изменений в нашу динамическую структуру, а только выдает результат. Нам только нужно знать ожидаемый результат, ко- торый в данном случае составляет примерно 85,3333.
Так как же мы будем рассчитывать средний балл? Концепция понят- на из нашего опыта расчета среднего значения всех величин в массиве.
Мы должны просуммировать все значения в коллекции, а потом раз- делить сумму на количество значений. Когда мы писали код для расче- та среднего значения в массиве, то использовали цикл for от 0 до дли- ны массива минус один, используя итератор цикла как индекс массива.
В случае со связным списком мы не можем использовать цикл for, так как нам заранее неизвестно количество итераций. Мы должны переби- рать узлы один за другим, пока не достигнем нулевого значения в поле next очередного узла, что будет означать окончание списка. Такие усло- вия предполагают использование цикла while, что-то подобное мы ис- пользовали ранее в этой главе для перебора массива неизвестной дли- ны. Подобный проход по связному списку от начала к концу называется
обход списка. Это одна из базовых операций по работе со связным спи- ском. Давайте реализуем идею обхода для решения этой задачи:
double averageRecord(studentCollection sc) {
X int count = 0;
Y double sum = 0;
Z listNode * loopPtr = sc;
[ while (loopPtr != NULL) {
\ sum += loopPtr->grade;
] count++;
^ loopPtr = loopPtr->next;
}
_ double average = sum / count;
return average;
}
Сначала мы объявляем переменную count для хранения количе- ства пройденных узлов списка
X
, в итоге там будет храниться коли- чество узлов в списке, которое мы будем использовать для расчета среднего значения. Дальше мы объявляем переменную sum для хра- нения кумулятивной суммы баллов из списка
Y
. Затем мы объявляем указатель listNode * с именем loopPtr, который будет использовать- ся для обхода списка
Z
. Это эквивалент итератора цикла for, кото- рый отражает наше текущее положение в связном списке, но не в виде номера позиции, а сохраняя указатель на узел, который мы в данный момент проходим.
С этого момента начинается обход. Цикл обхода длится до тех пор, пока указатель цикла не дойдет до значения NULL
[
. Внутри