【说明】 设计一个类模板SamPle用于对一个有序数组采用二分法查找元素下标。 【C++程序】 #include ＜ iostream. h ＞ #define Max 100//最多元素个数 template ＜ class T ＞ class Sample { T A[Max]: //存放有序数序 int n: //实际元素个数 public Sample( ) { } //默认构造函数 Sample(T a[] ,int i); //初始化构造函数 int seek(T c); void disp( ) { for(int i=0;i ＜n;i ++) cout＜＜A[i] ＜＜" "; cout＜＜endl: } } template ＜ class T ＞ Sample ＜T＞: :Sample(T a[ ],int i) { n=i: for( intj =0;j ＜ i;j ++ ) (1) ; } template ＜ class T ＞ int Sample ＜ T ＞:: seek( T c) { int low =0,high = n-1 ,mid; while( (2) ) { mid = (low + high)/2; if( (3) ) return mid; else if( (4) ) low=mid+|; else (5) ; } return-1; } void main( ) { char a[ ] ="acegkmpwxz"; Sample ＜ char ＞ s(a, 1); cout＜＜"元素序列:" ;s. disp( ); cout＜＜"元素’g’的下标:"＜＜s. seek(’g’) ＜＜endl; }
参考答案：
解析：(1)A[j]=a[j] (2)low＜=high (3)A[mid]==c (4)A[mid]＜c (5)high=mid-1 在主函数中，首先由类模板实例化成Sample＜char＞模板类。(1)空所在处为构造函数的声明，将参数中的值赋值到类的成员变量中，所以(1)空应填入“A[j]=a[j]”。 成员函数seek()采用二分法查找元素下标，变量low和high分别表示查找区间的下标，如果查询到目标，则返回相应的下标，若没有查询到，则其结束的条件即(2)空的内容为“low＜=high”。根据二分法的原理，当中间的元素恰好等于目标元素时，则返回其下标，所以(3)空应填入“A[mid] ==c”；若中间的元素小于目标元素时，则mid+1作为新的查找区间的起始下标，所以(4)空应填入“A[mid]＜c”；否则mid-1作为新的查找区间的结束下标，所以(5)空应填入“high=mid-1”。