首页 > C/C++ > 二进制思考(三):位排序、位索引(bit-map)简单举例

二进制思考(三):位排序、位索引(bit-map)简单举例

2012年3月1日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

本节目的是利用上一节的知识加深理解《编程珠玑》中的一道位排序题目,位排序的思想比较简单,具体代码见参考文献吧,这里就不罗列了。

本文主要是写一下《The C Programming Language》第二章中一道非常简单的小题目,文中使用了三种方法,可以对比一下。

题目:编写函数squeeze(s1,s2),将字符串s1中任何与字符串s2中字符匹配的字符都删除。

分析:这道题目的注意点主要有两个,一是搜索匹配的字符,二是删除字符时后续字符的前移。这两方面都是有技巧在里面的,见代码

方法一:暴力搜索

#include<stdio.h>

void squeeze(char *s1, char *s2);
int ishave(char *s2, char c); // 判重

void main()
{
	char s1[] = "abcdefghigklmn";
	char s2[] = "helloworld";
	squeeze(s1,s2);
	printf("%s\n",s1);
}

void squeeze(char *s1, char *s2)
{
	int i = 0, j = 0;
	for(; s1[i] != '\0'; ++i)
	{
		if(!ishave(s2,s1[i]))
		{
			s1[j++] = s1[i];
		}
	}
	s1[j] = '\0';
}

int ishave(char *s2, char c)
{
	int i = 0;
	while(s2[i] != '\0')
	{
		if(s2[i] == c)
			return 1;
		++i;
	}
	return 0;
}

方法二:基于字符ASCII码的索引

#include<stdio.h>

char index[256] = {0}; // ASCII码为0

void squeeze(char *s1, char *s2);
void creatIndex(char *s2);

void main()
{
	char s1[] = "abcdefghigklmn";
	char s2[] = "helloworld";
	creatIndex(s2);
	squeeze(s1,s2);
	printf("%s\n",s1);
}

void squeeze(char *s1, char *s2)
{
	int i = 0, j = 0;
	for(; s1[i] != '\0'; ++i)
	{
		if(!index[s1[i]])
		{
			s1[j++] = s1[i];
		}
	}
	s1[j] = '\0';
}

void creatIndex(char *s2)
{
	int i = 0;
	while(s2[i] != '\0')
	{
		index[s2[i++]] = 1;
	}
}

方法三:位索引(bit-map)

#include<stdio.h>

#define INTBITS 32
#define MASK 0x1f
#define SHIFT 5
#define CHARNUM 256

int index[CHARNUM/INTBITS];
void creatIndex(char *s2);
void squeeze(char *s1, char *s2);
void set(int i) { index[i >> SHIFT] |= 1 << (i & MASK);	} //i&MASK相当于对32取余,即看i用第几位表示
int test(int i)	{ return index[i >> SHIFT] &  1 << (i & MASK); }

void main()
{
	char s1[] = "abcdefghigklmn";
	char s2[] = "helloworld";
	creatIndex(s2);
	squeeze(s1,s2);
	printf("%s\n",s1);
}

void squeeze(char *s1, char *s2)
{
	int i = 0, j = 0;
	for(; s1[i] != '\0'; ++i)
	{
		if(!test(s1[i]))
		{
			s1[j++] = s1[i];
		}
	}
	s1[j] = '\0';
}
void creatIndex(char *s2)
{
	int i = 0;
	while(s2[i] != '\0')
	{
		set(s2[i++]);
	}
}

相比第一种方法,后两种方法皆是“以空间换时间”的案例,第三种方法在搜索判重时,使用位索引(哈希),利用的空间更加少。

下一节,整理下关于位运算的几道经典题目。

(全文完)

参考文献(位排序代码):

http://www.cs.bell-labs.com/cm/cs/pearls/  ( Column15 bitsort.c )

  • http://mazheng.org 冰上游鱼

    好的hash的确是空间换时间的利器。

  • Yx.Ac

    哇哈哈,改天整个面试题,用bit-map实现下,印象更深@依水远行

  • 依水远行

    感谢博主,让我迅速了解了bitmap,讲解的很详细。