高级数据结构及应用之使用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'; }
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接