2019-10-18 | UNLOCK

skip-list

联创考试的时候让学跳表,学了以下。

跟 $k$ 有关的操作可以查indexed skip list之类的?

写了好久(摔!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cstring>
#include <ctime>
#define MAXLEVEL 15
struct Random {//一个创造随机级别的结构体
Random() {
srand((int)time(NULL));
}
int makeRandomInt(int higher) {//产生一个在[1, higher]之间的级别
int re=1;
while(re<higher) {
if(rand()%10<5) re++;
else break;
}
return re;
}
}randomInt;
struct SkipList {
struct Node {
int key;
struct Level { //每一个节点都有指向每一层的前向指针
Node *forward;
int width;//每条线多长
}level[MAXLEVEL];
};
int level;//跳表的高度
int length;//总共多少个
Node *header;
Node * createNode(int itsLevel, int key) {
Node *node=(Node *)malloc(sizeof(*node));
// printf("%d\n", sizeof(*node));
node->key = key;
return node;
}
SkipList() {
level = 1;
header = createNode(MAXLEVEL, 0);
for(int i=0; i<MAXLEVEL; i++) {
header->level[i].forward = NULL;
header->level[i].width = 0;
}
}
Node *findNode(int key) {//辅助函数,找到node
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward!=NULL && key>node->level[i].forward->key)
node = node->level[i].forward;
}
if(node->level[0].forward!=NULL && node->level[0].forward->key==key) {
return node->level[0].forward;
}
else return NULL;
}
void insert(int key) {
if(findNode(key)) {
printf("错误!请不要重复插入相同的数字,您的这次插入无效。\n");
return ;
}
int itsLevel=randomInt.makeRandomInt(MAXLEVEL);
int stepsAtMove[MAXLEVEL];
memset(stepsAtMove, 0, sizeof(stepsAtMove));
Node *behinds[MAXLEVEL];//每一层刚好被node卡在后头的那个节点
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward!=NULL && key>node->level[i].forward->key) {

stepsAtMove[i] += node->level[i].width;
node = node->level[i].forward;

}
behinds[i] = node;
}
node = createNode(itsLevel, key);
// printf("%p\n", node);
if(itsLevel>level) {
for(int i=level; i<itsLevel; i++) behinds[i] = header;
level = itsLevel;
}
int steps=0;
for(int i=0; i<level; i++) {
node->level[i].forward = behinds[i]->level[i].forward;
behinds[i]->level[i].forward = node;
node->level[i].width = behinds[i]->level[i].width-steps;//behinds到node那个点在上一层差下多少steps
behinds[i]->level[i].width = steps + 1;
steps += stepsAtMove[i];
}
for(int i=level; i<MAXLEVEL; i++)
header->level[i].width++;
length++;
printf("插入成功。\n");
}
void dele(int key) {//还没更新width
if(findNode(key)==NULL) {
printf("错误!您不能删除一个不存在的数。\n");
return ;
}
Node *behinds[MAXLEVEL];//每一层刚好被node卡在后头的那个节点
Node *node=header;
// printf("%d as level\n", level);
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward!=NULL && key>node->level[i].forward->key) {
node = node->level[i].forward;
}
behinds[i] = node;
// printf("behinds%d: %p\n", i, behinds[i]);
}
node = node->level[0].forward;
for(int i=0; i<level; i++) {
if(behinds[i]->level[i].forward==node) {
behinds[i]->level[i].width = behinds[i]->level[i].forward->level[i].width - 1;
behinds[i]->level[i].forward = node->level[i].forward;
}
}
for(int i=level; i<MAXLEVEL; i++) header->level[i].width--;
while(level>1 && header->level[level-1].forward==NULL) level--;
free(node);
length--;
printf("删除成功!\n");
}
int findkth(int key) {
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward && key>=node->level[i].width) {
key -= node->level[i].width;
node = node->level[i].forward;
}
}
return node->key;
}
void whichRank(int key) {
if(findNode(key)==NULL) {
printf("这个数不存在!\n");
return ;
}
int steps=0;
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward && key>node->level[i].forward->key) {
steps += node->level[i].width;
node = node->level[i].forward;
}
}
printf("%d是第%d大。\n", key, steps+1);
}
void whichAfter(int key) {
Node *re=findNode(key);
if(re==NULL) printf("您给的数字不存在!\n");
else if(re->level[0].forward==NULL) printf("%d的后继不存在!\n", key);
else printf("%d的后继是%d。\n", key, re->level[0].forward->key);
}
void query(int l, int r) {
printf("符合条件的有:[ ");
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward && l>node->level[i].forward->key) {
node = node->level[i].forward;
}
}
node = node->level[0].forward;
while(node!=NULL && node->key>=l && node->key<=r) {
printf("%d ", node->key);
node = node->level[0].forward;
}
printf("]。\n");
}
void rangeDele(int l, int r) {
Node *node=header;
for(int i=level-1; i>=0; i--) {
while(node->level[i].forward && l>node->level[i].forward->key) {
node = node->level[i].forward;
}
}
node = node->level[0].forward;
while(node!=NULL && node->key>=l && node->key<=r) {
Node *nxt=node->level[0].forward;
dele(node->key);
node = nxt;
}
}
}skipList;
int main() {
printf("欢迎来到跳表测试!请按规定输入指令,否则会造成不可预料的错误!\n请输入数字代号并按下回车进行操作。\n");
printf("1:插入一个数\n");
printf("2:删除一个数\n");
printf("3:查看第k大的数字\n");
printf("4:查看一个数是第几大\n");
printf("5:询问一个数的后继\n");
printf("6:输出一个区间里存在的数字\n");
printf("7:删除一个区间里存在的数字\n");
printf("8:结束\n");
while(true) {
int opr, usr, rsu;
printf("请输入数字代号:");
std::cin>>opr;
switch(opr) {
case 1:
printf("请输入你想要插入的数k:\n");
std::cin>>usr;
skipList.insert(usr);
break;
case 2:
printf("请输入你想要删除的数k:\n");
std::cin>>usr;
skipList.dele(usr);
break;
case 3:
printf("你想要查看第几大的数字?请输入:\n");
std::cin>>usr;
if(usr>skipList.length) printf("当前没有这么多数字,本次操作无效。\n");
else printf("第%d大的数字是%d。\n", usr, skipList.findkth(usr));
break;
case 4:
printf("你想查看谁是第几大?请输入:\n");
std::cin>>usr;
skipList.whichRank(usr);
break;
case 5:
printf("你想查看谁的后继?请输入:\n");
std::cin>>usr;
skipList.whichAfter(usr);
break;
case 6:
printf("请输入区间左右端点(中间用空格分开):\n");
std::cin>>usr>>rsu;
skipList.query(usr, rsu);
break;
case 7:
printf("请输入区间左右端点(中间用空格分开):\n");
std::cin>>usr>>rsu;
skipList.rangeDele(usr, rsu);
break;
case 8: return 0; break;
default: break;
}
}
return 0;
}