蒟蒻求助,RE
查看原帖
蒟蒻求助,RE
132907
CUFT楼主2020/10/29 11:05

代码在本地跑能把数据正确输出,但最后会显示程序停止运行(return value 255)。

如果把析构函数注释掉的话能在本地正常运行(return value 0),但交上来会RE。 代码如下:

#include <cstdio>
#include <iostream>
using namespace std;

template <typename Type>
class BST {
private:
    //默认值
    Type DefaultValue;
    //节点
    struct Node {
        //数据
        Type Value;
        //同样的数据有多少个
        int Number;
        //该节点的左右分别各有多少个数据,注意不是节点的个数
        int LeftNumber, RightNumber;
        //左右孩子
        struct Node *LeftChild, *RightChild;
        //Node的构造函数
        Node(Type value) {
            this->Value      = value;
            this->Number     = 1;
            this->LeftNumber = this->RightNumber = 0;
            this->LeftChild = this->RightChild = NULL;
        }
    } * root;

    //递归删除节点以及它的两个子节点
    void del(struct Node* node) {
        if (node != NULL) {
            del(node->LeftChild);
            del(node->RightChild);
            delete node;
            node=NULL;
        }
    }

public:
    //构造函数
    BST(Type defaultValue);
    //析构函数
    ~BST(void);
    //插入数据
    void insert(Type data);
    //获取数据的排位
    int getTurn(Type data);
    //获取排位的数据
    Type getValue(int turn);
    //获取数据的前一个数据
    Type getFront(Type data);
    //获取数据的后一个数据
    Type getBack(Type data);
};

template <typename Type>
BST<Type>::BST(Type defaultValue) {
    root         = NULL;
    DefaultValue = defaultValue;
}

template <typename Type>
BST<Type>::~BST(void) {
    del(root);
}

template <typename Type>
void BST<Type>::insert(Type data) {
    if (root == NULL) {
        root = new struct Node(data);
        return;
    }
    struct Node* node = root;
    while (!(node->Value == data)) {
        if (data < node->Value) {
            node->LeftNumber++;
            if (node->LeftChild == NULL) {
                node->LeftChild = new struct Node(data);
                return;
            } else {
                node = node->LeftChild;
            }
        } else {
            node->RightNumber++;
            if (node->RightChild == NULL) {
                node->RightChild = new struct Node(data);
                return;
            } else {
                node = node->RightChild;
            }
        }
    }
    node->Number++;
}

template <typename Type>
int BST<Type>::getTurn(Type data) {
    int          turn = 0;
    struct Node* node = root;
    while (!(node == NULL) && !(node->Value == data)) {
        if (node->Value > data) {
            node = node->LeftChild;
        } else {
            turn += node->LeftNumber;
            turn += node->Number;
            node = node->RightChild;
        }
    }
    if (node == NULL) {
        return 0;
    } else {
        return turn + node->LeftNumber + 1;
    }
}

template <typename Type>
Type BST<Type>::getValue(int turn) {
    struct Node* node = root;
    while (1) {
        if (turn <= node->LeftNumber) {
            node = node->LeftChild;
        } else if (node->LeftNumber < turn && turn <= node->LeftNumber + node->Number) {
            return node->Value;
        } else {
            turn -= node->LeftNumber;
            turn -= node->Number;
            node = node->RightChild;
        }
    }
}

template <typename Type>
Type BST<Type>::getFront(Type data) {
    struct Node* node        = root;
    Type         parentValue = -1 * DefaultValue;
    while (node != NULL && !(node->Value == data)) {
        if (data < node->Value) {
            node = node->LeftChild;
        } else {
            parentValue = node->Value;
            node        = node->RightChild;
        }
    }
    if (node == NULL) {
        return -1 * DefaultValue;
    } else if (node->LeftChild == NULL) {
        return parentValue;
    } else {
        return node->LeftChild->Value;
    }
}

template <typename Type>
Type BST<Type>::getBack(Type data) {
    struct Node* node        = root;
    Type         parentValue = DefaultValue;
    while (!(node->Value == data) && node != NULL) {
        if (data < node->Value) {
            parentValue = node->Value;
            node        = node->LeftChild;
        } else {
            node = node->RightChild;
        }
    }
    if (node == NULL) {
        return DefaultValue;
    } else if (node->RightChild == NULL) {
        return parentValue;
    } else {
        return node->RightChild->Value;
    }
}

int main(void) {
    BST<int> bst(2147483647);
    int      q, t, x;
    cin >> q;
    while (q--) {
        cin >> t >> x;
        switch (t) {
            case 1:
                cout << bst.getTurn(x) << endl;
                break;
            case 2:
                cout << bst.getValue(x) << endl;
                break;
            case 3:
                cout << bst.getFront(x) << endl;
                break;
            case 4:
                cout << bst.getBack(x) << endl;
                break;
            case 5:
                bst.insert(x);
                break;
        }
    }
    bst.~BST();
    return 0;
}
2020/10/29 11:05
加载中...