[C++]Ordinare alfabeticamente e dire la frequenza delle lettere di una stringa

[alchemy22]

Ciao a tutti,
mi è stato dato questo programmino, ho cercato di farlo ma ho qualche problema....

Questo è il testo:
Scrivere un algoritmo che legga una stringa di 100 caratteri e stampi in uscita:
1) La stringa ordinata alfabeticamente.
2) La frequenza delle lettere dell'alfabeto italiano.

Questo è quello che ho cercato di fare:

#include<stdio.h>
#include<iostream.h>
#include<ctype.h>
#include<conio.h>
#include<cstring.h>
#include<stdlib.h>
typedef char str[101];
char ord_alfa(str);
int freq_lett(str);
void main()
{
  char alfa;
  int freq;
  str z;
  cout<<"Inserisci una stringa \n";
  gets(z);
  alfa=ord_alfa(z);
  freq=freq_lett(z);
  cout<<"La stringa ordinata è "<<alfa;
  cout<<"\n La freq. delle lettere è "<<freq;
}
char ord_alfa(str z)
{
  int i,aux;
  char alfa,x;
  for(i=0;i<strlen(z)-1;i++)
  {
	  for(x=i+1;i<strlen(z);x++)
		  if(z[i]>z[x])
		  {
			  aux=z[i];
			  z[i]=z[x];
			  z[x]=aux;
		  }
	}
	return(alfa);
} 
int freq_lett(str z)
{
	int lettere[21],i;
	char freq;
	for(i=0;i<strlen(z);i++)
	{
		if((z[i]>='a')&&(z[i]<='z'))
		{
			 lettere[z[i]-'a']++;
		}
	}
	for(i=0;i<21;i++)
	{
		if(lettere[i]>0)
		{
			 return(freq);
		}
}

Grazie in anticipo a chi mi possa dare una mano.

[kyxzme]

Counting sort
Quickort

strcmp

Originariamente inviato da alchemy22

Ciao a tutti,
mi è stato dato questo programmino, ho cercato di farlo ma ho qualche problema....

Questo è il testo:
Scrivere un algoritmo che legga una stringa di 100 caratteri e stampi in uscita:
1) La stringa ordinata alfabeticamente.
2) La frequenza delle lettere dell'alfabeto italiano.

Questo è quello che ho cercato di fare:

