什么是跳表？ 想要弄清这个，可以查看一篇大佬的文章，把跳表分析的非常透彻，并且剖析了Redis源码，我这里只讲解不带span的Redis源码C++复现。（后续会有带span的完美Redis源码C++复刻） 大佬的讲解 如果想查看Redis源码的各位，可以点进这个链接https://github1s.com/redis/redis/blob/unstable/src/t_zset.c skiplist图片正式实现跳表的创建Redis实现 跳表结构：sds类型是Redis内部实现的字符串 创建函数，这时前面定义的level[]类型的优势就体现出来了，在C中这个类型算是未完成的类型，所以需要根据你给它分配的内存来进行具体的使用，没有分配内存前，你可以sizeof(zskiplistNode);试一试，你会发现level不计内存！ 销毁函数 cpp实现struct SkiplistNode { // string ele; 此题不需要维护元素字段，所以舍去 double score; SkiplistNode *backward; struct SkiplistLevel { struct SkiplistNode *forward; // unsigned long span;此题不需要维护跨度，所以省去 }* level; //TODO 构造和析构 SkiplistNode(int level,double score):level(new SkiplistLevel[level]) ,score(score),backward(nullptr){} ~SkiplistNode(){ delete[] level; } }; class Skiplist { struct SkiplistNode *header, *tail; unsigned long length; //当前跳表中的元素个数 int level; //当前跳表中最大表的高度 public: /** * 构造函数和析构函数 */ Skiplist():level(1),length(0),tail(nullptr){ header = new SkiplistNode(Skiplist_MAXLEVEL,0); for (int j = 0; j < Skiplist_MAXLEVEL; j++) { header->level[j].forward = nullptr; } header->backward = nullptr; } ~Skiplist(){ SkiplistNode* node = header, *next; while(node) { next = node->level[0].forward; delete node; node = next; } } }; Insert插入元素Redis实现 cpp实现 带span和ele的1:1还原 SkiplistNode* Skiplist::Insert(double score,const string& ele){ SkiplistNode *update[Skiplist_MAXLEVEL], *x; unsigned int rank[Skiplist_MAXLEVEL]; int i,level; //TODO part1：找到需要插入位置的前一个跳表节点，顺便更新update数组（存储着经过路径中的每个层级最多走到了哪个节点(用于连接新节点的每个层级的forward和更新span)）和rank数组（存储着路径中经过的层级节点到header的长度） x = header; for (i = this->level-1; i >= 0; i--) { rank[i] = i == (this->level-1) ? 0 : rank[i+1]; cout<<rank[i]<<endl; while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && x->level[i].forward->ele<ele))) { rank[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; } //TODO 生成节点内存，如果随机生成的节点拥有的层级比当前最高的节点还高，则需要把update数组和rank数组中高于当前level的部分看作是前一个节点是header来更新 level = RandomLevel(); if (level > this->level) {…