ДЕРЕВО AVL в C++
У меня есть проблема с этим очень простым блоком кода. дайте мне свой совет. (Моя эта проблема решена, и в решении этой проблемы, человек, имеющий идентификатор stakx действительно, помог мне, единственная проблема состояла в том, что я использовал стек
перед кодом Вам нужно к suppse следующее дерево
сопроводительный текст http://img44.imageshack.us/img44/7016/avlimage06.jpg
поскольку Вы видите в изображении, что корень равняется 8, и стек имеют два узла т.е. 6 и 4. я передаю этот стек и корневой узел к следующему коду
void Avltree::attachwithtree(treeNode* tree, Stack&s)
{
if(!s.isempty())
{
treeNode *stacknode;
stacknode=s.pop();
cout<<"\ninside the attachwithtree function, stack node is "<data;
stacknode->right=tree;//attaching the passed node to the right of popped node
root=stacknode;//setting the root to stack node which is the private data member of class
updatebalance(root);//this function is ok, it does not create problem
while(!s.isempty())
{
cout<<"\nstack is still not empty";
stacknode=s.pop();
cout<<"\nright side of "<data<<" is "<<(root->right)->data;
//the below three lines causing the problem i don't know why,
root=stacknode;
treeNode* temp;
temp=root->right;
cout<<"\n\n\nthe right side of "<data<<" is now "<<(temp->right)->data;
updatebalance(root);
}
ouptput этой функции дают 
вот код поп-метода стека, который я использую
template
t * Stack::pop()
{
if(topelement!=NULL)
{
t* num;
current=topelement;
num=&(current->object);
topelement=topelement->preptr;
current=topelement;
return(num);
}
else
{
head=NULL;
}
}
вот код метода нажатия стека
template
void Stack::push(t &number)
{
Node* newNode=new Node;
if(head==NULL)
{
head=newNode;
topelement=newNode;
current=newNode;
head->object=number;
head->preptr=NULL;
}
else
{
topelement=newNode;
newNode->preptr=current;
current=topelement;
newNode->object=number;
}
}
2 ответа
Оригинальный ответ:
Может ли это быть что узел 4 на стеке имеет другой узел 6 к его правой (тот, один с узлом 7 справа), чем у узла 6 (с узлом 8 С его стороны) вы работаете? Вы можете сравнить их адреса, чтобы убедиться, что у вас нет двух разных копий узла 6 .
Разработка приведенного выше аргумента:
Давайте посмотрим на подпись вашего метода:
void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)
S определяется как ссылка на стек .
Может быть, что он должен быть стек ?
в зависимости от вашего класса TREENODE , возможно, что при нажатии x ] В этом стеке вы на самом деле заканчиваете копию x , а не x сам. Точно так же, когда вы попьете из стека, вы, возможно, не на самом деле не получите элемент, который вы нажали, но идентично выглядящую его копию!?
Это будет означать, что в то время, когда вы нажимаете узел 6 на стеке его правый ребенок является узлом 7 . Но вы нажали новый, идентичный узел в стеке. Даже если вы попмете этот элемент из стека и измените его, вы меняйте только копию и оставляете только оригинальный узел дерева, как это было раньше.
Следовательно, вы бы работаете на разных копиях узла 6 . Во-первых, вы поп-копию его из стека, и добавьте дерево в качестве своего правого ребенка. Проверка этого даст правильный результат.
Затем вы поп-копию узла 4 из стека. Это правый ребенок узел 6 , как и ожидалось, , но не тот, который вы просто изменяли, но оригинал! Поэтому вы получаете 7 на правой стороне узла 6 .
Продемонстрируя разницу между Pass-Value и Pass-Restional:
Хорошо, вот-то вы должны понимать при работе с указателями или ссылками. Он в основном показывает разницу между прохождением параметра по значению (будет создан копию) или передает ее посредством ссылки (копия не будет создана).
Внимательно изучите его, а затем посмотрите, как оно относится к вашей проблеме.
#include <iostream>
class someObject
{
private:
int _value;
public:
someObject(int value) : _value(value) { }
int getValue()
{
return _value;
}
};
void someFunction(someObject objCopy, someObject* objPtr)
{
std::cout << "objCopy.getValue() -> " << objCopy.getValue() << std::endl;
std::cout << "objPtr->getValue() -> " << objPtr->getValue() << std::endl;
if ( &objCopy != objPtr )
{
std::cout << "objCopy is not actually *objPtr but a copy of it." << std::endl;
}
else
{
std::cout << "objCopy and *objPtr are one and the same object." << std::endl;
}
}
int main()
{
someObject X(17);
someFunction(X, &X);
return 0;
}
Подсказка : Да, в вашем методе POP , вы работаете с указателями, но, скорее всего, с указателем на копию объекта, изначально нажатой на стек.
Если они не обязательно должны быть случайными, но просто не явно линейными (1, 2, 3, 4,...), то вот простой алгоритм:
Выберите два простых числа. Одна из них будет самой большой, которую вы можете генерировать, так что она должна быть около одного миллиарда. Другой должен быть довольно большим.
max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
previous_serial += step
previous_serial %= max_value
print "Serial: %09i" % previous_serial
Просто храните предыдущий серийный каждый раз, чтобы вы знали, где вы ушли. Я не могу доказать математически, что это работает (слишком долго с тех конкретных классов), но это явно правильно с меньшими простыми числами:
s = set()
with open("test.txt", "w+") as f:
previous_serial = 0
for i in xrange(0, 2711):
previous_serial += 1811
previous_serial %= 2711
assert previous_serial not in s
s.add(previous_serial)
Вы также можете доказать это эмпирически с 9-значными простыми числами, это просто займет немного больше работы (или много больше памяти).
Это означает, что, учитывая несколько серийных номеров, можно было бы выяснить, каковы ваши значения - но только с девятью цифрами, маловероятно, что вы все равно идете за невыясненными числами.
-121--1210162-Нужно ли это, чтобы быть криптографически безопасным или просто трудно угадать? Насколько плохи столкновения? Потому что если он должен быть криптографически сильным и иметь нулевые столкновения, это, к сожалению, невозможно.
-121--1210156-Это ваш собственный класс Stack? Быстрый взгляд на STL говорит мне, что pop () имеет возвращаемый тип void.
Может быть, что ставка на что-то здесь. Если функция pop () возвращает копию верхнего элемента, а не ссылку на него, внесенные изменения будут применяться только к копии. Добавить копию обратно в дерево в явном виде после ее изменения?