郁闷的出纳员伸展树 C语言

广工《算法和高级数据结构教程课程设计》 郁闷的出纳员（伸展树）C语言实现

#include 
#include 
#include 

#define maxn 100005
#define nil 0
#define oo 1000000000

int n minp root tot w;
int d[maxn] son[maxn][2] fa[maxn] s[maxn];
inline void update（int rot）
{
    s[rot] = s[son[rot][0]] + s[son[rot][1]] + 1;
}
void rotate（int x int w）
{
    int y = fa[x];
    son[y][w ^ 1] = son[x][w];
    if（son[x][w] != nil） fa[son[x][w]] = y;
    fa[x] = fa[y];
    if（fa[y] != nil）
    {
        if（y == son[fa[y]][0]） son[fa[y]][0] = x;
        else son[fa[y]][1] = x;
    }
    son[x][w] = y; fa[y] = x;
    update（y）; update（x）;
}
void splay（int x int poi）
{
    if（x == nil） return;
    while（fa[x] != poi）
    {
        if（fa[fa[x]] == poi）
        {
            if（x == son[fa[x]][0]） rotate（x 1）;
            else rotate（x 0）;
        }
        else
        {
            if（fa[x] == son[fa[fa[x]]][0]）
            {
                if（x == son[fa[x]][0]）
                {
                    rotate（fa[x] 1）; rotate（x 1）;
                }
                else
                {
                    rotate（x 0）; rotate（x 1）;
                }
            }
            else
            {
                if（x == son[fa[x]][0]）
                {
                    rotate（x 1）; rotate（x 0）;
                }
                else
                {
                    rotate（fa[x] 0）; rotate（x 0）;
                }
            }
        }
    }
    if（poi == nil） root = x;
}
void insert（int rot int x）
{
    ++s[rot];
    if（d[rot] <= x）
    {
        if（son[rot][1] == nil）
        {
            d[++tot] = x;
            s[tot] = 1;
            fa[tot] = rot;
            son[rot][1] = tot;
            son[tot][0] = son[tot][1] = nil;
            splay（rot nil）;
        }
        else
        {
            insert（son[rot][1] x）;
        }
    }
    else
    {
        if（son[rot][0] == nil）
        {
            d[++tot] = x;
            s[tot] = 1;
            fa[tot] = rot;
            son[rot][0] = tot;
            son[tot][0] = son[tot][1] = nil;
            splay（rot nil）;
        }
        else
        {
            insert（son[rot][0] x）;
        }
    }
}
int succ（int rot int k）
{
    if（rot == nil） return nil;
    if（d[rot] >= k）
    {
        int t = succ（son[rot][0] k）;
        if（t == nil） return rot;
        else return t;
    }
    else
    {
        return succ（son[rot][1] k）;
    }
}
int select（int rot int k）
{
    if（rot == nil || k < 0） return -1;
    if（s[son[rot][1]] + 1 == k） return d[rot] + w;
    if（s[son[rot][1]] >= k） return select（son[rot][1] k）;
    return select（son[rot][0] k - s[son[rot][1]] - 1）;
}
int main（）
{
    char opt;
    int k sum = 0;
    printf（“请输入下面命令条数和工资下界：“）;
    scanf（“%d%d“ &n &minp）;
    d[root = ++tot] = （oo << 1）;
    s[tot] = 1;
    fa[tot] = son[tot][0] = son[tot][1] = nil;
    while（n--）
    {
        pri

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-01-02 03:56  cashier\
     目录           0  2017-12-27 21:23  cashier\bin\
     目录           0  2018-01-02 03:49  cashier\bin\Debug\
     文件       33435  2018-01-02 03:49  cashier\bin\Debug\cashier.exe
     文件        1110  2017-12-27 21:23  cashier\cashier.cbp
     文件         141  2018-01-02 03:07  cashier\cashier.depend
     文件         359  2018-01-02 03:56  cashier\cashier.layout
     文件        3891  2018-01-02 03:30  cashier\main.c
     目录           0  2017-12-27 21:23  cashier\obj\
     目录           0  2018-01-02 03:49  cashier\obj\Debug\
     文件        7681  2018-01-02 03:49  cashier\obj\Debug\main.o