20CN网络安全小组论坛 - 编程破解 - 从字符串s1中删除所有在s2出现的字符,返回删除个数

论坛: 编程破解标题: 从字符串s1中删除所有在s2出现的字符,返回删除个数

作者: seny11 [seny11]

论坛用户

1.要求编写int squeeze(char s1[],const char s2[])
功能:从字符串s1中删除所有在s2出现的字符,返回删除个数
偶的想法:有引进第三个数组和链表两种,但是链表要用2倍的空间(多一个next),哪一种好.
有没有更好的解决办法呢?

2.这段程序是否有错:
quick_sort 函数递归并调用split函数实现数组快速排序.

void quick_sort(int x[],int first,int last)
{if (first<last)
{
split_poing=split(x,first,last);
quick_sort(x,first,split_poing-1);
quick_sort(x,split_poing+1,last);
}
}

int split(int x[],int first,int last)
{
int split_poing,pivot;
pivot=x(first);
split_point=first;
for(int unknown=first+1;unknown<=last;unknown++)
if (x[unknown]<pivot)
{
split_point++; //问题:这句是否应放在if的最后?整个程序是否有错?
int t=x[split_point];
x[split_point]=x[unknown];
x[unknown]=t; //是否放在这? split_point++;
}
x[first]=x[split_point];
x[split_point]=pivot;
return split_point;
}

原标题：请教啊。

[此贴被 286(unique) 在 12月27日19时05分编辑过]

地主发表时间: 04-12-27 16:01

回复: 286 [unique]

版主

眼花了，不喜欢看源代码了。只回答第一个吧。

既然两个都是字符串，依次在第一个串中找第二个串中的每一个字符，如果遇到，就把该位改成不是字符的数，不就行了。最后查一下有多少个数。
int squeeze(char s1[],const char s2[])
{
int num=0,i,j;
char nochar='\1';//nochar表示一个肯定不会在s1,s2中出现的字符。
for (i=0;i<strlen(s2);i++)
{
for (j=0;j<strlen(s1);j++)
{
if (s1[j]==s2[i])
{
s1[j]=nochar;
num++;
}
}
}
return num;
}

B1层发表时间: 04-12-27 19:14

回复: kert_t8 [kert_t8]

论坛用户

哈希表！！典型的......
把第二个数组做成Hash table，在第一个字符串里面读取到一个字符，就到2里面去找。一共就26个字母10个数字，顶多加点别的也不会超过Ascii码表的的个数吧？直接按Ascii码排不就得了，一共多少个元素？不算扩展的那一部分应该是2^7=128个吧？常数啊！，而且效率很高，特别是你s1很长的时候，对吧？

第二个，有时间的帮看吧，我要睡了:/L Sorry

B2层发表时间: 04-12-27 14:53

回复: lida1818 [lida1818]

论坛用户

第一个问题完全可以不必再开辟另外的空间，另外286的函数有点小问题^_^
int squeeze(char s1[],const char s2[])
{
int i,j,T=0,S1=strlen(s1),S2=strlen(s1);//strlen放在循环中有些不妥，因为每执行一次循环就要执行strlen一次

for(i=0;i<S1;i++)
{
for(j=0;j<S2;j++)
{
if(s1[i]==s2[j])break;
}
if(j==S2)s1[T++]=s1[i];//随便替你删去^_^
}
s1[T]='\0';
return S1-T;
}

B3层发表时间: 04-12-27 15:49

回复: kert_t8 [kert_t8]

论坛用户

使用Hash表的程序

代码:


int squeeze(char s1[],const char s2[]) {
	int ascTable[128];
	int i;			// for loops
	int counter=0;		// for return

	for (i=0;i<128;i++)
		ascTable[i]=0;

	for (i=0;i<strlen(s2);i++)
		ascTable[toascii(s2[i])]=1;

	for (i=0;i<strlen(s1);i++)
		if (ascTable[toascii(s1[i])]==1) {
			counter++;
			s1[i]='\1';
		}

	return counter;
}

B4层发表时间: 04-12-29 12:56

论坛: 编程破解