C 实现链表的高速公路-跳跃表

本文所需基础：

1.知道如何用c写链表。

2.下文将会教到的柔性数组。

预准备（柔性数组）：

为了下文讲述方便，先介绍柔性数组，看下面一段代码：

typedef struct node* link;

struct node

{

int number;

link a[1];

};

这里的结构体中包含了一个长度为1的数组，那么这个数组有什么用呢？看下面两行代码：

1.malloc(sizeof(struct node))

2.malloc(sizeof(struct node)+sizeof(link)*5)

第一行代码为结构体分配的空间不包括数组，第二行代码为数组也开辟空间，并且数组最多可以放入5个元素，所以link a[1]并不会对数组长度进行限制，也就是说结构体的大小是可以变化的。

正式开始：

（正文分为4个部分，最后是代码实现）

1.链表的初级加速：

假设我们有一个长度为1000的有序链表，想要找到第600个节点，我们不得不遍历前面所有节点。因为每次查找都要从头开始。那么如何才能每次不都从头开始呢：方法很简单，记录一下第500个节点的地址，查找后面的节点时，直接跳到第500个节点，再继续查找，这样就省去了前面那些节点的遍历时间。换句话说，在第0个节点和第500个节点之间建立高速公路，一站到达。

2.再加速：

既然在第0个节点和第500个节点之间建立起来了高速公路，为什么不在第0个节点和第250个节点之间也建立一条呢？如此下去，岂不是也就方便了第250个节点到第500个节点之间的节点？但是要注意一点的是随着高速站点的建立，高速公路也会变慢，如果为每个元素都创建高速公路站点的话，高速公路就会退化成与原来一模一样的链表。

那么如何平衡这个矛盾呢？既要让每个节点享受到高速公路的便捷，又不能拖垮高速公路的速度。

我们可以每隔一个节点建立一个高速站点，查找元素时候先从高速公路查找。发现节点在两个高速站点之间再用原来的链表查找。比如下图查找4，从1找到3,发现4在3和它的下一个节点5之间，从3开始，3- >4，就找到了该元素，如下图：

但是这样，我们查找最后一个元素也要查找500次，还是有点慢，但是我们可以不断向上搭建高速公路，像这样： '

这样的话，一个理论上完美的跳跃表就完成了。

3.实际情况对应的改进：

为什么说上面的跳跃表是理论上完美呢？因为一个有序的跳跃表应该像链表一样允许随时插入，删除。但是像上面那样的表如果在前面插入一个元素，后面基本所有的高速公路上的节点都要改。那么如何改进这个问题呢：

随机化！ 举个栗子：(下面的高速站点指的都是每个结构体指向下面那些结构体的指针)

比如想要插入一个元素为3的节点，首先我们要决定给它往上建几个高速站点，由于每条高速公路的节点数都差不多是下面高速公路的一半，所以插入3的时候，生成0，1随机数决定是否多往上建立一个高速站点，如果随机数显示的是"是"，那么继续生成随机数是否再继续往上建立，直到随机数显示不再往上建立高速站点。(注意所有节点的高速站点数量不能超过第一个节点的高速站点数量，一般初始化的时候，会把第一个的高速站点设的多一些，因为每次开始都要从第一个的节点的最上面的高速站点开始查找)柔性数组满足了这种结构，每个节点可以有不同的高速站点数量。这样当插入的节点足够多的时候，就会满足每一条高速公路的节点数量是下面那条高速公路节点数量的一半：

虽然从局部来看，有的地方速度不太好，但是随机化保证了在大量数据中，整体效果还不错。

4.代码实现：(只实现初始化和插入功能)

#include<stdio.h>

#include<stdlib.h>

typedef struct node* link;

struct node{int no;link next[1];};

link init(int max); //max为第一个节点要建立多少个高速站点,通常第一个节点不会保存数据，从第二个开始保存。

int height(void); //决定一个节点到底要有几个高速站点

void insert(int x,link head,int max,int k); // x为插入的元素，head为跳跃表头指针，max为第一个节点有多少高速站点，k是插入的元素要有几个高速站点

link init(int max)

{

link head= malloc(sizeof(*head)+sizeof(link)*max);

return head;

}

int height(void)

{

int i = 0;

while(rand()%2) //生成0或1随机数

i++;

return i;

}

void insert(int x,link head,int max,int k)

{

link p = head;

link temp = NULL;

link ptr = malloc(sizeof(*ptr)+sizeof(link)*k); ptr->no = x;

//第一个while循环是争取找到x的插入位置，(可能找不到)。但是先不进行插入操作。

while(max>k) {

while(p->next[max]!=NULL) {

if((p->next[max]->no)<x) p = p->next[max];

else break;

}

max--;

}

//第二个while循环，如果已经找到了，那么就不断的在每个高速道路插入，如果没找到就接着找，找到了再不断的在每个高速路上插入。

while(max>=0) {