Итоги второй недели

1: // **********************************

2: //

3: // Название: Подведение итогов

4: //

5: // Файл: Week2

6: //

7: // Описание: Демонстрация создания и использования связанного списка

8: //

9: // Классы: PART - содержит идентификационный

10: // номер детали и обеспечивает возможность

11: // добавлять другие данные

12: // PartNode - функционирует как узел в PartsList

13: //

14: // PartsList - реализует механизм связывания

15: // узлов в список

16: //

17: // **********************************

18:

19: #include < iostream.h>

20:

21:

22:

23: // **************** Part ************

24:

25: // Абстрактный базовый класс, общий для всех деталей

26: class Part

27: {

28: public:

29: Part(): itsPartNumber(1) { }

30: Part(int PartNumber): itsPartNumber(PartNumber) { }

31: virtual ~Part() { };

32: int GetPartNumber() const { return itsPartNumber; }

33: virtual void Display() const =0; // должна быть замещена как private

34: private:

35: int itsPartNumber;

36: };

37:

38: // выполнение чистой виртуальной функции в

39: // стандартном виде для всех производных классов

40: void Part:: Display() const

41: {

42: cout < < " \nНомер детали: " < < itsPartNumber < < endl;

43: }

44:

45: // ************* Автомобильные детали **********

46:

47: class CarPart: public Part

48: {

49: public:

50: CarPart(): itsModelYear(94){ }

51: CarPart(int year, int partNumber);

52: virtual void Display() const

53: {

54: Part:: Display(); cout < < " Год создания: ";

55: cout < < itsModelYear < < endl;

56: }

57: private:

58: int itsModelYear;

59: };

60:

61: CarPart:: CarPart(int year, int partNumber):

62: itsModelYear(year),

63: Part(partNumber)

64: { }

65:

66:

67: // ************* Авиационные детали **********

68:

69: class AirPlanePart: public Part

70: {

71: public:

72: AirPlanePart(): itsEngineNumber(1){ };

73: AirPlanePart(int EngineNumber, int PartNumber);

74: virtual void Display() const

75: {

76: Part:: Display(); cout < < " Номер двигателя: ";

77: cout < < itsEngineNumber < < endl;

78: }

79: private:

80: int itsEngineNumber;

81: };

82:

83: AirPlanePart:: AirPlanePart(int EngineNumber, intPartNumber):

84: itsEngineNumber(EngineNumber),

85: Part(PartNumber)

86: { }

87:

88: // ************** Узлы списка деталей **********

89: class PartNode

90: {

91: public:

92: PartNode (Part*);

93: ~PartNode();

94: void SetNext(PartNode * node) { itsNext = node; }

95: PartNode * GetNext() const;

96: Part * GetPart() const;

97: private:

98: Part *itsPart;

99: PartNode * itsNext;

100: };

101:

102: // Выполнение PartNode...

103:

104: PartNode:: PartNode(Part* pPart):

105: itsPart(pPart),

106: itsNext(0)

107: { }

108:

109: PartNode:: ~PartNode()

110: {

111: delete itsPart;

112: itsPart = 0;

113: delete itsNext;

114: itsNext = 0;

115: }

116:

117: //Возвращается NULL, если нет следующего узла PartNode

118: PartNode * PartNode:: GetNext() const

119: {

120: return itsNaxt;

121: }

122:

123: Part * PartNode:: GetPart() const

124: {

125: if (itsPart)

126: return itsPart;

127: else

128: return NULL; // ошибка

129: }

130:

131: // **************** Список деталей ************

132: class PartsList

133: {

134: public:

135: PartsList();

136: ~PartsList();

137: // Необходимо, чтобы конструктор-копировщик и оператор соответствовали друг другу!

138: Part* Find(int & position, int PartNumber) const;

139: int GetCount() const { return itsCount; }

140: Part* GetFirst() const;

141: static PartsList& GetGlobalPartsList()

142: {

143: return GlobalPartsList;

144: }

145: void Insert(Part *);

146: void Iterate(void (Part:: *f)()const) const;

147: Part* operator[](int) const;

148: private:

149: PartNode * pHead;

150: int itsCount;

151: static PartsList GlobalPartsList;

152: };

153:

154: PartsList PartsList:: GlobalPartsList;

