ep6_4_0.cpp

这里有大量的c语言习题呢！真的是题海哦

/* 6.4  将自定义字符串类用于对半查找的函数模板。*/
//使用成员函数
#include<iostream>
using namespace std;
const int n=256;
class mystring{//为简单只保留用到的函数
	char str[n];        //存放字符串的数组容器
	int maxsize;          //最大可用元素数，可防止数组出界，提高健壮性
	int last;              //已用元素数
public:
	mystring(){
		last=0;
		maxsize=n;
		str[0]='\0';
		cout<<"缺省构造函数"<<endl;
	}
	mystring(char *s){//当C字符串过长，初始化时采用截尾处理
		last=-1;
		maxsize=n;
		do{
			last++;
			str[last]=s[last];
		}while(s[last]!='\0'&&last<maxsize-1);
		str[last] ='\0'; //截尾处理时，必须加串结束符
		cout<<"构造函数"<<endl;
	}
	mystring(mystring & ms){
		last=-1;
		maxsize=n;
		do{
			last++;
			str[last]=ms.str[last];
		}while(last<ms.last);
		cout<<"拷贝构造函数"<<endl;
	}
	~mystring(){
		cout<<"析构函数"<<endl;
	}
	void show(){//如需重载<<，则请参见9.3节，暂时未学到，替代的方法是改用一个show()函数
		cout<<str;
	}
	mystring & operator=(char * ms);//这里重载的=是把C风格字符串赋给mystring
	mystring& operator=(mystring &);
	bool operator<(mystring &);
};
mystring & mystring::operator=(char* ms){ //用C字符串赋值自定义字符串
	last=-1;	
	do{
		last++;
		str[last]=ms[last];
	}while(ms[last]!='\0'&&last<maxsize-1);
	str[last] ='\0'; //截尾处理时，必须加串结束符
	return *this;
}//这里返回值为引用，不调用拷贝构造函数
mystring& mystring::operator=(mystring & ms){
	last=-1;	
	do{
		last++;
		str[last]=ms.str[last];
	}while(last<ms.last);
	cout<<"赋值函数"<<endl;
	return *this;
}
bool mystring::operator<(mystring & ms){
	int i=0,k;
	do{
		k=str[i]-ms.str[i];
		i++;
	}while(k==0&&i<last&&i<ms.last);
	if(k<0) return true;
	if(i==last&&i!=ms.last) return true;
	return false;
}
template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	T slist[size];
public:
	int getlast(){return last;}
	T getslist(int k){return slist[k];}
	void putslist(T t,int k){slist[k]=t;}
	Orderedlist(){last=-1;maxsize=size;}
	bool Insert(T & elem,int i);
	void print();
	int BinarySearch(T);
	// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
	if (i<0||i>last+1||last==maxsize-1) return false;
	else{
		last++;
		for (int j=last;j>i;j--) slist[j]=slist[j-1];
		slist[i]=elem;
		return true;
	}
}
template <typename T,int size> void Orderedlist<T,size>::print(){
	int i;
	for(i=0;i<=last;i++){
		slist[i].show();		
		if(i%5==4) cout<<endl; //打印5个名称换行
		else cout<<'\t';
	}
	cout<<endl;
}
template <typename T,int size> int Orderedlist<T,size>::BinarySearch(T x){//成员函数模板
	int high=last,low=0,mid;  //size当前有序表元素数量
	while(low<=high){
		mid=(low+high)/2;
		if(x<slist[mid])  high=mid-1;  //左缩查找区间，这里只有重载的小于号
		else if(slist[mid]<x) low=mid+1;// 右缩查找区间
		     else return mid;
	}
	return mid;
}

int main(){
	const int h=8;
	int i;
	Orderedlist<mystring,h> ordlist;
	mystring n[h];
	char sp[h][10]={"东南大学","复旦大学","交通大学","南京大学","清华大学",
		"天津大学","同济大学","浙江大学"};	
	for(i=0;i<h;i++)  n[i]=sp[i];
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
	cout<<"排序表："<<endl;
	ordlist.print();	
	mystring x("交通大学"),y("东南大学");
	i=ordlist.BinarySearch(x);
	cout<<i<<endl;
	i=ordlist.BinarySearch(y);
	cout<<i<<endl;
	return 0;
}