Информатика и технология программирования


Результат функции рекурсивного поиска - часть 2



char *step(char *lw ) // результат - строка с цепочкой слов


{ ... // параметр - слово, с которого


// начинается цепочка


for (n=0; w[n]!=NULL;n++) //просмотр оставшихся слов


{
char *pw,*pp; int l; // слово уже выбрано -


if (*w[n]==0) continue; // пропустить


if ((l=TEST(lw,w[n]))!=-1 )
// можно присоединить к текущему


{
pw=w[n]; //убрать очередное слово из списка


w[n]=""; //рекурсивный вызов для нового


if ((pp=step(pw))!=NULL)
{ // !=NULL - цепочка выcтроена


s=new char[l+strlen(pp)];
strcpy(s,lw); // присоединить текущее слово


strcpy(s+l,pp); // к началу и использовать как


delete pp; // новый результат


}
w[n]=pw;
}
} ...}

Естественно, что из множества полученных результатов выбирается единственный, который " ретранслируется наверх" . В нашем случае - из полученных цепочек выбирается минимальная по длине - что делается классическим циклом поиска минимума


smin=NULL;
for (n=0; w[n]!=NULL;n++)
{ ...if ((pp=step(pw))!=NULL)
{
s= ... //сформировать очередной результат


delete pp; //запоминание самой короткой строки


if (smin==NULL) smin=s; else
if (strlen(smin)&#62strlen(s))
{ delete smin; smin=s; }
}
}
return smin;

Окончательный вариант программы приведен ниже. Функция проверки " перекрытия " слов возвращает количество " неперекрытых" букв в первом слове, 0 - если первое слово - пустая строка, либо -1, если слова не перекрываются


//------------------------------------------------------bk54-04.cpp


&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
char *w[]={"bba","abb","ba",NULL};


int TEST(char *s, char *r)
{
int n,k;
k=n=strlen(s);
if (n==0) return 0;
for (;*s!=0 &#38&#38 n&#62 0; s++,n--)
if (strncmp(s,r,n)==0)
return k-n;
return -1;
}


char *step(char *lw)
{ int n; char *s,*smin;
for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL)
{
s=new char[strlen(lw)+1];
strcpy(s,lw);
return s;
}
smin=NULL;
for (n=0; w[n]!=NULL;n++)



Начало  Назад  Вперед



Книжный магазин