#include<stdio.h>
#include<iostream.h>
#include<ctype.h>
#include<conio.h>
#include<cstring.h>
#include<stdlib.h>
typedef char str[101];
char ord_alfa(str);
int freq_lett(str);
void main()
{
  char alfa;
  int freq;
  str z;
  cout<<"Inserisci una stringa \n";
  gets(z);
  alfa=ord_alfa(z);
  freq=freq_lett(z);
  cout<<"La stringa ordinata è "<<alfa;
  cout<<"\n La freq. delle lettere è "<<freq;
}
char ord_alfa(str z)
{
  int i,aux;
  char alfa,x;
  for(i=0;i<strlen(z)-1;i++)
  {
	  for(x=i+1;i<strlen(z);x++)
		  if(z[i]>z[x])
		  {
			  aux=z[i];
			  z[i]=z[x];
			  z[x]=aux;
		  }
	}
	return(alfa);
} 
int freq_lett(str z)
{
	int lettere[21],i;
	char freq;
	for(i=0;i<strlen(z);i++)
	{
		if((z[i]>='a')&&(z[i]<='z'))
		{
			 lettere[z[i]-'a']++;
		}
	}
	for(i=0;i<21;i++)
	{
		if(lettere[i]>0)
		{
			 return(freq);
		}
}

Grazie in anticipo a chi mi possa dare una mano.

[tomminno]

Io userei un vector di char e l'algoritmo sort, a meno che questo non sia un esercizio scolastico, che però riguarda il C invece del C++

[Don[ITA]]

Se puoi sfruttare le potenzialità del C++ potresti fare qualcosa del genere:

#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

//true se la lettera è maiuscola
bool is_upper(const char& ch) {
    return ch >= 'A' && ch <= 'Z';
}

//true se la lettera appartiene all'alfabeto italiano
bool italian(const char& ch) {
    return ch != 'j' && ch != 'k' && ch != 'w' && ch != 'x' && ch != 'y';
}

//comparatore usato per ordinare la mappa
struct charcomp {
    bool operator() (const char& ch1, const char& ch2) const {
        if(is_upper(ch1) & !is_upper(ch2)) return ch1 < ch2 + 32;
        else if(!is_upper(ch1) & is_upper(ch2)) return ch1 + 32 < ch2;
        else return ch1 < ch2;
    }
};

//inizializza la mappa ponendo a 0 le occorrenze delle lettere
void fill_map(map<char, int, charcomp>& m) {
    for(unsigned int i = 97; i < 123; i++) {
        if(italian(i))    //escludo le lettere straniere
            m[i] = 0;
    }
}

//legge la stringa da analizzare, se è troppo lunga la tronca
string leggi_stringa(int len, istream& in) {
    char str[len + 1];
    in.get(str, len + 1);
    string s(str);
    return s;
}

//ordina la stringa mediante la funzione sort di algorithm
void sort_string(string& str) {
    sort(str.begin(), str.end());
}

//conta le occorrenze delle lettere dell'alfabeto italiano nella stringa
void count_char(map<char, int, charcomp>& m, const string& s) {
    for(unsigned int i = 0; i < s.length(); i++) {
        if(italian(s[i])) {
            if(is_upper(s[i])) m[s[i] + 32]++;
            else m[s[i]]++;
        }
    }
}

int main(int argc, char *argv[])
{
    int length = 100;               //lunghezza della stringa che vuoi leggere
    string str;                     //stringa da analizzare
    map<char, int, charcomp> m;     //mappa per contare i caratteri

    cout << "Inserisci la stringa: ";
    str = leggi_stringa(length, cin);
    cout << "Hai inserito: " << str << endl;
    sort_string(str);
    cout << "Stringa ordinata: " << str << endl;
    fill_map(m);
    count_char(m, str);
    cout << "Frequenza lettere:" << endl;
    for(map<char, int, charcomp>::iterator i = m.begin(); i != m.end(); i++)
        cout << (*i).first << " -> " << (*i).second << endl;
    system("PAUSE");
    return 0;
}

Ovviamente non ho gestito alcuni casi d'errore per non farti trovare proprio tutta la pappa pronta.

Ciao

[alchemy22]

Originariamente inviato da kyxzme

Counting sort
Quickort

strcmp

Per quanto riguarda l'ordinamento devo utilizzare il cosidetto "ordinamento ingenuo", quello che ho fatto io, in teoria, dovrebbe far tornare al main la stringa ordinata ma restituisce solo la scritta "La stringa ordinata è" e basta.
Non capisco proprio dove sia l'errore.
Per la frequenza delle lettere stavo pensando di creare un array con le lettere dell'alfabeto e poi usare strcmp per fare il confronto.... il problema è che non so come fare e se possa funzionare.

Originariamente inviato da tomminno

Io userei un vector di char e l'algoritmo sort, a meno che questo non sia un esercizio scolastico, che però riguarda il C invece del C++

Si è un esercizio scolastico.
Il prof parla sempre di C++... boh(a volte mi viene il dubbio se sappia veramente quello che dice)

Originariamente inviato da Don[ITA]

Se puoi sfruttare le potenzialità del C++ potresti fare qualcosa del genere:

#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

//true se la lettera è maiuscola
bool is_upper(const char& ch) {
    return ch >= 'A' && ch <= 'Z';
}

//true se la lettera appartiene all'alfabeto italiano
bool italian(const char& ch) {
    return ch != 'j' && ch != 'k' && ch != 'w' && ch != 'x' && ch != 'y';
}

//comparatore usato per ordinare la mappa
struct charcomp {
    bool operator() (const char& ch1, const char& ch2) const {
        if(is_upper(ch1) & !is_upper(ch2)) return ch1 < ch2 + 32;
        else if(!is_upper(ch1) & is_upper(ch2)) return ch1 + 32 < ch2;
        else return ch1 < ch2;
    }
};

//inizializza la mappa ponendo a 0 le occorrenze delle lettere
void fill_map(map<char, int, charcomp>& m) {
    for(unsigned int i = 97; i < 123; i++) {
        if(italian(i))    //escludo le lettere straniere
            m[i] = 0;
    }
}

//legge la stringa da analizzare, se è troppo lunga la tronca
string leggi_stringa(int len, istream& in) {
    char str[len + 1];
    in.get(str, len + 1);
    string s(str);
    return s;
}

//ordina la stringa mediante la funzione sort di algorithm
void sort_string(string& str) {
    sort(str.begin(), str.end());
}

//conta le occorrenze delle lettere dell'alfabeto italiano nella stringa
void count_char(map<char, int, charcomp>& m, const string& s) {
    for(unsigned int i = 0; i < s.length(); i++) {
        if(italian(s[i])) {
            if(is_upper(s[i])) m[s[i] + 32]++;
            else m[s[i]]++;
        }
    }
}

int main(int argc, char *argv[])
{
    int length = 100;               //lunghezza della stringa che vuoi leggere
    string str;                     //stringa da analizzare
    map<char, int, charcomp> m;     //mappa per contare i caratteri

    cout << "Inserisci la stringa: ";
    str = leggi_stringa(length, cin);
    cout << "Hai inserito: " << str << endl;
    sort_string(str);
    cout << "Stringa ordinata: " << str << endl;
    fill_map(m);
    count_char(m, str);
    cout << "Frequenza lettere:" << endl;
    for(map<char, int, charcomp>::iterator i = m.begin(); i != m.end(); i++)
        cout << (*i).first << " -> " << (*i).second << endl;
    system("PAUSE");
    return 0;
}

Ovviamente non ho gestito alcuni casi d'errore per non farti trovare proprio tutta la pappa pronta.

Ciao

Don purtroppo molte cose che hai scritto non le conosco, cominciando dalla libreria include <map> che non l'ho mai sentita, sei troppo avanti
io sono ancora al 3° anno

[kyxzme]

il counting sort funziona in questo modo, allochi un array di 21 elementi, conti le occorrenze in un testo di varie lettere 0=a 21=z

a ogni indice assegni un intero e ogni volta che trovi una corrispondenza di una lettera incrementi quell'intero, per esempio se trovi 3 volte una A allora temp[0] è 3

fatto questo tu hai già il numero di volte in cui compare la singola stringa, e hai fatto metà dell'esercizio usando cunting sort, però il counting sort non è ancora finito, successivamente comunque (nel tuo caso dovresti salvarti l'array temp , visto che ti serve il numero di corrispondenze) quindi ti fai un nuovo array di interi e copi i valori che hai nel primo pari pari, in più addi all'elemento attualmente puntato il numero di occorrenze dell'elemento successivo, in questo modo

