Реализация левой кучи в с ++

Question

Реализация левой кучи в с ++

Добрый день, я пытаюсь реализовать левую кучу, вот мой заголовочный файл и исходный файл для заголовочного файла

#include<iostream>
template<class comparable>
class leftistheap;

template<class comparable>
class leftistnode
{
    comparable element;
    leftistnode *left;
    leftistnode *right;
    int  npl;
    leftistnode(const comparable  &theelement,leftistnode *lt=NULL,leftistnode *rt=NULL,int np=0):element(thelement),left(lt),right(rt),npl(np){}
    friend class leftistheap<comparable>;
    };
template<class comparable>
class leftistheap
{
public:
    leftistheap();
    leftistheap (const leftistheap &rhs);
    ~leftistheap();
    bool isempthy()const ;
    bool isfull() const;
    const comparable &findmin() const;
    void insert(const comparable &x);
    void deletemin();
    void deletemin(comparable &minitem);
    void makeempthy();
    void merge(leftistheap &rhs);

    const leftistheap & operator=(const leftistheap &rhs);
private:
    leftistnode<comparable>*root;
    leftistnode<comparable>*merge(leftistnode<comparable>*h1,leftistnode<comparable>*h2)const;
     leftistnode<comparable> * merge1( leftistnode<comparable> *h1,
                                              leftistnode<comparable> *h2 ) const;
            void swapchildren( leftistnode<comparable> * t ) const;
            void reclaimmemory( leftistnode<comparable> * t ) const;
            leftistnode<comparable> * clone( leftistnode<comparable> *t ) const;
        };

и исходный файл

#include<iostream>
#include "leftist.h"
using namespace std;
template<class comparable>
leftistheap<comparable>::leftistheap()
{
    root=NULL;
}
template<class comparable>
leftistheap<comparable>::leftistheap(const leftistheap<comparable>&rhs)
{
    root=NULL;
    *this=rhs;
}
template<class comparable>
leftistheap<comparable>::~leftistheap()
{
    makeempthy();
}
template<class comparable>
void leftistheap<comparable>::merge(leftistheap &rhs)
{
    if(this==&rhs)
         return;
    root=merge(root,rhs.root);
    rhs.root=NULL;

}
template<class comparable>
leftistnode<comparable>*leftistheap<comparable>::merge(leftistnode <comparable>*h1,leftistnode<comparable>*h2)const
{

    if(h1==NULL)
         return h2;
    if(h2==NULL)
         return h1;
    if(h1->element<h2->element)
        return merge1(h1,h2);
    else
        return merge1(h2,h1);


}

template<class comparable>
leftistnode<comparable>*leftistheap<comparable>::merge1(leftistnode<comparable>*h1,leftistnode<comparable>*h2)const
{

    if(h1->left==NULL)
        h1->left=h2;
    else
    {

        h1->right=merge(h1->right,h2);
        if(h1->left->npl<h1->right->npl)
            swapchildren(h1);
        h1->npl=h1->right->npl+1;






    }
     return h1;

}
template<class comparable>
void leftistheap<comparable>::swapchildren(leftistnode<comparable>*t)const
{
    leftistnode<comparable> *temp=t->left;
    t->left=t->right;
    t->right=emp;


}
template<class comparable>
void leftistheap<comparable>::insert(const comparable &x)
{
    root=merge(new leftistnode<comparable>(x),root);

}
template<class comparable>
const comparable &leftistheap<comparable>::findmin()const
    {
         if(isempty())
             throw Underflow();
    return root->element;


}
template<class comparable>
void leftistheap<comparable>::deletemin()
{
    if(isempty())
         throw Underflow();
    leftistnode<comparable>*oldroot=root;
    root=merge(root->left,root->right);
    delete oldroot;


}
template<class comparable>
void leftistheap<comparable>::deletemin(comparable & minitem)
{
    minitem=findmin();
    deletemin();

}
template<class comparable>
bool leftistheap<comparable>::isempthy() const
{


return root=NULL;
}
template<class comparable>
bool leftistheap<comparable>::isfull( ) const
        {
            return false;
        }