155:

156: // Выполнение списка...

157:

158: PartsList:: PartsList():

159: pHead(0),

160: itsCount(0)

161: { }

162:

163: PartsList:: ^PartsList()

164: {

165: delete pHead;

166: }

167:

168: Part* PartsList:: GetFirst() const

169: {

170: if (pHead)

171: return pHead-> GetPart();

172: else

173: return NULL; // ловушка ошибок

174: }

175:

176: Part * PartsList:: operator[](int offSet) const

177: {

178: PartNode* pNode = pHead;

179:

180: if (! pHead)

181: return NULL; // ловушка ошибок

182:

183: if (offSet > itsCount)

184: return NULL; // ошибка

185:

186: for (int i=0; i< offSet; i++)

187: pNode = pNode-> GetNext();

188:

189: return pNode-> GetPart();

190: }

191:

192: Part* PartsList:: Find(int & position, int PartNumber) const

193: {

194: PartNode * pNode = 0;

195: for (pNode = pHead, position = 0;

196: pNode! =NULL;

197: pNode = pNode-> GetNext(), position++)

198: {

199: if (pNode-> GetPart()-> GetPartNumber() == PartNumber)

200: break;

201: }

202: if (pNode == NULL)

203: return NULL;

204: else

205: return pNode-> GetPart();

206: }

207:

208: void PartsList:: Iterate(void (Part:: *func)()const) const

209: {

210: if (! pHead)

211: return;

212: PartNode* pNode = pHead;

213: do

214: (pNode-> GetPart()-> *func)();

215: while (pNode = pNode-> GetNext());

216: }

217:

218: void PartsList:: Insert(Part* pPart)

219: {

220: PartNode * pNode = new PartNode(pPart);

221: PartNode * pCurrent = pHead;

222: PartNode > > pNext = 0;

223:

224: int New = pPart-> GetPartNumber();

225: int Next = 0;

226: itsCount++;

227:

228: if (! pHead)

229: {

230: pHead = pNode;

231: return;

232: }

233:

234: // Если это значение меньше головного узла,

235: // то текущий узел становится головным

236: if (pHead-> GetPart()-> GetPartNumber()-> New)

237: {

238: pNode-> SetNext(pHead);

239: pHead = pHode;

240: return;

241: }

242:

243: for (;;)

244: {

245: // Если нет следующего, вставляется текущий

246: if (! pCurrent-> GetNext())

247: {

248: pCurrent-> SetNext(pNode);

249: return;

250: }

251:

252: // Если текущий больше предыдущего, но меньше следующего, то вставляем

253: // здесь. Иначе присваиваем значение указателя Next

254: pNext = pCurrent-> GetNext();

255: Next = pNext-> GetPart()-> GetPartNumber();

256: if (Next > New)

257: {

258: pCurrent-> SetNext(pNode);

259: pNode-> SetNext(pNext);

260: return;

261: }

262: pCurrent = pNext;

263: }

264: }

265:

266: int main()

267: {

268: PartsList& pl = PartsList:: GetGlobalPartsList();

269: Part * pPart = 0;

270: int PartNumber;

271: int value;

272: int Choice;

273:

274: while (1)

275: {

276: cout < < " (0)Quit (1)Car (2)Plane: ";

277: cin > > choice;

278:

279: if (! choice)

280: break;

281:

282: cout < < " New PartNumber?: ";

283: cin > > PartNumber;

284:

285: if (choice == 1)

286: {

287: cout < < " Model Year?: ";

288: cin > > value;

289: pPart = new CarPart(value, PartNumber);

290: }

291: else

292: {

293: cout < < " Engine Number?: ";

294: cin > > value;

295: pPart = new AirPlanePart(value, PartNumber);

296: }

297:

298: pl.Insert(pPart);

299: }

300: void (Part:: *pFunc)()const = Part:: Display;

301: pl.Iterate(pFunc);

302: return 0;

303: }

Результат:

(0)Quit (1)Car (2)Plane: 1

New PartNumber?: 2837

Model Year? 90

(0)Quit (1)Car (2)Plane: 2

New PartNumber?: 378

Engine Number?: 4938

(0)Quit (1)Car (2)Plane: 1

New PartNumber?: 4499

