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

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

Войти
Регистрация
Восстановить пароль
 
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
#1

Вставка листа в дерево - C++

23.07.2013, 20:07. Просмотров 449. Ответов 9
Метки нет (Все метки)

Я тут изучал реализацию двоичного дерева поиска и застопорился на одном моменте: не могу понять зачем при вставке листа( узла ) в дерево используется указатель на указатель на узел. Пробовал сделать через указатель на узел, но ничего не получилось. Подскажите, для чего здесь нужен указатель на указатель?

Кусок кода из Tree.h
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
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE& value )
{
    insertNodeHelper( &rootPtr, value );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE >** ptr, const NODETYPE& value )
{
    if( *ptr == 0 )
        *ptr = new TreeNode< NODETYPE >( value );
    else // поддерево не пусто
    {
        if( value < ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->leftPtr), value );
        else
        {
            if( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr), value );
            else 
                cout << value << " - duplicate" << endl;
        }
    }
}
TreeNode.h
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
#pragma once
 
template< typename NODETYPE > class Tree; // опережающее объявление шаблона класса
 
template< typename NODETYPE >
class TreeNode
{
    friend class Tree< NODETYPE >;
 
public:
    TreeNode( const NODETYPE& d )
        : leftPtr( 0 ), rightPtr( 0 ), data( d )
    {
        
    }
 
    NODETYPE getData() const
    {
        return data;
    }
private:
    TreeNode< NODETYPE >* leftPtr;
    TreeNode< NODETYPE >* rightPtr;
    NODETYPE data;
};
Полный заголовочный файл Tree.h
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
#pragma once
 
#include "TreeNode.h"
 
#include <iostream>
using std::cout;
using std::endl;
 
#include <new>
 
template< typename NODETYPE >
class Tree
{
public:
    Tree();
    void insertNode( const NODETYPE& );
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;
private:
    TreeNode< NODETYPE >* rootPtr; // корневой узел
 
    // сервисные функции:
    void insertNodeHelper( TreeNode< NODETYPE >*, const NODETYPE& ); // указатель на указатель, 
                                                                      // чтобы функция могла изменять значение указателя
    void preOrderHelper( TreeNode< NODETYPE >* ) const;
    void inOrderHelper( TreeNode< NODETYPE >* ) const;
    void postOrderHelper( TreeNode< NODETYPE >* ) const;
};
 
template< typename NODETYPE >
Tree< NODETYPE >::Tree()
{
    rootPtr = 0;
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE& value )
{
    insertNodeHelper( &rootPtr, value );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE >** ptr, const NODETYPE& value )
{
    if( *ptr == 0 )
        *ptr = new TreeNode< NODETYPE >( value );
    else // поддерево не пусто
    {
        if( value < ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->leftPtr), value );
        else
        {
            if( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr), value );
            else 
                cout << value << " - duplicate" << endl;
        }
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
    preOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        cout << ptr->data << ' ';
        preOrderHelper( ptr->leftPtr );
        preOrderHelper( ptr->rightPtr );
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
    inOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        inOrderHelper( ptr->leftPtr );
        cout << ptr->data << ' ';
        inOrderHelper( ptr->rightPtr );
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{
    postOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        postOrderHelper( ptr->leftPtr );
        postOrderHelper( ptr->rightPtr );
        cout << ptr->data << ' ';
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 20:10     Вставка листа в дерево #2
этот вопрос говорит о том, что не полностью понимаете тему указателей. попробуйте передать указатель в функцию и в ней поменять значение указателя.
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
23.07.2013, 20:26  [ТС]     Вставка листа в дерево #3
Thinker, попробовал. Все меняется.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using std::cout;
using std::endl;
 
void func( int* );
 
int main()
{
    int someInt = 5;
    int* intPtr = &someInt;
    func( intPtr );
 
    system("pause");
    return 0;
}
 
void func( int* ptr )
{
    int sInt = 55;
    ptr = &sInt;
 
    cout << *ptr << endl;
}
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 20:41     Вставка листа в дерево #4
да, вынесете cout за функцию и посмотрите

Не по теме:

p.s. что-то невнимательный сегодня

Discoverer
16 / 14 / 2
Регистрация: 05.07.2013
Сообщений: 27
23.07.2013, 20:43     Вставка листа в дерево #5
WindSlasher, в этой функции меняется значение копии указателя, а не самого указателя. Поместите вывод после вызова функции, а не в ее теле, и увидите.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
23.07.2013, 21:12     Вставка листа в дерево #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using std::cout;
using std::endl;
 
void func( int* );
 
int main()
{
    int* intPtr;
 
    func( intPtr );
    cout<<"address of new int after func is Invalid:"<<intPtr  <<endl;
    system("pause");
    return 0;
}
 
void func( int* ptr )
{
    ptr = new int;
    cout<<"address of new int inside func is Valid:"<<    ptr  <<endl;
}
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
23.07.2013, 21:41  [ТС]     Вставка листа в дерево #7
Для чего вы мне это все показываете? Я не могу понять, как это относится к использованию указателя на указатель на узел, в моих исходниках? Походу я слишком туп

P.S. в полном файле Tree.h ошибка в 25 строке. Там должно быть "void insertNodeHelper( TreeNode< NODETYPE >**, const NODETYPE& );"
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 21:44     Вставка листа в дерево #8
к тому, что каждая вершина дерева содержит информационные поля и ссылочные (указатели). чтобы вставить вершину в дерево, надо в некоторой вершине изменить значение этого самого указателя. а так как вы не понимаете как менять значение самого указателя, у вас и возникают трудности
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
23.07.2013, 22:06     Вставка листа в дерево #9
Цитата Сообщение от WindSlasher Посмотреть сообщение
Для чего вы мне это все показываете?
Потому что был вопрос
Цитата Сообщение от WindSlasher Посмотреть сообщение
для чего здесь нужен указатель на указатель?
Ответ - запусти пример из поста 6, и ты увидишь, что адрес выделенной в функции памяти теряется после выхода из функции, если передавать в неё просто одинарный указатель.

Потому что в данном примере (в отличие от примеров, когда в функцию передаётся указатель на внешнюю переменную, которая будет изменяться внутри функции по указателю)
В отличие от этого случая нам нужно выудить из функции не значение переменной, а её корректный адрес, выделенный new. и в таком случае сам адрес будет играть роль переменной величины, интересующей нас.
А раз так, этот адрес нельзя передавать аргументом по значению - требуется передавать его через указатель.

А это и будет указатель на указатель! TreeNode< NODETYPE >** ptr
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2013, 00:04     Вставка листа в дерево
Еще ссылки по теме:

C++ Разбиение листа на части
C++ Поиск минимального листа дерева
Добавление листа в книгу Excel C++
Перетасовка карт в 52 листа C++
Взять элементы из определенного листа C++

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

Или воспользуйтесь поиском по форуму:
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
24.07.2013, 00:04  [ТС]     Вставка листа в дерево #10
Thinker, кажется я понял, спасибо. Получается, если бы я использовал просто указатель, то присваивал бы адрес, возвращаемый операцией new, указателю ptr в функции insertNodeHelper, а не одному из элементов данных-указателей класса TreeNode.

Добавлено через 29 минут
Спасибо за уделенное время
Yandex
Объявления
24.07.2013, 00:04     Вставка листа в дерево
Ответ Создать тему
Опции темы

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