объекта адрес того узла, из которого он был передан. В случае создания первого промежуточного узла этому указателю будет присвоен адрес хвостового узла, поскольку, как вы помните, именно хвостовой узел передал свой указатель this.
Теперь, после того как был создан узел InternalNode, адрес этого узла присваивается указателю dataNode в строке 141, и именно этот адрес возвращается теперь методом TailNode::Insert(). Так мы возвращаемся к методу HeadNode::Insert(), где адрес узла InternalNode присваивается указателю myNext узла HeadNode (строка 169). И наконец, адрес узла HeadNode возвращается в связанный список — туда, где в строке 197 он был сброшен (ничего страшного при этом не произошло, так как связанному списку уже был известен адрес головного узла).
Зачем было беспокоиться о возвращении адреса, если он не используется? Метод Insert был объявлен в базовом классе Node. Для выполнения метода необходимо задать значение возврата. Если изменить значение возврата функции HeadNode::Insert(), то компилятор покажет сообщение об ошибке. Это все равно что возвратить узел HeadNode и позволить связанному списку выбросить его адрес.
Так что же все-таки произошло? Данные были введены в список. Список передал эти данные головному узлу. Головной узел передал их дальше по тому адресу, что хранится в его указателе. В первом цикле в этом указателе хранился адрес хвостового узла. Хвостовой узел немедленно создает новый промежуточный узел, указателю которого присваивается адрес хвостового узла. Затем хвостовой узел возвращает адрес промежуточного узла в головной узел, где он присваивается указателю myNext головного узла. Итак, свершилось то, что требовалось: данные расположились в списке правильным образом (рис. 12.7).
После ввода первого промежуточного узла программа переходит к строке 211 и выводит предложение пользователю ввести новое значение. Предположим, что в этот раз было введено значение 3. В результате в строке 215 создается новый объект класса Data и вводится в список в строке 216.
Рис. 12.7. Вид связанного списка после того, как был добавлен первый промежуточный узел
И вновь в строке 197 список передает новое значение в головной узел HeadNode. Метод HeadNode: :Insert(), в свою очередь, передает эти данные по адресу, хранящемуся в указателе myNext. Как вы помните, теперь он указывает на узел, содержащий объект типа Data со значением 15. В результате в строке 96 вызывается метод InternalNode::Insert(). В строке
100 указатель myData узла InternalNode сообщает объекту этого узла (значение которого сейчас равно 15) о необходимости вызвать метод Compare(), принимающий в качестве аргумеи'- та новый объект Data со значением 3. Метод Compare() объявлен в строке 41.
Происходит сравнение значений двух объектов, и, поскольку значение myValue соответствует 15, а theOtherData.myValue равно 3, метод возвращает константу kIsLarget. B соответствии со значением возвращенной константы программа переходит к выполнению строки 109.
Создается новый узел InternalNode для нового объекта данных. Новый узел будет указывать на текущий объект узла InternalNode, и адрес нового узла InternalNode возвращается методом InternalNode:;Insert() в головной узел HeadNode. Таким образом, новый узел, значение которого меньше значения текущего объекта, добавляется в связанный список, после чего связанный список выглядит так, как показано на рис, 12.8.
Натретьем цикле пользователь ввел значение 8. Оно больше чем 3, но меньше чем 15, поэтому программа должна ввести новый объект данных между двумя существующими промежуточными узлами. Последует та же серия операций, что и в предыдущем цикле, за тем исключением, что при вызове метода Compare() для объекта типа Data, значение кото- рогоравно 3, будет вОзвращена константа kIsSmaller, а не kIsLarger, как в предыдущем случае (поскольку значение текущего объекта 3 меньше значения нового объекта 8).
В результате метод InternalNode::Insert() переведет выполнение программы на строку 116. Вместо создания и ввода в список нового узла, новые данные будут переданы в метод Insert того объекта, на который ссылается указатель myNext текущего объекта. В данном случае будет вызван метод InsertNode для промежуточного узла, значение объекта которого равняется 15.
Вновь будет проведено сравнение данных, которое в этот раз завершится созданием нового промежуточного узла. Этот новый узел будет ссылаться на тот промежуточный узел, значение которого 15, а адрес нового узла будет присвоен указателю узла со значением 3, как показано в строке 116.
Рис. 12.8. Вид связанного списка после того, как был добавлен второй промежуточный узел
В результате новый узел вновь будет вставлен в правильную позицию.
Если вы переписали эту программу И запустили на своем компьютере, то с помощью средства отладки можно посмотреть, как будет происходить ввод других данных программой. Каждый раз будет проводиться сравнение данных и новые узлы будут добавляться в список строго в порядке возрастания значений.
Что мы узнали в этой главе
В программах, рассмотренных выше, не осталось ничего от привычных нам процедурных программ. При процедурном программировании контрольный метод сравнивает данные и вызывает функцию. При объектно-ориентированном программировании каждый отдельный объект служит для выполнения ограниченного набора четко определенных задач. Так, связанный список отвечает за поддержание головного узла: Головной узел немедленно передает данные по адресу своего указателя, не анализируя ни передаваемые данные, ни адресуемый объект.
Хвостовой узел создает новые узлы и добавляет их в список, если они содержат данные. Хвостовому узлу известно, что если новые объекты содержат какие-то данные, то они должны располагаться в списке до него.
Промежуточные узлы выполняют более сложные функции. Они обращаются к своим текущим объектам и сравнивают их значения со значениями новых объектов. В зависимости от результата сравнения, они либо вставляют объекты перед собой, либо передают их другому узлу.
Обратите внимание, что промежуточные узлы сами по себе не имеют никакого представления о данных объектов и о том, как их сравнивать. Сравнение выполняется методами, вызываемыми объектами. Все, за что отвечает промежуточный узел, — это обращение к своему объекту с требованием вызвать метод сравнения текущего значения с новым переданным значением. В зависимости от того, какую константу возвратит метод сравнения, узел либо добавляет объекты перед собой, либо передает их другому узлу, не беспокоясь о том, что будет с этим объектом дальше.
Кто же стоит над всем этим? В хорошо сконструированной объектно-ориентированной программе нет необходимости создавать какой-либо всеохватывающий объект контроля. Каждый объект выполняет свою маленькую партию, и результаты работы всех объектов сливаются в стройный хор.
Классы массивов
По сравнению с использованием встроенных массивов написание собственного класса массивов дает ряд преимуществ. Так, можно разработать систему контроля за вводом данных в массив для предупреждения ошибок или создать класс массива, динамически изменяющий размер. При создании массив может содержать только один элемент, постепенно прирастая по мере выполнения программы.
Можно разработать механизм сортировки или какого-либо другого упорядочения элементов массива либо использовать множество других эффективных вариантов массивов, наиболее популярны среди которых следующие:
• отсортированные коллекции: каждый член массива автоматически занимает свое определенное место;
• наборы: ни один из членов не повторяется в массиве дважды;
• словари: связанные пары элементов массива, где один член выполняет роль ключа для возвращения второго члена;
• разреженные массивы: допускается использование произвольных значений индексов, но в массив будут добавляться только реально существующие элементы. Так, можно ввести и использовать элемент с индексом SprseArray[5] или SpcseArray[2Q0], HO 3TO не значит, что в массиве реально существуют все элементы с меньшими индексами;
• мультимножества: неупорядоченные коллекции, члены которых добавляются и возвращаются в произвольном порядке.
Перегрузив оператор индексирования ([]), можно превратить связанный список в отсортированную коллекцию. Если добавить функцию отслеживания одинаковых членов, то отсортированная коллекция превратится в набор. Если все объекты списка связать попарно, то связанный список превратится в словарь или в разреженный массив.
Резюме
Сегодня вы узнали, как создавать массивы в C++. Массив представляет собой коллекцию объектов одинакового типа с фиксированным числом элементов.
Массивы никак не контролируют свой размер. Поэтому вполне возможно в программе заносить данные за пределы массива, что часто является причиной ошибок. Отсчет индексов массива начинается с 0. Часто допускаемой ошибкой является указание индекса n для массива с размером n.
