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

194: // Делегирование, делегирование, делегирование

195: void LinkedList::Insert(Data * pData)

196: {

197:    myHead->Insert(pData);

198: }

199:

200: // выполняемая тестовая программа

201: int main

202: {

203:    Data * pData;

204:    int val;

205:    LinkedList 11;

206:

207:    // Предлагает пользователю ввести значение,

208:    // которое передается в список

209:    for (;;)

210:    {

211:       cout << "What value? (0 to stop): ";

212:       cin >> val;

213:       if (!val)

214:          break;

215:       pData = new Data(val);

216:       ll.Insert(pData);

217:    }

218:

219:    // теперь пройдемся по списку и посмотрим значения

220:    ll.ShowAll;

221:    return 0; // 11 выходит за установленные рамки и поэтому удалено!

222: }

Результат:

What value? (0 to stop) 5

What value? (0 to stop) 8

What value? (0 to stop) 3

What value? (0 to stop) 9

What value? (0 to stop) 2

What value? (0 to stop) 10

What value? (0 to stop) 0

2

3

5

8

9

10

Анализ: Первое, на что следует обратить внимание, — это константное перечисление, в котором представлены константы kIsSmaller, kIsLarger и kIsSame. Любой объект, представленный в списке, должен поддерживать метод Compare('). Константы, показанные выше, возвращаются в результате выполнения этого метода.

В строках 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.