跳表是一个很有意思的数据结构,它实现简单,但是性能又可以和平衡二叉搜索树差不多。
据MIT公开课上教授的讲解,它的想法和纽约地铁有异曲同工之妙,简而言之就是不断地增加“快线”,从而降低时间复杂度。
当“快线”的数量为lgn时,我们就得到了现在的快表——一个类似于平衡二叉搜索树的数据结构。
网上没有比较标准的实现方案,CLRS中也没有给出伪代码。(可能是因为他们觉得太容易实现了...)所以我给出是一个完全由我自己根据快表性质写的一个版本,如果大家有更好的实现版本欢迎和我分享。
增加层数的方案用的是抛硬币,即根据随机数来确定是否增加“快线”,这也是MIT公开课上给出的一个比较简单的实现方法。
代码如下:(仅供参考)
1 class Skiplist {
2 private :
3 struct Node {
4 int key;
5 Node * prev;
6 Node * next;
7 Node * down;
8 Node * top;
9 Node() : key(0), prev(nullptr), next(nullptr), down(nullptr), top(nullptr) {}
10 };
11 private :
12 Node * head;
13 int level;
14 int size;
15 private :
16 void bindNewNode(Node * x, Node * p);
17 void delNode(Node * x);
18 Node * searchNode(int key);
19 public :
20 Skiplist() : head(new Node), level(1),size(0)
21 {head->key = INT_MIN; srand(static_cast<int>(time(0)));}
22 ~Skiplist() {delete head;}
23 void insert(int key);
24 void remove(int key);
25 bool search(int key) {return (searchNode(key) != nullptr);}
26 void showSkiplist();
27 int getLevel() {return level;}
28 int getSize() {return size;}
29 };
30
31 void Skiplist::bindNewNode(Node * x, Node * p) {
32 if (!x->next) {
33 x->next = p;
34 p->prev = x;
35 }
36 else {
37 p->next = x->next;
38 x->next->prev = p;
39 p->prev = x;
40 x->next = p;
41 }
42 }
43
44 void Skiplist::insert(int key) {
45 Node * p = new Node;
46 p->key = key;
47
48 Node * x = head;
49 while (1) { //find the prev node of p, which represents the right insert place
50 if (x->key <= key) {
51 if (x->next)
52 x = x->next;
53 else if (x->down)
54 x = x->down;
55 else break;
56 }
57 else if (x->prev->down)
58 x = x->prev->down;
59 else {
60 x = x->prev;
61 break;
62 }
63 }
64 bindNewNode(x, p);
65 while (rand() % 2) { //throw the coin, then judge whether it needs to be higher according to the results
66 Node * highp = new Node;
67 highp->key = key;
68 while (!x->top && x->prev)
69 x = x->prev;
70 if (x->top) {
71 x = x->top;
72 bindNewNode(x, highp);
73 highp->down = p;
74 p->top = highp;
75 }
76 else { //already the top, add a sentry
77 Node * top = new Node;
78 x = top;
79 top->key = INT_MIN;
80 top->down = head;
81 head->top = top;
82 head = top;
83 bindNewNode(top, highp);
84 highp->down = p;
85 p->top = highp;
86 ++level;
87 }
88 p = highp;
89 }
90 ++size;
91 }
92
93 void Skiplist::delNode(Node * x) {
94 if (!x->next) { //node x is the last one
95 if (x->prev == head && head->down) { //x is not at the bottom and x is the last one of this level
96 head = head->down;
97 head->top = nullptr;
98 delete x->prev;
99 --level;
100 }
101 else
102 x->prev->next = nullptr;
103 }
104 else {
105 x->prev->next = x->next;
106 x->next->prev = x->prev;
107 }
108 delete x;
109 }
110
111 void Skiplist::remove(int key) {
112 Node * x = searchNode(key);
113 if (x) {
114 while (x->down) {
115 Node * y = x->down;
116 delNode(x);
117 x = y;
118 }
119 delNode(x);
120 --size;
121 }
122 }
123
124 Skiplist::Node * Skiplist::searchNode(int key) {
125 Node * x = head;
126 while (1) { //find the prev node of p, which represents the right insert place
127 if (x->key == key)
128 return x;
129 else if (x->key < key) {
130 if (x->next)
131 x = x->next;
132 else if (x->down)
133 x = x->down;
134 else
135 return nullptr;
136 }
137 else if (x->prev->down)
138 x = x->prev->down;
139 else {
140 return nullptr;
141 }
142 }
143 }
144
145 void Skiplist::showSkiplist() {
146 Node * x = head, * y = head;
147 while (y) {
148 x = y;
149 while (x) {
150 if (x->prev != nullptr)
151 cout << x->key << ' ';
152 x = x->next;
153 }
154 cout << endl;
155 y = y->down;
156 }
157 }
原文链接: https://www.cnblogs.com/yxsrt/p/12249745.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/192606
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!