c++实现skipList「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

    Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

    跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，跳跃表使用概率均衡技术而不是使用强制性均衡，因此，对于插入和删除结点比传统上的平衡树算法更为简洁高效。

一个跳表具有以下特征：
1.一个跳表应该有几个层（level）组成；
2.跳表的第一层包含所有的元素；
3.每一层都是一个有序的链表；
4.如果元素x出现在第i层，则所有比i小的层都包含x；
5.第i层的元素通过一个down指针指向下一层拥有相同值的元素；
6.Top指针指向最高层的第一个元素。

 下面来研究一下跳表的核心思想: 先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。

    如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。

    如上图所示，是一个即为简单的跳跃表。传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要O(n)的时间，查找操作需要O(n)的时间。如果我们使用上图的跳跃表，就可以减少查找所需时间为O(n/2)，因为我们可以先通过每个节点的最上面的指针先进行查找，这样子就能跳过一半的节点。比如我们想查找19，首先和6比较，大于6之后，在和9进行比较，然后在和12进行比较……最后比较到21的时候，发现21大于19，说明查找的点在17和21之间，从这个过程中，我们可以看出，查找的时候跳过了3、7、12等点，因此查找的复杂度为O(n/2)。

   当然上面只是最简单的就是跳跃表，真正的跳表每一个结点不单单只包含指向下一个结点的指针，可能包含很多个指向后续结点的指针，这样就可以跳过一些不必要的结点，从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针，这个过程是通过一个随机函数生成器得到，就是通过随机生成一个结点中指向后续结点的指针数目。

通过上面的跳表的很容易设计这样的数据结构：
定义每个节点类型：
typedef struct nodeStructure *node;
typedef struct nodeStructure
{

    keyType key; // key值
    valueType value; // value值
    // 向前指针数组，根据该节点层数的
    // 不同指向不同大小的数组
    node forward[1];
};

上面的每个结构体对应着图中的每个节点，如果一个节点是一层的节点的话（如7，12等节点），那么对应的forward将指向一个只含一个元素的数组，以此类推。
先不看代码先用图来描述一下Skip List构造，插入和删除的过程：

构造Skip List
1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。

插入过程

例子：插入 119， level = 2

如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4

删除 21

看到这就很清楚了，上面已经提到所谓的Skip List是每层从它的下一层按照某种规律抽出一些元素，它的操作也很简单，它的操作其实按层来操作链表，基本上是从上往下来操作。

具体的实现如下：

定义数据结构

using namespace std;

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */


template <typename SCORE_TYPE,typename MEMBER_TYPE>
struct skiplistNode
{
    skiplistNode(int level)
    {
        this->level = level;
        this->levels = new zskiplistLevel[level];
        for (int i = 0;i < level;i++)
        {
            this->levels[i].forward = NULL;
        }
    }

    ~skiplistNode()
    {
        if (levels) delete[] levels;
        levels = NULL;
    }
    SCORE_TYPE score;  //排序key，必须是一个可以比较的类型，必须实现对象的比较操作符(一般位数值类型(long,int,double等))
    MEMBER_TYPE ele;  //分数对应的对象信息,必须是一个可以比较的类型，必须实现对象的比较操作符
    //每层的节点信息
    struct zskiplistLevel
    {
        skiplistNode<SCORE_TYPE,MEMBER_TYPE> *forward;  //当前层当前节点下一个节点
    };
    int level;
    zskiplistLevel *levels;
};

template <typename SCORE_TYPE,typename MEMBER_TYPE>
struct skiplist
{
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *header, *tail; //header和tail分别指向头结点和尾结点，
    unsigned long length; //结点数量，
    int level; //level为表中结点的最高等级。
};

相关操作api

//
//  Created by dguco on 20-1-9.
//

#ifndef SERVER_SKIP_LIST_H
#define SERVER_SKIP_LIST_H

using namespace std;

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */


template <typename SCORE_TYPE,typename MEMBER_TYPE>
struct skiplistNode
{
    skiplistNode(int level)
    {
        this->level = level;
        this->levels = new zskiplistLevel[level];
        for (int i = 0;i < level;i++)
        {
            this->levels[i].forward = NULL;
        }
    }

