一，字典的基本概念

?操作:检索、插入元素和删除元素,其中最主要的运算是进行检索
●检索:给定一个key ,在字典中找出关键码等于key的元素

字典有顺序存储，链式存储和散列表示三种存储方式，其中，链式存储又有跳跃链表和树形结构两种方式存储。

静态字典: 一旦建立好，基本不动
动态字典:经常需要更新
?

评价标准:平均检索长度( Average Search Length )

?二，跳跃链表

1，跳跃链表的基本概念

链表其缺点是只能顺序查找,即使是有序的链表也不能实现二分查找操作。跳跃链表(skiplist) 是有序链表的变种，它能够达到O(log n)的查找性能,是一种高效的字典结构。在单链表中只有一个指向直接后继的指针，而在跳跃链表中增加指向其他后继结点的指针，使得访问链表的过程中可以交替的跳过他的直接后继结点,

?横向叫做层，竖向叫做塔。

越高层链表结点是底层链表结点的子集，底层结点包含了所有词条，跳跃链表查找时从最高层开始找，最坏的情况就是找到最低层。

2，跳跃链表的建立和查找

#define MAX_ LEVEL 6    //定义最大层数
typedef int KeyType;    //跳跃链表结点结构定义
typedef struct node
{
    int level;    //结点层数
    KeyType key;    //结点的值
    struct node *next[MAX_ LEVEL]; // 指针数组
}*PNode;

//跳跃链表结构定义
typedef struct
{
    int num;     //跳跃链表数据个数
    int maxLevel;    //跳跃链表最大层数
    PNode head; // 跳跃链表的头指针
}*SkipList;

//创建带有头结点的空跳跃链表
SkipList SetNullSkipList(int level)
{
    SkipList list = (SkipList)malloc(sizeof(SkipList));
    if (list == NULL)//申请内存失败
        return NULL;
    list->num= 0; //空跳跃链表计数器赋值0
    list->maxLevel = level; //跳跃链表的层数
    list->head = CreateNode(level, -1://头结点的数据域赋值为-1
    if (list->head == NULL)
    {
        free(list); return NULL;
    }
    for (inti= 0;i< level; i++) //头结点的每一层的后继为空
        list- >head->next[i] = NUL;
    return list;
}

生成一个新结点

PNode CreateNode(int level, KeyType key) //生成个一新结点
{
    PNode p = (PNode)malloc(sizeof(struct node) + sizeof(PNode)*level);
    if (p == NULL) return NULL;
    p->level = level;
    p->key = key;
    return p;
}

查找：

PNode SkipListSearch(SkipList list, KeyType key) 
//按值查找，存在返回key的位置，失败返回NULL
{
    int n = 0;PNode p = NULL, q = NULL; p = list->head;

    for (int i-lit->maxLevel- 1;i>= 0; i) //从高层开始，纵向逐层比较
    {
        while ((q = p->next[i]) && (q->key <= key)) //横向比较
        {
            p= q;
            n++;    //记录比较次数
            if (p->key == key)
                { printf("%d\n", n); return p; }
        }
    }
    return NULL;
}

查找算法过程:假设要查找元素key,从最高层的指针开始，如果找到该元素，则返回结点指针。如果到达了链表的末尾，或者找到大于key的某个元素elem,接着降低一层，从包含elem的那个结点的前一个结点重新开始查找。重复该过程直到找到key,或者在第一层查找达到了链表末尾，或者找到了一个大于key的元素。
?

3，跳跃链表的插入和删除：

插入过程:首先进行查找，查找成功，返回0 (因为在这里约定不能有相同的key)故不再插入。查找失败，则创建一个结点，接着，逐层修改关联的指针，跳跃链表的计数器加1.
?

创建结点的层数根据投币产生，在算法中使用逻辑表达式rand() % 2来模拟投币过程，通过(伪)随机数的奇偶来模拟一次理想的投币过程。根据RandomLevel的返回值插入到相应的层。
?

//插入结点，成功返回1,否则返回0
int SkipListInsert(SkipList list, KeyType key)
{
    int level = 0;
    PNode Pre[MAX_ LEVEL]; //记录每层的前驱结点位置
    PNode p, q = NULL;
    p = list->head;
    //查找位置，记录前驱结点信息
    for (int i= list->maxLevel- 1; i>= 0; i--) //纵向控制层
    {
        //横向查找插入位置，而for循环是 纵向移动查找位置
        while ((q = p->next[i]) && (q->key< key)) p= q;
        Pre[i]= p;
    }
    //已经存在相同的key,不能插入
    if ((q != NULL) && (q->key == key)) return 0;
    level = RandomLevel(list->maxLevel); /产生-一个随机层数
    p = CreateNode(level, key); //创建新结点
    if (p == NULL) return 0;
    //纵向逐层修改指针
    for (inti= 0;i< level; i++)
    {
        p->next[i] = Pre[i]->next[i];
        Pre[i]->next[i]= p;
    }
    list->num++; //跳跃链表的计数器加1
    return 1;
}

int RandomLevelint maxlevel)//产生随机层数,在各塔中自底向上逐层生长。
{
    int i= 1;
    while (rand() % 2)
        i++;
    i= (i> maxlevel) ? maxlevel :i;
    return i; 
}