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

Почему переприсваивается адрес последнего элемента? - C++

Восстановить пароль Регистрация
 
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
25.11.2014, 16:37     Почему переприсваивается адрес последнего элемента? #1
Привет парни. Я пишу домашку на тему АА дерева.

Я сделал класс дерева, в него вложил класс узла. Реализую первый метод дерева - create(), как вы наверное догадались, метод создаёт дерево с нуля.

Немного про логику программы.
При создании класса дерева автоматом создаётся узел nil (лист дерева, он в полях правого и левого сына ссылается сам на себя). При добавлении первого элемента - корня, разрываются связи nil'a и перенаправляются на адрес корня (в полях правого и левого сына, корень ссылается на адрес nil'a: на подобие кольца - все новые элементы замыкаются на nil).

Кликните здесь для просмотра всего текста
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
 
class Tree
{
    public: 
 
    class Node
    {
        public:
 
        //node info
        Node* left;
        Node* right;
        int _key;
        int _level;
 
        //construct NIL node
        Node()
        {
            left = this;
            right = this;
            _level = 0;
            _key = -1;
        }
 
        Node(int key, Node NIL)
        {
            left = &NIL;
            right = &NIL;
            _level = 1;
            _key = key;
        }
    };
 
    Node nil;
 
    Tree() {}
 
    void skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот в право
            Node left;
 
            left = *thisNode->left;
            *thisNode->left = *left.right;
            left.right = thisNode;
            *thisNode = left;
        }
    }
 
    void split(Node *thisNode)
    {
        if (thisNode->right->right->_level == thisNode->_level)
        {   //повернуть влево
            Node right;
            right = *thisNode->right;
            *thisNode->right = *right.left;
            right.left = thisNode;
            *thisNode = right;
            //увеличить уровень
            thisNode->_level++;
        }
    }
 
    void create()
    {
        char key;
 
        printf("\n   .. Create AATree, to stop input \'E\'\n");
 
        while (true)
        {   
            std::cin >> &key;
 
            if (key == 'E')
            {   // выходим из цикла
                break;
            }
            else if (nil.left == &nil && nil.right == &nil)
            {   //сделать корень, т.к. у nil'а нет детей, следовательно - нет корня
                Node root(atoi(&key), nil);
                nil.left = nil.right = &root;
            }
            else 
            {   //добавить к сыну nil (корню) узел: начинается поиск места для вставки c этого узла
                insert(*nil.left, atoi(&key));
            }
        }
    }
 
    bool insert(Node thisNode, int key)
    {
        if (key < thisNode._key)
        {   // спускаемся влево
            if (thisNode.left != &nil)
                // сын этого узла - не nil: идём глубже
                insert(*thisNode.left, key);
            else
            {   // сын этого узла - nil: создали узел (левый сын) и связали с этим узлом
                Node newNode(key, nil);
                thisNode.left = &newNode;
            }
        }
        else if (key > thisNode._key)
        {   // спускаемся вправо
            if (thisNode.right != &nil)
                // сын этого узла - не nil: идём глубже
                insert(*thisNode.right, key);
            else
            {   // сын этого узла - nil: создали узел (правый сын) и связали с этим узлом
                Node newNode(key, nil);
                thisNode.right = &newNode;
            }
        }
        else
        {   // key = thisNode
            printf("   .. key \'%i\' is bysu, use another key", key);
            return 0;
        }
 
        //балансируем дерево в этом узле
        skew(&thisNode);
        split(&thisNode);
    }
};
 
 
int main()
{
    Tree AATree;
    AATree.create();
}


Основная проблема в методе Tree::create().
Метод create() сделан в стиле дружелюбного пользователю кода: в его ядре лежит while(true), по команде цикл прерывается.

Начинается первый проход цикла.
При создании корня всё идёт как по маслу: делается первый проход цикла, считывается с клавиатуры ключ, определяется есть ли корень, если нет корня (а у нас его нет на первом проходе), создаётся корень. Корень ссылается всеми потомками на nil, nil ссылается всеми потомками на корень. То есть образуется такое дерево, как на картинке.
Название: Снимок.PNG
Просмотров: 26

Размер: 4.9 Кб

Начинается второй проход цикла.
Всё хорошо: корень ссылается на nil, nil ссылается на корень. Как только отладчик проходит строку
C++
1
std::cin >> &key;
Сразу же (в отладчике прям видно) наш корень начинает ссылаться правым и левом сыном на какой-то мусор, почему-то меняет связи. Связь разорвана и получается какая-то чушь. Заметьте, мы даже ещё не прошли следующую строку, а связи разорваны
C++
1
if (key == 'E')
а это значит, что проблема в вводе.

