Цель данной программы состоит в создании функционального связанного списка. В узлах созданного списка можно хранить записи о деталях и агрегатах, что позволяет использовать его в реальных прикладных программах баз данных складов. Хотя здесь представлена не окончательная форма программы, она достаточно хорошо демонстрирует возможности создания совершенной структуры накопления и обработки данных. Листинг программы содержит 311 строк. Попробуйте самостоятельно проанализировать код, прежде чем прочтете анализ, приведенный после листинга.
Итоги второй недели
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().
