C++如何實現BitMap數據結構

更新時間：2022年07月22日 15:23:09 作者：yanerhao

這篇文章主要介紹了C++如何實現BitMap數據結構，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

一、BitMap位圖

該數據結構描述了一個有限定義域內的稠密集合，其中的每一個元素最多出現一次并且沒有其他任何數據與該元素相關聯。

即使這些條件沒有完全滿足（例如，存在重復元素或額外的數據），也可以用有限定義域內的鍵作為一個表項更復雜的表格索引。

所謂的Bit-map就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。

由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節(jié)省。

例如假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。

那么我們就可以采用Bit-map的方法來達到排序的目的。

要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，

如下圖：

遍歷第一個元素4，則在第4為標1：

以此來推，遍歷完所有后結構：

我們現在遍歷一遍Bit區(qū)域，將該位是bit 1的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。

二、C++實現

我們可以用一個unsigned int類型的數組或者向量來表示位圖，假設我們定義vector<unsigned int> a，則第i位可表示為a[i/32]的i%32位（其中，32*N+r = i，r為i%32，也就是i/32的余數）。

由于計算機對位的操作比乘除法更有效率，這里計算i/32可以用位移操作：i>>5；計算i%32可以用1&31。

若是一個char數組str，則str的第i位為i/8(i>>3)地址塊的第i%8(i&7)位.下面以char為例說明，int類比可知。

#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
class BitMap{
private:
        char *bitmap;
        int gsize;
public:
       BitMap(){
       gsize=(10000>>3)+1;//default 10000
       bitmap= new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                }
       BitMap(int n){
       gsize=(n>>3)+1;
       bitmap=new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                  }
       ~BitMap(){delete []bitmap;}
       int get(int x){
       int cur=x>>3;
       int red=x&7;
       if(cur>gsize)return -1;
       return (bitmap[cur]&=1>>red); 
                      }
       bool set(int x){
       int cur=x>>3;//獲取元素位置,除8得到哪個元素，x/2^3得到那一個byte 
       int red=x&(7);//邏輯與，獲取進準位置,x&7==x%8.該Byte里第幾個 
       if(cur>gsize)return 0;
       bitmap[cur]|=1>>red;//賦值，1向右移動red位，|表示該位賦值1
       return 1; 
                       }
};

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: