C語言中位圖怎么實(shí)現(xiàn)

這篇文章主要介紹C語言中位圖怎么實(shí)現(xiàn)，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

本文實(shí)例為大家分享了C語言位圖及位圖的實(shí)現(xiàn)具體代碼，供大家參考，具體內(nèi)容如下

1.概念

位圖（bitset）是一種常用的數(shù)據(jù)結(jié)構(gòu)，常用在給一個(gè)很大范圍的數(shù)，判斷其中的一個(gè)數(shù)是不是在其中。在索引、數(shù)據(jù)壓縮方面有很大的應(yīng)用。

位圖是用數(shù)組實(shí)現(xiàn)的，數(shù)組的每一個(gè)元素的每一個(gè)二進(jìn)制位都表示一個(gè)數(shù)據(jù)，0表示該數(shù)據(jù)不存在，1表示該數(shù)據(jù)存在。

2.C++庫中bitset的使用

3.bitset的簡單實(shí)現(xiàn)

當(dāng)我們存放一個(gè)數(shù)據(jù)時(shí)的思路是：

1）確定數(shù)據(jù)在哪個(gè)區(qū)間上，即_bitSet的第幾個(gè)元素上，_bitSet是順序表，每個(gè)元素是char類型，value/8可得到

2）確定數(shù)據(jù)在哪個(gè)區(qū)間的哪個(gè)bit位上，value%8可以得到

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

4）重置的時(shí)候，將該bit位置0

#pragma once
#include<vector>
 
//只能用于整型，節(jié)省空間 
class BitSet
{
public:
 BitSet(size_t range)
 {
  //當(dāng)range為8以下的時(shí)候，會(huì)開辟0個(gè)空間，會(huì)出錯(cuò)
  _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轉(zhuǎn)為無符號數(shù)就是最大值
 b.Set(5);
 b.Set(999);
 b.Set(1022);
 b.Set(111110000);
 
 cout<<b.Test(5)<<endl;
 cout<<b.Test(100)<<endl; //100不在位圖當(dāng)中
 cout<<b.Test(999)<<endl;
 cout<<b.Test(1022)<<endl;
 cout<<b.Test(111110000)<<endl;
}

以上是“C語言中位圖怎么實(shí)現(xiàn)”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！