    ~skiplistNode()
    {
        if (levels) delete[] levels;
        levels = NULL;
    }

    bool operator==(const skiplistNode& other)
    {
        return  other.score = this->score && other.ele == this->ele;
    }

    SCORE_TYPE score;  //排序key，必须是一个可以比较的类型，必须实现对象的比较操作符(一般位数值类型(long,int,double等))
    MEMBER_TYPE ele;  //分数对应的对象信息,必须是一个可以比较的类型，必须实现对象的比较操作符
    //每层的节点信息
    struct zskiplistLevel
    {
        skiplistNode<SCORE_TYPE,MEMBER_TYPE> *forward;  //当前层当前节点下一个节点
    };
    int level;
    zskiplistLevel *levels;
};

template <typename SCORE_TYPE,typename MEMBER_TYPE>
struct skiplist
{
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *header, *tail; //header和tail分别指向头结点和尾结点，
    unsigned long length; //结点数量，
    int level; //level为表中结点的最高等级。
};

template <typename SCORE_TYPE,typename MEMBER_TYPE>
class CSkipList
{
public:
    /**
     * 注意初始化的时候调表的头部指针已经存在但是长度为0
     */
    CSkipList()
    {
        mskiplist.level = 1;
        mskiplist.length = 0;
        mskiplist.header = new skiplistNode<SCORE_TYPE,MEMBER_TYPE>(ZSKIPLIST_MAXLEVEL);
        mskiplist.tail = NULL;
    }

    ~CSkipList()
    {
        skiplistNode<SCORE_TYPE,MEMBER_TYPE> *node = mskiplist.header->levels[0].forward, *next;
        delete mskiplist.header;
        while(node) {
            next = node->levels[0].forward;
            delete node;
            node = next;
        }
    }

    skiplist<SCORE_TYPE, MEMBER_TYPE> &GetMskiplist()
    {
        return mskiplist;
    }

    /**
     * 插入一个新的节点如果ele已存在，则更新积分
     * @param zsl
     * @param score
     * @param ele
     * @return 插入的skiplistNode
     */
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *Insert(SCORE_TYPE score, MEMBER_TYPE ele);
    /**
     * 删除一个节点
     * @param score
     * @param ele
     * @return 1 ok 0 not found
     */
    int DeleteNode(SCORE_TYPE score);
    /**
     *
     * @param newscore
     * @return
     */

    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *GetNode(SCORE_TYPE curscore);
private:
    /**
     * 创建一个节点
     * @param level
     * @param score
     * @param value
     * @return
     */
    skiplistNode<SCORE_TYPE,MEMBER_TYPE>* CreateSkipListNode(int level,SCORE_TYPE score,MEMBER_TYPE value);

    //随机跳表的层数
    int RandomLevel(void)
    {
        int level = 1;
        while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
            level += 1;
        return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
    }
private:
    skiplist<SCORE_TYPE,MEMBER_TYPE> mskiplist;
};

template <typename SCORE_TYPE,typename MEMBER_TYPE>
skiplistNode<SCORE_TYPE,MEMBER_TYPE> *CSkipList<SCORE_TYPE,MEMBER_TYPE>::Insert(SCORE_TYPE score, MEMBER_TYPE ele)
{
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *update[ZSKIPLIST_MAXLEVEL] = {0}; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *tmpNode;
    int i, level;

    tmpNode = mskiplist.header;
    for (i = mskiplist.level-1; i >= 0; i--)
    {
        //不可能出现这种情况，如果出现则说明调表结构已经被破坏,排行榜已经乱了
        if (!(i < tmpNode->level))
        {
            printf("The data of skiplist is bad\n");
            return NULL;
        }
        //如果当前节点的下一个节点is not null，且他的下一个节点的score小于插入节点的score，或者他们积分相等但是ele小于插入节点的ele，则继续往后找，直到
        //找到条件不满足的跳出循环，则新插入的节点需要插入该层的当前节点后面，把此节点记录到update数组中
        while (tmpNode->levels[i].forward &&
               (tmpNode->levels[i].forward->score < score))
        {
            tmpNode = tmpNode->levels[i].forward;
        }
        update[i] = tmpNode;
    }

    //随机层数
    level = RandomLevel();
    //如果随机的层数比当前skiplist的层数要大，则补充高出的层的每层update节点信息
    if (level > mskiplist.level)
    {
        for (i = mskiplist.level; i < level; i++)
        {
            update[i] = mskiplist.header; //当前节点初始化为header
        }
        mskiplist.level = level;  //更新skiplist的层数
    }

    //创建节点
    tmpNode = CreateSkipListNode(level,score,ele);
    for (i = 0; i < level; i++)
    {
        //修改创建节点tmpNode,需要修改的节点的forward指针(从每层来看上是一个链表的插入操作即把tmpNode插入到update[i]后面)
        tmpNode->levels[i].forward = update[i]->levels[i].forward;
        update[i]->levels[i].forward = tmpNode;
    }

    if (tmpNode->levels[0].forward == NULL)
    {
        mskiplist.tail = tmpNode;
    }
    mskiplist.length++;
    return tmpNode;
}

template <typename SCORE_TYPE,typename MEMBER_TYPE>
int CSkipList<SCORE_TYPE,MEMBER_TYPE>::DeleteNode(SCORE_TYPE score) {
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *update[ZSKIPLIST_MAXLEVEL] = {0}; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> * tmpNode;
    int i;

    tmpNode = mskiplist.header;
    for (i = mskiplist.level-1; i >= 0; i--)
    {
        //不可能出现这种情况，如果出现则说明调表结构已经被破坏,排行榜已经乱了
        if (!(i < tmpNode->level))
        {
            printf("The data of skiplist is bad\n");
            return 0;
        }
        //如果当前节点的下一个节点is not null，且他的下一个节点的score小于插入节点的score，或者他们积分相等但是ele小于插入节点的ele，则继续往后找，直到
        //找到条件不满足的跳出循环，则每层要删除的节点的前一个节点都存在update数组中
        while (tmpNode->levels[i].forward && tmpNode->levels[i].forward->score < score)
        {
            tmpNode = tmpNode->levels[i].forward;
        }
        update[i] = tmpNode;
    }

    tmpNode = tmpNode->levels[0].forward;
    if(tmpNode != NULL && tmpNode->score == score)
    {
        //逐层删除，和普通列表删除一样
        for(int i = 0; i < mskiplist.level; i++)
        {
            if(update[i]->levels[i].forward == tmpNode)
            {
                update[i]->levels[i].forward = tmpNode->levels[i].forward;
            }
        }
        delete tmpNode;
        //如果删除的是最大层的节点，那么需要重新维护跳表的
        for(int i = mskiplist.level-1; i >= 0; i--)
        {
            if(mskiplist.header->levels[i].forward == NULL)
            {
                mskiplist.level--;
            }
        }
        mskiplist.length--;
        return true;
    }

    return false; /* not found */
}


template <typename SCORE_TYPE,typename MEMBER_TYPE>
skiplistNode<SCORE_TYPE,MEMBER_TYPE> *CSkipList<SCORE_TYPE,MEMBER_TYPE>::GetNode(SCORE_TYPE curscore) {
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *update[ZSKIPLIST_MAXLEVEL] = {0}; //每一层需要修改的结点,在每层中，新的节点需要插入在该节点的后面
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> * tmpNode;
    int i;

    tmpNode = mskiplist.header;
    for (i = mskiplist.level-1; i >= 0; i--) {
        //不可能出现这种情况，如果出现则说明调表结构已经被破坏,排行榜已经乱了
        if (!(i < tmpNode->level))
        {
            printf("The data of skiplist is bad\n");
            return NULL;
        }
        //如果当前节点的下一个节点is not null，且他的下一个节点的score小于插入节点的score，或者他们积分相等但是ele小于插入节点的ele，则继续往后找，直到
        //找到条件不满足的跳出循环，则每层要update的节点的前一个节点都存在update数组中
        while (tmpNode->levels[i].forward && tmpNode->levels[i].forward->score < curscore)
        {
            tmpNode = tmpNode->levels[i].forward;
        }
        update[i] = tmpNode;
    }

    tmpNode = tmpNode->levels[0].forward;
    return tmpNode;
}


