高级数据结构：跳跃表的基本操作和应用

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MOD 1000000//宏定义取模数值，方便修改 #define MAX_L 16 //设置跳跃表最大层数 #define new_node(n) ((Node*)malloc(sizeof(Node)+n*sizeof(Node*))) //由node生成一个Node结构体,同时生成包含n个Node *元素的数组 const int inf = 0x7f7f7f7f; int minx = -inf, maxx = inf;//设置全局变量，把minx设置成最大，maxx设置成最小 //定义key和value的类型 typedef int keyType; typedef int valueType; //每个节点的数据结构 typedef struct node { keyType key;// key值 valueType value;// value值 struct node *next[0];// 后继指针数组，可实现结构体的变长 } Node; //跳跃表结构 typedef struct skip_list { int level;// 最大层数 Node *head;//指向头结点 } skip_list; //函数声明 Node *create_node(int level, keyType key, valueType val); //创建节点函数,成功返回Node*类型指针,否则返回NULL //level 节点层数 key 节点关键字 val 节点的数值 skip_list *create_sl(); //创建跳跃表函数，成功返回skip_list*类型指针,否则返回NULL int randomLevel(); //随机化算法函数，插入元素的时候元素所占有的层数需要随机算法,返回随机层数 bool insertNode(skip_list *sl, keyType key, valueType val); //插入函数，插入节点，插入成功返回true，否则返回false //sl 跳跃表指针 key 节点关键字 val 节点的值 bool eraseNode(skip_list *sl, keyType key); //删除函数，删除节点，成功返回true，否则返回false //sl 跳表指针 key 节点关键字 valueType *search(skip_list *sl, keyType key); //查找函数，查找节点，成功返回valueT*类型的指针，否则返回NULL //sl 跳表指针 key 节点关键字 bool valueSearch(skip_list *sl, keyType key); //查找函数2，查找节点，成功返回true，否则返回false //sl 跳表指针 key 节点关键字 void print_sl(skip_list *sl); //从最高层开始逐层打印 void sl_free(skip_list *sl); //销毁跳跃表函数，释放跳跃表 //sl 跳表指针 void appsolve(); //解决实际应用问题——宠物收养所 // 创建节点 Node *create_node(int level, keyType key, valueType val) { Node *p=new_node(level); if(!p) return NULL; p->key=key; p->value=val; return p; } //创建跳跃表 skip_list *create_sl() { int i; skip_list *sl=(skip_list*)malloc(sizeof(skip_list));//申请跳跃表结构内存 if(NULL==sl) return NULL; sl->level=0;//初始化跳跃表的层level，初始的层为0层（数组从0开始） Node *h=create_node(MAX_L-1, 0, 0);//创建头结点 if(h==NULL) { free(sl); return NULL; } sl->head = h; for(i=0; i<MAX_L; ++i) // 将header的next数组初始化，设置为NULL { h->next[i] = NULL; } srand(time(0)); return sl; } //插入元素的时候元素所占有的层数完全是随机算法 int randomLevel() { int level=1; while (rand()%2) level++; level=(MAX_L>level)? level:MAX_L; return level; } //插入节点 bool insertNode(skip_list *sl, keyType key, valueType val) { Node *update[MAX_L]; Node *q=NULL,*p=sl->head;//q,p初始化 int i; //从最高层往下查找需要插入的位置,并更新update数组 for(i=sl->level-1; i>=0; --i) { while((q=p->next[i])&& q->key<key) p=q; update[i]=p; }//把降层节点指针保存到update数组 if(q && q->key == key)//key已经存在的情况下 { q->value = val; return true; } //产生一个随机层数level int level = randomLevel(); //如果新生成的层数比跳跃表的层数大 if(level>sl->level) { //在update数组中将新添加的层指向head for(i=sl->level; i<level; ++i) { update[i]=sl->head; } sl->level=level; } //新建一个待插入节点,一层一层插入 q=create_node(level, key, val); 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 eraseNode(skip_list *sl, keyType key) { Node *update[MAX_L]; Node *q=NULL, *p=sl->head; int i = sl->level-1; for(; i>=0; --i) { while((q=p->next[i]) && q->key < key) { p=q; } update[i]=p; } //判断是否为待删除的key if(!q || (q&&q->key != key)) return false; //逐层删除与普通链表删除一样 for(i=sl->level-1; i>=0; --i) { if(update[i]->next[i]==q)//删除节点 { update[i]->next[i]=q->next[i]; //如果删除的是最高层的节点,则level-- if(sl->head->next[i]==NULL) sl->level--; } } free(q); q=NULL; return true; } // 查找元素 valueType *search(skip_list *sl, keyType key) { Node *q,*p=sl->head; q=NULL; int i=sl->level-1; for(; i>=0; --i) { while((q=p->next[i]) && q->key<key) { p=q; } if(q && key==q->key) return &(q->value); } return NULL; } // 判断待查找元素是否存在 bool valueSearch(skip_list *sl, keyType key) { Node *q,*p=sl->head; q=NULL; int i=sl->level-1; for(; i>=0; --i) { while((q=p->next[i]) && q->key<key) { p=q; } if(q && key==q->key) return true; } return false; } //找出待找关键字的前驱 Node *preNodeSearch(skip_list *sl, keyType key) { Node *q,*p=sl->head; q=NULL; for(int i=sl->level-1; i>=0; --i) { while((q=p->next[i]) && q->key<key) p=q; } //printf("1\n"); return p; } //从最高层开始逐层打印 void print_sl(skip_list *sl) { Node *q; int i=sl->level-1; for(; i>=0; --i) { q=sl->head->next[i]; printf("level %d:\n", i+1); while(q) { printf("key:%d val:%d\t", q->key, q->value); q=q->next[i]; } printf("\n"); } } // 释放跳跃表 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); } //解决实际问题——宠物收养所 void sppsolve() { skip_list *sl=create_sl(); int N, sum = 0, ans, a, b, num = 0; Node *p; printf("请输入一年当中来到收养所的宠物和领养者的总数，例如：8+Enter。\n请输入一个非负整数："); scanf("%d",&N);//输入一年当中来到收养所的宠物和领养者的总数 printf("请输入一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b;\n其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。\n例如：1 3+Enter。\n"); while( N-- ) { printf("请输入一组数字："); scanf("%d%d",&a,&b); if( !num ) //宠物和领养者数量刚好相同 { insertNode(sl, b, b); num++; ans = a; } else if( ans == a )//与第一个插入结点的情况相同 { insertNode(sl, b, b); num++; } else //与第一个插入跳跃表的情况不一样时 { minx = -inf, maxx = inf; p=preNodeSearch(sl,b);//找出比待查关键字的小的最大整数 //printf("2\n"); //printf("%d \n",p->value); if(valueSearch(sl, b))//查找关键字刚好匹配成功 { num--; eraseNode(sl, b); continue; } else if(!p->key&&p->next[0]->key) //待查找的关键字比第一个节点小的情况 { maxx=p->value; sum+=abs(maxx-b); eraseNode(sl, p->value); num--; } else if(p->key&&!(p->next[0])) //待查找的关键字比最后一个节点大的情况 { minx=p->value; sum+=abs(b-minx); eraseNode(sl, p->value); num--; } else