Optimization of multiple ifs into something more practical

Question

I have a string alphabetical:

char string[] = "aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";

I want to go through it all and for every character of it, say how many times it repeats in the string.

Example:

#include <string.h>
#include <stdio.h>

struct Quantidade{
   int qtd;
};

char string = 
"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";


int main(){
     struct Quantidade vetor[];

     for(i=0; i<strlen(string); i++{
        if(string[i] == 'a'){
            vetor[0].qtd++;    
        } 
        else if(string[i] == 'b'){
            vetor[1].qtd++;
        }
        ...
        else if(string[i] == 'z'){
             vetor[25].qtd++;
        }
     }

   return 0;
 }

Instead of using 26 ifs within the code, as I can do more optimally?

Answer 1

If only lower case letters can make one array with 26 positions and keep in them according to what you find.

In *string - 'a' is a calculation to find out the position of the array. You can almost always use math to help simplify algorithms. So I take the content pointed by the pointer string which is the character of that step, it will be evaluated according to the ascii table. Then the a is code 97, we don’t want that, we want 0, so it’s simple, we subtract 97, but to be more readable we subtract the own a which is worth 97. And if the character is d, not 100 - 97 gives 3, so the element used will be how much of array. Everything works out.

When using to restore the character you have to add the 97 again.

Thus:

#include <stdio.h>

int main() {
    char *string = "aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";
    int quantidade[26] = { 0 }; //inicializa todos elementos zerados
    for (; *string != '\0'; string++) { //termina quando chegar no nulo que é fim de string
        quantidade[*string - 'a']++; //incrementa conteúdo apontado por string - código 'a'
    }
    for (int i = 0; i < 26; i++) {
        printf("%c => %d\n", i + 'a', quantidade[i]); //soma 'a' pra ter o caractere correto
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

If you can have other characters, just increase the number of positions in the array to fit all and count the character always using the first possible.

This does not work if you can have separate character ranges. This algorithm only works for a single track of any size.

If you want you can filter the ones with 0 not to print in the list, this is very easy.

This algorithm does the same as the question.

But if zeroes can’t even be on array, then you will have to create a more complex structure where you store the character and its sum, only when it reaches at least 1. And there will have to be a search algorithm in this *array8 that can be linear, logarithm or constant depending on how much assurance of performance and acceptable complexity. It’s much more complicated to do this.

Note that I avoided the use of strlen() which is not the most appropriate. So I walk the pointer (string++) in each character and checks whether came to the end. If you have difficulty reading this see pointer operators.

I almost did with while, I think it was the best in this case.

Answer 2

#include <string.h>   // strlen()
//#include <stdio.h>

#define NUM_ALPHA 26
struct Quantidade{
   int qtd;
};

//char string =
//"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";
char string[] =
"aouihuiahsudasduihqmdoiqjnduiamsdoqnwuidamodkjwodkaposdj";

int main(){
     //struct Quantidade vetor[];
     struct Quantidade vetor[ NUM_ALPHA ];

     for( int i=0; i<NUM_ALPHA; i++ )
     {
         vetor[ i ].qtd = 0;  // initialize
     }

     // for(i=0; i<strlen(string); i++{
     for( size_t i=0; i<strlen(string); i++ )
     {
        //if(string[i] == 'a'){
        //    vetor[0].qtd++;
        //}
        //else if(string[i] == 'b'){
        //    vetor[1].qtd++;
        //}
        //...
        //else if(string[i] == 'z'){
        //     vetor[25].qtd++;
        //}
        vetor[ string[i] - 'a' ].qtd++;
     }

   return 0;
 }