ep6_4_0.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /* 6.4  将自定义字符串类用于对半查找的函数模板。*/
  2. //使用成员函数
  3. #include<iostream>
  4. using namespace std;
  5. const int n=256;
  6. class mystring{//为简单只保留用到的函数
  7. char str[n];        //存放字符串的数组容器
  8. int maxsize;          //最大可用元素数,可防止数组出界,提高健壮性
  9. int last;              //已用元素数
  10. public:
  11. mystring(){
  12. last=0;
  13. maxsize=n;
  14. str[0]='';
  15. cout<<"缺省构造函数"<<endl;
  16. }
  17. mystring(char *s){//当C字符串过长,初始化时采用截尾处理
  18. last=-1;
  19. maxsize=n;
  20. do{
  21. last++;
  22. str[last]=s[last];
  23. }while(s[last]!=''&&last<maxsize-1);
  24. str[last] =''; //截尾处理时,必须加串结束符
  25. cout<<"构造函数"<<endl;
  26. }
  27. mystring(mystring & ms){
  28. last=-1;
  29. maxsize=n;
  30. do{
  31. last++;
  32. str[last]=ms.str[last];
  33. }while(last<ms.last);
  34. cout<<"拷贝构造函数"<<endl;
  35. }
  36. ~mystring(){
  37. cout<<"析构函数"<<endl;
  38. }
  39. void show(){//如需重载<<,则请参见9.3节,暂时未学到,替代的方法是改用一个show()函数
  40. cout<<str;
  41. }
  42. mystring & operator=(char * ms);//这里重载的=是把C风格字符串赋给mystring
  43. mystring& operator=(mystring &);
  44. bool operator<(mystring &);
  45. };
  46. mystring & mystring::operator=(char* ms){ //用C字符串赋值自定义字符串
  47. last=-1;
  48. do{
  49. last++;
  50. str[last]=ms[last];
  51. }while(ms[last]!=''&&last<maxsize-1);
  52. str[last] =''; //截尾处理时,必须加串结束符
  53. return *this;
  54. }//这里返回值为引用,不调用拷贝构造函数
  55. mystring& mystring::operator=(mystring & ms){
  56. last=-1;
  57. do{
  58. last++;
  59. str[last]=ms.str[last];
  60. }while(last<ms.last);
  61. cout<<"赋值函数"<<endl;
  62. return *this;
  63. }
  64. bool mystring::operator<(mystring & ms){
  65. int i=0,k;
  66. do{
  67. k=str[i]-ms.str[i];
  68. i++;
  69. }while(k==0&&i<last&&i<ms.last);
  70. if(k<0) return true;
  71. if(i==last&&i!=ms.last) return true;
  72. return false;
  73. }
  74. template <typename T,int size>class Orderedlist{
  75. int maxsize;
  76. int last;
  77. T slist[size];
  78. public:
  79. int getlast(){return last;}
  80. T getslist(int k){return slist[k];}
  81. void putslist(T t,int k){slist[k]=t;}
  82. Orderedlist(){last=-1;maxsize=size;}
  83. bool Insert(T & elem,int i);
  84. void print();
  85. int BinarySearch(T);
  86. // 无关成员函数省略,缺省的=等不必定义
  87. };//再次指出分号不可少
  88. template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
  89. if (i<0||i>last+1||last==maxsize-1) return false;
  90. else{
  91. last++;
  92. for (int j=last;j>i;j--) slist[j]=slist[j-1];
  93. slist[i]=elem;
  94. return true;
  95. }
  96. }
  97. template <typename T,int size> void Orderedlist<T,size>::print(){
  98. int i;
  99. for(i=0;i<=last;i++){
  100. slist[i].show();
  101. if(i%5==4) cout<<endl; //打印5个名称换行
  102. else cout<<'t';
  103. }
  104. cout<<endl;
  105. }
  106. template <typename T,int size> int Orderedlist<T,size>::BinarySearch(T x){//成员函数模板
  107. int high=last,low=0,mid;  //size当前有序表元素数量
  108. while(low<=high){
  109. mid=(low+high)/2;
  110. if(x<slist[mid])  high=mid-1;  //左缩查找区间,这里只有重载的小于号
  111. else if(slist[mid]<x) low=mid+1;// 右缩查找区间
  112.      else return mid;
  113. }
  114. return mid;
  115. }
  116. int main(){
  117. const int h=8;
  118. int i;
  119. Orderedlist<mystring,h> ordlist;
  120. mystring n[h];
  121. char sp[h][10]={"东南大学","复旦大学","交通大学","南京大学","清华大学",
  122. "天津大学","同济大学","浙江大学"};
  123. for(i=0;i<h;i++)  n[i]=sp[i];
  124. for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
  125. cout<<"排序表:"<<endl;
  126. ordlist.print();
  127. mystring x("交通大学"),y("东南大学");
  128. i=ordlist.BinarySearch(x);
  129. cout<<i<<endl;
  130. i=ordlist.BinarySearch(y);
  131. cout<<i<<endl;
  132. return 0;
  133. }