Program liczący ilość konkretnych liter w słowie - ocena algorytmu

Witam, W ramach ćwiczeń musiałem, napisać program, który prosi o podanie jakiegoś słowa (wystarcza male litery i alfabet angielski), a następnie zlicza, ile słowo ma liter oraz ile razy dana litera występuje w danym słowie. Napisałem taki program:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>


int main()
{
   int f = 0; int i=0; int i2=0;
   char ch;

   char alf[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; //tablica ma 26 elementow
   int wynik[26] = {[25] = 0}; // automatycznie wypelnia cala tablice 0

   printf("Wpisz jakies slowo (max 99 liter), a ja wypisze, ile razy wystepuje dana litera\n");
   printf("Wpisz slowo: \n");

   while( (ch = getchar()) != '\n')
   {
       while(f<1)
       {

        if(ch == alf[i])
        {
           wynik[i]++;
           f=1;
        } i++;

       } f=0; i=0;
       i2++;
   } i=0;

   printf("\nPodane slowo ma %d liter\n", i2);
   printf("\nZawiera nastepujace litery:\n");

   while(i<26)
   {
       if(wynik[i] == 0)
       {
           i++;
           continue;
       }

       printf("Litera %c wystepuje %d razy\n", alf[i], wynik[i]);
       i++;
   }
   getchar();


    return 0;
}

Generalnie wszystko działa, jednak chciałbym Was poprosić o ocenę algorytmu, jaki wymyśliłem i zastosowałem. Może być coś takiego? Czy nie jest to wg. Was jakiś beznadziejny algorytm (na pewno lepszy niż wypisanie 26 ifów xD)? I czy można to zrobić jakoś lepiej? Generalnie czasami mam problem z algorytmiką, więc chciałbym żeby ten kod ocenił ktoś bardziej doświadczony.

edit: w sumie mniejsza z tym limitem 99 znaków. Tego limitu tutaj jednak ma nie być.

Litera to wartość liczbowa. Zamiast robić tablicę znaków, wystarczy Ci zależność, że litera jest >= 'a' i <= 'z' Tak samo z cyframi. Cyfra jest >= '0' i <= '9'.

Zamiast lecieć przez całą tablicę dla każdego znaku odczytałbym znak który jak wiadomo jest zapisany w kodzie ASCII i zamieniłbym na indeks tablicy.
Najlepiej przekonwertować wszystkie znaki na małe albo duże litery i następnie odejmować od nich 'a'/'A'.
Dla przykładu

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2
...

Dla słów do 99 liter Mógłbyś uzyskać lepszą złożoność, najpierw sortując słowo (n * logn), a potem zliczać litery iterującraz po słowie, to dało by Ci max, jakieś 7n; teraz Masz 26n.

Po co Ci zmienna i2?

Jak na newbie wygląda ok, ale możesz użyć funkcji isalpha z <ctype.h> zamiast definiować i przeszukiwać tablicę samodzielnie. Poza tym, w tym przypadku wygodniej by było zadeklarować ją tak:

char alf[] = "abcdefghijklmnopqrstuvwxyz";

albo jeszcze lepiej

char const alf[] = "abcdefghijklmnopqrstuvwxyz";

A Jakbyś użył hasha, to Miałbyś złożoność level expert O(n) - mniej się już nie da:)

Jaki hash? A z tym sortowaniem to masz na myśli, żeby posortować podane słowo w porządku alfabetycznym od a do z i nasępnie po kolei zliczyć tylko te litery, które faktycznie w nim występują, zamiast sprawdzać każdą literę alfabetu oddzielnie?

Jak to jaki hash? Hashtable: https://en.wikipedia.org/wiki/Hash_table
Tak, to właśnie miałem na myśli pisząc o sortowaniu.
A tak wygląda pseudokod liniowego algorytmu z symbol table:

fun frequ(s):
    d = hashtable<string, int>()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] = d[c] + 1
    return d

Panowie, niestety muszę odświeżyć temat. xD
Przetestowałem sobie ponownie program i wpisałem z ciekawości:

!!$$

Nie wpisałem żadnej małej litery, a program i tak zliczył, że są 4 znaki. Zmieniłem fragment kodu, wrzucając zmienną i2 (odpowiadająca za zliczanie ogólnej ilości słów) do ifa sprawdzającego, czy zmienna ch == wartości z tablicy alf[]:

        if(ch == alf[i])
        {
           i2++;
           wynik[i]++;
           f=1;
        } i++;

Jednak pomimo tego program dalej zlicza te znaki, potem zacząłem dalej testować program i zauważyłem, że działa poprawnie tylko, jak wpiszę znaki z tablicy alf[], w innym przypadku wartość i2 i tak jest inkrementowana, ale już nie wartość w tablicy wynik[], a to jest dziwne, bo skoro program wchodzi do tego ifa, to te dwie zmienne powinny być inkrementowane, jednak zmienna wynik[] już nie jest zwiększana. Czy ktoś może to skompilować i sprawdzić, co jest źle, bo siedziałem wczoraj nad tym i nie mogłem nigdzie znaleźć błędu.

Wołam:
@lion137 @kq @Spine @atmal

Na pewno gdzieś poza ifem nie Inkrementujesz tego i2? Poza tym oryginalny program działa poprawnie(sprawdzałem) zgodnie z tym, jak go Zaprojektowałeś, zlicza te znaki, które są w tablicy. Więc o co chodzi z tym dodawaniem symboli spoza niej?

Pokaż cały kod to znajdziemy problem, bez sensu tak zgadywać ;)

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>


