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 этого
