c++ - 我的跳过列表中的堆损坏

Question

当我在我的 int main() 中 return 0; 时，我的跳跃列表实现出现了这个问题，我得到了堆损坏。这至少是我调试到的地方，直到它崩溃。

这是我的代码:

跳过节点.h

template <typename T>
class SkipNode
{
public:
    T data;
    SkipNode<T> **next;
    SkipNode(T d, int level);
    ~SkipNode();
};

跳过节点.cpp

#include "skipnode.h"

template<typename T>
SkipNode<T>::SkipNode(T d, int level)
{
    data = d;
    next = new SkipNode<T>*[level];

    for (int i = 0; i < level; i++)
        next[i] = 0;
}

template<typename T>
SkipNode<T>::~SkipNode()
{
    delete [] next;
}

跳表.h

#include "skipnode.cpp"

#define MAXLEVEL 4

template<typename T>
class SkipList
{
public:
    SkipList();
    ~SkipList();
    int randLvl(int max);
    T search(T);
    void insert(T);
private:
    SkipNode<T> *root; 
};

跳表.cpp

#include "skiplist.h"
#include <stdlib.h>
#include <time.h>

template<typename T>
SkipList<T>::SkipList()
{
    root = new SkipNode<T>(0,MAXLEVEL);
}

template<typename T>
SkipList<T>::~SkipList()
{
    delete root;
}

template<typename T>
int SkipList<T>::randLvl(int max)
{
    srand(time(NULL));
    return rand() % max + 1; //+ 1, så værdien ikke bliver 0
}

template<typename T>
void SkipList<T>::insert(T value)
{
    int level = randLvl(MAXLEVEL);

    SkipNode<T> *insertNode = new SkipNode<T>(value,level);
    SkipNode<T> *currentNode = root;

    for (int i = level; i > 0; i--)
    {
        for (; currentNode->next[i] != 0; currentNode = currentNode->next[i])
        {
            if (currentNode->next[i]->data > value)
                break;
        }
        if (i <= level)
        {
            insertNode->next[i] = currentNode->next[i];
            currentNode->next[i] = insertNode;
        }
    }
}

主要.cpp

#include "skiplist.cpp"

int main()
{
    SkipList<int> SList;
    SList.insert(3);
    return 0;
}

我有一个理论，错误可能发生在 skiplist.cpp 的这一行:

if (currentNode->next[i]->data > value)

因为好像不能访问next->data，但是不知道为什么。

谁能帮帮我？抱歉，如果我问错了问题，我是 Stack Overflow 的新手。提前致谢!

Answer 1

你有一个 off-by-one error在insert(T)的for循环中，应该是

for (int i = level-1; i >= 0; i--)

还有 insert() 泄漏内存，删除 insertNode