C語言位圖及位圖的實現

Posted on by

本文實例為大傢分享瞭C語言位圖及位圖的實現具體代碼，供大傢參考，具體內容如下

1.概念

位圖（bitset）是一種常用的數據結構，常用在給一個很大范圍的數，判斷其中的一個數是不是在其中。在索引、數據壓縮方面有很大的應用。

位圖是用數組實現的，數組的每一個元素的每一個二進制位都表示一個數據，0表示該數據不存在，1表示該數據存在。

2.C++庫中bitset的使用

3.bitset的簡單實現

當我們存放一個數據時的思路是：

1）確定數據在哪個區間上，即_bitSet的第幾個元素上，_bitSet是順序表，每個元素是char類型，value/8可得到

2）確定數據在哪個區間的哪個bit位上，value%8可以得到

3）找到該位置後，將bit位置1

4）重置的時候，將該bit位置0

#pragma once
#include<vector>
 
//隻能用於整型，節省空間 
class BitSet
{
public:
 BitSet(size_t range)
 {
  //當range為8以下的時候，會開辟0個空間，會出錯
  _bitSet.resize(range/8+1,0);
 }
 
 void Set(size_t value)
 {
  size_t index = value / 8;  //value>>3
  size_t pos = value % 8;
 
  _bitSet[index] |= (1<<pos); //置1：或1
 }
 
 void ReSet(size_t value) //重置
 {
  size_t index = value / 8;
  size_t pos = value % 8;
 
  _bitSet[index] &= ~(1<<pos); //置0: 與0
 }
 
 bool Test(size_t value) //檢測
 {
  size_t index = value / 8;
  size_t pos = value % 8;
  
  return _bitSet[index] & (1<<pos);
 
 }
 
protected:
 vector<char> _bitSet;
};
 
void TestBitMap()
{
 BitSet b(-1); //-1轉為無符號數就是最大值
 b.Set(5);
 b.Set(999);
 b.Set(1022);
 b.Set(111110000);
 
 cout<<b.Test(5)<<endl;
 cout<<b.Test(100)<<endl; //100不在位圖當中
 cout<<b.Test(999)<<endl;
 cout<<b.Test(1022)<<endl;
 cout<<b.Test(111110000)<<endl;
}

以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。

推薦閱讀：