论坛: 编程破解 标题: 从字符串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

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号