目錄

成都創(chuàng)新互聯(lián)公司執(zhí)著的堅(jiān)持網(wǎng)站建設(shè)，微信小程序定制開發(fā)；我們不會(huì)轉(zhuǎn)行，已經(jīng)持續(xù)穩(wěn)定運(yùn)營10年。專業(yè)的技術(shù)，豐富的成功經(jīng)驗(yàn)和創(chuàng)作思維，提供一站式互聯(lián)網(wǎng)解決方案，以客戶的口碑塑造品牌，攜手廣大客戶，共同發(fā)展進(jìn)步。

1. 頭文件

2. 完整代碼

3.運(yùn)行結(jié)果及截圖

---

1. 頭文件

#include#include#include#define Rank int

class Bitmap { //位圖Bitmap類：以空間作為補(bǔ)償，節(jié)省初始化時(shí)間（既允許插入，亦支持刪除）
private:
    Rank* F; Rank N; //規(guī)模為N的向量F，記錄[k]被標(biāo)記的次序（即其在棧T[]中的秩）
    Rank* T; Rank top; //容量為N的棧T，記錄被標(biāo)記各位秩的棧，以及棧頂指針
public:
    Bitmap(Rank n = 8) //按指定（或默認(rèn)）規(guī)模創(chuàng)建比特圖（為測(cè)試暫時(shí)選用較小的默認(rèn)值）
    {
        N = n; F = new Rank[N]; T = new Rank[N]; top = 0;
    } //在O(1)時(shí)間內(nèi)隱式地初始化
    ~Bitmap() { delete[] F; delete[] T; } //析構(gòu)時(shí)釋放空間

 // 接口
    inline void reset() { top = 0; } //復(fù)位：從邏輯上切斷所有校驗(yàn)環(huán)，O(1)
    inline void set(Rank k) { //插入：從邏輯上將B[k]置為true，O(1)
        if (!test(k)) { //忽略已帶標(biāo)記的位
            T[top] = k; F[k] = top++; //創(chuàng)建校驗(yàn)環(huán)
        }
    }
    inline void clear(Rank k) { //刪除：從邏輯上將B[k]置為false，O(1)
        if (test(k)) //忽略不帶標(biāo)記的位
            if (--top) { //清除校驗(yàn)環(huán)，同時(shí)回收棧T的空閑單元（留意對(duì)空棧的處理）
                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]; //常規(guī)位圖
    Bitmap M(n); //高效位圖
    while (t-- >0) { //重復(fù)使用位圖多次
        memset(B, 0, n * sizeof(bool)); //逐位清零，O(n)
        M.reset(); //邏輯清零，O(1)
        for (int i = 0; i< 3 * n; i++) { //反復(fù)地
            int k = dice(n); //在隨機(jī)位置上
            if (dice(2)) { //以50%的概率插入
                B[k] = true; M.set(k);
            }
            else { //或50%的概率清除
                B[k] = false; M.clear(k);
            }
        }
        //M.set( 29 ); //有時(shí)可賣個(gè)破綻，以反向測(cè)試本測(cè)試程序
        int k;
        for (k = 0; k< n; k++) //逐位地對(duì)比
            if (B[k] != M.test(k)) //一旦發(fā)現(xiàn)不合
                break; //隨即退出
        if (k< n) { //并報(bào)告（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)); //設(shè)置隨機(jī)種子
    int i = rand() % 50;
    testBitmap(0, i); //啟動(dòng)測(cè)試
    system("pause");
    return 0;
}

3.運(yùn)行結(jié)果及截圖

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)----位圖-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://www.rwnh.cn/article48/ephhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、域名注冊(cè)、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站營銷、虛擬主機(jī)、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)