AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构（荣誉）实验四 Splay伸展树

2022-12-03 85
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构（荣誉）实验四 Splay伸展树

1. Splay —— Ver.I


题目描述


image.png


输入


第一行包含一个整数n，表示初始序列的长度。 以下n行每行包含一个整数，描述初始的序列。 接下来一行包含一个整数n，表示插入操作的数目。 以下m行每行描述一个操作。


接下来一行包含一个整数q，表示查询和删除操作的总数目，以下q行描述一个操作


输出


对于所有操作，输出正确的答案。


样例输入


5

1 2 3 4 5

3

ADD 9

ADD 10

ADD 199

5

QUERY 1

QUERY 3

DELETE 1

DELETE 3

QUERY 3


样例输出


the number is good

the number is good

2 3 4 5 9 10 199

2 4 5 9 10 199

the number is bad


题解

#include <iostream>
#include <string>
using namespace std;
struct Node
{
    struct Node *lchild;
    struct Node *rchild;
    struct Node *parent;
    int data;
    Node()
    {
        lchild = rchild = parent = NULL;
        data = 0;
    }
};
void Print(Node *root)
{
    if (root)
    {
        Print(root->lchild);
        if (root->data == 0)
        {
        }
        else
        {
            cout << root->data << ' ';
        }
        Print(root->rchild);
    }
}
void left_single_rotate(Node *&root, Node *&node)
{
    if (node == NULL)
    {
        return;
    }
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    parent->rchild = node->lchild;
    if (node->lchild)
    {
        node->lchild->parent = node->parent;
    }
    parent->parent = node;
    node->lchild = parent;
    node->parent = grandparent;
    if (grandparent)
    {
        if (grandparent->lchild == parent)
        {
            grandparent->lchild = node;
        }
        else
        {
            grandparent->rchild = node;
        }
    }
    else
    {
        root = node;
    }
}
void right_single_rotate(Node *&root, Node *&node)
{
    if (node == NULL)
    {
        return;
    }
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    parent->lchild = node->rchild;
    if (node->rchild)
    {
        node->rchild->parent = parent;
    }
    parent->parent = node;
    node->rchild = parent;
    node->parent = grandparent;
    if (grandparent)
    {
        if (grandparent->lchild == parent)
        {
            grandparent->lchild = node;
        }
        else
        {
            grandparent->rchild = node;
        }
    }
    else
    {
        root = node;
    }
}
void SplayUp(Node *&root, Node *&node)
{
    Node *parent = node->parent;
    Node *grandparent = parent->parent;
    if (grandparent->lchild == parent && parent->lchild == node)
    {
        right_single_rotate(root, node);
        right_single_rotate(root, node);
    }
    else if (parent->lchild != node && grandparent->lchild != parent)
    {
        left_single_rotate(root, node);
        left_single_rotate(root, node);
    }
    else if (grandparent->lchild == parent && parent->lchild != node)
    {
        left_single_rotate(root, node);
        right_single_rotate(root, node);
    }
    else if (grandparent->lchild != parent && parent->lchild == node)
    {
        right_single_rotate(root, node);
        left_single_rotate(root, node);
    }
}
void AddSplay(int x, Node *&root, Node *par)
{
    if (!root)
    {
        root = new Node;
        root->data = x;
        root->parent = par;
    }
    else if (x < root->data)
    {
        AddSplay(x, root->lchild, root);
    }
    else if (x > root->data)
    {
        AddSplay(x, root->rchild, root);
    }
}
void CreatSplay(int n, Node *&root)
{
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        AddSplay(temp, root, NULL);
    }
}
Node *FindLChild(Node *r)
{
    while (r->lchild)
    {
        r = r->lchild;
    }
    return r;
}
Node *FindSplay(int x, Node *&root)
{
    if (!root)
        return NULL;
    if (root->data < x)
        return FindSplay(x, root->rchild);
    else if (root->data > x)
        return FindSplay(x, root->lchild);
    return root;
}
void splay(Node *&root, Node *node)
{
    while (root->lchild != node && root->rchild != node && root != node)
        SplayUp(root, node);
    if (root->lchild == node)
        right_single_rotate(root, node);
    if (root->rchild == node)
        left_single_rotate(root, node);
}
void QuerySplay(int x, Node *&root)
{
    Node *node = FindSplay(x, root);
    if (node)
    {
        cout << "the number is good" << endl;
        splay(root, node);
    }
    else
        cout << "the number is bad" << endl;
}
bool isDel(int x, Node *&root)
{
    Node *node = FindSplay(x, root);
    if (!node)
    {
        return false;
    }
    splay(root, node);
    if (!node->rchild)
    {
        Node *tmp = root;
        root = root->lchild;
        return true;
    }
    Node *min = FindLChild(node->rchild);
    node->data = min->data;
    if (min->parent->lchild == min)
    {
        min->parent->lchild = min->rchild;
    }
    else
    {
        min->parent->rchild = min->rchild;
    }
    return true;
}
void Delete(int x, Node *&root)
{
    if (isDel(x, root))
    {
        Print(root);
        cout << endl;
    }
    else
        cout << "Failed" << endl;
}
int main()
{
    Node *splayRoot = new Node;
    int n, temp;
    cin >> n;
    CreatSplay(n, splayRoot);
    cin >> temp;
    for (int i = 0; i < temp; i++)
    {
        string ope;
        int index;
        cin >> ope >> index;
        AddSplay(index, splayRoot, NULL);
    }
    cin >> temp;
    for (int i = 0; i < temp; i++)
    {
        string ope;
        int index;
        cin >> ope >> index;
        if (ope == "QUERY")
        {
            QuerySplay(index, splayRoot);
        }
        else if (ope == "DELETE")
        {
            Delete(index, splayRoot);
        }
    }
    return 0;
}

2. 宠物收养所(Splay —— 前驱后继操作)


题目描述


最近，贝贝开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，贝贝根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。


这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。


1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。


2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。


【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。


输入


第一行为一个正整数n，n<=80000，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个）


输出


仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。


样例输入


5

0 2

0 4

1 3

1 2

1 5


样例输出

3


题解

#include <iostream>
#define MAXLEN 80002
using namespace std;
int ans, n;
struct splaytree
{
    int a[MAXLEN], l[MAXLEN], r[MAXLEN];
    int t, tot;
    void zig(int &x)
    {
        int lc = l[x];
        l[x] = r[lc];
        r[lc] = x;
        x = lc;
    }
    void zag(int &x)
    {
        int rc = r[x];
        r[x] = l[rc];
        l[rc] = x;
        x = rc;
    }
    void splay(int &t, int x)
    {
        if (!t)
            return;
        int pl = 0, pr = 0;
        for (;;)
        {
            if (x == a[t])
                break;
            if (x < a[t] && !l[t])
                break;
            if (x > a[t] && !r[t])
                break;
            if (x < a[t])
            {
                if (x < a[l[t]] && l[l[t]])
                    zig(t);
                l[pr] = t, pr = t, t = l[t];
            }
            else
            {
                if (x > a[r[t]] && r[r[t]])
                    zag(t);
                r[pl] = t, pl = t, t = r[t];
            }
        }
        l[pr] = r[t];
        r[pl] = l[t];
        l[t] = r[0];
        r[t] = l[0];
        l[0] = r[0] = 0;
    }
    void insert(const int &x)
    {
        a[++tot] = x;
        if (!t)
        {
            t = tot;
            return;
        }
        splay(t, x);
        if (x < a[t])
        {
            l[tot] = l[t];
            l[t] = tot;
        }
        else
        {
            r[tot] = r[t];
            r[t] = tot;
        }
    }
    void suit(const int &x)
    {
        if (!t)
            return;
        splay(t, x);
        splay(l[t], a[t]);
        splay(r[t], a[t]);
        int pl = abs(a[l[t]] - x), pm = abs(a[t] - x), pr = abs(a[r[t]] - x);
        if (x < a[t] && pl <= pm && l[t])
        {
            ans += pl;
            ans %= 1000000;
            l[t] = l[l[t]];
        }
        else if (x > a[t] && pr < pm && r[t])
        {
            ans += pr;
            ans %= 1000000;
            r[t] = r[r[t]];
        }
        else
        {
            ans += pm;
            ans %= 1000000;
            if (l[t])
            {
                r[l[t]] = r[t];
                t = l[t];
            }
            else if (r[t])
            {
                l[r[t]] = l[t];
                t = r[t];
            }
            else
                t = 0;
        }
    }
} SP[2];
int main()
{
    int x, y;
    cin >> n;
    while (n--)
    {
        cin >> x >> y;
        if (SP[x].t)
        {
            SP[x].suit(y);
        }
        else
        {
            SP[!x].insert(y);
        }
    }
    cout << ans << endl;
    return 0;
}
关键词：
数据结构树
数据结构实验
数据结构荣誉树
wstqfqdpnmll4
目录
相关文章
XIAZHI
|
29天前
|
存储 算法 编译器
数据结构实验之矩阵的运算器（二维数组）
本实验旨在通过团队合作，掌握数组和矩阵相关运算的代码实现，包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中，成员们需分工协作，解决编程难题，最终实现一个功能完备的矩阵计算器。通过本实验，不仅锻炼了编程能力，还加深了对数学概念的理解，同时培养了团队合作精神。
XIAZHI
56 4
XIAZHI
|
29天前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术，通过创建文本文件、实现单词计数与定位功能，最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单，以增强对字符串处理的理解与应用能力。
XIAZHI
44 4
XIAZHI
|
29天前
|
算法
数据结构实验之最长公共子序列
本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法，以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出，`memset()`函数用于内存初始化，且对于特定输入，程序能正确输出最长公共子序列之一。
XIAZHI
51 4
XIAZHI
|
29天前
|
算法
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题，掌握队列的基本操作如入队、出队等，利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能，并通过菜单式界面进行交互。实验结果显示基本功能可正常执行，但在连续操作时存在执行失败的情况，需进一步优化。
XIAZHI
41 4
XIAZHI
|
29天前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
53 4
XIAZHI
|
29天前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索（DFS）算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历，按预序（根、左、右）输出节点值。接着，通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表，展示了如何将树结构转换为线性结构。最后，讨论了此算法的优点，如实现简单和内存效率高，同时也指出了潜在的内存管理问题，并分析了算法的时间复杂度。
XIAZHI
49 0
龙大吉
|
22天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
43 5
XIAZHI
|
29天前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
81 4
XIAZHI
|
29天前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念，并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素，以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用，还涉及到了算法逻辑的设计与优化。实验结果显示，学生能够有效掌握并运用这些知识完成指定任务。
XIAZHI
51 4
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
75 16