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

• Название: Освой самостоятельно С++ за 21 день.
• Автор: Джесс Либерти
• Жанр: Программирование

В книге широко представлены возможности новейшей версии программного продукта Microsoft Visual C++. Подробно описаны средства и подходы программирования современных профессиональных приложений. Материалы книги дополнены многочисленными демонстрационными программами, в процессе разработки которых максимально используются возможности программных инструментов Microsoft Visual Studio. Особое внимание уделено новинкам версии 6.0 и новейшим технологиям объектно-ориентированного программирования, включая использование библиотеки MFC и шаблонов классов, а также создание связанных списков. Отдельное занятие посвящено вопросам объектно-ориентированного анализа и проектирования приложений. Подробно рассмотрены все средства и подходы конструирования собственных пользовательских классов.

Книга рассчитана на широкий круг читателей, интересующихся современными проблемами программирования.

---

35:    private:

36:       int myValue;

37: };

38:

39: // Сравнение используется для определения

40: // позиции в списке для нового узла.

41: int Data::Compare(const Data & theOtherData)

42: {

43:    if (myValue < theOtherData.myValue)

44:       return kIsSmaller;

45:    if (myValue > theOtherData.myValue)

46:       return kIsLarger;

47:    else

48:       return kIsSame;

49: }

50:

51: // Объявления

52: class Node;

53: class HeadNode;

54: class TailNode;

55: class InternalNode;

56:

57: // ADT-представление узловых объектов списка.

58: // В каждом производном классе должны быть замещены функции Insert и Show

59: class Node

60: {

61:    public:

62:       Node(){ }

63:       virtual ~Node(){ }

64:       virtual Node * Insert(Data * theData)=0;

65:       virtual void Show() = 0;

66:    private:

67: };

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

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