开发语言 数据结构 位图（c++）

文章目录

1.位图概念2.位图的实现3.应用（解决整形存在或次数问题）3.1存在问题3.2次数问题

5.搜索的方法对比：

1.位图概念

和哈希一样，都是一个表来记录某个元素的个数或者存在与否；不同的是哈希使用的计算机定义的完整空间向数组的int类型；而位图则是时使用的一个或者多个（不会太多）bit位来表示表示一个数字的个数或者存在与否。

2.位图的实现

第一步定义空间. 位图由于是使用bit位来记录的，但是单个bit位无法开出来，所以我们先可以使用int定义出来空间（即定义一个可以下位图的空间）； 第二步定义类中的接口 构造函数： 输入函数： 删除函数：

查找函数： 解释i和j： 这里删除函数和输入函数的i表示的是：数x在数组的第几个数； 这里删除函数和输入函数的j表示的是：数x在数组的第i个数的第几个bit位；

代码

//位图

template

class bitset

{

public:

bitset()

{

//_bits.resize(N/32+1,0);

_bits.resize((N >> 5) + 1, 0);

}

void set(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

_bits[i] |= (1 << j);

}

void reset(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

_bits[i] &= ~(1 << j);

}

bool test(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

return _bits[i] & (1 << j);

}

private:

vector _bits;

};

3.应用（解决整形存在或次数问题）

3.1存在问题

在【42，39】中是否存在39，40，41，42； 头文件和上面的一样

template

class bitset

{

public:

bitset()

{

//_bits.resize(N/32+1,0);

_bits.resize((N >> 5) + 1, 0);

}

void set(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

_bits[i] |= (1 << j);

}

void reset(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

_bits[i] &= ~(1 << j);

}

bool test(size_t x)

{

size_t i = x / 32;

size_t j = x % 32;

return _bits[i] & (1 << j);

}

private:

vector _bits;

};

源文件：

#define _CRT_SECURE_NO_WARNINGS 1

#include

using namespace std;

#include"bitset.h"

int main()

{

bit::bitset<100> bs;

bs.set(40);

bs.set(39);

cout << bs.test(38) << endl;

cout << bs.test(39) << endl;

cout << bs.test(40) << endl;

cout << bs.test(41) << endl;

cout << bs.test(42) << endl << endl;

return 0;

}

3.2次数问题

题目：查找【1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 】中出现一次和两次的数字 对比存在问题需将插入函数和输出函数修改即可修改在下： 头文件：

template

class twobitset

{

public:

void set(size_t x)

{

//00->01

//01->10

//10->11

//11->不变

if (_bs1.test(x) == false && _bs2.test(x) == false)

{

_bs2.set(x);

}

else if (_bs1.test(x) == false && _bs2.test(x) == true)

{

_bs1.set(x);

_bs2.reset(x);

}

else if (_bs1.test(x) == true && _bs2.test(x) == false)

{

_bs1.set(x);

_bs2.set(x);

}

}

void Print()

{

for (size_t i = 0; i < N; i++)

{

if (_bs1.test(i) == false && _bs2.test(i) == true)

{

cout << "1->" << i << endl;

}

else if (_bs1.test(i) == true && _bs2.test(i) == false)

{

cout << "2->" << i << endl;

}

}

cout << endl;

}

private:

bitset _bs1;

bitset _bs2;

};

源文件：

int main()

{

int a[] = { 1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 };

bit::twobitset<100> bs;

for (auto e : a)

{

bs.set(e);

}

bs.Print();

return 0;

}

5.搜索的方法对比：

推荐文章