Форум программистов, компьютерный форум CyberForum.ru

Трай , где неправильная работа с памятью? - C++

Восстановить пароль Регистрация
 
fatalis
8 / 8 / 1
Регистрация: 09.08.2013
Сообщений: 68
12.09.2013, 11:22     Трай , где неправильная работа с памятью? #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Trie
{
  struct Node
    {
        int count ;
        Node **r;
        Node()
        {
            count = 0;
            r=new Node*[4];
        }
    };
    Node *root;
    Node* insert(Node* root,string s,int t)
    {
        if(root==nullptr)
        {
            root=new Node;
        }
        if(s.length()==t)
        {
            return root;
        }
        else
        {
            root->count++;
            int k=s[t]-'a';
            if(root->r[k]==nullptr)root->r[k]=new Node;
            root->r[k]=insert(root->r[k],s,t+1);
            return root;
        }
    }
    int find(Node *root,string s,int t)
    {
        if(root==nullptr)return 0;
        if(s.length()==t)return root->count;
        int k = s[t]-'a';
        return find(root->r[k],s,t+1);
        
    }
public:
    void insert(string s)
    {
        root=insert(root, s, 0);
    }
    int find(string s)
    {
        return find(root,s,0);
    }
    Trie():root(nullptr)
    {
        
    }
};
В общем,где-то неправильну пишу в память,где - не знаю. Работать может и иногда правильно - да вот не всегда
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2013, 11:22     Трай , где неправильная работа с памятью?
Посмотрите здесь:

Какая-то ошибка с памятью, где накосячил? C++
Неправильная работа с файлами C++
C++ Строковые С++,неправильная работа функции
Неправильная работа программы C++
Неправильная работа цикла C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
12.09.2013, 11:30     Трай , где неправильная работа с памятью? #2
может где то ошибка на конкретную строку указывает?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 11:30     Трай , где неправильная работа с памятью? #3
t - это что? Какие значения могут быть? В коде обращения по этому индексу, может там где-то выход...
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
12.09.2013, 11:32     Трай , где неправильная работа с памятью? #4
Цитата Сообщение от fatalis Посмотреть сообщение
if(root==nullptr)
{
тут странно получается, а если создастся экземпляр с root != nullptr, надо это в конструкторе прописать
C++
1
root = nullptr;
а точнее в списке инициализации root(nullptr)
fatalis
8 / 8 / 1
Регистрация: 09.08.2013
Сообщений: 68
12.09.2013, 11:38  [ТС]     Трай , где неправильная работа с памятью? #5
Цитата Сообщение от alsav22 Посмотреть сообщение
t - это что? Какие значения могут быть? В коде обращения по этому индексу, может там где-то выход...
Кажется,t никак не может стать больше за длину s.
Размер алфавита выбран 4,соотстветственно и строки состоят исключительно из 'a','b','c','d'
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 11:53     Трай , где неправильная работа с памятью? #6
Цитата Сообщение от fatalis Посмотреть сообщение
Кажется,t никак не может стать больше за длину s.
А равным? Это тоже будет выход. Вот здесь, например, передаётся t + 1:
C++
1
return find(root->r[k],s,t+1);
fatalis
8 / 8 / 1
Регистрация: 09.08.2013
Сообщений: 68
12.09.2013, 11:54  [ТС]     Трай , где неправильная работа с памятью? #7
C++
1
if(s.length()==t)return root->count;
Если становится равным - то сразу же возвращаем результат.Кажется,здесь проблемы нет
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 12:02     Трай , где неправильная работа с памятью? #8
Давайте кода больше.
fatalis
8 / 8 / 1
Регистрация: 09.08.2013
Сообщений: 68
12.09.2013, 12:15  [ТС]     Трай , где неправильная работа с памятью? #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;
#define For(i,x,y) for(int i=x;i<y;i++)
class Trie
{
  struct Node
    {
        int count ;
        Node **r;
        Node()
        {
            count = 0;
            r=new Node*[4];
        }
    };
    Node *root;
    Node* insert(Node* root,string s,int t)
    {
        if(root==NULL)
        {
            root=new Node;
        }
        if(s.length()==t)
        {
            return root;
        }
        else
        {
            root->count++;
            int k=s[t]-'a';
            if(root->r[k]==NULL)root->r[k]=new Node;
            root->r[k]=insert(root->r[k],s,t+1);
            return root;
        }
    }
    int find(Node *root,string s,int t)
    {
        if(root==NULL)return 0;
        if(s.length()==t)return root->count;
        int k = s[t]-'a';
        return find(root->r[k],s,t+1);
        
    }
public:
    void insert(string s)
    {
        root=insert(root, s, 0);
    }
    int find(string s)
    {
        return find(root,s,0);
    }
    Trie():root(NULL)
    {
      //  root=new Node;
    }
};
int main(int argc, const char * argv[])
{
   Trie t;
   t.insert("abc");
   t.insert("abcd");
   t.insert("abcdbcd");
   t.insert("abadabcadacad");
   t.find("ababacadacab");
   t.find("abacad");
   t.find("adacadabadacada");
   return 0;
}
Вот весь код.
Segmentation fault (core dumped)
Проверяю здесь http://www.compileonline.com/compile_cpp_online.php (Так как "родной" компилятор исполнит и код с выходами за массив)
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 13:38     Трай , где неправильная работа с памятью? #10
Для начала.
Миниатюры
Трай , где неправильная работа с памятью?  
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.09.2013, 14:47     Трай , где неправильная работа с памятью? #11
В массиве указателей мусор, из-за этого.
Если обнулить, то вылетов нет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
struct Node
    {
        int count;
        Node **r;
        Node()
        {
            count = 0;
            r = new Node*[4];
            for (int i = 0; i < 4; ++i)
                r[i] = NULL;
        }
    };
Если не обнулять, то здесь:
C++
1
2
3
4
5
6
7
8
9
10
11
...
else
{
       root->count++;
       int k = s[t] -'a';
       if(root ->r[k] == NULL)
            root ->r[k] = new Node;
        root ->r[k] = insert(root ->r[k], s, t + 1);
        return root;
}
...
создание Node пропускается и в insert(), первым параметром, передаётся мусор.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2013, 17:38     Трай , где неправильная работа с памятью?
Еще ссылки по теме:

C++ Трай-хэширование
C++ Неправильная работа деструктора

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
fatalis
8 / 8 / 1
Регистрация: 09.08.2013
Сообщений: 68
12.09.2013, 17:38  [ТС]     Трай , где неправильная работа с памятью? #12
Цитата Сообщение от alsav22 Посмотреть сообщение
В массиве указателей мусор, из-за этого.
Если обнулить, то вылетов нет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
struct Node
    {
        int count;
        Node **r;
        Node()
        {
            count = 0;
            r = new Node*[4];
            for (int i = 0; i < 4; ++i)
                r[i] = NULL;
        }
    };
Если не обнулять, то здесь:
C++
1
2
3
4
5
6
7
8
9
10
11
...
else
{
       root->count++;
       int k = s[t] -'a';
       if(root ->r[k] == NULL)
            root ->r[k] = new Node;
        root ->r[k] = insert(root ->r[k], s, t + 1);
        return root;
}
...
создание Node пропускается и в insert(), первым параметром, передаётся мусор.
Да,вы правы! Большое спасибо.Дурацкая ошибка
Yandex
Объявления
12.09.2013, 17:38     Трай , где неправильная работа с памятью?
Ответ Создать тему
Опции темы

Текущее время: 14:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru