ex6_14.cpp

纯粹是学习专用～

#include<iostream.h>

template <typename T>struct Node{
	T  key;
	// 其他域省略
};//再次指出分号不可少
template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	Node<T> slist[size];
public:
	Orderedlist(){last=-1;maxsize=size;}
	int Binarysearch(const T & x,const int low,const int high);
	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 low,const int high){  // x为定值
	int mid=-1;
	if (low<=high){
		mid=(low+high)/2;
		if(slist[mid].key<x) mid=Binarysearch(x,mid+1,high);
		//中间点小于定值，查找右区间，注意mid+1
		else if(slist[mid].key>x) mid=Binarysearch(x,low,mid-1);
		//中间点大于定值，查找左区间，注意 mid-1
	}
	return mid ;  // 找到返回下标，未找到但结束了，返回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].key=a[i];
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立升序顺序表
	i=ordlist.Binarysearch(k,1,19);
	cout<<"系数47在表中位置（下标）："<<i<<endl;
}