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) }
You could leave a comment if you were logged in.