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

68:

69: // Этот узел поддерживает реальные объекты.

70: // В данном случае объект имеет тип Data

71: // 0 другом, более общем методе решения этой

72: // задачи мы узнаем при рассмотрении шаблонов.

73: class InternalNode: public Node

74: {

75: public:

76: InternalNode(Data * theData, Node * next);

77: ~InternalNode { delete myNext; delete myData; }

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

79: virtual void Show { myData->Show; myNext->Show; } // Делегирование!

80:

81: private:

82: Data * myData; // данные списка

83: Node * myNext; // указатель на следующий узел в связанном списке

84: };

85:

86: // Инициализация, выполняемая каждым конструктором

87: InternalNode::InternalNode(Data * theData, Node * next):

88: myData(theData), myNext(next)

89: {

90: }

91:

92: // Сущность списка.

93: // Когда в список передается новый объект,

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('). Константы, показанные выше, возвращаются в результате выполнения этого метода.