Model Year?: 94

(0)Quit (1)Car (2)Plane: 1

New PartNumber?: 3000

Model Year? 93

(0)Quit (1)Car (2)Plane: 0

Part Number: 378

Engine No.: 4938

Part Number: 2837

Model Year: 90

Part Number: 3000

Model Year: 93

Part Number: 4499

Model Year: 94

Представленная программа создает связанный список объектов класса Part. Связанный список — это динамическая структура данных вроде массива, за исключением того, что в список можно добавлять произвольное число объектов указанного типа и удалять любой из введенных объектов.

Данный связанный список разработан для хранения объектов класса Part, где Part — абстрактный тип данных, служащий базовым классом для любого объекта с заданной переменной-членом itsPartNumber. В программе от класса Part производятся два подкласса - CarPartHAirPlanePart.

Класс Part описывается в строках 26—36, где задаются одна переменная-член и несколько методов доступа. Предполагается, что затем в объекты класса будет добавлена другая ценная информация и возможность контроля за числом созданных объектов в базе данных. Класс Part описывается как абстрактный тип данных, на что указывает чистая виртуальная функция Display().

Обратите внимание, что в строках 40-43 определяется выполнение чистой виртуальной функции Display(). Предполагается, что метод Display() будет замещаться в каждом производном классе, но в определении замещенного варианта допускается просто вызывать стандартный метод из базового класса.

Два простых производных класса, CarPart и AirPlanePart, описываются в строках 47—59 и 69—87 соответственно. В каждом из них замещается метод Display() простым обращением к методу Display() базового класса.

Класс PartNode выступает в качестве интерфейса между классами Part и PartList. Он содержит указатель на Part и указатель на следующий узел в списке. Методы этого класса только возвращают и устанавливают следующий узел в списке и возвращают соответствующий объект Part.

За " интеллектуальность" связанного списка полностью отвечает класс PartsList, описываемый в строках 132—152. Этот класс содержит указатель на головной узел списка (pHead) и, с его помощью продвигаясь по списку, получает доступ ко всем другим методам. Продвижение по списку означает запрашивание текущего узла об адресе следующего вплоть до обнаружения узла, указатель которого на следующий узел равен NULL.

Безусловно, в этом примере представлен упрощенный вид связанного списка. В реально используемой программе список должен обеспечивать еще больший доступ к первому и последнему узлам списка или создавать специальный объект итерации, с помощью которого клиенты смогут легко продвигаться по списку.

В то же время класс PartsList предлагает ряд интересных методов, упорядоченных по алфавиту. Зачастую такой подход весьма эффективен, поскольку упрощает поиск нужных функций.

Функция Find() принимает в качестве параметров PartNumber и значение int. Если найден раздел с указанным значением PartNumber, функция возвращает указатель на Part и порядковый номер этого раздела в списке. Если же раздел с номером PartNumber не обнаружен, функция возвращает значение NULL.

Функция GetCount() проходит по всем узлам списка и возвращает количество объектов в списке. В PartsList это значение записывается в переменную-член itsCount, хотя его можно легко вычислить, последовательно продвигаясь no списку.

Функция GetFirst() возвращает указатель на первый объект Part в списке или значение NULL, если список пустой.

Функция GetGlobalPartsList() возвращает ссылку на статическую переменную-член GiobalPartsList. Описание статической переменной GlobaiPartsList является типичным решением для классов типа PartsList, хотя, безусловно, могут использоваться и другие имена. В законченном виде реализация этой идеи состоит в автоматическом изменении конструктора класса Part таким образом, чтобы каждому новому объекту класса присваивался номер с учетом текущего значения статической переменной GiobalPartsList.

Функция Insert принимает значение указателя на объект Part, создает для него PartNode и добавляет объект Part в список в порядке возрастания номеров PartNumber.

Функция Iterate принимает указатель на константную функцию-член класса Part без параметров, которая возвращает void. Эта функция вызывается для каждого объекта Part в списке. В описании класса Part таким характеристикам соответствует единственная функция Display(), замещенная во всех производных классах. Таким образом, будет вызываться вариант метода Display(), соответствующий типу объекта Part.

