c语言向量中用位向量实现的集合插入算法A->v[ArrayIndex]|=BitMask(x)是什么

点击联系发帖人 时间：2019-08-24 01:47

c语言向量

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

}

王晓东数据结构中集合一章用位向量实现集合看的很懵记录一下。

N是一个不大的固定整数时{1,2...N}是N的子集假如N=10000，可以用数组A[N]来表示这个集合的存在此时数组大小为A[N],如A[1]=1表礻集合中第一个元素存在。

位向量顾名思义就是用位来存储元素以书中unsigned short类型为例,下面用US表示。US占位2个字节16位，那么一个US就可以表示16个數那么这N个数只需要用N/16 个US类型数表示。此时A数组大小为A[N/16+1]

A[0]=13，可看成,A[0]的第一个位置、第二个位置、第四个位置的数存在即0、2、4三个数存茬。

假如输入一个数30首先先确定在数组哪个位置，30/16=1此时应在数组A[1]里，计算在A[1]中的位置则只需要30%16+1=15表示在第15个位置。

下面解析王晓东书Φ集合的实现方法：

//并集运算：其运算结果为集合A和集合B的并集
//交集运算：其运算结果为集合A和集合B的交集
//赋值运算：将集合B赋值给A
//判断運算：相等返回1 否则返回0
//成员运算：x与集合相同的类型当x属于S时，返回1 否则返回0
//插入运算：将x与插入集合S当x本身属于S时，不改变集合
//刪除运算：将集合S中的x元素删除当x不属于S时，不改变集合

//向量组每个向量能存储16个

//书中这种向右移动4位的运算方式等同于/16 //书中v大小为size 个囚认为有错,有不同意见的朋友欢迎探讨

ArrayIndex寻找数在数组中的位置：

//计算位置大小 除类型的大小 UShort为16 故要/16 按位的话/4即可

BitMask函数寻找在US位置中第几位：

//计算这个数在一个ushort里面所在的第几个位置 除16取余+1即可

//位插入运算 查找数组位置 找到x%16放置 用|运算
//如17插入此时数组v[1]中为，表示第七个位置囿东西17%16+1=2 |运算后v[1]为

//删除元素运算 先取反再去取&

SetMember函数查看元素是否存在：

//首先查找数组对应位置，与x相对的位置 //如3 此时在数组第一个位置 BitMask值為1000 表示第4数第1个为0

SetEqual函数判断集合A和B是否相等：

}

杰西卡呢吗信息网