こんにちは、私は左派のヒープを実装しようとしています。ここに私のヘッダーファイルとヘッダーファイルのソースファイルがあります
#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 として宣言しましたが、それを変更していないので、何が問題なのですか?私はこの関数を定義しようとしていますが、これは私がしたくないことです。同じ問題がルートにもあります。なぜコンパイラは、ルートの値を変更しようとしていると言うのですか? isempthy() 関数は (root==NULL) かどうかをチェックするだけですが、その値は変更されません。混乱しています。const キーワードを削除した場合、コードはコンパイルされますか?コードの主な動作は変更されませんか?私はここに新しく、非常に大きなコードを投稿して申し訳ありませんが、コードをより明確にするために、ヘッダーとソース ファイルを一緒に投稿します作業を簡素化するために、私を助けてください、私はとても良いサイトが存在することを嬉しく思います。
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 ==========