Функция Operator[] позволяет получить прямой доступ к объекту Part по заданному смещению. Этот метод обеспечивает простейший способ определения границ списка: если список нулевой, или заданное смещение больше числа объектов в списке, возвращается значение NULL, сигнализирующее об ошибке.

В реальной программе имело бы смысл все эти комментарии с описанием назначений функций привести в описании класса.

Тело функции main() представлено в строках 266-303. В строке 268 описывается ссылка на PartsList и инициализируется значением GiobalPartsList. Обратите внимание, что GiobalPartsList инициализируется в строке 154. Эта строка необходима, поскольку описание статической переменной-члена не сопровождается ее автоматическим определением. Поэтому определение статической переменной-члена должно выполняться за пределами описания класса.

В строках 274—299 пользователю предлагается указать, вводится ли деталь для машины или для самолета. В зависимости от выбора, запрашиваются дополнительные сведения и создается новый объект, который добавляется в список в строке 298.

Выполнение метода Insert() класса PartList показано в строках 218—264. При вводе идентификационного номера первой детали — 2837 — создается объект CarPart, который передается в LinkedList:: Insert()c введенными номером детали и годом создания 90.

В строке 220 создается новый объект PartNode, принимающий значения новой детали. Переменная New инициализируется номером детали. Переменная-член itsCount класса PartsList увеличивается на единицу в строке 226.

В строке 228 проверяется равенство указателя pHead значению NULL. В данном случае возвращается значение TRUE, поскольку это первый узел списка и указатель pHead в нем нулевой. В результате в строке 230 указателю pHead присваивается адрес нового узла и функция возвращается.

Пользователю предлагается ввести следующую деталь. В нашем примере вводится деталь от самолета с идентификационным номером 37 и номером двигателя 4938. Снова вызывается функция PartsList:: Insert() и pNode инициализируется новым узлом. Статическая переменная-член itsCount становится равной 2 и вновь проверяется pHead. Поскольку теперь pHead не равен нулю, то значение указателя больше не изменяется.

В строке 236 номер детали, указанный в головном узле, на который ссылается pHead (в нашем случае это 2837), сравнивается с номером новой детали — 378. Поскольку последний номер меньше, условное выражение в строке 236 возвращает TRUE и головным узлом в списке становится новый объект.

Строкой 238 указателю pNode присваивается адрес того узла, на который ссылался указатель pHead. Обратите внимание, что в следующий узел списка передается не новый объект, а тот, который был введен ранее. В строке 239 указателю pHead присваивается адрес нового узла.

На третьем цикле пользователь вводит деталь для автомобиля под номером 4499 с годом выпуска 94. Происходит очередное приращение счетчика и сравнивается номер текущего объекта с объектом головного узла. В этот раз новый введенный идентификационный номер детали оказывается больше номера объекта, определяемого в pHead, поэтому запускается цикл for в строке 243.

Значение идентификационного номера головного узла равно 378. Второй узел содержит объект со значением 2837. Текущее значение — 4499. Исходно указатель pCurrent связывается с головным узлом. Поэтому при обращении к переменной next объекта, на который указывает pCurrent, возвращается адрес второго узла. Следовательно, условное выражение в строке 246 возвратит False.

Указатель pCurrent устанавливается на следующий узел, и цикл повторяется. Теперь проверка в строке 246 приводит к положительному результату. Если следующего элемента нет, то новый узел вставляется в конец списка.

На четвертом цикле вводится номер детали 3000. Дальнейшее выполнение программы напоминает предыдущий этап, однако в этом случае текущий узел имеет номер 2837, а значение следующего узла равно 4499. Проверка в строке 256 возвращает TRUE, и новый узел вставляется между двумя существующими.

Когда пользователь вводит 0, условное выражение в строке 279 возвращает TRUE и цикл while(1) прерывается. В строке 300 функция-член Display() присваивается указателю на функции-члены pFunc. В профессиональной программе присвоение должно проходить динамически, основываясь на выборе пользователем.

Указатель функции-члена передается методу Iterate класса PartsList. В строке 208 метод Iterate() проверяет, не является ли список пустым. Затем в строках 213—215 последовательно с помощью указателя функции-члена вызываются из списка все объекты Part. В итоге для объекта Part вызывается соответствующий вариант метода Display(), в результате чего для разных объектов выводится разная информация.