binary_search_list.h

数据结构-二叉树

#include<iostream.h>
template<class type> class dataList;

template<class type> class Node
{
	friend class dataList<type>;
	public:
		Node(const type& value=0):key(value){};
		type getKey()
		{
			return key;
		}
		void setKey(type k)
		{
			key=k;
		}
	private:
		type key;
		//other;
};



template<class type> class dataList
{
	public:
		dataList(int sz=10):ArraySize(sz),Element(new Node<type>[sz]){};
	
	    order_dataList(dataList<type>& LL);
		virtual ~dataList(){delete [] Element;}
		friend ostream &operator <<(ostream &OutStream,const dataList<type> &OutList);
		friend istream &operator >>(istream &InStream,dataList<type> &InList);
		//int Search(const type & x);
	protected:
		Node<type> * Element;
		int ArraySize,CurrentSize;
};




template<class type>ostream & operator <<(ostream & OutStream,const dataList<type> &OutList)
{
	OutStream <<'\n'<<"数组存储情况 : ";
	for(int i=0;i<OutList.CurrentSize;i++)
		OutStream<<OutList.Element[i].getKey()<<' ';
	OutStream<<endl;
	OutStream<<"当前数组大小 :"<<OutList.CurrentSize<<endl;
	return OutStream;
}




template<class type>istream & operator >>(istream & InStream,dataList<type> & InList)
{
	type k;
	cout<<endl<<"指定本次搜索所需空间 : ";
	InStream>>InList.CurrentSize;
	while(InList.CurrentSize>InList.ArraySize)
	{
		cout<<endl<<"对不起！占用空间不能大于已分配的空间 "<<InList.ArraySize<<" : ";
		InStream>>InList.CurrentSize;
	}
	cout<<endl<<"输入关键码 : "<<endl;
	for(int i=0;i<InList.CurrentSize;i++)
	{
		cout<<"第"<<i<<"个关键码 : ";
		InStream>>k;
//------------------------------------------------------------------------------------
//判断是否有关键码重复
		int j=0;
		while(j<i)
		{
			if(InList.Element[j].getKey()==k)
			{
				cout<<"关键码 "<<k<<"已存在,请重新输入 : ";
				InStream>>k;
				j=0;
			}
			else
				j++;
		}
//-------------------------------------------------------------------------------------
		InList.Element[i].setKey(k);	
	}
	return InStream;
}



////////////////////////////////////////////////////////////////////////////////////////
template<class type> dataList<type>::order_dataList(dataList<type>& ll)
{
	int k=ll.CurrentSize;
	for(int p=0;p<k;p++)
	{
		type temp;
		for(int j=p+1;j<k;j++)
		{
			if(ll.Element[p].getKey()>ll.Element[j].getKey())
			{
				temp=ll.Element[p].getKey();
				ll.Element[p].setKey(ll.Element[j].getKey());
				ll.Element[j] .setKey(temp);
			}
		}
	}

}
/////////////////////////////////////////////////////////////////////////////////////////




template <class type> class orderedList:public dataList<type>{
	public:
		orderedList(int sz=10): dataList<type>(sz) {}
		virtual ~orderedList(){};
		virtual int BinarySearch(const type& x);
};



template<class type> int orderedList<type>::BinarySearch(const type& x)
{
	int high=CurrentSize-1,low=0,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(Element[mid].getKey()<x)
			low=mid+1;
		else if(Element[mid].getKey()>x)
			high=mid-1;
		else return mid;
	}
	return -1;
}