Три дерева.Невозможно получить доступ к памяти - PullRequest
Новая
       16

Три дерева.Невозможно получить доступ к памяти

0 голосов
/ 27 сентября 2018

Я новичок в C ++ и у меня есть некоторые проблемы с двумя отдельными ошибками.Невозможно получить доступ к памяти и переполнению стека.

Это моя реализация дерева Trie, использующая указатели слов, содержащих символы az.При запуске тестов я могу успешно добавить несколько сотен или даже тысяч узлов без проблем, пока в конечном итоге не произойдет сбой.Ошибка: невозможно получить доступ к памяти.Я чаще получаю эту ошибку, когда пытаюсь выполнить запрос и использую функцию isAWord.Я также получаю переполнение стека, когда я пытаюсь запустить деконструктор.Любая помощь приветствуется, так как я потратил 2 дня на попытки отладки с небольшим успехом. 

#include "Trie.h"
#include <iostream>
#include <iterator>
#include <sstream>

using namespace std;    

//sets up tree
Trie::Trie()
{
    for (int i = 0; i < ALPH; i++)
        this->childs[i] = nullptr;

    endNode = false;
}

//add 'userInput' string to trie

void Trie::addAWord(std::string userInput)
{
    Trie* start = this;

    for (int i = 0; i < userInput.length(); i++)
    {
        int index = userInput[i] - 'a';

        if (start->childs[index] == nullptr)
            start->childs[index] = new Trie();

        start = start->childs[index];
    }

    start->endNode = true;
}

//returns true if 'wordFind' is in tree

bool Trie::isAWord(std::string wordFind)
{
    if (this == nullptr)
        return false;

    Trie* start = this;

    for (int i = 0; i < wordFind.length(); i++)
    {
        int index = wordFind[i] - 'a';
        start = start->childs[index];

        if (start == nullptr)
            return false;
    }

    return start->endNode;
}

//returns a vector containing the words in tree with prefix 'prefFind'

vector<std::string> Trie::allWordsStartingWithPrefix(std::string prefFind)
{
    string pres = PrefixRec(prefFind,*this);
    stringstream preStream(pres);
    istream_iterator<std::string> begin(preStream), end;
    vector<std::string> stringSet(begin, end);
    copy(stringSet.begin(), stringSet.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    return stringSet;
}

//helper method for AllWordsStartingWithPrefix

std::string Trie::PrefixRec(std::string& key, Trie const temp)
{
    if (temp.endNode)
        return(key + " ");

    for (char index = 0; index < ALPH; ++index)
    {
        index = key[index] - 'a';

        Trie const* curChild = temp.childs[index];
        if (curChild)
        {
            key.push_back(index);
            PrefixRec(key, *curChild);
            key.pop_back();
        }
    }
}

//copy cons and assignment op

Trie& Trie::operator=(const Trie& other)
{
    Trie* newPtr = new Trie(other);
    other.~Trie();
    return *newPtr;
}

//deconstructor

Trie::~Trie()
{
    if (this == nullptr)
        return;

        for (int i = 0; i < ALPH; i++)
        {
            if (childs[i] != nullptr)
                childs[i]->~Trie();
        }
        delete this;
        return;
}


#include <iostream>
#include <vector>
#include <string>

#define ALPH 26

class Trie
{
public:
    bool endNode;
    Trie* childs[ALPH];

    Trie();
    void addAWord(std::string key);
    bool isAWord(std::string key);
    std::vector<std::string> allWordsStartingWithPrefix(std::string key);
    Trie& operator=(const Trie& other);
    std::vector<std::string> wordsWithWildcardPrefix(std::string);
    std::string PrefixRec(std::string& key, Trie const temp);
    ~Trie();
};

1 Ответ

0 голосов
/ 27 сентября 2018

Я также получаю переполнение стека при попытке запустить деконструктор.

Это из-за этой строки: 

delete this;

Это то, что delete делает

Выражение delete вызывает деструктор (если есть) для объекта, который уничтожается,

Вы можете себе представить, почему вызывается deleteизнутри деструктор будет проблематичным.(Подсказка: Бесконечная рекурсия )

Вам не нужно ничего delete this в вашем коде.

Как только вы избавитесь от этого, возникают другие проблемы. (Хотя вы можете жить только исправив это).Например, явный вызов деструктора, как вы делаете в этой строке (и некоторых других строках) 

other.~Trie();

From iso cpp :

Должен ли я явно вызывать деструктор для локальной переменной?

Нет!

Деструктор будет вызван снова при закрытии} блокав котором был создан местный.Это гарантия языка;это происходит автоматически;нет способа остановить это.Но вы можете получить действительно плохие результаты от вызова деструктора для того же объекта во второй раз! Взрыв!Вы мертвы!

Замените явные вызовы деструктора на delete и позвольте ему правильно вызывать деструктор.

Я бы порекомендовал заменить любые необработанные указателии new и delete с интеллектуальным указателем .Начните с shared_ptr для начала.(raw_pointers 2010;))

Сноска: избавьтесь от этих проверок.Они не идиоматичны.Это нормально и желательно для вызывающего абонента при вызове функции-члена на nullptr 

if (this == nullptr)
    return false;
...