最初想法來自于《編程珠璣》，下午實現了一下
不多說了，直接看代碼吧
1 //
2 // HashTable
3 //
4 // goonyangxiaofang(AT)163(DOT)com
5 // QQ: 五九一二四七八七六
6 //
7
8 #include <iostream>
9 #include <string>
10
11 #define MYTRACE(t, f) std::cout << #t": " << t << std::endl; if(f == 1) std::cin.get()
12 #define PRINTNAME(name) std::cout << #name": " << std::endl
13
14 template <typename Key, typename Data, unsigned int prime = 11>
15 class HashTable
16 {
17 struct Node
18 {
19 Key key;
20 Data data;
21 Node* next;
22 Node() : next(0) {}
23 Node(const Key& k) : key(k), next(0) {}
24 Node(const Key& k, const Data& d) : key(k), data(d), next(0) {}
25 Node(const Key& k, const Data& d, const Node* p) : key(k), data(d), next(p) {}
26 Node(const Node& n) : key(n.key), data(n.data), next(n.next) {}
27 ~Node() {}
28 };
29 Node** table;
30 private:
31 unsigned int getKey(const Key& k)
32 {
33 unsigned int ret = 0;
34 char* h = reinterpret_cast<char*>(const_cast<Key*>(&k));
35 for (unsigned int i = 0; i < sizeof (Key); ++i)
36 {
37 ret += static_cast<unsigned int>(h[i]) * 10;
38 }
39 return ret % prime;
40 }
41 public:
42 HashTable()
43 {
44 table = new Node*[prime];
45 for (unsigned int i = 0; i < prime; ++i)
46 {
47 table[i] = 0;
48 }
49 }
50 HashTable(const HashTable& ht)
51 {
52 table = new Node*[prime];
53 for (unsigned int i = 0; i < prime; ++i)
54 {
55 table[i] = 0;
56 Node** p = &(table[i]);
57 Node* q = ht.table[i];
58 while (q)
59 {
60 Node* r = new Node(q->key, q->data);
61 *p = r;
62 p = &(r->next);
63 q = q->next;
64 }
65 }
66 }
67 HashTable& operator=(const HashTable& ht)
68 {
69 if (this != &ht)
70 {
71 clear();
72 table = new Node*[prime];
73 for (unsigned int i = 0; i < prime; ++i)
74 {
75 table[i] = 0;
76 Node** p = &table[i];
77 Node* q = ht.table[i];
78 while (q)
79 {
80 Node* r = new Node(q->key, q->data);
81 *p = r;
82 p = &(r->next);
83 q = q->next;
84 }
85 }
86 }
87 return * this;
88 }
89 bool find(const Key& k)
90 {
91 Node* p = table[getKey(k)];
92 while (p)
93 {
94 if (k == p->key)
95 {
96 return true;
97 }
98 p = p->next;
99 }
100 return false;
101 }
102 bool insert(const Key& k, const Data& d)
103 {
104 if (find(k))
105 {
106 return true;
107 }
108 unsigned int key = getKey(k);
109 Node*& p = table[key];
110 Node* q = new Node(k, d);
111 if (q == 0)
112 {
113 return false;
114 }
115 q->next = p;
116 p = q;
117 return true;
118 }
119 bool insert(const Key& k)
120 {
121 if (find(k))
122 {
123 return true;
124 }
125 unsigned int key = getKey(k);
126 Node*& p = table[key];
127 Node* q = new Node(k);
128 if (q == 0)
129 {
130 return false;
131 }
132 q->next = p;
133 p = q;
134 return true;
135 }
136 Data& get(const Key& k)
137 {
138 Node* p = table[getKey(k)];
139 while (p)
140 {
141 if (k == p->key)
142 {
143 return p->data;
144 }
145 p = p->next;
146 }
147 insert(k);
148 Data d;
149 return d;
150 }
151 const Data& operator[](const Key& k) const
152 {
153 Node* p = table[getKey(k)];
154 while (p)
155 {
156 if (k == p->key)
157 {
158 return p->data;
159 }
160 p = p->next;
161 }
162 insert(k);
163 Data d;
164 return d;
165 }
166 Data& operator[](const Key& k)
167 {
168 Node* p = table[getKey(k)];
169 while (p)
170 {
171 if (k == p->key)
172 {
173 return p->data;
174 }
175 p = p->next;
176 }
177 insert(k);
178 Data d;
179 return d;
180 }
181 bool empty()
182 {
183 for (unsigned int i = 0; i < prime; ++i)
184 {
185 if (table[i] != 0)
186 {
187 return false;
188 }
189 }
190 return true;
191 }
192 void print()
193 {
194 std::cout << std::endl;
195 for (unsigned int i = 0; i < prime; ++i)
196 {
197 Node* p = table[i];
198 std::cout << i << ": ";
199 while (p)
200 {
201 std::cout << "( " << p->key << ", " << p->data << " ) ";
202 p = p->next;
203 }
204 std::cout << std::endl;
205 }
206 std::cout << std::endl;
207 }
208 void clear()
209 {
210 for (unsigned int i = 0; i < prime; ++i)
211 {
212 Node* p = table[i];
213 Node* q = p;
214 while (p)
215 {
216 p = p->next;
217 delete q;
218 q = p;
219 }
220 }
221 delete [] table;
222 }
223 ~HashTable()
224 {
225 clear();
226 }
227 };
228
229 int main()
230 {
231 HashTable<long, std::string> ht1;
232 for (long i = 0; i < 26; ++i)
233 {
234 std::string s;
235 s += 'A' + i;
236 ht1.insert(i, s);
237 }
238 PRINTNAME(ht1);
239 ht1.print();
240
241 for (long i = 0; i < 26; ++i)
242 {
243 std::string s;
244 s += 'A' + i;
245 ht1.insert(i, s);
246 }
247 PRINTNAME(ht1);
248 ht1.print();
249
250 HashTable<long, std::string> ht2(ht1);
251 PRINTNAME(ht2);
252 ht2.print();
253
254 ht1[25] = "xxxxxxxx";
255 ht1.print();
256 ht2.print();
257
258 HashTable<long, std::string> ht3;
259 ht3 = ht1;
260 PRINTNAME(ht3);
261 ht3.print();
262 return 0;
263 }
posted on 2011-03-09 18:57
unixfy 閱讀(429)
評論(0) 編輯 收藏 引用