define _CRT_SECURE_NO_WARNI NGS include stdio include stdlib include m

  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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#define CharLength 100 // максимальная длина слова
struct SkipListElement {
SkipListElement **mass;
int k;
char *val;
};
struct SkipListElement *InitSkipList(int m)
{
int i;
SkipListElement *l;
l=(SkipListElement*)malloc(sizeof(SkipListElement));
l->mass = (SkipListElement**)malloc(m*sizeof(SkipListElement*));
l->k=0;
l->val=(char*)malloc(CharLength*sizeof(char));
for (i=0; i<m; i++) l->mass[i] = 0;
return l;
}
struct SkipListElement* Succ(SkipListElement *p)
{
return (p->mass[0]);
}
void Skip(SkipListElement *l, int m, int k, SkipListElement **p)
{
SkipListElement *x = l;
int i;
for (i = m-1; i>=0; i--) {
while ((x->mass[i])&&(k>x->mass[i]->k)) x = x->mass[i];
p[i]=x;
}
}
void Delete(SkipListElement *l, int m, int k)
{
int i;
SkipListElement *x, **p = (SkipListElement**)malloc(m*sizeof(SkipListElement*));
Skip(l, m, k, p);
x=Succ(p[0]);
for (i=0; ((i<m)&&(p[i]->mass[i]==x)); i++) p[i]->mass[i]=x->mass[i];
free(x->val);
free(x->mass);
free(x);
free(p);
}
void Insert(SkipListElement *l, int m, int k, char *v)
{
int r, i;
SkipListElement *x, **p = (SkipListElement**)malloc(m*sizeof(SkipListElement*));
Skip(l, m, k, p);
srand((unsigned int)time(0));
x = InitSkipList(m);
strncpy(x->val, v, CharLength);
x->k=k;
r = rand()*2;
for (i=0; ((i<m)&&!(r%2)); i++, r/=2) {
x->mass[i]=p[i]->mass[i];
p[i]->mass[i]=x;
}
free(p);
}
void LookUp(SkipListElement *l, int m, int k)
{
SkipListElement **p = (SkipListElement**)malloc(m*sizeof(SkipListElement*));
Skip(l, m, k, p);
printf("%s\n", (Succ(p[0]))->val);
free(p);
}
void Rank (SkipListElement *l, int m, int k)
{
int i;
SkipListElement *x = l;
for(i=0; k!=x->k; x=x->mass[0], i++);
printf("%d\n", i-1);
}
void main()
{
int i, n, m, k;
char v[CharLength], a[7];
SkipListElement *l;
scanf("%d", &n);
m = log((float)n)/log((float)2) + 1;
l = InitSkipList(m);
for (i=0; i<n; i++) {
scanf("%s", a);
switch (a[0]) {
case 'I':
scanf("%d %s", &k, v);
Insert(l, m, k, v);
break;
default:
scanf("%d", &k);
switch (a[0]) {
case 'L': LookUp(l, m, k); break;
case 'D': Delete(l, m, k); break;
case 'R': Rank(l, m, k); break;
}
}
}
}