template <typename SCORE_TYPE,typename MEMBER_TYPE>
skiplistNode<SCORE_TYPE,MEMBER_TYPE>* CSkipList<SCORE_TYPE,MEMBER_TYPE>::CreateSkipListNode(int level,SCORE_TYPE score,MEMBER_TYPE value)
{
    skiplistNode<SCORE_TYPE,MEMBER_TYPE> *zn = new skiplistNode<SCORE_TYPE,MEMBER_TYPE>(level);
    zn->score = score;
    zn->ele = value;
    return zn;
}
#endif //SERVER_SKIP_LIST_H

测试

//
// Created by dguco on 20-1-11.
//

#include <map>
#include "rankskip_list.h"

#define  MAX_RANK 100

class Score
{
public:
    Score()
    {
        id = -1;
        chinese = 0;
        math = 0;
        english = 0;
    }
    Score(int id,int chinese, int math, int english)
        : id (id),chinese(chinese), math(math), english(english)
    {

    }
    int Sum()
    {
        return chinese + math + english;
    }

    bool operator==(const Score& d)
    {
        return this->id == d.id && this->chinese == d.chinese &&
            this->math == d.math && this->english == d.english;
    }

    bool operator !=(const Score& d)
    {
        return !(*this == d);
    }

    bool operator > (const Score& d)
    {
        int sumMe = chinese + math + english;
        int sumHe = d.chinese + d.math + d.english;
        if (sumMe > sumHe)
        {
            return true;
        }
        else if (sumMe == sumHe)
        {
            if (this->chinese > d.chinese)
            {
                return true;
            }
            else if (this->chinese == d.chinese)
            {
                if (this->math > d.math)
                {
                    return true;
                }
                else if (this->math == d.math)
                {
                    if (this->english > d.english)
                    {
                        return true;
                    }
                    else if (this->english == d.english)
                    {
                        return id > d.id;
                    } else{
                        return false;
                    }
                } else{
                    return false;
                }
            } else{
                return false;
            }
        } else{
            return false;
        }
    }

    bool operator < (const Score& d)
    {
        if (*this == d)
            return false;
        return !(*this > d);
    }

    int getId() const
    {
        return id;
    }
    int getChinese() const
    {
        return chinese;
    }
    int getMath() const
    {
        return math;
    }

    int getEnglish() const
    {
        return english;
    }

private:
    int id;
    int chinese;
    int math;
    int english;
};

int main()
{
    std::map<int,Score> tmpMap;
    std::map<int,bool> res;
    CSkipList<Score,int>* rankSkipList = new CSkipList<Score,int>();
    for (int i = 1;i <= 100;i++)
    {
        Score score = Score(i, std::rand() % 100 + 1, std::rand() % 100 + 1, std::rand() % 100 + 1);
        rankSkipList->Insert(score, i);
        tmpMap[i] = score;
    }
    rankSkipList->Insert(Score(101, 0, 0, 1), 101);
    rankSkipList->Insert(Score(102, 100, 100, 100), 102);
    for (int i = 1;i <= 10;i++)
    {
        int index = 20 + i * 5;
        auto itScore = tmpMap.find(index);
        if (itScore != tmpMap.end())
        {
            rankSkipList->DeleteNode(itScore->second);
        }
        res[index] = true;
    }

    int i = 1;
    skiplistNode<Score,int>* node = rankSkipList->GetMskiplist().header->levels[0].forward;
    do{
        if (node != NULL)
        {
            Score score = node->score;
            if (res.find(score.getId()) != res.end())
            {
                printf("rank error id = %d \n",score.getId());
            }
            printf("rank = %d id = %d,sum = %d,chinese = %d,math = %d,english = %d\n",
                   i,score.getId(),score.Sum(), score.getChinese(),score.getMath(),score.getEnglish());
            res[score.getId()] = true;
            i++;
            node = node->levels[0].forward;
        }
    }while (node != NULL);

    delete  rankSkipList;
    return  0;
}

