C++ 二进制最大堆读取访问冲突

Question

所以我正在为我的 c++ class 创建一个二进制最大堆，我一直遇到这个异常，说我在我的 class 方法中返回一个 nullptr。我无法找到它在我的代码中的位置，因此将不胜感激任何帮助。不断抛出的异常如下：

Unhandled exception thrown: read access violation.
**std::_String_alloc<std::_String_base_types<char,std::allocator<char> > ::_Get_data**(...) returned nullptr. occurred

这是我的树的头文件： #ifndef HEAP_H #define HEAP_H

    #include <iostream>
    #include "THeapNode.h"

    class TreeHeap {
    private:
        THeapNode *root;  // the top node of the heap

        int next_loc;   // the next valid location to place a node

        void bubble_up(THeapNode *node);    //performs the bubble up operation on the given node

        void bubble_down(THeapNode *node);  //performs the bubble down operation on the given node

        void clear_heap(THeapNode *node); // removes all elements from the heap




    public:

        TreeHeap();    // the constructor

        ~TreeHeap();   // the destructor

        THeapNode* find_node(const int position);   // finds the node in the position given and returns a pointer to it

        void insert(const string &item);    // creates a node with the string given as the value and places it in the next location

        bool Delete();  // removes the root of the heap and returns false if the tree is empty
    };

    #endif

这是我的节点的 .h 文件：

    #ifndef NODE_H
    #define NODE_H
    #include<string>
    using std::string;

    struct THeapNode {
        string data;    // stores a data string
        THeapNode *parent;  // a pointer to the parent node
        THeapNode *rightChild;     // a pointer to the right child node
        THeapNode *leftChild;   // a pointer to the left child node
        THeapNode( const string &str );
    };

    #endif

这是我的 .cpp 文件：

    #include "stdafx.h"
    #include <cmath>
    #include "TreeHeap.h"
    #include "THeapNode.h"


    TreeHeap::TreeHeap() {
        root = NULL;   
        next_loc = 1;
    };

    TreeHeap::~TreeHeap() {

        THeapNode *current = root;
        THeapNode *deleteNode = NULL;
        int d = floor(log2(next_loc - 1));
        int j = next_loc;

        for ( int i = 1; i <= j-1; i++ ) {

            while (1) {

                int d = floor(log2(next_loc - i));
                int power = std::pow(2, d - 1);

                if (next_loc == 1) {
                    deleteNode = current;
                    j -= 1;
                }
                else if (next_loc < (std::pow(2, d - 1) * 3)) {
                    current = current->leftChild;
                }
                else {
                    current = current->rightChild;
                }

                // Update location and depth to reflect traversal
                next_loc = std::pow(2, d - 1) + next_loc % power;
                d = d - 1;
            }

            clear_heap(deleteNode);

        }

    }

    void TreeHeap::clear_heap(THeapNode *node) {

        if (node == NULL) {
            return;
        }

        node->data = "";
        node->leftChild = NULL;
        node->rightChild = NULL;
        node->parent = NULL;

    }

    void TreeHeap::insert( const string &value ) {

        THeapNode newNode = THeapNode(value);
        int loc = next_loc;

        if (loc == 1) {
            *root = newNode;
        }

        THeapNode *current = root;

        while (1) {

            int d = floor(log2(loc));
            int power = std::pow(2, d - 1);

            if (loc < (power * 3)) {
                if (current->leftChild = nullptr) {
                    *current->leftChild = newNode;
                    newNode.parent = current;
                    next_loc += 1;
                    break;
                }
                else {
                    current = current->leftChild;
                }
            }

            else {
                if (current->rightChild = nullptr) {
                    *current->rightChild = newNode;
                    newNode.parent = current;
                    next_loc = +1;
                    break;
                }
                else {
                    current = current->rightChild;
                }
            }

            // Update location and depth to reflect traversal
            loc = std::pow(2, d - 1) + loc % power;
            d = d - 1;

        }
        std::cout << current->data << "\n";
        system("PAUSE");

    }

    void TreeHeap::bubble_up( THeapNode *node ) {

        if (node == NULL) {
            return;
        }

        THeapNode *parent = node->parent;

        while ( parent->data < node->data ) {
            parent = node->parent;
            string temp = parent->data;
            parent->data = node->data;
            node->data = temp;
            }

    }

    void TreeHeap::bubble_down( THeapNode *node ) {

        if (node == NULL) {
            return;
        }

        while( node->data < node->rightChild->data || node->data < node->leftChild->data ){
            if (node->rightChild->data > node->leftChild->data) {

                THeapNode *right = node->rightChild;
                string temp = right->data;
                right->data = node->data;
                node->data = temp;
            }
            else if (node->rightChild->data < node->leftChild->data) {

                THeapNode *left = node->leftChild;
                string temp = left->data;
                left->data = node->data;
                node->data = temp;
            }
        }
    }

    THeapNode* TreeHeap::find_node( const int position ){

        int loc = position;
        int d = floor(log2(position));
        int power = std::pow(2, d - 1);
        THeapNode *returnValue = root;

        while (returnValue != NULL && 1 < position && position < (next_loc - 1)) {

            if (loc == 1) {
                return returnValue;
            }
            else if (loc < ( std::pow( 2, d-1 ) * 3)) {
                returnValue = returnValue->leftChild;
            }
            else {
                returnValue = returnValue->rightChild;
            }

            // Update location and depth to reflect traversal
            loc = std::pow(2, d - 1) + loc % power;
            d = d - 1;
        }
        std::cout << returnValue->data<<"\n";
        return returnValue;
    }

    bool TreeHeap::Delete() {

        if (next_loc = 1) {
            return false;
        }

        int d = floor(log2(next_loc - 1));
        THeapNode *current = root;
        THeapNode *usedNode = NULL;
        int loc = next_loc - 1;

        while ( 1 ) {

            int d = floor(log2(loc));
            int power = std::pow(2, d - 1);

            if (loc == 1) {
                usedNode = current;
                break;
            }
            else if (loc < (std::pow(2, d - 1) * 3)) {
                current = current->leftChild;
            }
            else {
                current = current->rightChild;
            }

            // Update location and depth to reflect traversal
            loc = std::pow(2, d - 1) + loc % power;
            d = d - 1;
        }



        THeapNode *temp = root;
        clear_heap(root);
        root = usedNode;
        delete temp;

        bubble_down(root);

        return true;
    }

在此先感谢您提供的任何帮助。

Answer 1

快速检查会发现您的 bubble_up 和 bubble_down 函数中存在错误。

在 bubble_up 中，您有以下内容：

    THeapNode *parent = node->parent;

    while ( parent->data < node->data ) {
        parent = node->parent;
        string temp = parent->data;
        parent->data = node->data;
        node->data = temp;
        }

当节点冒泡到顶部时，这将失败，因为它不检查节点是否位于根。你需要写：

while (parent != NULL && parent->data < node->data)

在 bubble_down 中，您有此代码：

    while( node->data < node->rightChild->data || node->data < node->leftChild->data ){
        if (node->rightChild->data > node->leftChild->data) {

您不检查 rightChild 或 leftChild 是否为 NULL。

更重要的是，这对我来说就像一个无限循环，因为您永远不会更改 node 的值。

这些只是我在快速阅读您的代码时看到的错误。可能还有更多。

C++ 二进制最大堆读取访问冲突

C++ binary max heap Read Access Violation

c++

heap

binary-tree

exception