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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Различные цеха завода выпускают продукцию нескольких наименований http://www.cyberforum.ru/cpp-beginners/thread1310561.html
Различные цеха завода выпускают продукцию нескольких наименований. Сведения о выпущенной продукции включают: • наименование; • количество; • номер цеха. Для заданного цеха выведите количество выпущенных изделий по указанному наименованию в порядке убывания их количества. Проблема с выводам:( #include <iomanip> #include <iostream> #include <conio.h>
C++ Написать программу: работа с си строками, функции strlen, strcpy С помощью данного алгоритма нужно вставить слово в конец и начало строки. С помощью strlen() узнать длину строки и длину слова, после перезаписать строку ---> подвинуть строку на длину слова и вставить туда это слово. Так же нужно использовать указатель. Как это организовать? http://www.cyberforum.ru/cpp-beginners/thread1310560.html
C++ Выполнить циклическую перестановку элементов массива влево или вправо
Сформулировать одномерный массив целых чисел, используя датчик случайных чисел. По запросу выполнить циклическую перестановку элементов массива влево или вправо. Вывести полученный массив слева направо, начиная с k-ого элемента, и в k-1-го. Удалить из массива первый и последний элементы. Вывести полученный массив справа налево от k-го до k + 1-го элемента.
Найти три числа последовательности, сумма которых равняется некоторому числу C++
Помогите пожалуйста написать код задачи(Новичок). Даны целые числа m, a1, .... , a20. Найти три натуральных числа i, j, k, каждое из которых не превосходит двадцати, такие, что Ai+Aj+Ak = m. Если таких чисел нет, то сообщить об этом.
C++ Оператор присваивания по умолчанию http://www.cyberforum.ru/cpp-beginners/thread1310505.html
#include <iostream> using namespace std; class Foo { private: int var; //int var = 17; public: /*Foo& operator=(const Foo& right)
C++ Ребят памогите решать упражнения Вот пример и решение \sum_{i=0}^{n+m} {({i}^{2}+k)}^{2} #include <iostream> using namespace std; int main() { int n, m, k, s,i; подробнее

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

Я сделал класс дерева, в него вложил класс узла. Реализую первый метод дерева - 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++;
}
помогло, элементы добавлялись как надо и ссылались куда положено. Что опять же доказывает что проблема в вводе
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 08:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru