大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

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://dzwzjz.com/article/ephhp.html
在线咨询
服务热线
服务热线:028-86922220
TOP