Помогите решить эту проблему. Мне надо чтобы все новые узлы ссылались на nil.

Что я пытался сделать:
- менял cin на scanf() - не помогло
- убрал cin и поставил обычный счётчик в замен вводу с клавиатуры в стиле
C++
1
2
3
4
5
6
int key = 8;
while (true)
{
//....
key++;
}
помогло, элементы добавлялись как надо и ссылались куда положено. Что опять же доказывает что проблема в вводе
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2014, 16:37     Почему переприсваивается адрес последнего элемента?
Посмотрите здесь:

Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне [c,d] и расположенных до первого четного элемента. C++
Адрес первого и последнего хоста в сети C++
C++ Удаление последнего элемента списка
Удаление последнего элемента в строке C++
C++ удаление последнего элемента из списка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11844 / 6823 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
25.11.2014, 16:41     Почему переприсваивается адрес последнего элемента? #2
А зачем вы берете адрес локальной переменной key при вводе?

Может всё-таки
C++
1
std::cin >> key ;
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
25.11.2014, 16:43  [ТС]     Почему переприсваивается адрес последнего элемента? #3
Да, есть такое - не знаю, видимо пока экспериментировал оставил этот мусор в коде, спасибо. Исправил.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11844 / 6823 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
25.11.2014, 16:47     Почему переприсваивается адрес последнего элемента? #4
Так же вы берете адрес переменной root, которая будет уничтожена при выходе из блока.
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
25.11.2014, 16:49  [ТС]     Почему переприсваивается адрес последнего элемента? #5
Хорошо, тогда если мы её вынесем за пределы метода, то у нас появится лишняя переменная. Это не желательно. Сейчас вынесу и посмотрю что изменится.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11844 / 6823 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
25.11.2014, 16:52     Почему переприсваивается адрес последнего элемента? #6
Ничего не изменится. Дерево нужно строить в динамической памяти, а не из автоматических переменных.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2014, 21:16     Почему переприсваивается адрес последнего элемента?
Еще ссылки по теме:

C++ Односвязный список. Вывести сумму последнего элемента и первого, предпоследнего и последнего и т.д.
Адрес элемента динамического массива C++
C++ Удаление последнего элемента Дека

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

Или воспользуйтесь поиском по форуму:
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
25.11.2014, 21:16  [ТС]     Почему переприсваивается адрес последнего элемента? #7
Цитата Сообщение от Croessmah Посмотреть сообщение
Так же вы берете адрес переменной root, которая будет уничтожена при выходе из блока.
Да, помогло. Спасибо!
Но вот только пока решение проблемы я сделал посредством добавления новой переменной Node root. Меня это не очень радует - лишняя переменная, лишние вопросы. Я раньше хотел обойтись чисто нилом, без привлечения новых переменных, и как видите, у меня дальше используется такое же каличное решение в функции Tree::insert.
C++
1
2
3
4
5
6
7
8
9
10
11
12
    bool insert(Node thisNode, int key)
    {
        if (key < thisNode._key)
        {   // спускаемся влево
            if (thisNode.left != &nil)
                // сын этого узла - не nil: идём глубже
                insert(*thisNode.left, key);
            else
            {   // сын этого узла - nil: создали узел (левый сын) и связали с этим узлом
                Node newNode(key, nil);
                thisNode.left = &newNode;
            }
Node newNode(key, nil) - создаст новый узел в пределах этого метода, не возникнет ли потом с этим проблем?

Добавлено через 6 минут
Цитата Сообщение от Croessmah Посмотреть сообщение
Ничего не изменится. Дерево нужно строить в динамической памяти, а не из автоматических переменных.
а, понял, то есть таким методом:
C++
1
Node *a = new Node();
Добавлено через 4 часа 9 минут
Хм, мистика. перешёл на динамические переменные. Стал выделять память под указатель через
C++
1
Node *tmp = new Node();
- программа работает нормально.

Но у меня есть второй конструктор
C++
1
2
3
Node *tmp = new Node(key, child);
//key - int
//child - Node
Так вот, при вызове
C++
1
Node *tmp = new Node(8, nil);
в теле цикла, после выхода из цикла автоматом вызывается деструктор. А при вызове
C++
1
Node *tmp = new Node();
деструктор не вызывается и всё хорошо.

Как жить? планировалось второй деструктор использовать на полную, дабы освободить код от лишних строк.
Yandex
Объявления
25.11.2014, 21:16     Почему переприсваивается адрес последнего элемента?
Ответ Создать тему
Опции темы

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