首页
社区
课程
招聘
[求助]一个非常有挑战性的程序
发表于: 2007-6-1 11:57 6019

[求助]一个非常有挑战性的程序

2007-6-1 11:57
6019
题目是这样的:
   
  使用Windows搜索工具在磁盘中查找文件时,在被查找的文件名文本框内允许出现含有通配符“*”和“?”的字符串,以达到搜索多个文件的目的,称这样一个字符串为模板。搜索的过程就是在已知的若干文件名字符串中查找与模板匹配的文件名。以下程序实现模板与字符串的匹配判断功能。给出一个模板pat及一个字符串str,模板中可能含有通配符“*”和“?”,其中“*”表示在该位置上有0个或多个任意字符,“?”表示在该位置上有一个任意字符。函数match对它们作匹配判断后,返回1表示匹配,返回0表示不匹配。例如,模板为“e*p?e”,若字符串为“example”,则两者是匹配的;若字符串为“europe”,则两者是不匹配的。

一开始我编的程序是这样的:
#include<stdio.h>

int  match(char *pat,char * str)
{char *p = pat,*q = str;
int i=1;
while((*p != NULL)&&(*q != NULL))
{
  if(*p == *q || *p == '?')
  {p++;
   q++;
  }
  else if(*p == '*')
  {
        p++;
    while(*q != *p && *q != NULL)
        q++;
  }
  else
  {
   i = 0;
   break;
  }
}
if(*p !=NULL ||*q != NULL)
         i = 0;
return i;
}
void main()
{
char a[10],b[10];
int yesno;
gets(a);
gets(b);
yesno=match(a,b);
printf("%s %s %s\n",a,yesno?"match":"unmatch",b);
}

后来被一个朋友发现其中错误:
输入如下时:
a*ab
aabab
运行结果为:
a*ab unmatch aabab
Press any key to continue

现在反思一下,这个程序真的非常棘手,想了好久了,也没想到完美的解决办法。

[课程]FART 脱壳王!加量不加价!FART作者讲授!

收藏
免费 0
支持
分享
最新回复 (9)
雪    币: 217
活跃值: (99)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
如果没有什么特殊原因,随便找个正则表达式库就解决了.
2007-6-1 12:06
0
雪    币: 226
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
bootst有很好的正则库
2007-6-1 16:19
0
雪    币: 325
活跃值: (97)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
4
ATL的正则库 也可以讲究用 虽然俺喜欢NET的
2007-6-2 15:10
0
雪    币: 242
活跃值: (14)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
Wild card Match

网上搜下,写出来很简单
2007-6-4 13:08
0
雪    币: 242
活跃值: (14)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
6
考虑到匹配效率和使用方便的话,正则表达式并不是最适合得
2007-6-4 13:28
0
雪    币: 331
活跃值: (56)
能力值: ( LV13,RANK:410 )
在线值:
发帖
回帖
粉丝
7
状态机~~~~
2007-6-4 17:52
0
雪    币: 191
活跃值: (55)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
8
谢谢大家了。
其实这个程序是不允许用库的,后来我仔细想了一下还是便出来了,在这贴出来让大家看下,大家有兴趣可以参考下,
#include<stdio.h>
#include<string.h>
/*seach为配匹函数,在source窜中搜索dest窜,其中ptr存储第一次匹配的位置,n为紫窜长*/

int seach(char *source ,char *dest, char **ptr,int n)
{
  int i,flag;
  for(;*(source+n-1);source++)
  {
          for(i = 0,flag = 1; i < n; i++)
          {
                  if(*(source+i) != *(dest+i))
                  {   
                          flag=0;
                          break;
                  }
          }
      if(flag)
          {
                *ptr = source+i;
                return 1;
          }
  }
  return 0;
}
/*match函数判定两个窜是否匹配,其思想是这样的,不断将两个*之间的字符赋值给一个临时字*//符窜数组,然后调用 seach函数找出temp 在第二个窜中第一次出现的位置。
int match(char *pat, char *str )
{   
        int i,len;
        char temp[10];
        char *ptr,*p;
        for(p = pat,i = 0; *p != '\0'; p++)
        {
                if(*p == '*')
                {
                        if(i==0)
                                continue;
                        else if(!seach(str,temp,&ptr,i))
                       
                          return 0;
                          str=ptr;
                          i=0;
                       
                }
                else
                {
                        temp[i] = *p;
                        i++;
                }
        }
        for(int j=0; j < i; j++)  //此处对最后一个*号后的部分进行处理
        {   
                len=strlen(str);
                if(*(str+len-j-1)!=temp[i-j-1])
                return 0;
        }
        return 1;
}
void main()
{
char a[30],b[50];
int yesno;
gets(a);
gets(b);
yesno=match(a,b);
printf("%s %s %s\n",a,yesno?"match":"unmatch",b);
}
人太懒,加上程序流程也比较简单,不想打字了,呵呵。
2007-6-4 22:12
0
雪    币: 202
活跃值: (77)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
9
楼主是美女哟
2007-6-5 02:31
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
没有看懂是怎么回事还,吃饭回来了再学习!
2007-6-5 19:30
0
游客
登录 | 注册 方可回帖
返回
//