(急)一道C语言数据结构习题

发布网友发布时间：2022-05-21 01:56

我来回答

共1个回答

热心网友时间：2023-10-11 08:24

　　相关代码见后面。

　　这里整理一下需求如下：

　　函数 char*String_Match(int dir,char* str,char* exp);

　　dir表示方向，1表示正向查找 -1表示逆向查找

　　str是待查找的字符串，里面是一个空字符结尾的字符串

　　exp是要查找的表达式，可能包含？（匹配任意一个非空字符）或者*（匹配任意字符串）

　　代码如下 vs2010编译通过（控制台程序工程、无MFC支持、cpp代码）

#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
//空间复杂度是O(n) 时间复杂度是O(n的平方) 是的，效率不高
char* String_Match(int dir,char* str,char* exp);
int main(int argc,char**argv,char**env)
{
    char str[]="abcdefghijklmn";
    char exp1[]="a*c";
    char exp2[]="h*?l";
    char* sub = String_Match(1,str,exp1);
    printf("%s",sub);//注意这里会将整个字符串打印出来，如果只要部分，需要修改函数，我这里只返回字串的首地址指针
    sub = String_Match(-1,str,exp2);
    printf("%s",sub);
    return 0;
}
bool match(char *str,char *pat)
{
switch(*pat){
case '\0':
return !*str;
case '*':
return match(pat+1,str)||(*str)&&match(pat,str+1);
case '?':
return *str&&match(pat+1,str+1);
default:
break;
}
return (*pat==*str)&&match(pat+1,str+1);
}
char* String_Match(int dir,char* str,char* exp)
{
int i;
char* ret = NULL;
//参数检查没有检查str或者exp的有效性
if(dir != -1 &&(dir!=1)) return NULL;
if(str==NULL || (exp == NULL))return NULL;
int nLen = strlen(str);
int nExpLen = strlen(exp);
if((nLen <= 0) || (nExpLen <= 0) || (nLen<nExpLen))//注意这里排除了exp比str长的可能
return NULL;
//方向处理
char* Str = NULL;
char* Exp = NULL;
if(dir==-1){//对于逆序查找，可以将要查找的字符串和表达式逆序，然后就变成顺序查找了
Str = new char[nLen];
Exp = new char[nExpLen];
if(Str == NULL || (Exp == NULL)){
if(Str)delete []Str;
if(Exp)delete []Exp;
return NULL;
}
for (i=nLen-1;i>=0;i--)
{
Str[nLen-i-1] = str[i];
}
for (i=nExpLen-1;i>=0;i--)
{
Exp[nExpLen-i-1] = exp[i];
}
}else{
Str = str;
Exp = exp;
}
//现在进行顺序查找即可了
do{
int nIndex = 0;
char* pFirst = NULL;
char fr = 0;
int nCount = 0;
std::string subExp;//表达式中最前的不包含通配符的连续子串
std::string preSub;//表达式中最前的通配符子串
for(i=0;i<nExpLen;i++)//寻找第一个非通配符字符，并统计前面的通配符个数
{
fr = Exp[i];
if(fr=='?')nCount++;
if((fr=='?')||(fr=='*'))
preSub += fr;
} while ((fr!='?')&&(fr!='*'));
if(fr == '?' || (fr == '*')){//全是通配符,直接返回即可
ret = exp;
break;
}
for(i=0;i<nLen;i++)
{
if(match(Str+i,Exp)){
ret = Str+i;
break;
}
}
}while(0);
if(dir==-1){//回收内存
if(ret!=NULL){//因为是逆序的，所以要颠倒一下
ret = str + nLen - (ret-Str) -1;
}
delete[]Str;
delete[]Exp;
}
return ret;
}