ep6_4_0.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
- /* 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]=' ';
- cout<<"缺省构造函数"<<endl;
- }
- mystring(char *s){//当C字符串过长,初始化时采用截尾处理
- last=-1;
- maxsize=n;
- do{
- last++;
- str[last]=s[last];
- }while(s[last]!=' '&&last<maxsize-1);
- str[last] =' '; //截尾处理时,必须加串结束符
- 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]!=' '&&last<maxsize-1);
- str[last] =' '; //截尾处理时,必须加串结束符
- 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;
- }