跳跃表的C++实现

andalousie

参考资料：Algorithms in C++ Parts 1-4, Robert Sedgewick
代码如下：

1. #ifndef SKIPLIST_H
   
2. #define SKIPLIST_H
   
3. #include "Random.h"
   
4. 
   
5. static const int max_level = 30;
   
6.         //for small lists, max_level can be set 5
   
7. 
   
8. template<typename Key, typename Value>
   
9. class SkipList
   
10. {
    
11.         struct Node
    
12.         {
    
13.                 Key   key;
    
14.                 Value val;
    
15.                 int   sz;
    
16.                 Node ** next;
    
17. 
    
18.                 Node (Key key, Value value, int n)
    
19.                         : key(key), val(value), sz(n)
    
20.                 {
    
21.                         next = new Node* [n];
    
22.                         for(int i = 0; i < n; ++i)
    
23.                                 next[i] = 0;
    
24.                 }
    
25.         };
    
26. public:
    
27.         SkipList ()
    
28.                 : lgN(0)
    
29.         {
    
30.                 head = new Node(0, 0, max_level);
    
31.         }
    
32. 
    
33.         int  count () { return count(head, 0); }
    
34. 
    
35.         void insert (const Key& k, const Value& v) { rootInsert(head, new Node(k, v, rand_gen()), lgN); }
    
36. 
    
37.         Value search (const Key& k) { return search(head, k, lgN); }
    
38. 
    
39.         void remove (const Key& k) { remove(head, k, lgN); }
    
40. private:
    
41.         Node * head;
    
42.         int    lgN;
    
43.         Random rnd;
    
44. 
    
45.         int rand_gen ()
    
46.         {
    
47.                 int i, t = rnd.randomInt();
    
48.                 for (i = 1; i < max_level; ++i)
    
49.                 {
    
50.                         int res = t >> (31-i);
    
51.                         if (res) break;
    
52.                 }
    
53.                 if (i > lgN) lgN = i;
    
54.                 return i;
    
55.         }
    
56. 
    
57.         int count (Node * t, int c)
    
58.         {
    
59.                 Node * t0 = t->next[0];
    
60.                 if (!t0) return c;
    
61.                 return count(t0, c+1);
    
62.         }
    
63. 
    
64.         void rootInsert (Node * t, Node * x, int n)
    
65.         {
    
66.                 Key v = x->key;
    
67.                 Node * pos = t->next[n];
    
68.                 if (!pos || v < pos->key)
    
69.                 {
    
70.                         if (n < x->sz)
    
71.                         {
    
72.                                 x->next[n] = pos;
    
73.                                 t->next[n] = x;
    
74.                         }
    
75.                         if (!n) return;
    
76.                         rootInsert(t, x, n-1);
    
77.                         return;
    
78.                 }
    
79.                 rootInsert(pos, x, n);
    
80.         }
    
81. 
    
82.         Value search (Node * t, Key k, int n)
    
83.         {
    
84.                 if (!t) return 0;
    
85.                 if (k == t->key) return t->val;
    
86.                 Node * x = t->next[n];
    
87.                 if(!x || k < x->key)
    
88.                 {
    
89.                         if (!n) return 0;
    
90.                         return search(t, k, n-1);
    
91.                 }
    
92.                 return search(x, k, n);
    
93.         }
    
94. 
    
95.         void remove (Node * t, Key k, int n)
    
96.         {
    
97.                 if (!t) return;
    
98.                 Node * x = t->next[n];
    
99.                 if (!x || x->key >= k)
    
100.                 {
     
101.                         if (x)
     
102.                         {
     
103.                                 if (k == x->key)
     
104.                                         t->next[n] = x->next[n];
     
105.                                 if (!k)
     
106.                                 {
     
107.                                         delete x;
     
108.                                         return;
     
109.                                 }
     
110.                         }
     
111.                         if (!n) return;
     
112.                         remove(t, k, n-1);
     
113.                 }
     
114.                 remove(t->next[n], k, n);
     
115.         }
     
116. };
     
117. 
     
118. #endif

复制代码

由于原来我发布过的代码里面有Random.h，这里就不重读列出了。参见http://bbs.fishc.com/thread-44631-1-1.html的附件。