c++ - 使用分而治之在 char 数组中搜索字符串

Question

假设我有一个结构数组，每个元素都有一个名称。喜欢:

struct something{
  char name[200];
}a[NMAX];

给定一个新字符串(字符数组)，我需要使用分而治之法为其找到正确的索引。喜欢:

char choice[200];
cin>>chioce;
int k=myFunction(choice);  // will return the index, 0 otherwise
                           // of course, could be more parameters
if( k )  
 cout<<k;

我不知道如何创建搜索功能(我尝试过，我知道 D&C 是如何工作的，但我仍在学习!)。

不，我不想使用字符串!

这是我尝试过的:

int myFunction(char *choice, int l,int r)   // starting with l==0 && r==n-1
{
    int m;
    if(strcmp(a[m].name,choice)==0)
            return m;
    else{
            m=(l+r)/2;
            return myFunction(choice,l,m-1);
            return myFunction(choice,m+1,r);
    }
}

Answer 1

这是我针对您上述问题的解决方案。但我已经修改了您的代码中的一些内容。

#include<iostream>
using namespace std;

#define NMAX 10

struct something{
  char *name; //replaced with char pointer so that i can save values the way i have done
}a[NMAX];

int myFunction(char *choice, int l,int r)   // starting with l==0 && r==NMAX-1
{
    if(l>r) //return if l has become greater than r
        return -1;
    int m=(l+r)/2;

    if(strcmp(a[m].name,choice)==0)
            return m+1;
    else if(l==r) //returned -1 as the value has not matched and further recursion is of no use
                return -1;
    else{

            int left= myFunction(choice,l,m-1);//replaced return
            int right= myFunction(choice,m+1,r);//by saving values returned
            if(left!=-1)                      //so that i can check them,
                return left;                  //otherwise returning from here onlywould never allow second satatement to execute
            if(right!=-1)
                return right;
            else
                return -1;
    }
}

int main(){

a[0].name="abc";
a[1].name="a";
a[2].name="abcd";
a[3].name="abcf";
a[4].name="abcg";
a[5].name="abch";
a[6].name="abcj";
a[7].name="abck";
a[8].name="abcl";
a[9].name="abcr";
char choice[200];
cin>>choice;
int k=myFunction(choice,0,NMAX-1);  // will return the index, 0 otherwise
                           // of course, could be more parameters
if( k !=-1)
 cout<<k;
 else
    cout<<"Not found";
return 0;
}

希望对您有所帮助。