0001 class Bitmap { //位图Bitmap类:以空间作为补偿,节省初始化时间(仅允许插入,不支持删除) 0002 private: 0003 Rank* F; Rank N; //规模为N的向量F,记录[k]被标记的次序(即其在栈T[]中的秩) 0004 Rank* T; Rank top; //容量为N的栈T,记录被标记各位秩的栈,以及栈顶指针 0005 0006 protected: 0007 inline bool valid ( Rank r ) { return ( 0 <= r ) && ( r < top ); } 0008 0009 public: 0010 Bitmap ( Rank n = 8 ) //按指定(或默认)规模创建比特图(为测试暂时选用较小的默认值) 0011 { N = n; F = new Rank[N]; T = new Rank[N]; top = 0; } //在O(1)时间内隐式地初始化 0012 ~Bitmap() { delete [] F; delete [] T; } //析构时释放空间 0013 0014 // 接口 0015 inline void set ( Rank k ) { //插入 0016 if ( test ( k ) ) return; //忽略已带标记的位 0017 F[ k ] = top++; T[ F[ k ] ] = k; //建立校验环 0018 } 0019 inline bool test ( Rank k ) //测试 0020 { return valid ( F[ k ] ) && ( k == T[ F[ k ] ] ); } 0021 };