bit数据结构new

《bit数据结构new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012CSDN博客之星评选正式上线【免费】解读海外市场营销奥秘CSDN博客频道推出TAG功能[置顶]数据结构：位图法分类：AlgorithmsDatastructs2012-11-2912:485247人阅读评论(5)收藏举报目录(?)[+]1.一定义2.二数据结构3.三相关操作1.写入数据2.读指定位4.四位图法的缺点5.五位图法的应用6.六实现一、定义位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个

2、bitset容器，其实就是位图法，引用bitset介绍：Abitsetisaspecialcontainerclassthatisdesignedtostorebits(elementswithonlytwopossiblevalues:0or1,trueorfalse,...).Theclassisverysimilartoaregulararray,butoptimizingforspaceallocation:eachelementoccupiesonlyonebit(whichiseighttimeslessthant

3、hesmallestelementaltypeinC++:char).Eachelement(eachbit)canbeaccessedindividually:forexample,foragivenbitsetnamedmybitset,theexpressionmybitset[3]accessesitsfourthbit,justlikearegulararrayaccessesitselements.二、数据结构unsignedintbit[N];在这个数组里面，可以存储N*sizeof(int)个数据，但是最大的数

4、只能是N*sizeof(int)-1。假如，我们要存储的数据范围为0-15，则我们只需要使得N=1，这样就可以把数据存进去。如下图：数据为【5，1，7，15，0，4，6，10】，则存入这个结构中的情况为三、相关操作1，写入数据定义一个数组：unsignedcharbit[8*1024];这样做，能存8K*8=64K个unsignedshort数据。bit存放的字节位置和位位置（字节0~8191，位0~7）比如写1234，字节序：1234/8=154;位序：1234&0b111=2，那么1234放在bit的下标154字节处，把该

5、字节的2号位（0~7）置为1字节位置：intnBytePos=1234/8=154;位位置：intnBitPos=1234&7=2;[cpp]viewplaincopyprint?1.//把数组的154字节的2位置为12.unsignedshortval=1<

6、val;//写入1234得到arrBit[154]=0b00000100//把数组的154字节的2位置为1unsignedshortval=1<

7、t[nBytePos]

8、val;//写入1234得到arrBit[154]=0b00000100再比如写入1236，字节位置：intnBytePos=1236/8=154;位位置：intnBitPos=1236&7=4[cpp]viewplaincopyprint?1.///把数组的154字节的4位置为12.val=1<

9、val;//再写入1236得到arrBit[154]=0b00010100///把数组的154字节的4位置为1val=1

10、<

11、val;//再写入1236得到arrBit[154]=0b00010100函数实现：[cpp]viewplaincopyprint?1.#defineSHIFT52.#defineMAXLINE323.#defineMASK0x1F4.voidsetbit(int*bitmap,inti){5.bitmap[i>>SHIFT]

12、=(1<<(i&MASK));6.}#defineSHIFT5#defineMAXLINE32#defineMAS

13、K0x1Fvoidsetbit(int*bitmap,inti){bitmap[i>>SHIFT]

14、=(1<<(i&MASK));}2，读指定位[cpp]viewplaincopyprint?1.boolgetbit(int*bitmap1,inti){2.returnbit