template <class comparable>
void leftistheap<comparable>::makeempthy()
        {
            reclaimmemory( root );
            root = NULL;
        }
        template<class comparable>
        const leftistheap<comparable>& leftistheap<comparable >::operator=(const leftistheap<comparable>& rhs)
        {
            if(this != &rhs)
            {
            makeempthy();
            root=clone(rhs.root);

            }
            return *this;
        }
        template<class comparable>
        void leftistheap<comparable>::reclaimmemory(leftistnode<comparable>*t) const
        {
            if(t!=NULL)
            {
                reclaimmemory(t->left);
                reclaimmemory(t->right);
                 delete t;


            }


        }
        template<class comparable>
        leftistnode<comparable>*leftistheap<comparable>::clone(leftistnode<comparable> *t)const
        {

            if(t==NULL)
                 return NULL;
            else
                return new leftistnode<comparable>( t->element, clone( t->left ),
                                              clone( t->right ), t->npl );
        }


int main()
{
    int numitems=100;
    leftistheap<int>h;
    leftistheap<int>h1;
    leftistheap<int>h2;
    int i=37;
    for(i=37;i!=0;i=(i+37)%numitems)
        if(i%2==0)
            h1.insert(i);
        else
            h.insert(i);
    h.merge(h1);
    h2=h;
     for( i = 1; i < numitems; i++ )
            {
                int x;
                h2.deletemin( x );
                if( x != i )
                    cout << "Oops! " << i << endl;
            }

            if (! h1.isempthy( ) )
                cout << "Oops! h1 should have been empty!" << endl;


    return 0;
}

но я получаю эти ошибки, пожалуйста, помогите мне, почему эти ошибки? Я объявил функции как const, но я не изменяю это, так в чем проблема? Я пытаюсь просто определить эти функции, и это все, что я хочу делать, та же проблема также с root, почему компилятор говорит, что я пытаюсь изменить значение root?isempthy() функция просто проверяет, если (root==NULL), но не меняет его значение, так что я действительно Я не уверен, что это изменит мой основной код. Я новичок здесь и прошу прощения за публикацию такого большого кода, но чтобы сделать код более четким, я постил заголовок и исходный файл вместе для упрощения задачи, пожалуйста, помогите мне, ребята, я рад, что существует такой хороший сайт. Я был бы рад, если вы получите помощь от вас, ошибки:

2010\projects\leftist_heap\leftist_heap\leftist_heap.cpp(115): error C3490: 'root' cannot be modified because it is being accessed through a const object
1>          2010\projects\leftist_heap\leftist_heap\leftist_heap.cpp(112) : while compiling class template member function 'bool leftistheap<comparable>::isempthy(void) const'
1>          with
1>          [
1>              comparable=int
1>          ]
1>          2010\projects\leftist_heap\leftist_heap\leftist_heap.cpp(169) : see reference to class template instantiation 'leftistheap<comparable>' being compiled
1>          with
1>          [
1>              comparable=int
1>          ]
1>2010\projects\leftist_heap\leftist_heap\leftist_heap.cpp(115): warning C4800: 'leftistnode<comparable> *const ' : forcing value to bool 'true' or 'false' (performance warning)
1>          with
1>          [
1>              comparable=int
1>          ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

-2

c++ leftist-tree

Источник

user1649103 05 сен '12 в 13:07

2 ответа

Решение

template<class comparable>
bool leftistheap<comparable>::isempthy() const
{


return root=NULL;
}

это ваша проблема - const после метода означает, что он не будет изменять состояние объекта, но делает это путем изменения значения root.

3

Источник

user842543 05 сен '12 в 13:11

Другие вопросы по тегам c++ leftist-tree

user733152 05 сен '12 в 13:11 2012-09-05 13:11 · Accepted Answer · 2012-09-05 13:11

Измените реализацию вашего isempty функция-член to (логика - проверить, пусто дерево или нет):

template<class comparable>
bool leftistheap<comparable>::isempthy() const
{
return root==NULL;
}

5

Источник

user733152 05 сен '12 в 13:11