一个有序表可以看成是一个已按关键字排序的有序集. 表的最后添增设了一个被称作哨兵的元素, 关键字为INF. 若表长为n, 需要在l[n]位置存放哨兵元素. 增加哨兵元素以后, 在for循环中不再需要通过下标来判定是否已经查完整个表. 当表中l[i]的关键字值大于等于指定元素x的关键字时, for循环结束. 搜索失败的平均搜索长度: n / 2 + 2. 实现代码: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "assert.h" using namespace std; const int MAXN = 9999; enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent }; template <class T> class DynamicSet { public: virtual ResultCode Search(T &x) const = 0; // 表中搜索与x关键字相同的元素, 若存在则赋值给x并且返回Success, 否则返回NotPresent virtual ResultCode Insert(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Duplicate, 若表已满返回Overflow, 若表未满返回Success virtual ResultCode Remove(T &x) = 0; // 表中搜索与x关键字相同的元素, 若存在该元素, 赋值给x返回Success, 否则返回NotPresent virtual bool IsEmpty() const = 0; // 集合为空返回true virtual bool IsFull() const = 0; // 集合为满返回true /* data */ }; template <class T> class ListSet: public DynamicSet<T> { public: ListSet( int mSize ); ~ListSet() { delete []l; } bool IsEmpty() const { return n == 0; } bool IsFull() const { return n == maxSize; } ResultCode Search(T &x) const; ResultCode Insert(T &x); ResultCode Remove(T &x); void Print(); private: T *l; int maxSize, n; /* data */ }; template <class T> void ListSet<T>::Print() { for(int i = 0; i < n; ++i) cout << l[i] << "\t"; cout << endl; } template <class T> ListSet<T>::ListSet(int mSize) { maxSize = mSize; l = new T[maxSize]; n = 0; } template <class T> ResultCode ListSet<T>::Insert(T &x) { assert(!IsFull()); l[n++] = x; l[n] = MAXN; return Success; } template <class T> ResultCode ListSet<T>::Remove(T &x) { } template <class T> ResultCode ListSet<T>::Search(T &x) const { for(int i = 0; l[i] <= x; ++i) if(l[i] == x) { x = l[i]; return Success; } return NotPresent; } int main(int argc, char const *argv[]) { ListSet<int> ls(20); int x = 11; ls.Insert(x); x = 22; ls.Insert(x); x = 33; ls.Insert(x); x = 44; ls.Insert(x); x = 88; ls.Insert(x); x = 100; ls.Insert(x); ls.Print(); x = 88; if(ls.Search(x) == Success) cout << "Found " << x << endl; else cout << "Not Found " << x << endl; return 0; } ~~~