С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gudsaf
104 / 15 / 3
Регистрация: 29.11.2010
Сообщений: 328
#1

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

25.11.2014, 16:37. Просмотров 229. Ответов 6
Метки нет (Все метки)

Привет парни. Я пишу домашку на тему АА дерева.

Я сделал класс дерева, в него вложил класс узла. Реализую первый метод дерева - 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
Просмотров: 28

Размер: 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++;
}
помогло, элементы добавлялись как надо и ссылались куда положено. Что опять же доказывает что проблема в вводе
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2014, 16:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Почему переприсваивается адрес последнего элемента? (C++):

Объяснить почему указатель выводит всю строку сразу, а не адрес первого элемента - C++
Всем привет :) Начал изучать сей замечательный язык и появились кое-какие вопросы к гуру! Запутался в указателях... ...

Односвязный список. Вывести сумму последнего элемента и первого, предпоследнего и последнего и т.д. - C++
Считываю с клавиатуры числа пока не встречаю 0. Например 1 3 7 5 8 1 0 Вывожу суму последнего элемента и первого, предпоследнего и...

Убедиться, что адрес первого элемента массива и адрес, хранящийся в указатели на этот массив равны. - C++
Убедиться, что адрес первого элемента массива и адрес, хранящийся в указатели на этот массив - равны.

Адрес первого и последнего хоста в сети - C++
Собсно, из файла читается ip\mask. Нужно вывести имя первого и последнего хоста сети. Код написал но где - то ошибка, скорее всего...

Многомерный массив. Дублирование значения первого элемента строки в значении последнего элемента предыдущей - C++
Здравствуйте уважаемые форумчане! Решил я сегодня разобраться с многомерными массивами! И немного разочаровался в своих результатах....

Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне [c,d] и расположенных до первого четного элемента. - C++
помогите с задачкой Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне и расположенных до...

6
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.11.2014, 16:41 #2
А зачем вы берете адрес локальной переменной key при вводе?

Может всё-таки
C++
1
std::cin >> key ;
1
Gudsaf
104 / 15 / 3
Регистрация: 29.11.2010
Сообщений: 328
25.11.2014, 16:43  [ТС] #3
Да, есть такое - не знаю, видимо пока экспериментировал оставил этот мусор в коде, спасибо. Исправил.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.11.2014, 16:47 #4
Так же вы берете адрес переменной root, которая будет уничтожена при выходе из блока.
1
Gudsaf
104 / 15 / 3
Регистрация: 29.11.2010
Сообщений: 328
25.11.2014, 16:49  [ТС] #5
Хорошо, тогда если мы её вынесем за пределы метода, то у нас появится лишняя переменная. Это не желательно. Сейчас вынесу и посмотрю что изменится.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.11.2014, 16:52 #6
Ничего не изменится. Дерево нужно строить в динамической памяти, а не из автоматических переменных.
0
Gudsaf
104 / 15 / 3
Регистрация: 29.11.2010
Сообщений: 328
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();
деструктор не вызывается и всё хорошо.

Как жить? планировалось второй деструктор использовать на полную, дабы освободить код от лишних строк.
0
25.11.2014, 21:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2014, 21:16
Привет! Вот еще темы с ответами:

Найти сумму первого максимального элемента массива А и последнего минимального элемента массива В - C++
Вот задание : Даны целочисленные массивы А и В. Найти сумму первого максимального элемента массива А и последнего минимального элемента...

Номер последнего элемента - C++
Нужно написать программу на С++ которая бы выводила : Номер последнего элемента массива, значение которого равнопроизведению его соседних...

Адрес первого элемента массива - C++
1. Написать функцию, принимающую в качестве параметра количество строк и столбцов в таблице умножения. Функция должна создать двумерный...

Адрес элемента динамического массива - C++
Здравствуйте, создан динамический массив, нужно вычислить адрес какого-нибудь элемента (зная адрес нулевого). В автоматическом знаю как...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.