【数据结构】中实现一个位图

青旅半醒 2022-06-10 00:41 157阅读 0赞

位图法就是bitmap的缩写。关于bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。

通常是用来判断某个数据存不存在的。

位图的优缺点：

优点：

(1),是速度快，内存空间占用小，能表示大范围的数据。

缺点：

(2),可读性差  
(3),位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。  
(4),位图对有符号类型数据的存储，需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数，元素值大小上限减半。

位图的实现：

#include<iostream>
    using namespace std;
    #include<vector>
    
    class BieSet
    {
    public:
    	BieSet(size_t rang)
    	{
    		_a.resize((rang >> 5) + 1);
    	}
    	void Set(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		_a[index] |= (1 << pos);
    	}
    	void Reset(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		_a[index] &= ~(1 << pos);
    	}
    	bool Test(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		return _a[index] & (1 << pos);
    	}
    protected:
    	vector<int> _a;
    };
    
    void BitSetTest()
    {
    	BieSet b(1000);
    	b.Set(1);
    	b.Set(33);
    }
    
    int main()
    {
    	BitSetTest();
    	system("pause");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关【高阶数据结构】位图&布隆过滤器

处理海量数据的数据结构——位图&布隆过滤器

ゞ浴缸里的玫瑰/ 2024年04月20日 12:05/ 0 赞/ 82 阅读

相关【算法&数据结构初阶篇】：位图bitMap

> 在java中，一个int类型占4个字节，也就是32bit，我们用一个int数组来表示时 new int\[32\],总计占用内存大概32\32bit,如果说我们存放的海量数

偏执的太偏执、/ 2024年03月29日 16:07/ 0 赞/ 105 阅读

相关 Java图教程–如何实现图数据结构

这个全面的Java Graph教程详细介绍了Graph数据结构。它包括如何在Java中创建，实现，表示和遍历图：图数据结构主要表示连接各个点的网络。这些点称为顶点，连接这些

港控/mmm°/ 2023年10月04日 08:53/ 0 赞/ 54 阅读

相关位图结构

文章目录简介实现原理位运算的实现实现简介位图结构实现是参考\

蔚落/ 2023年07月10日 00:54/ 0 赞/ 2 阅读

相关【数据结构与算法】【算法思想】位图

位图BitMap 算法 public class BitMap { // Java中char类型占16bit，也即是2个字节 private

缺乏、安全感/ 2022年12月08日 14:15/ 0 赞/ 225 阅读

相关【数据结构与算法】详解什么是图结构，并用代码手动实现一个图结构

本系列文章【数据结构与算法】所有完整代码已上传 github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接 [https://gi

系统管理员/ 2022年12月04日 07:51/ 0 赞/ 158 阅读

相关【数据结构】中的位图详解

定义：位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。优缺点

朴灿烈づ我的快乐病毒、/ 2022年06月17日 10:15/ 0 赞/ 215 阅读

相关【数据结构】中实现一个位图

位图法就是bitmap的缩写。关于bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。位图的优缺点

青旅半醒/ 2022年06月10日 00:41/ 0 赞/ 158 阅读

相关数据结构-位图（可对海量数据进行处理）

在学习linux过程中，wait函数中的status参数的用法其实就如同位图，位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但

我会带着你远行/ 2022年06月04日 06:51/ 0 赞/ 331 阅读

相关【数据结构】位图

位图（bitmap)，就是用每一位存放某种状态，适用于数据较多，且状态不多的情况。在Linux系统中，用位图来表示是否接收到进程发送的信号，接收到信号则将相关的比特位置1。

- 日理万妓/ 2022年05月27日 06:07/ 0 赞/ 250 阅读