ex6_15.cpp

纯粹是学习专用～

#include<iostream.h>

template <typename T>class Node{
	T  key;
	// 其他域省略
public:
	void putkey(T k){key=k;}
	T GetNodekey()const{return key;}//注意这里加了const
};//再次指出分号不可少
template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	Node<T> slist[size];
public:
	Orderedlist(){last=-1;maxsize=size;}
	T getkey(int i)const{return slist[i].GetNodekey();}//注意这里加了const
	int BinarySearch(const T & x)const;//注意这里加了const,凡它调用的函数都有const
	bool Insert(Node<T> & elem,int i);
	// 无关成员函数省略
};//再次指出分号不可少
template <typename T,int size> bool Orderedlist<T,size>::Insert(Node<T> & elem ,int i){
	if (i<0||i>last+1||last==maxsize-1) return false;
	else{
		for (int j=last;j>i;j--) slist[j]=slist[j-1];
		slist[i]=elem;
		last++;
		return true;
	}
}
template <typename T,int size> int Orderedlist<T,size>::BinarySearch(const T & x)const{
	int high=last ,low=0,mid;  // last 当前有序表最大下标
	while(low<=high){
		mid=(low+high)/2;
		if(getkey(mid)>x)  high=mid-1;  //左缩查找区间
		else if(getkey(mid)<x) low=mid+1;// 右缩查找区间
		     else return mid;
	}
	return mid;
}

void main(){
	const int h=19;
	int i,k=47;
	Orderedlist<int,100> ordlist;
	int a[h]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
	Node<int> n[h];
	for(i=0;i<h;i++)  n[i].putkey(a[i]);
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立升序顺序表
	i=ordlist.BinarySearch(k);
	cout<<"系数47在表中位置（下标）："<<i<<endl;
}