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

94: // программа определяет позицию в списке

95: // для нового узла

96: Node * InternalNode::Insert(Data * theData)

97: {

98:

99: // Этот новенький больше или меньше чем я?

100: int result = myData->Compare(*theData);

101:

102:

103: switch(result)

104: {

105: // По соглашению, если он такой же как я, то он идет первым

106: case kIsSame: // условие выполняется

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