精华内容
下载资源
问答
  • 跳表实现

    2020-03-05 02:50:15
    跳表插入元素x 删除跳表内元素x,若不存在则抛出异常 删除跳表内关键字最小的元素 删除跳表内关键字最大的元素 其他根据需要实现,注意数据的可访问性 格式 输入格式 输入包含 1+n+m 行数据 第一行包含两个数字 n,...

    要求
    实现并分析跳表结构
    构造并实现跳表ADT,跳表ADT包括如下操作:

    初始化跳表
    查找跳表内是否存在元素x
    向跳表插入元素x
    删除跳表内元素x,若不存在则抛出异常
    删除跳表内关键字最小的元素
    删除跳表内关键字最大的元素
    其他根据需要实现,注意数据的可访问性
    格式
    输入格式
    输入包含 1+n+m 行数据
    第一行包含两个数字 n, m (0 \leq n \leq 1000, 0 \leq m \leq 10000≤n≤1000,0≤m≤1000)
    之后的 n 行,每行包含一个数字与一个字符串,表示一个元素,数字为跳表的关键字(0\leq key \leq 1,000,000,000)(0≤key≤1,000,000,000),字符串为元素的值。
    之后的 m 行表示 m 个跳表ADT操作。每行第一个数字 a 用来区别操作。

    a 为 1 时,表示查找操作,其后的一个数字 b 为要查询的元素的关键字, 输出 该元素的值,不存在则输出 -1。
    a 为 2 时,表示插入操作,其后的一个数字 b 为要插入的元素,一个字符串 c 为对应的值, 不输出 。
    a 为 3 时,表示删除操作,其后的一个数字 b 为要删除的关键字, 输出 该关键字与其对应的元素值,若删除关键字不存在或删除失败,输出 -1。
    a 为 4 时,表示删除最小元素操作。 输出 跳表内最小关键字 c 与其对应的元素值,并将对应元素在跳表内部删除
    a 为 5 时,表示删除最大元素操作。 输出 跳表内最大关键字 c 与其对应的元素值,并将对应元素在跳表内部删除
    输出格式
    请根据输入描述,完成跳表的相应操作,输出正确的信息

    样例
    输入

    3 6
    10 apple
    1 mi
    5 oops
    1 10
    2 7 oppo
    3 4
    3 5
    4
    5
    

    输出

    apple
    -1
    5 oops
    1 mi
    10 apple
    

    可能出现的问题:
    删除时不是指删除找到的第一个元素
    要继续下一层查找 元素会同时存在多层

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <iostream> 
    using namespace std;
    typedef int Key;
    int maxlevel=20;
    struct item{Key key;
    };
    typedef struct sknode* link;
    struct sknode{//建结构
    	item it;//元素->用来排序
    	string str;//元素值
    	link *next;//指向下一个节点
    	int s;//连接数
    };
    
    link head;//头指针
    link endd;//尾指针
    
    int allnode;//节点总数
    int highlevel;//层数
    
    struct item NULLit;//判断空
    string NULLstr="-1";//判断空
    Key key(item it){
    	return it.key;
    }
    
    link NEW(item it,string str,int s){
    	link x=new sknode;//使用new使得string分配到空间
    	//x->next=new sknode*;//若值不为string类型可用
    	x->next=(link *)malloc(s*sizeof(link));
    	x->it=it;
    	x->s=s;
        if(str!="-1"){x->str=str;
    	}
    	for(int i=0;i<s;i++){
    		x->next[i]=endd;
    	}
    	return x;
    }
    
    void skinit(){//初始化
    	allnode=0;highlevel=0;
    	endd=NEW(NULLit,NULLstr,1000);
    	head=NEW(NULLit,NULLstr,maxlevel+1);
    }
    
    int randnode(){//随机数生成
    	int i,j,t=rand();
    	for(i=1,j=2;i<maxlevel;i++,j+=j){
    		if(t>RAND_MAX/j){break;
    		}
    	}
    	if(i>highlevel){
    			highlevel=i;
    		}
    		return i;
    }
    
    void insert(link t,link x,int s){//t:原跳表 x:插入元素 s:层数 
    	Key v=key(x->it),u=key(t->next[s]->it);
    	if(v<u||u==0){
    		if(s<x->s){
    			x->next[s]=t->next[s];
    			t->next[s]=x;
    		}
    		if(s==0){return;
    		}
    		insert(t,x,s-1);return;//这层不应该被插入 从下一层开始找
    }
    	}
    	insert(t->next[s],x,s);//下一个元素
    
    void skinsert(item it,string str){
    	insert(head,NEW(it,str,randnode()),highlevel);
    	allnode++;
    }
    
    void deletenode(link t,Key k,int s){//t:原跳表 k:插入元素 s:层数
        if(t==endd){cout<<-1<<endl;return;
    	}
    	link x=t->next[s];
    	if(!(key(x->it)<k)||key(x->it)==0){
    		if(k==key(x->it)){//找到元素
    			t->next[s]=x->next[s];//链表删除
    			if(s==0){cout<<k<<' '<<x->str<<endl;return;
    			}
    			
    		} 
    		if(s==0){cout<<"-1"<<endl;return;//层数归零
    		}
    		deletenode(t,k,s-1);return;//这层未找到元素 从下一层开始找
    	}
    	deletenode(t->next[s],k,s);//下一个元素
    }
    
    void skdelete(Key k){
    	deletenode(head,k,highlevel);
    	allnode--;
    }
    void search(link t,Key k,int s){//查找
    	if(t==endd){cout<<-1<<endl;return;
    	}
    	if(k==key(t->it)){cout<<t->str<<endl;return ;
    	}
    	Key u=key(t->next[s]->it);
    	if(k<u||u==0){
    		if(s==0){cout<<"-1"<<endl;return;
    		}else{search(t,k,s-1);return;//下一层
    		}
    	}
    	search(t->next[s],k,s);//下一个元素
    } 
    
    void sksearch(Key k){
    	search(head,k,highlevel);
    }
    
    void searchsmall(){//头结点的下一个为最小元素
        link t= head;
    	skdelete(key(t->next[0]->it));return;
    }
    void searchbig(){//第0层节点遍历后的最后一个为最大元素
    	link t = head ;
    	while(t->next[0] !=endd){
    		if(t->next[0]->next[0]==endd){skdelete(key(t->next[0]->it));return;
    		}
     		t = t->next[0];
    	 }
    }
    void p(){//遍历所有元素 
     	link t = head ;
     	while(t->next[0] !=endd){
     		cout<<t->next[0]->it.key<<' '<<t->next[0]->str<<endl;
     		t = t->next[0];
    	 }
    	 cout<<endl;
     }
    int main(){
    	int n,m;
    	skinit();//初始化
    	int a;
    	string st;
    	item nu;
    	cin>>n>>m;
    	for(int i=0;i<n;i++){//插入
    		cin>>nu.key>>st;
    		skinsert(nu,st);
    	}
    	for(int i=0;i<m;i++){
    		cin>>a;
    	    if(a==1){//查找
    	    	cin>>a;
    	    	sksearch(a);
    		}else if(a==2){//插入元素
    			cin>>nu.key>>st;
    			skinsert(nu,st);
    		}else if(a==3){//删除指定元素
    			cin>>a;
    			skdelete(a);
    		}else if(a==4){//删除最小
    			searchsmall();
    		}else if(a==5){//删除最大
    			searchbig();
    		}
    	} 
    	//p();
    }
    
    展开全文
  • 跳表简单介绍

    2020-08-30 20:05:38
    跳表是为了让链表的查找更快而诞生的一种数据结构 跳表在链表的基础上,向上建立索引 跳表的查找从最上层开始,逐层向下进行查找 跳表的插入: ...跳表插入和删除的时间复杂近似为O(logN) ...

    跳表是为了让链表的查找更快而诞生的一种数据结构

    跳表在链表的基础上,向上建立索引

    跳表的查找从最上层开始,逐层向下进行查找

    跳表的插入:

    需要先在链表中插入数据,再去跟新索引。

    跳表的上层节点个数一般是下层节点个数的1/2

    跳表插入和删除的时间复杂近似为O(logN)

     

     

    展开全文
  • 跳表

    2020-08-06 08:58:36
    有序的链表:在一个有序的链表里面,查询跟插入的算法复杂度都是O(n)。 跳表:是一种改进的有序的链表,结点是跳过一部分的,从而加快了查询的速度。 图片来源:[link]

    在这里插入图片描述

    • 有序的链表:在一个有序的链表里面,查询跟插入的算法复杂度都是O(n)。

    • 跳表:是一种改进的有序的链表,结点是跳过一部分的,从而加快了查询的速度。

      图片来源:[link](

    展开全文
  • 数据结构(9)-- 跳表

    千次阅读 热门讨论 2021-02-12 13:52:10
    文章目录跳表跳表的搜索跳表的插入抛硬币跳表的删除跳表的代码实现跳表数据结构初始化跳表插入节点删除节点销毁跳表为什么Redis要用跳表来实现有序集合? 跳表 让你现场手写一棵红黑树、AVL树、伸展树之类的,你行吗...

    在这里插入图片描述

    跳表

    让你现场手写一棵红黑树、AVL树、伸展树之类的,你行吗?
    要不让我查资料,我估计只能扯皮。

    跳表就不一样了,看懂它的原理很简单,根据它的原理直接手写也是可以实现的。

    为什么?
    跳表(skip list) 对应的是平衡树(AVL Tree),是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单容易实现方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树,如 redis, leveldb 等。

    跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。

    链表会写不?链表不会写的话,可以走了。

    开头那张图看着有感觉吗?我第一眼看到那个图,大概就明白了,同时觉得,秀啊!!!
    还能这么玩。

    一个节点要不要被索引,建几层的索引,都在节点插入时由抛硬币决定。当然,虽然索引的节点、索引的层数是随机的,为了保证搜索的效率,要大致保证每层的节点数目与上节的结构相当(差不多对半开)。

    在这里插入图片描述


    跳表的搜索

    在这里插入图片描述

    我现在要在这里面搜索“17”,具体流程是如何的呢?

    为了加快搜索,需要从最高层4开始搜索(因为最高层的节点少,容易定位),首先查看6节点,发现17比其大,向后搜索,发现6后面的节点指向了Nil(4),那么搜索的层数降低1层,
    
    从此节点的第3层开始搜索,发现下个节点是25,大于17,那么再降低一层,从2层开始搜索,发现第2层是9,小于17,继续搜索,发现9节点的下一个数是17,搜索完成。总共查询了
    
    4次,完成搜索(不包含Nil节点的访问。),这种情况下普通有序链表需要6次访问。可以设想下,如果层数为1层的话,那么此时跳表为最坏的情况,退化成有序单链表。复杂度O(n)

    跳表的插入

    第一步:找到待插入节点该去的位置。
    第二步:确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的)。
    第三步:在 Level 1 … Level K 各个层的链表都插入元素。
    第四步:用Update数组记录插入位置,同样从顶层开始,逐层找到每层需要插入的位置,再生成层数并插入。
    (这个update数组不知道的话先存疑)


    抛硬币

    抛硬币,如果是正面(random() < p)则层数加一,直到抛出反面为止。设置一个 MaxLevel,防止如果运气太好,层数就会太高,而太高的层数往往并不会提供额外的性能。


    跳表的删除

    删除的时候和插入相同,都是先搜索。唯一注意的一点是删除的节点也许要修改skiplist->length的值。

    销毁整个调表的时候,从level=1销毁即可,别忘记释放head和skiplist。

    这里就不过多的放图了,意会一下子。

    大年初一还要搞代码,哎。


    跳表的代码实现

    跳表数据结构

    如上图中的E节点,表示的是头节点,一般跳表的实现,最大有多少层(MAX_LEVEL)是确定的。所以e的个数是固定的。

    #define SKIPLIST_MAXLEVEL 32
    #define ZSKIPLIST_P 0.25
    
    typedef struct skiplistNode_t{
        void* value;
        double score;
        struct skiplistNode_t* forward[];
    }skiplistNode;
    
    typedef struct skiplist{
        skiplistNode* head;
        int level;
        uint32_t length;
    }skiplist;
    

    初始化跳表

    skiplistNode* createNode(int level,void* value,double score)
    {
        skiplistNode *slNode = (skiplistNode*)malloc(sizeof(*slNode)+level*sizeof(skiplistNode));
        if(!slNode)
        {
            return NULL;
        }
        slNode->value = value;
        slNode->score = score;
        return slNode;
    }
    
    skiplist* slCreate(void)
    {
        int i;
        skiplist* sl = (skiplist*)malloc(sizeof(*sl));
        if(!sl)
        {
            return NULL;
        }
        sl->length = 0;
        sl->level = 1;
        sl->tail = NULL;
        sl->head = createNode(SKIPLIST_MAXLEVEL,NULL,0.0);
        for(i=0;i<SKIPLIST_MAXLEVEL;i++)
        {
            sl->head->forward[i] = NULL;
        }
        return sl;
    }
    

    插入节点

    插入的时候,会调用一个randomLevel的函数,他可以概率返回1~MAX_LEVEL之间的值,但是level的值越大,概率越小。

    skiplistNode *slInsert(skiplist *sl, void* value, double score)
    {
        skiplistNode* sn,*update[SKIPLIST_MAXLEVEL];
        int i, level;
        sn = sl->head;
        for(i=sl->level-1;i>=0;i--)
        {
            while(sn->forward[i]&&(sn->forward[i]->score<score)){
                sn = sn->forward[i];
            }
            update[i] = sn;
        }
        if(sn->forward[0]&&sn->forward[0]->score == score)
        {
            printf("insert failed,exist!!\n");
            return NULL;
        }
    
        level = slRandomLevel();
        printf("score:%.2lf level:%d\n",score,level);
        if(level>sl->level){
            for(i=sl->level;i<level;i++)
            {
                update[i] = sl->head;
            }
            sl->level = level;
        }
        sn = createNode(level,value,score);
        for(i=0;i<level;i++)
        {
            sn->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = sn;
        }
        sl->length++;
        return sn;
    }
    

    删除节点

    int slDelete(skiplist *sl, double score)
    {
        skiplistNode *update[SKIPLIST_MAXLEVEL];
        skiplistNode *sn;
        int i;
        sn = sl->head;
        for(i=sl->level-1;i>=0;i--)
        {
            while(sn->forward[i]&&sn->forward[i]->score<score){
                sn = sn->forward[i];
            }
            update[i] = sn;
        }
        sn = sn->forward[0];
        if(sn->score != score)
        {
            return -1;
        }
        for(i=0;i<sl->level;i++)
        {
            if(update[i]->forward[i] != sn){
                break;
            }
            update[i]->forward[i] = sn->forward[i];
        }
        free(sn);
        while(sl->level>1&&sl->head->forward[sl->level-1] == NULL){
            sl->level--;
        }
        sl->length--;
        return 0;
    }
    

    销毁跳表

    销毁整个调表的时候,从level=1销毁即可,别忘记释放head和skiplist。

    void slFree(skiplist *sl)
    {
        skiplistNode* sn = sl->head,*st;
        st = sn->forward[0];
        free(sn);
        while(st)
        {
            sn = st->forward[0];
            free(st);
            st = sn;
        }
        free(sl);
    }
    

    接下来我们看点其它的,碧如说跳表与redis。(我第一次接触跳表也是在redis的源码中)


    为什么Redis要用跳表来实现有序集合?

    性能. 主要是对标AVL. 但是AVL实现复杂,对于频繁的增删操作极大可能造成子树的平衡操作,这样很明显就会浪费性能。

    请看开发者说的,他为什么选用skiplist The Skip list:

    There are a few reasons:1) They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.About the Append Only durability & speed, I don’t think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.About threads: our experience shows that Redis is mostly I/O bound. I’m using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the “Redis Cluster” solution that I plan to develop in the future.


    在并发环境下skiplist有另外一个优势,红黑树在插入和删除的时候可能需要做一些rebalance的操作,这样的操作可能会涉及到整个树的其他部分,而skiplist的操作显然更加局部性一些,锁需要盯住的节点更少,因此在这样的情况下性能好一些。


    我的代码实现

    #include<iostream>
    #include<vector>
    #include<time.h>
    
    using namespace std;
    
    
    //跳表节点类
    class sk_list_node {
    public:
    	sk_list_node(int val)
    		:val(val),
    		next(nullptr),
    		next_floor(nullptr) 
    	{}
    
    	sk_list_node(sk_list_node* node) 
    		:val(node->get_value()),
    		next(nullptr),
    		next_floor(nullptr)
    	{
    	}
    
    	void set_next(sk_list_node* node) {
    		this->next = node;
    	}
    
    	void set_next_floor_node(sk_list_node* node) {
    		this->next_floor = node;
    	}
    
    	int get_value() { return this->val; }
    
    	sk_list_node* get_next() {
    		return this->next;
    	}
    
    	sk_list_node* get_next_floor() {
    		return this->next_floor;
    	}
    
    	int equal(sk_list_node* node) {
    		if (node->get_value() == val) {
    			return 0;
    		}
    		else if(node->get_value() > val){
    			return 1;
    		}
    		else {
    			return -1;
    		}
    	}
    
    private:
    	int val;	//当前节点值
    	sk_list_node* next;	//下一个节点
    	sk_list_node* next_floor;	//下一层对应节点
    };
    
    //跳表类
    class sk_list {
    public:
    	sk_list(int f,int p) 
    		:floors(f),
    		probability(p),
    		head(new sk_list_node(INT_MIN))
    	{
    		if (p <= f) {	//概率要比楼层大,因为下面我要玩点好玩的
    			p = f + 1;
    		}
    
    		//初始化第一列
    		sk_list_node* temp = head;
    		for (int i = 0; i < f; i++) {
    			temp->set_next_floor_node(new sk_list_node(INT_MIN));
    			temp = temp->get_next_floor();
    		}
    	}
    
    
    	//寻找某节点
    	bool search_node(sk_list_node* node){
    		sk_list_node* temp = head;
    		
    		while (temp) {
    			if (temp->equal(node) == 0) {
    				return true;
    			}
    			else if (temp->equal(node) == 1) {
    				return false;
    			}
    			else {
    				if (temp->get_next() && temp->get_next()->equal(node) == 1) {
    				//如果下一节点大于当前节点,则往下
    					temp = temp->get_next_floor();	
    				}
    				//否则不论小或等都往后
    				temp = temp->get_next();
    			}
    		}
    		return false;
    	}
    
    
    	void insert_(sk_list_node* node) {
    		int floor = floors - get_probabily();
    		insert_floor(search_front(node, floor), node, floor);
    	}
    
    
    	void delete_(sk_list_node* node) {
    		sk_list_node *temp = search_front(node);
    		if (temp == nullptr) {
    			return;
    		}
    		else {
    			while (temp) {
    				if (temp->get_next()->equal(node) == 0) {
    					temp->set_next(temp->get_next()->get_next());
    					temp = temp->get_next_floor();	//删除时也要横向推进
    				}
    				temp = temp->get_next();
    			}
    		}
    	}
    
    private:
    	int get_probabily() {
    		//根据概率获取层数
    		int num = 0;
    		int p = 0;
    		srand(time(NULL));
    
    		while (p == 0 && num <= floors) {
    			p = rand() % probability;
    			--probability;	//放缓概率递减的速度
    			++num;
    		}
    
    		return num;
    	}
    
    	//寻找某节点的前驱结点
    	//供插入用
    	sk_list_node* search_front(sk_list_node* node,int floor) {
    		sk_list_node* temp = head;
    
    		while (temp) {
    			if (temp->equal(node) == 0) {	//如果就这么巧,那就不存了吧
    				return nullptr;
    			}
    			else {
    				if (temp->get_next()) {
    					if (temp->get_next()->equal(node) == 1) {
    						//如果下一节点大于当前节点,则往下
    						if (floor == 0) {	//如果楼层够了,就返回吧
    							return temp;
    						}
    						temp = temp->get_next_floor();
    						--floor;
    					}
    					temp = temp->get_next();
    				}
    				else {	//如果说当前层没有后继节点了
    					if (temp->get_next_floor() == nullptr) {	//最尾巴了
    						return temp;
    					}
    
    					temp = temp->get_next_floor();	//那就往下一层
    				}
    			}
    		}
    		return nullptr;
    	}
    	
    	//供删除用
    	sk_list_node* search_front(sk_list_node* node) {
    		sk_list_node* temp = head;
    
    		while (temp) {	
    			/*if (temp->equal(node) == 0) {	//只有一种情况,那就是头被删除,但是不可能
    				return temp;
    			}*/
    			
    			if (temp->get_next()) {
    				if (temp->get_next()->equal(node) == 1) {
    					//如果下一节点大于当前节点,则往下
    					temp = temp->get_next_floor();
    				}
    				temp = temp->get_next();
    			}
    			else if (temp->get_next()->equal(node) == 0) {
    				return temp;
    			}
    			else {	//如果说当前层没有后继节点了
    				if (temp->get_next_floor() == nullptr) {	//最尾巴了
    					return nullptr;	//查无此节点
    				}
    
    				temp = temp->get_next_floor();	//那就往下一层
    			}
    		}
    		
    		return nullptr;
    	}
    
    	//从指定节点开始插入节点
    	void insert_floor(sk_list_node* h, sk_list_node* node, int floors) {
    		
    		//如果节点已存在,就不插了
    		if (h == nullptr) {
    			return;
    		}
    
    		sk_list_node* temp_node = node;
    		int keep_floors = floors;
    
    		//先把一列弄明白吧
    		while (keep_floors) {
    			temp_node->set_next_floor_node(new sk_list_node(node));
    			temp_node = temp_node->get_next_floor();
    			--keep_floors;
    		}
    		
    		//再把每一层串上
    		//sk_list_node* temp = head;
    			
    		while (floors) {
    			if (h->get_next() != nullptr) {
    				node->set_next(h->get_next());
    			}
    			h->set_next(node);
    			h = h->get_next_floor();
    			node = node->get_next_floor();
    			--floors;
    		}
    	}
    
    	int floors;	//楼层数
    	int probability;	//上升概率
    
    	sk_list_node* head;	//左上角节点
    };
    

    大过年的,祝大家新年快乐哦!!!
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 但是跳表插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的,时间复杂度都是O(logn),而且跳表有一个特性是红黑树无法匹敌的(具体什么特性后面会提到)。所以在工业中,跳表也会经常被用到。废话不多说了,...
  • 跳表的实现插入删除搜索算法详解

    千次阅读 2016-11-10 13:51:30
    跳表久闻其名,以前写过AVL树,红黑树,都是平衡结构。但是跳表呢,它不是树形结构,它是通过链表实现的。 我们知道,在链表中查找一个元素的时间复杂度是O(n)。 在一个有序链表中,我们如果在链表中部额外增加一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,988
精华内容 2,795
关键字:

跳表插入