#include "iostream.h"#ifndef MAXKEY#define MAXKEY 32767#endif		const MaxM=100;		template <class Type> class Mtree;		template <class Type> class Btree;		template <class Type> class Mnode {					// B_樹結點類定義		public:			void insertkey(int,Type,Mnode<Type>*);			Mnode(){n=0;parent=NULL;for (int i=0;i<=MaxM;i++) ptr[i]=NULL;}		private:		   int n;									//當前結點中關鍵碼個數		   Mnode<Type> *parent;						//雙親結點指針		   Type key[MaxM+1];								//key[MaxM]為監視哨兼工作單元, key[0]未用		   Mnode<Type> *ptr[MaxM+1];						//子樹結點指針數組, ptr[m]未用		   friend ostream& operator <<(ostream& strm, Mnode<Type>& mn);		   friend class Mtree<Type>;		   friend class Btree<Type>;		};				template <class Type>		class Triple {								//搜索結果		public:		   Mnode<Type> *r;							//B_樹結點地址		   int i;  char tag;							//結點中關鍵碼序號及搜索成功標志		   friend ostream& operator <<(ostream& strm, Triple<Type>& tp);		};		template <class Type> class Mtree {                 		public:		   Mtree(int d=3){root=NULL;m=d;};		   		   void insertkey(Mnode<Type>*,int,Type,Mnode<Type>*);		   Triple<Type>  Search ( const Type & );		   friend ostream& operator <<(ostream& strm, Mtree<Type>& mt);		protected:			void move ( Mnode<Type>*p, Mnode<Type>*q, int s, int m );			void print(ostream& strm,Mnode<Type> *p);		   Mnode<Type> *root;		   int m;		};		template <class Type> Triple<Type>  Mtree<Type>::Search ( const Type & x ) {		//用關鍵碼x搜索駐留在磁盤上的m路搜索樹。各結點格式為n, A[0], (k[1],A[1]),……,  (K[n],A[n]), n < m。		//函數返回一個類型為Triple (r, i, tag)的對象。tag=1, 表示x 在結點r找到, 是該結點的K[i];  tag=0, 表		//示沒有找到x, 這時可以插入的結點是r, 插入到該結點的K[i]與K[i+1]之間。		   Triple<int> result;							//存放結果的工作單元		   GetNode ( root );						//從磁盤上讀取位于根root的結點		   Mnode <Type> *p = root, *q = NULL;			//p是掃描指針, q是p的父結點指針		   int i;		   while ( p != NULL ) {						//繼續搜索			 i = 0;  p->key[(p->n)+1] = MAXKEY;			 while ( p->key[i+1] < x ) i++;				//在結點內順序搜索			 if ( p->key[i+1] == x ) {					//搜索成功, 本結點有x				result.r = p;  result.i = i+1;  result.tag = 0;				return result;					//返回結果, 返回主程序			 }			 q = p;  p = p->ptr[i];					//本結點無x, q記下當前結點, p下降到相應子樹			 GetNode (p);							//從磁盤上讀取p結點		   }		   result.r = q;  result.i = i;  result.tag = 1;		   return result;							//x可能落入的區間[ Ki, Ki+1 )		}		template <class Type> class Btree : public Mtree<Type> {		//B_樹的類定義		public:		   //Search從Mtree繼承;		   int Insert ( const Type& x );						//插入關鍵碼x		   int Remove ( const Type& x );					//刪除關鍵碼x		private:				void LeftAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j );		void RightAdjust ( Mnode<Type> *p, Mnode<Type> *q, const int d, const int j );		void compress ( Mnode<Type> *p, const int j );		void merge ( Mnode<Type> *p, Mnode<Type> *q, Mnode<Type> *p1, int j) ;		};		template <class Type>			void GetNode(Mnode<Type> *p)		{			//理論上應該從磁盤讀入結點p,現在這里可以為空		};				template <class Type>			void PutNode(Mnode<Type> *p)		{			//理論上應該從磁盤寫結點p,現在這里可以為空		};				template <class Type>			void Mtree<Type>::print(ostream& strm,Mnode<Type> *p)		{			if (p)			{					strm<<*p;			if (p->n)			{	strm<<"(";				for (int i=0;i<=p->n;i++)									print(strm,p->ptr[i]);							strm<<")";			}			}		}		template <class Type>		ostream& operator <<(ostream& strm, Mtree<Type>& mt)		{			mt.print(strm,mt.root);			return strm;		}		template <class Type>		ostream& operator <<(ostream& strm, Mnode<Type>& mn)		{			strm<<"[";			for (int i=1;i<=mn.n;i++)			{				if (i!=1) strm<<',';				strm<<mn.key[i];			}			strm<<"]";			return strm;					}	template <class Type>	 ostream& operator <<(ostream& strm, Triple<Type>& tp)	{		if (tp.tag) strm<<"Key Not Found";			else			strm<<"Key Found at :"<<*tp.r<<" No. "<<tp.i<<" key";		return strm;	}	template <class Type>		void Mnode<Type>::	insertkey(int i,Type K,Mnode<Type>* q)	{		for (int j=n;j>=i;j--)		{			key[j+1]=key[j];			ptr[j+1]=ptr[j];		}		key[i]=K;		ptr[i]=q;		n++;	};	template <class Type>		void Mtree<Type>::	insertkey(Mnode<Type>* p,int i,Type K,Mnode<Type>* q)	{		p->insertkey(i,K,q);	}	template <class Type>		void Mtree<Type>::move ( Mnode<Type>*p, Mnode<Type>*q, int s, int m )	//將 p的key[s+1..m]和ptr[s..m]移到q的key[1..s-1]和ptr[0..s-1]	//p->n改為s, q->n改為m-s	{		int j=0;		q->ptr[0]=p->ptr[s];		if (q->ptr[0])			q->ptr[0]->parent=q; 		for (int i=s+1;i<=m;i++)		{			j++;			q->key[j]=p->key[i];			q->ptr[j]=p->ptr[i];			if (q->ptr[j])				q->ptr[j]->parent=q;		}		q->n=m-s;		p->n=s-1;	}