Освой самостоятельно С++ за 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: // теперь пройдемся по списку и посмотрим значения