Повреждение кучи в моем списке пропуска

У меня возникла проблема с реализацией моего списка пропусков, когда я получаю повреждение кучи, когда я return 0; в своем int main(). Это, по крайней мере, то, где я отлаживался, пока он не разбился.

Ошибка отладки

введите здесь описание изображения

Это мой код:

skipnode.h

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

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;
        }
    }
}

main.cpp

#include "skiplist.cpp"

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

У меня есть теория, что ошибка может происходить в этой строке в skiplist.cpp:

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

потому что кажется, что он не может получить доступ к следующим-> данным, но я не знаю, почему.

Может кто-нибудь мне помочь? И извините, если я задаю вопрос неправильно, я новичок в Stack Overflow. Заранее спасибо!


person Thisen    schedule 03.12.2014    source источник
comment
Это не связано со сбоем, но постоянное заполнение вашего RNG временем будет означать, что он будет возвращать одно и то же число снова и снова, пока время не изменится, что, вероятно, не то, что вы намеревались.   -  person Gareth Davidson    schedule 03.12.2014
comment
Хм, он выдает разные результаты. Может я не совсем понимаю, что вы имеете в виду?   -  person Thisen    schedule 03.12.2014
comment
Уверены ли вы? time возвращает time_t, который на большинстве платформ представляет собой количество секунд с начала эпохи. Вы заполняете этим генератор псевдослучайных чисел, поэтому он должен возвращать одно и то же число, пока часы не перейдут на следующую секунду.   -  person Gareth Davidson    schedule 03.12.2014
comment
Только что проверил. Выходы: 4, 3, 3, 1, 2, 4, 1. Вроде работает :)   -  person Thisen    schedule 03.12.2014
comment
Работает на моем ПК, мэм.   -  person Gareth Davidson    schedule 03.12.2014
comment
Было бы лучше, если бы вы могли исправить мою основную проблему. ;)   -  person Thisen    schedule 03.12.2014
comment
Попробуйте использовать Microsoft Application Verifier, чтобы отловить повреждение. Он вызовет остановку отладки, если она будет найдена.   -  person rrirower    schedule 03.12.2014


Ответы (2)


У вас есть ошибка off-by-one_error в цикле for в insert(T), это наверное должно быть

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

Также вставка () приводит к утечке памяти, удалите insertNode

person Tatu Lahtela    schedule 04.12.2014

возможно, попробуйте gflags, посмотрите этот ответ:

https://stackoverflow.com/a/2476077/3986139

после включения gflags вы можете получить исключение в VS прямо во время повреждения кучи вместо исключения после события

person hobo    schedule 04.12.2014