Um amigo meu na USP esta iniciando o curso de TI, e aprendendo a programar em C. Fez como desafio uma função
Conta_Ocorrs() para contar o número de ocorrência de uma palavra em uma dada frase. Aproveitei seu algoritmo para ensinar algumas práticas melhores, comentei seus erros, corrigi, e também sugeri uma nova função
contaoc().
Na nova função, discuti se vale a pena incluir um
break para sair da função, ou se é melhor deixar o laço acabar por exaustão.
Abaixo a solução:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 80
//funcao Conta_Ocorrs antes do main
//evita ter que escrever o prototipo
//int Conta_Ocorrs(char *pal, char *fra); //<= repare o ponto-e-virgula no prototipo
int Conta_Ocorrs(char *pal, char *fra)
{
int k; //conta as buscas da palavra na frase
int r; //conta as ocorrencias de caracteres de palavra em frase
int o=0; //conta as ocorrencias aqui!
int n, m;
//n=sizeof(fra); Este operador da o tamanho do "tipo" de variavel (int eh 2 bytes, char eh 1 byte, etc).
//m=sizeof(pal); Nao da o tamanho da string. Para isso, use:
n=strlen(fra);
m=strlen(pal);
printf("Tamanhos: frase: %d, palavra: %d\n", n, m);
for (k=m;k<=n;k++)
{
r=1; //r eh zerado em cada pesquisa -- os indices comecam em zero
while (r<=m && pal[m-r]==fra[k-r]) //r<=m para dar zero
r++;
if (r>=m)
o++;
}
return o;
}
//a funcao acima conta comparando indices de tras para frente, o que afeta o desempenho
//o melhor eh comparar os indices na direcao da memoria, para deixar o compilador otimizar melhor o codigo
//descomente os printfs abaixo para ver os indices.
//testei com as frases
//teste 1: frase: "a casa bonita casa". palavra: "casa"
//teste 2: frase: "mamama". palavra: "mama"
//teste 3: frase: "a casa bonita cas". palavra: "casa"
int contaoc(char *pal, char *fra)
{
int p=0; //indice da palavra
int f=0; //indice da frase
int o=0; //ocorrencias
// int tfra, tpal; //use nomes melhores para lembrar do que se trata
// tfra=strlen(fra); //sera que vale a pena conferir?
// tpal=strlen(pal); //veja resposta abaixo
//aproveito que se sabe que ao final de uma string sempre tem o caracter nulo '/0'
while(fra[f+p]!='\0')
{
// printf("outside p:%d, f:%d, o:%d\n", p, f, o);
while(pal[p]!='\0' && fra[f+p]!='\0' && pal[p]==fra[f+p])
// {
// printf("inside p:%d, f:%d, o:%d\n", p, f, o);
p++;
// }
if(pal[p]=='\0') //o pal[p] foi ate o fim, entao encontrou ocorrencia, caso contrario, acabou a frase ou sao diferentes
o++;
//evita calcular o restinho da frase menor que a palavra
// if(f+tpal > tfra)
// {
// printf("strlen p:%d, f:%d, o:%d\n", p, f, o);
// break;
// }
//talvez nao valha a pena. Vejamos:
//A frase "a casa bonita casa" tem 18 letras. A palavra "casa" tem 4. Somente quando f=15, as ultimas 3 letras da frase
//teremos o break. Isso vai evitar 3 giradas do laco externo (e talvez do interno se a frase fosse "a casa bonita cas")
//estamos falando de evitar entao:
// 3 whiles externos e no pior caso, 3+2+1 whiles internos com seus respectivos p++, mais 3 if(pal[p]=='\0')
// mais 3 p=0 e f++
// TOTAL de 24 operacoes
// Incluindo o if(t+tpal>tfra) e seu break, eliminamos 24 operacoes, mas inserimos:
// 2 strlen() no inicio
// para casa laco externo antes dos 3 ultimos (ou seja, 15 lacos): um if(t+tpal..., e a adicao em si do t+tpal
// TOTAL de 30 operacoes!!!
// Caso geral: supoe-se que frases podem ser maiores, mas as palavras acabam por ter um tamanho limitado
// Portanto, em um caso geral, a frase maior e uma palavra de tamanho limitado
// no algoritmo com break: aumenta o total de operacoes do if do break, e nao diminui consideravelmente os lacos
// no algoritmo sem break: o restinho do laco continua sendo executado sem necessidade, mas o numero de operacoes permanece pequeno
// Conclusao: melhor deixar o laco sem teste de break
p=0;
f++;
}
// printf("return p:%d, f:%d, o:%d\n", p, f, o);
return o;
}
// Função principal
int main(void)
{
char palavra[MAX], frase[MAX]; //ponteiros nao sao vetores! Eh preciso alocar o espaco para guardar dados, e isso eh feito com vetor
// contadores mudaram para dentro da funcao int m,n; //Definicao dos contadores
// nao estava sendo utilizada int o; //Definicao do valor de retorno da funcao
//Entrada de dados (inverti a ordem para melhor clareza)
printf("Entre com a frase (max %d letras pois 1 fica reservado para o caracter nulo): ", MAX-1);
//scanf("%s",frase); //nao se usa operador endereco & em ponteiros ou vetores
fgets(frase, MAX-1, stdin); //scanf para de ler ao ver espaco. use fgets(). fgets inclui o ENTER ao final. Elimine-o se nao quiser
frase[strlen(frase)-1]='\0'; //eliminando o ENTER final. Veja explicacao do strlen na funcao acima
printf("Entre com a palavra (max %d letras pois 1 fica reservado para o caracter nulo): ", MAX-1);
scanf("%s",palavra); //nao se usa operador endereco & em ponteiros ou vetores
//Inicializacao dos contadores pode ser feita na funcao, para diminuir numero de parametros
//m=sizeof(palavra);
//n=sizeof(frase);
//Saida de dados
printf("A palavra %s ocorre %d vez(es) na frase\n",palavra, Conta_Ocorrs(palavra, frase));
printf("Funcao contaoc(pal,fra): ocorrencias %d\n", contaoc(palavra, frase));
//Fim
//Nunca use isto. Seu algoritmo nao depende de sistema operacional. system("pause");
//Se precisa dar um tempo antes de retornar, use:
//getchar();
//mas o melhor eh aprender a executar o programa na linha de comando do prompt (shell)
}
