2011:03:contar-palavras-em-uma-frase

Contar palavras em uma frase

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)
}
Enter your comment:
 
  • 2011/03/contar-palavras-em-uma-frase
  • Last modified: 2011/03/30 13:36