高级数据结构及应用之使用bitmap进行字符串去重的方法实例
bitmap即为由单个元素为boolean（0/1,0表示未出现，1表示已经出现过）的数组。
如果C/C++没有原生的boolean类型，可以用int或char来作为bitmap使用，如果我们要判断某字符（char）是否出现过
使用int作为bitmap的底层数据结构，bitmap即为int数组，一个int长度为32个bit位，
- c/32⇒bitmap中的第几个int
- c%32⇒bitmap中的某int中的第几个bit位；
使用char作为bitmap的底层数据结构，bitmap即为char数组，一个char长度为8个bit位；
- c/8⇒bitmap中的第几个char
- c%8⇒bitmap中某char中的第几个bit位；
ASCII
- A-Z：65-90
- a-z：97-122
如果使用char作为bitmap的替代底层数据结构，为了实现字符串的去重需要char的长度为多少呢？122/8+1⇒16。如果使用int作为bitmap的底层实现，则需要int数组的长度为122/32+1⇒4
1.int作为底层数据结构
voiddedup(constchar*src,char*dst)
{
unsignedintexists[4]={0};
inti=0,j=0;
unsignedintmask;
charc;
while(src[i])
{
c=src[i];
mask=1<<(c%32);
if((exists[c/32]&mask)==0)
{
dst[j++]=c;
exists[c/32]|=mask;
}
i++;
}
dst[j]='\0';
}
2.使用char作为底层数据结构
voiddedup(constchar*src,char*dst)
{
unsignedcharexists[16]={0};
inti=0,j=0;
unsignedintmask;
charc;
while(src[i])
{
c=src[i];
mask=1<<(c%8);
if((exists[c/8]&mask)==0)
{
dst[j++]=c;
exists[c/8]|=mask;
}
i++;
}
dst[j]='\0';
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接