By

文章目录

跳表用于数据的存储，包含插入删除和查找，它的效率近似于平衡二叉树，但是跳表原理简单，易于理解。
针对一个有序的链表，元素的查找也要从表头开始逐一比较，不能使用二分查找的方法。此时，我们可以提取一些节点出来，作为链表的索引。
如此搜索的时候便可以减少比较次数。同时，也可以再根据一级索引建立二级索引。
当链表中的元素足够多时，通过索引查找元素优势明显，因此，跳表是“空间换时间”的应用。
通过上图可以看出，跳表每一层数据有序，上一层可以作为下一层的索引，最底层包含所有数据，除最底层外，每个节点包含两个指针，一个指向同层链表的下一个元素，一个指向下面一层元素。
对于跳表，主要功能仍然是查找，插入和删除。

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
#include "skiplist.hpp"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
typedef struct node
{
    int value;
    struct node *next[1];
    
}Node;
typedef struct skip_list
{
    int level;
    Node *head;
}skip_list;
#define new_node(n) ((Node*)malloc(sizeof(Node)+n*sizeof(Node*)))
#define MAX_L 10
Node *create_node(int level ,int value)
{
    Node *p = new_node(level);
    if(!p)
    {
        return NULL;
    }
    p->value = value;
    return p;
}
skip_list *create_sl()
{
    skip_list *sl = (skip_list*)malloc(sizeof(skip_list));
    if(NULL==sl)
        return NULL;
    sl->level = 0;
    Node *h = create_node(MAX_L-1,0);
    if(h==NULL)
    {
        free(sl);
        return NULL;
    }
    sl->head = h;
    int i;
    for(i = 0;i<MAX_L;i++)
    {
        h->next[i]=NULL;
    }
    srand((int)time(0));
    return sl;
}
int randomLevel()
{
    int level = 0;
    while(rand()%2)
    {
        level++;
    }
    level = (MAX_L>level)?level:MAX_L;
    return level;
}
bool insert(skip_list *sl,int value)
{
    Node *update[MAX_L];
    Node *q = NULL,*p=sl->head;
    int i;
    for(i = sl->level;i>=0;i--)
    {
        while((q=p->next[i])&&q->value<value)
        {
            p=q;
        }
        update[i]=p;
    }
    if(q&&q->value == value)
        return true;
    int level = randomLevel();
    if(level>sl->level)
    {
        for(i = sl->level;i<level;i++)
        {
            update[i] = sl->head;
        }
        sl->level = level;
    }
    q = create_node(level,value);
    if(!q)
        return false;
    for(i = level-1;i>=0;--i)
    {
        q->next[i]=update[i]->next[i];
        update[i]->next[i] = q;
    }
    return true;
}
bool erase(skip_list *sl,int value)
{
    Node *update[MAX_L];
    Node *q = NULL,*p = sl->head;
    int i = sl->level;
    for(;i>-0;i--)
    {
        while((q = p->next[i]) && q->value < value)
        {
            p =q;
        }
        update[i] = p;
    }
    if(!q ||(q&&q->value!=value))
        return false;
    for(i = sl->level;i>=0;--i)
    {
        if(update[i]->next[i]==q)
        {
            update[i]->next[i] = q->next[i];
            if(sl->head->next[i]==NULL)
                sl->level--;
        }
    }
    free(q);
    q = NULL;
    return false;
}
int *search(skip_list *sl,int value)
{
    Node *q,*p =sl->head;
    q = NULL;
    int i = sl->level;
    for(;i>=0;i--)
    {
        while((q=p->next[i])&& q->value< value)
            p=q;
        if(q&&q->value == value)
            return &(q->value);
    }
    return NULL;
}
void sl_free(skip_list *sl)
{
    if(!sl)
        return ;
    Node *q = sl->head;
    Node *next;
    while(q)
    {
        next = q->next[0];
        free(q);
        q = next;
    }
    free(sl);
}

文章目录