Освой самостоятельно С++ за 21 день.

В строках 28—37 объявляется класс Data, а в строках 39—49 выполняется метод Compare. Объекты класса Data содержат данные и могут использоваться для сравнения с другими объектами класса Data. Они также поддерживают метод Show, отображающий значение объекта класса Data.

Чтобы лучше разобраться в работе связанного списка, проанализируем шаг за шагом выполнение программы, показанной выше. В строке 201 объявляется выполняемый блок программы, в строке 203 — указатель на класс Data, а в строке 205 определяется связанный список.

Для создания связанного списка в строке 189 вызывается конструктор. Единственное, что он делает, — выделяет области памяти для объекта HeadNode и присваивает адрес объекта указателю, поддерживаемому связанным списком и объявленному в строке 182.

При создании объекта HeadNode вызывается еще один конструктор, объявленный в строках 160—163, который, в свою очередь, создает объект TailNode и присваивает его адрес указателю myNext, содержащемуся в объекте HeadNode. При создании объекта TailNode вызывается конструктор TailNode, объявленный в строке 128. Тело конструктора содержится в той же строке программы, и он не создает никаких новых объектов.

Таким образом, создание связанного списка вызывает последовательность взаимосвязанных процессов, в результате которых для него выделяется область стековой памяти, создаются головной и хвостовой узлы и устанавливаются взаимосвязи между ними, как показано на рис. 12.6.

В строке 209 начинается бесконечный цикл. Появляется предложение пользователю ввести значение, которое будет добавлено в связанный список. Ввод новых значений можно продолжать до бесконечности. Ввод значения 0 завершает цикл. Введенное значение проверяется в строке 213.

Если введенное значение отличается от 0, то в строке 215 создается новый объект типа Data, а в строке 216 он вводится в связанный список. Предположим, что пользователь ввел число 15, после чего в строке 195 будет вызван метод Insert.

Рис. 12.6. Связанный список сразу после создания

Связанный лист немедленно передаст ответственность за ввод объекта головному узлу, вызвав в строке 167 метод Insert. Головной узел немедленно делегирует ответственность любому другому узлу (вызывает в строке 139 метод Insert), адрес которого хранится в указателе myNext. Сначала в этом указателе представлен адрес хвостового узла (вспомните, что при создании головного узла автоматически создается хвостовой узел и ссылка на него добавляется в головной узел).

Хвостовому узлу TailNode известно, что любой объект, переданный обращением TailNode::Insert, нужно добавить в список непосредственно перед собой. Так, в строке 141 создается объект InternalNode, который добавляется в список перед хвостовым узлом и принимает введенные данные и указатель на хвостовой узел. Эта процедура выполняется с помощью объявленного в строке 87 конструктора объекта InternalNode.

Конструктор объекта InternalNode просто инициализирует указатель класса Data адресом переданного объекта этого класса, а также присваивает указателю myNext этого

объекта адрес того узла, из которого он был передан. В случае создания первого промежуточного узла этому указателю будет присвоен адрес хвостового узла, поскольку, как вы помните, именно хвостовой узел передал свой указатель 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.