146; указывает на начало списка

147; class HeadNode ; public Node

148; {

149: public:

150; HeadNodeO;

151: HeadNodeO { delete myNext; >

152; virtual Node Insert(Data theData);

153; virtual void Show() { myNext->Show(); }

154; private:

155: Node myNext;

156: ) ;

157:

158: Как только создается головной узел,

159: он создает хвост

160: HeadNode;:HeadNodeO

161: {

162; myNext = new TailNode;

163: >

164:

165: Ничего не может быть перед головой, поэтому

166; любые данные передаются в следующий узел

167: Node * HeadNode::Insert(Data theData)

168: {

169: myNext = myNext->Insert(theData);

170: return this;

171: > 172:

173: Я только распределяю задачи между узлами

174: class Linkedlist

175: (

176: public:

177: LinkedListO;

178: LinkedListO { delete myHead; }

179; void Insert(Data theData);

180: void ShowAllO { myHead->Show(); }

181: private:

T82: HeadNode myHead;

183: } ;

184:

185: Список появляется с созданием головного узла,

186: который сразу создает хвостовой узел.

187: Таким образом, пустой список содержит указатель на головной узел,

188: указывающий, в свою очередь, на хвостовой узел, между которыми пока ничего

нет.

189: LinkedList:: LinkedListO

190: <

191: .myHead = new HeadNode;

192: }

193: .

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

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222

void LinkedList:;Insert(Data * pData) {

myHead->Insert(pData):

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

int mainO

Data ♦ pData; int val; LinkedList 11;

Предлагает пользователю ввести значение, которое передается в список for (;;) {

cout What value? (О to stop); ; cin val; if (!val)

break; pData = new Data(val); 11.Insert(pData);

теперь пройдемся no списку и посмотрим значения ll.ShowAlK);

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

What value? (О 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

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

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

Головной узел

Хвостовой узел

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

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

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

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