Ah, sí. Debes quitar el else, sustituyéndolo por un if, y sacarlo fuera del for. Así:
Saludos.
Código (c) [Seleccionar]
for(i=0;i<m;i++)
{
if(strcmp(nom,P[i].Nombre)==0)
{
printf("%s esta en la base de datos\n",nom);
break;
}
}
if(strcmp(nom,P[i].Nombre)!=0)printf("%s no esta en la base de datos\n",nom);
Saludos.