mtree.cpp

这些程序是本人学习数据结构时编的

// Mtree.cpp: implementation of the Mtree class.
//
//////////////////////////////////////////////////////////////////////

#include "Mtree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

template<class Type>
Mnode<Type>::Mnode(int m)
{
	n = 0;
	parent = NULL;
	key = new Type [m+1];
	ptr = new Mnode<Type>* [m+1];
	num = new int [m+1];
	if (!key || !ptr || !num)
	{
		cout<<"error on Mnode constructing"<<endl;
		exit(1);
	}
	for (int i = 0; i<m+1; i++)
		ptr[i] = NULL;
}

template<class Type>
Mnode<Type>::~Mnode()
{
	delete [] key;
	delete [] *ptr;
	delete [] num;
}

////////////////////////////////////////////////////////////////////////////
template<class Type>
Mtree<Type>::Mtree()
{
	cout<<"输入m:\n";
	cin>>m;
	root = new Mnode<Type>(m);
	if (!root)
	{
		cout<<"error on Mtree constructing"<<endl;
		exit(1);
	}
	cout<<"输入MAXKEY:\n";
	cin>>MAXKEY;
}

template<class Type>
Mtree<Type>::~Mtree()
{

};

template<class Type>
Triple<Type>& Mtree<Type>::Search (const Type& x)
{
	Triple<Type> result;						//记录搜索结果三元组
	int i=0;
	Mnode<Type> * p = root , * q = NULL;
	while( p != NULL)							//从根开始检测
	{
		i = 0; 
		p-> key[( p ->n) +1 ] = MAXKEY;
		while ( p ->key [i+1] < x) i ++;		//结点内搜索
		if ( p-> key[i+1] == x)					//搜索成功
		{
			result.r = p ; result.i = i+1; result.tag = 0;
			return result;
		}
		q = p ; p = p-> ptr[i];
	}
	result. r = q ; result.i = i + 1 ; result.tag = 1;
	return result;
};