输出

rank = 1 id = 101,sum = 1,chinese = 0,math = 0,english = 1
rank = 2 id = 78,sum = 57,chinese = 12,math = 40,english = 5
rank = 3 id = 79,sum = 63,chinese = 28,math = 29,english = 6
rank = 4 id = 36,sum = 66,chinese = 41,math = 16,english = 9
rank = 5 id = 99,sum = 78,chinese = 47,math = 1,english = 30
rank = 6 id = 91,sum = 81,chinese = 62,math = 14,english = 5
rank = 7 id = 47,sum = 85,chinese = 12,math = 44,english = 29
rank = 8 id = 8,sum = 85,chinese = 59,math = 23,english = 3
rank = 9 id = 76,sum = 89,chinese = 73,math = 14,english = 2
rank = 10 id = 16,sum = 90,chinese = 47,math = 6,english = 37
rank = 11 id = 73,sum = 91,chinese = 46,math = 8,english = 37
rank = 12 id = 63,sum = 92,chinese = 17,math = 9,english = 66
rank = 13 id = 93,sum = 95,chinese = 85,math = 7,english = 3
rank = 14 id = 17,sum = 97,chinese = 25,math = 58,english = 14
rank = 15 id = 12,sum = 101,chinese = 14,math = 71,english = 16
rank = 16 id = 26,sum = 103,chinese = 3,math = 98,english = 2
rank = 17 id = 46,sum = 104,chinese = 36,math = 38,english = 30
rank = 18 id = 41,sum = 105,chinese = 15,math = 25,english = 65
rank = 19 id = 62,sum = 109,chinese = 27,math = 45,english = 37
rank = 20 id = 57,sum = 110,chinese = 49,math = 5,english = 56
rank = 21 id = 48,sum = 112,chinese = 5,math = 77,english = 30
rank = 22 id = 86,sum = 112,chinese = 20,math = 82,english = 10
rank = 23 id = 96,sum = 112,chinese = 49,math = 54,english = 9
rank = 24 id = 61,sum = 116,chinese = 6,math = 79,english = 31
rank = 25 id = 49,sum = 117,chinese = 39,math = 14,english = 64
rank = 26 id = 97,sum = 117,chinese = 49,math = 34,english = 34
rank = 27 id = 15,sum = 117,chinese = 85,math = 26,english = 6
rank = 28 id = 44,sum = 119,chinese = 29,math = 38,english = 52
rank = 29 id = 38,sum = 121,chinese = 22,math = 52,english = 47
rank = 30 id = 23,sum = 122,chinese = 13,math = 40,english = 69
rank = 31 id = 90,sum = 122,chinese = 22,math = 6,english = 94
rank = 32 id = 10,sum = 126,chinese = 22,math = 74,english = 30
rank = 33 id = 64,sum = 126,chinese = 63,math = 38,english = 25
rank = 34 id = 7,sum = 128,chinese = 36,math = 68,english = 24
rank = 35 id = 34,sum = 129,chinese = 25,math = 20,english = 84
rank = 36 id = 18,sum = 129,chinese = 68,math = 15,english = 46
rank = 37 id = 92,sum = 132,chinese = 45,math = 60,english = 27
rank = 38 id = 59,sum = 133,chinese = 23,math = 41,english = 69
rank = 39 id = 3,sum = 135,chinese = 63,math = 22,english = 50
rank = 40 id = 37,sum = 140,chinese = 19,math = 24,english = 97
rank = 41 id = 94,sum = 141,chinese = 29,math = 69,english = 43
rank = 42 id = 21,sum = 141,chinese = 52,math = 4,english = 85
rank = 43 id = 5,sum = 141,chinese = 73,math = 27,english = 41
rank = 44 id = 54,sum = 142,chinese = 6,math = 91,english = 45
rank = 45 id = 75,sum = 142,chinese = 88,math = 43,english = 11
rank = 46 id = 32,sum = 153,chinese = 57,math = 68,english = 28
rank = 47 id = 29,sum = 155,chinese = 20,math = 45,english = 90
rank = 48 id = 19,sum = 160,chinese = 51,math = 44,english = 65
rank = 49 id = 43,sum = 163,chinese = 37,math = 60,english = 66
rank = 50 id = 83,sum = 163,chinese = 86,math = 26,english = 51
rank = 51 id = 80,sum = 165,chinese = 21,math = 59,english = 85
rank = 52 id = 20,sum = 165,chinese = 79,math = 77,english = 9
rank = 53 id = 52,sum = 166,chinese = 44,math = 25,english = 97
rank = 54 id = 95,sum = 167,chinese = 99,math = 59,english = 9
rank = 55 id = 98,sum = 170,chinese = 47,math = 68,english = 55
rank = 56 id = 58,sum = 173,chinese = 44,math = 100,english = 29
rank = 57 id = 77,sum = 176,chinese = 100,math = 20,english = 56
rank = 58 id = 51,sum = 177,chinese = 18,math = 70,english = 89
rank = 59 id = 6,sum = 181,chinese = 83,math = 30,english = 68
rank = 60 id = 39,sum = 183,chinese = 29,math = 65,english = 89
rank = 61 id = 84,sum = 183,chinese = 99,math = 43,english = 41
rank = 62 id = 89,sum = 184,chinese = 80,math = 43,english = 61
rank = 63 id = 87,sum = 184,chinese = 95,math = 56,english = 33
rank = 64 id = 74,sum = 187,chinese = 88,math = 19,english = 80
rank = 65 id = 67,sum = 188,chinese = 82,math = 32,english = 74
rank = 66 id = 68,sum = 190,chinese = 61,math = 95,english = 34
rank = 67 id = 71,sum = 190,chinese = 67,math = 27,english = 96
rank = 68 id = 42,sum = 193,chinese = 92,math = 44,english = 57
rank = 69 id = 22,sum = 194,chinese = 61,math = 33,english = 100
rank = 70 id = 66,sum = 200,chinese = 69,math = 51,english = 80
rank = 71 id = 27,sum = 203,chinese = 57,math = 53,english = 93
rank = 72 id = 56,sum = 206,chinese = 98,math = 65,english = 43
rank = 73 id = 33,sum = 207,chinese = 66,math = 87,english = 54
rank = 74 id = 28,sum = 210,chinese = 42,math = 87,english = 81
rank = 75 id = 85,sum = 215,chinese = 25,math = 91,english = 99
rank = 76 id = 4,sum = 215,chinese = 64,math = 60,english = 91
rank = 77 id = 72,sum = 217,chinese = 85,math = 91,english = 41
rank = 78 id = 2,sum = 217,chinese = 87,math = 36,english = 94
rank = 79 id = 9,sum = 219,chinese = 57,math = 94,english = 68
rank = 80 id = 24,sum = 222,chinese = 40,math = 95,english = 87
rank = 81 id = 11,sum = 222,chinese = 99,math = 38,english = 85
rank = 82 id = 88,sum = 224,chinese = 74,math = 70,english = 80
rank = 83 id = 13,sum = 230,chinese = 57,math = 81,english = 92
rank = 84 id = 31,sum = 230,chinese = 76,math = 82,english = 72
rank = 85 id = 14,sum = 231,chinese = 97,math = 71,english = 63
rank = 86 id = 100,sum = 239,chinese = 91,math = 50,english = 98
rank = 87 id = 1,sum = 249,chinese = 78,math = 87,english = 84
rank = 88 id = 81,sum = 249,chinese = 82,math = 97,english = 70
rank = 89 id = 82,sum = 251,chinese = 73,math = 93,english = 85
rank = 90 id = 53,sum = 264,chinese = 73,math = 100,english = 91
rank = 91 id = 69,sum = 279,chinese = 97,math = 100,english = 82
rank = 92 id = 102,sum = 300,chinese = 100,math = 100,english = 100