實現一個雙索引容器
基于雙索引實現一個具有插入、查找、刪除的容器，一個索引是 int 類型的，一個索引是自定義結構體類型的。
這個問題來自于網宿筆試的一個題目。
這里的功能已基本實現，支持雙索引，自定義結構體類型是有兩個 int 型元素的結構體。
支持迭代器，但是不支持模板。
實現如下：
1 #include <iostream>
2 using namespace std;
3
4 class StructKey
5 {
6 private:
7 int key1;
8 int key2;
9 public:
10 StructKey(int k1= 0, int k2 = 0) : key1(k1), key2(k2) {}
11 bool operator ==(const StructKey& rhs)
12 {
13 return key1 == rhs.key1 && key2 == rhs.key2;
14 }
15 bool operator < (const StructKey& rhs)
16 {
17 return key1 < rhs.key1 || key1 == rhs.key1 && key2 < rhs.key2;
18 }
19 ostream& print(ostream& out) const
20 {
21 out << "( " << key1 << ", " << key2 << " )";
22 return out;
23 }
24 };
25
26 ostream& operator <<(ostream& out, const StructKey& sk)
27 {
28 return sk.print(out);
29 }
30
31 struct Node
32 {
33 int intkey;
34 StructKey skey;
35 Node* next;
36 Node(int i = 0, int j = 0, int k = 0, Node* p = 0) : intkey(i), skey(j, k), next(p) {}
37 };
38
39 class DoulContainer
40 {
41 private:
42 Node* head;
43 Node* tail;
44 int size_;
45 public:
46 struct iterator
47 {
48 Node* p;
49 iterator() : p(0) {}
50 iterator(Node* q) : p(q) {}
51 ~iterator() {}
52 iterator& operator ++()
53 {
54 p = p->next;
55 return *this;
56 }
57 const iterator operator ++(int)
58 {
59 iterator t(*this);
60 ++(*this);
61 return t;
62 }
63 Node* operator ->()
64 {
65 return p;
66 }
67 Node& operator *()
68 {
69 return *p;
70 }
71 bool operator ==(const iterator& rhs)
72 {
73 return p == rhs.p;
74 }
75 bool operator !=(const iterator& rhs)
76 {
77 return !(p == rhs.p);
78 }
79 };
80 public:
81 DoulContainer() : head(0), tail(0), size_(0) {}
82 ~DoulContainer()
83 {
84 clear();
85 }
86 DoulContainer(const DoulContainer& dc) : head(0), tail(0), size_(0)
87 {
88 Node* p = dc.head;
89 while (p != 0)
90 {
91 insert(*p);
92 p = p->next;
93 }
94 }
95 DoulContainer& operator =(const DoulContainer& dc)
96 {
97 DoulContainer temp(dc);
98 myswap(head, temp.head);
99 myswap(tail, temp.tail);
100 myswap(size_, temp.size_);
101 return *this;
102 }
103 void myswap(Node*& p, Node*& q)
104 {
105 Node* t = p;
106 p = q;
107 q = t;
108 }
109 void myswap(int& i, int& j)
110 {
111 int t = i;
112 i = j;
113 j = t;
114 }
115 void clear()
116 {
117 Node* p = head, *q;
118 while (p != 0)
119 {
120 q = p->next;
121 delete p;
122 p = q;
123 }
124 head = tail = 0;
125 size_ = 0;
126 }
127 iterator begin()
128 {
129 return head;
130 }
131 iterator end()
132 {
133 if (head == 0)
134 {
135 return 0;
136 }
137 else
138 {
139 return tail->next;
140 }
141 }
142 iterator find(int ik)
143 {
144 Node* p = head;
145 while (p != 0)
146 {
147 if (p->intkey == ik)
148 {
149 return p;
150 }
151 p = p->next;
152 }
153 return end();
154 }
155 iterator find(const StructKey& sk)
156 {
157 Node* p = head;
158 while (p != 0)
159 {
160 if (p->skey == sk)
161 {
162 return p;
163 }
164 p = p->next;
165 }
166 return end();
167 }
168 int size()
169 {
170 return size_;
171 }
172 int size() const
173 {
174 return size_;
175 }
176 void insert(const Node& dc)
177 {
178 iterator it = find(dc.intkey);
179 if (it != end())
180 {
181 return;
182 }
183 Node* p = new Node(dc);
184 if (p == 0)
185 {
186 exit(1);
187 }
188 p->next = 0;
189 if (head == 0)
190 {
191 head = tail = p;
192 }
193 else
194 {
195 tail->next = p;
196 tail = p;
197 }
198 ++size_;
199 }
200
201 StructKey& operator [](int ik)
202 {
203 iterator it = find(ik);
204 if (it != end())
205 {
206 return it->skey;
207 }
208 Node* p = new Node;
209 if (p == 0)
210 {
211 exit(1);
212 }
213 p->intkey = ik;
214 p->next = 0;
215 if (head == 0)
216 {
217 head = tail = p;
218 }
219 else
220 {
221 tail->next = p;
222 tail = p;
223 }
224 ++size_;
225 return p->skey;
226 }
227 int& operator [](const StructKey& sk)
228 {
229 iterator it = find(sk);
230 if (it != end())
231 {
232 return it->intkey;
233 }
234 Node* p = new Node;
235 if (p == 0)
236 {
237 exit(1);
238 }
239 p->skey = sk;
240 p->next = 0;
241 if (head == 0)
242 {
243 head = tail = 0;
244 }
245 else
246 {
247 tail->next = p;
248 tail = p;
249 }
250 ++size_;
251 return p->intkey;
252 }
253 void del(int ik)
254 {
255 Node *p, *q;
256 q = head;
257 if (q != 0)
258 {
259 while (q != 0 && q->intkey == ik)
260 {
261 head = head->next;
262 delete q;
263 q = head;
264 --size_;
265 }
266 if (q == 0)
267 {
268 return;
269 }
270 p = q->next;
271 while (p != 0)
272 {
273 if (p->intkey == ik)
274 {
275 q->next = p->next;
276 delete p;
277 p = q->next;
278 --size_;
279 }
280 else
281 {
282 q = p;
283 p = p->next;
284 }
285 }
286 }
287 }
288 void del(const StructKey& sk)
289 {
290 Node *p, *q;
291 q = head;
292 if (q != 0)
293 {
294 while (q != 0 && q->skey == sk)
295 {
296 head = head->next;
297 delete q;
298 q = head;
299 --size_;
300 }
301 if (q == 0)
302 {
303 return;
304 }
305 p = q->next;
306 while (p != 0)
307 {
308 if (p->skey == sk)
309 {
310 q->next = p->next;
311 delete p;
312 p = q->next;
313 --size_;
314 }
315 else
316 {
317 q = p;
318 p = p->next;
319 }
320 }
321 }
322 }
323 };
324
325 int main()
326 {
327 DoulContainer dc;
328 cout << dc.size() << endl;
329 for (int i = 0; i < 10; ++i)
330 {
331 dc.insert(Node(i, i, i));
332 }
333 cout << dc.size() << endl;
334 for (DoulContainer::iterator it = dc.begin(); it != dc.end(); ++it)
335 {
336 cout << it->intkey << it->skey << endl;
337 }
338 DoulContainer dc2(dc), dc3;
339 cout << dc.size() << endl;
340 dc.clear();
341 cout << dc.size() << endl;
342 cout << endl;
343 cout << dc2.size() << endl;
344 for (int i = 0; i < 10; ++i)
345 {
346 dc2[i] = StructKey(i + 100, i + 100);
347 }
348 dc2.del(5);
349 for (DoulContainer::iterator it = dc2.begin(); it != dc.end(); ++it)
350 {
351 cout << it->intkey << it->skey << endl;
352 }
353 dc3 = dc2;
354 cout << dc2.size() << endl;
355 dc2.clear();
356 cout << dc2.size() << endl;
357 cout << endl;
358 cout << dc3.size() << endl;
359 for (int i = 0; i < 10; ++i)
360 {
361 dc3[StructKey(i + 100, i + 100)] = i + 10000;
362 }
363 dc3.del(StructKey(105, 105));
364 dc3.del(StructKey(107, 107));
365 for (DoulContainer::iterator it = dc3.begin(); it != dc.end(); ++it)
366 {
367 cout << it->intkey << it->skey << endl;
368 }
369 cout << dc3.size() << endl;
370 dc3.clear();
371 cout << dc3.size() << endl;
372 return 0;
373 }
posted on 2011-05-23 23:48
unixfy 閱讀(477)
評論(0) 編輯 收藏 引用