partendo da questo
x[0] = 2
x[1] = 3

arrivi a dire che a c'è 2 volte e b c'è 3 aggiungi quindi all'elemento puntato il numero di corrispondenze dell'elemento successivo e hai l'offset in cui devi terminare di inserire la lettera corrente e iniziare a inserire quella dopo

in pratica

x[0]=2
x[1]=5
x[2]=x[1]+corrispondenze di C

aabbb etcetc
io sono un libro stracciato però è abbastanza semplice ed è ciò che risolve il tuo problema più facilmente il counting sort

[alchemy22]

Grazie kyxzme mi sembra un buon metodo, non è che mi faresti vedere una bozza del codice? Giusto per darmi un'idea..
In teoria dovrei farlo per domani quindi, sempre in teoria, entro oggi dovrei riuscire a finirlo...

[Don[ITA]]

Ti scrivo uno pseudo codice al "volo":

algoritmo(string s)
begin:
    int occorrenze[21];
    for i := 0 to 21 do:
        occorrenze[i] := 0               //inizializzo l'array delle occorrenze a 0
    for ogni carattere c in s do:
        int i := indice(c);
        occorrenze[i]++;                 //incremento il contatore corrispondente al carattere c
    int indice = 0;
    for ogni int i in occorrenze do:
        if occorrenze[i] > 0 then:
            for j := indice to occorrenze[i] do:
                s[j] := carattere(i);
            indice := occorrenze[i];
    stampa(s);                             //stampo la stringa ordinata
    stampa(occorrenze);                //stampo le occorrenze di ogni carattere
end;

indice(char c)
begin:
    switch(c):
        case 'A':
        case 'a':
            return 0;
        case 'B':
        case 'b':
            return 1;
        ...eccetera eccetera...
end;

carattere(int i)
begin:
    switch(i):
        case 0: return 'a';
        case 1: return 'b':
        ...eccetera eccetera...
end;

Inutile dire che questo pseudo codice funziona correttamente se e solo se la tua stringa è composta da caratteri appartenenti all'alfabeto italiano.

[alchemy22]

mi scuso per l'assenza ma ho avuto problemi con la l'adsl.
comunque.... alla fine il problema l'ho risolto e funziona perfettamente, eccolo qui(non sarà il massimo della professionalità, ma l'importante è che funzioni..).

#include<stdio.h>
#include<iostream.h>
#include<ctype.h>
#include<conio.h>
#include<cstring.h>
#include<stdlib.h>
typedef char str[101];
void ord_alfa(str);
void freq_lett(str);
void main()
{
  str z;
  cout<<"Inserisci una stringa \n";
  gets(z);
  ord_alfa(z);
  freq_lett(z);
}
void ord_alfa(str z)
{
  int i,x,aux;
  for(i=0;i<strlen(z);i++)
  {
	  for(x=0;x<strlen(z);x++)
	  {
		  if(z[i]<z[x])
		  {
			  aux=z[i];
			  z[i]=z[x];
			  z[x]=aux;
		  }
	  }
	}
	cout<<"La stringa ordinata è ";
	for(i=0;i<strlen(z);i++)
	{
		 cout<<z[i];
	}
}
void freq_lett(str z)
{
  int i,j;
  int cont[21]={0};
  char alfabeto[22]="abcdefghilmnopqrstuvz";
  for(i=0;i<strlen(z);i++)
  {
	  for(j=0;j<strlen(alfabeto);j++)
	  {
			 if(z[i]==alfabeto[j])
			 {
				  cont[j]++;
			 }
		}
	}
	cout<<"\nLa frequenza delle lettere è:";
	for (j=0;j<21;j++)
	{
		cout<<"\n           "<<alfabeto[j]<<" -> "<<cont[j];

	}
}

grazie a tutti!!