ListSet_对半搜索的迭代算法
最后更新于：2022-04-01 20:51:44
递归函数效率低, 常使用相应的迭代算法.
mid, left, right均为元素下标, 如果当前表不为空, 则令x与l[mid]比较. 若两者相等, 则搜索成功. 若前者小于后者, 则继续查找左半部分, 否则查找右半部分. 下标范围分别为[left, mid - 1], [mid + 1, right]. 如果当前搜索表为空表, 搜索失败返回NotPresent.
实现代码:
~~~
#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 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 ListSet: public DynamicSet
{
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
void ListSet::Print()
{
for(int i = 0; i < n; ++i)
cout << l[i] << "\t";
cout << endl;
}
template
ListSet::ListSet(int mSize)
{
maxSize = mSize;
l = new T[maxSize];
n = 0;
}
template
ResultCode ListSet::Insert(T &x)
{
assert(!IsFull());
l[n++] = x;
l[n] = MAXN;
return Success;
}
template
ResultCode ListSet::Remove(T &x)
{
}
template
ResultCode ListSet::Search(T &x) const
{
int mid, left = 0, right = n -1;
while(left <= right) {
mid = (left + right) / 2;
if(x < l[mid]) right = mid - 1;
else if(x > l[mid]) left = mid + 1;
else {
x = l[mid];
return Success;
}
}
return NotPresent;
}
int main(int argc, char const *argv[])
{
ListSet ls(20);
int x = 21; ls.Insert(x);
x = 30; ls.Insert(x);
x = 36; ls.Insert(x);
x = 41; ls.Insert(x);
x = 52; ls.Insert(x);
x = 54; ls.Insert(x);
x = 66; ls.Insert(x);
x = 72; ls.Insert(x);
x = 83; ls.Insert(x);
x = 97; ls.Insert(x);
ls.Print();
x = 35;
if(ls.Search(x) == Success) cout << "Found " << x << endl;
else cout << "Not Found " << x << endl;
return 0;
}
~~~
';