Джесс Либерти - Освой самостоятельно С++ за 21 день.

107: case kIsLarger: // новые данные вводятся перед моими

108: {

109: InternalNode * dataNode = new InternalNode(theData, this);

110: return dataNode;

111: }

112:

113: // Он больше чем я, поэтому передается в

114: // следующий узел, и пусть тот делает с этими данными все, что захочет.

115: case kIsSmaller:

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

117: return this;

118: }

119: return this; // появляется MSC

120: }

121:

122:

123: // Хвостовой узел выполняет роль часового

124:

125: class TailNode : public Node

126: {

127: public:

128: TailNode(){ }

129: ~TailNode(){ }

130: virtual Node * Insert(Data * theData);

131: virtual void Show() { }

132:

133: private:

134:

135: };

136:

137: // Если данные подходят для меня, то они должны быть вставлены передо мной,

138: // так как я хвост и НИЧЕГО не может быть после меня

139: Node * TailNode::Insert(Data * theData)

140: {

141: InternalNode * dataNode = ew InternalNode(theData, this);

142: return dataNode;

143: }

144:

145: // Головной узел не содержит данных, он только

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

147: class HeadNode : public Node

148: {

149: public:

150: HeadNode();

151: ~HeadNode() { 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::HeadNode()

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: LinkedList();

178: ~LinkedList() { delete myHead; }

179: void Insert(Data * theData);

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

181: private:

182: HeadNode * myHead;

183: };

184:

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

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

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

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

189: LinkedList::LinkedList()

190: {

191: myHead = new HeadNode;

192: }

193:

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.

Теперь, после того как был создан узел InternalNode, адрес этого узла присваивается указателю dataNode в строке 141, и именно этот адрес возвращается теперь методом TailNode::Insert(). Так мы возвращаемся к методу HeadNode::Insert(), где адрес узла InternalNode присваивается указателю myNext узла HeadNode (строка 169). И наконец, адрес узла HeadNode возвращается в связанный список — туда, где в строке 197 он был сброшен (ничего страшного при этом не произошло, так как связанному списку уже был известен адрес головного узла).