C++数据结构学习----位图-创新互联
目录
成都创新互联公司执着的坚持网站建设,微信小程序定制开发;我们不会转行,已经持续稳定运营10年。专业的技术,丰富的成功经验和创作思维,提供一站式互联网解决方案,以客户的口碑塑造品牌,携手广大客户,共同发展进步。1. 头文件
2. 完整代码
3.运行结果及截图
1. 头文件
#include#include#include#define Rank int
class Bitmap { //位图Bitmap类:以空间作为补偿,节省初始化时间(既允许插入,亦支持删除)
private:
Rank* F; Rank N; //规模为N的向量F,记录[k]被标记的次序(即其在栈T[]中的秩)
Rank* T; Rank top; //容量为N的栈T,记录被标记各位秩的栈,以及栈顶指针
public:
Bitmap(Rank n = 8) //按指定(或默认)规模创建比特图(为测试暂时选用较小的默认值)
{
N = n; F = new Rank[N]; T = new Rank[N]; top = 0;
} //在O(1)时间内隐式地初始化
~Bitmap() { delete[] F; delete[] T; } //析构时释放空间
// 接口
inline void reset() { top = 0; } //复位:从逻辑上切断所有校验环,O(1)
inline void set(Rank k) { //插入:从逻辑上将B[k]置为true,O(1)
if (!test(k)) { //忽略已带标记的位
T[top] = k; F[k] = top++; //创建校验环
}
}
inline void clear(Rank k) { //删除:从逻辑上将B[k]置为false,O(1)
if (test(k)) //忽略不带标记的位
if (--top) { //清除校验环,同时回收栈T的空闲单元(留意对空栈的处理)
F[T[top]] = F[k]; T[F[k]] = T[top];
}
}
inline bool test(Rank k) //从逻辑上判断B[k]是否为true,O(1)
{
return (-1< F[k]) && (F[k]< top) && (k == T[F[k]]);
}
};
2. 完整代码#include#include "Bitmaps.h"
#include "Dice.h"
using namespace std;
int testBitmap(int n, int t) {
bool* B = new bool[n]; //常规位图
Bitmap M(n); //高效位图
while (t-- >0) { //重复使用位图多次
memset(B, 0, n * sizeof(bool)); //逐位清零,O(n)
M.reset(); //逻辑清零,O(1)
for (int i = 0; i< 3 * n; i++) { //反复地
int k = dice(n); //在随机位置上
if (dice(2)) { //以50%的概率插入
B[k] = true; M.set(k);
}
else { //或50%的概率清除
B[k] = false; M.clear(k);
}
}
//M.set( 29 ); //有时可卖个破绽,以反向测试本测试程序
int k;
for (k = 0; k< n; k++) //逐位地对比
if (B[k] != M.test(k)) //一旦发现不合
break; //随即退出
if (k< n) { //并报告(assert:: k == n+1)
cout<< endl<< "B[ ]:" ;//printf("\n B[]: ");
for (int j = 0; j<= k; j++)
B[j] ? (cout<< 'x') : (cout<< ' '); // printf("%6c", B[j] ? 'x' : ' ');
cout<< endl<< "M[ ]:";// printf("\n M[]: ");
for (int j = 0; j<= k; j++)
M.test(j) ? (cout<< 'x') : (cout<< ' ');// printf("%6c", M.test(j) ? 'x' : ' ');
cout<< endl;
}
else
printf("Test %4d OK\n", t);
}
delete[] B;
return 0;
}
int main() {
srand((unsigned int)time(NULL)); //设置随机种子
int i = rand() % 50;
testBitmap(0, i); //启动测试
system("pause");
return 0;
}
3.运行结果及截图你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站标题:C++数据结构学习----位图-创新互联
标题来源:http://scyanting.com/article/ephhp.html