int main()
{
   int f = 0; int i=0; int i2=0;
   char ch;

   char alf[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; //tablica ma 26 elementow
   int wynik[26] = {[25] = 0};

   printf("Wpisz jakies slowo, a ja wypisze, ile razy wystepuje dana litera\n");
   printf("Wpisz slowo: \n");

   while( (ch = getchar()) != '\n')
   {
       while(f<1)
       {

        if(ch == alf[i])
        {
           i2++;
           wynik[i]++;
           f=1;
        } i++;

       } f=0; i=0;
   } i=0;

   printf("\nPodane slowo ma %d liter\n", i2);
   printf("\nZawiera nastepujace litery:\n");

   while(i<26)
   {
       if(wynik[i] == 0)
       {
           i++;
           continue;
       }

       printf("Litera %c wystepuje %d razy\n", alf[i], wynik[i]);
       i++;
   }
   getchar();


    return 0;
}

Jedyna zmiana której dokonałem w porównaniu z pierwszym postem, to wrzucenie i2++ do ifa sprawdzającego zmienną ch, gdyż wcześniej był poza tym ifem(zresztą wtedy i tak to nie działało).

Naruszasz pamięć.
Inkrementujesz i dla tablicy alf w pętli while nie patrząc na maksymalny indeks, w rezultacie wychodząc poza tą tablicę.

atmal napisał(a):

Naruszasz pamięć.
Inkrementujesz i dla tablicy alf w pętli while nie patrząc na maksymalny indeks, w rezultacie wychodząc poza tą tablicę.

No ale jak wpisze sobie !!$$, to mamy znaki, których nie ma w tablicy alf[], więc program nie powinien chyba nawet wchodzić do tego ifa:

if(ch == alf[i])
        {
           i2++;
           wynik[i]++;
           f=1;
        } 

A najdziwniejsze jest to, że wchodząc do tego ifa, program zwiększa zmienną i2, ale już NIE zwiększa zmiennej wynik[i], a powinien, skoro wszedł do tego ifa. To wygląda tak, jakby program sobie po prostu pominął inkrementacje zmiennej wynik.

Przy naruszeniu pamięci ciężko powiedzieć co się dzieje.

Dodając takiego if pod i++:

if(i > 25)
    break;

Dla wejścia:

##$$

Program wyświetla:

Podane slowo ma 0 liter
Zawiera nastepujace litery: 

Zmodyfikowałem ponownie program wyrzucając z drugiej pętli ifa sprawdzającego, czy wynik[i] == 0, teraz druga pętla wygląda tak:

  while(i<26)
   {
       printf("Litera %c wystepuje %d razy\n", alf[i], wynik[i]);
       i++;
   }

Po wpisaniu znaków !!$$ taki jest wynik działania programu:

Jak widać na samym początku pojawia się dwa razy litera b, nie wiem czemu, ale kiedy wpiszę np "abc" lub "bc", to program działa normalnie.

Nie wiem, ja jeszcze nie ogarniam za dobrze działania pamięci, więc nie wiem co może być źle. :/

To jest w pętli, tak jak tu:

while ((ch = getchar()) != '\n')
{
    while(i < 26)
    {
        printf("Litera %c wystepuje %d razy\n", alf[i], wynik[i]);
        i++;
    }
}

Czy inaczej?

Bo tu działa mi normalnie.

Pisałem, że wywaliłem ifa z drugiej pętli, teraz program wygląda tak:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int main()
{
   int f = 0; int i=0; int i2=0;
   char ch;

   char alf[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; //tablica ma 26 elementow
   int wynik[26] = {[25] = 0};

   printf("Wpisz jakies slowo, a ja wypisze, ile razy wystepuje dana litera\n");
   printf("Wpisz slowo: \n");

   while( (ch = getchar()) != '\n')
   {
       while(f<1)
       {

        if(ch == alf[i])
        {
           i2++;
           wynik[i]++;
           f=1;
        } i++;

       } f=0; i=0;
   } i=0;

   printf("\nPodane slowo ma %d liter\n", i2);
   printf("\nZawiera nastepujace litery:\n");

   while(i<26)
   {
       printf("Litera %c wystepuje %d razy\n", alf[i], wynik[i]);
       i++;
   }
   getchar();


    return 0;
}

Ale problem znajduje się tu:

while ((ch = getchar()) != '\n')
{
    while (f < 1)
    {

        if (ch == alf[i])
        {
            i2++;
            wynik[i]++;
            f = 1;
        }
        i++; // Wartość tego i nigdy nie jest sprawdzana
    }
    f = 0;
    i = 0;
}
i = 0;
i = 0;

O czym pisałem wyżej.

Nie rozumiem. xD

Czemu ma być sprawdzana? Sprawdzany jest warunek, czy zmienna ch == elementowi tablicy afl[i], jeżeli nie, to program zwiększa jedynie zmienną i i wykonuje ponownie sprawdzenie warunku.

Ewentualnie czy możesz poprawić to tak, żeby działało, wtedy zobaczę sam o co chodzi.

Dobrze, ale zauważ że dla znaku # (lub jakiegokolwiek który nie znajduje się w tablicy alf) program działa tak że sprawdza wszystkie 26 liter (od indeksu 0 po indeks 25) a potem? Potem nadal leci i inkrementuje i wychodząc poza maksymalny indeks i nic go nie zatrzyma (oprócz ochrony naruszenia pamięci).

Racja, wrzuciłem na sam początek pętli while(f<1) taką instrukcję:

if(i==26)
   break;

Teraz wszystko działa poprawnie. Dzięki. :)