Newsgroup: it.comp.lang.c++
Titolo: rimuovere caratteri ripetuti in una stringa

Salve, mi dareste un aiutino - a parole - per risolvere questo tipo di 
esercizio?
"Scrivere un programma che rimuova tutti i caratteri ripetuti presenti
in una stringa.
Un possibile output del programma potrebbe essere questo:
Inserisci una stringa: Questa stringa contiene caratteri ripetuti
Stringa senza ripetizioni: Questa ringcop  "
PS: non abbiamo studiato nè puntatori nè classi e oop in generale...
 

 wrote

Bene questa e' una idea usando la libreria standard del C++. Se non avete 
studiato la libreria standard (ex STL), iteratori, string e set, come credo 
di capire, allora dovrai implementare la stessa idea (o simile) senza l'uso 
di queste classi gia' fatte:
<code>
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main()
{
    string str("Questa stringa contiene caratteri ripetuti");
    set<char> used;
    for(size_t i=0; i<str.size(); ++i){
        char c = str[i];
        if(used.find(c) == used.end()){
            used.insert(c);
            cout << c;
        }
    }
    cout << endl;
}
</code>
Il funzionamento e' semplice:
Hai una stringa str che contiene la tua stringa.
Hai un insieme (set) di caratteri che si chiama used, i caratteri che hai 
gia' usato, all'inizio questo insieme e' vuoto.
Dopo di che, con il ciclo for scorro la stringa dal primo carattere 
all'ultimo. Lo faccio utilizzando una variabile per non confonderti con 
iteratori ed altre cose che probabilmente non hai ancora visto.
A questo punto leggo il carattere corrente nella variabile c. Questa 
variabile alla prima iterazione conterra' il carattere 'Q' poi 'u' ...etc... 
fino a finire la stringa. In ogni iterazione controllo se il carattere 
corrente e' gia' stato utilizzato (usando la funzione find() lo cerco 
all'interno dell'insieme).
Se non e' stato utilizzato (== used.end()) allora lo inserisco nell'insieme 
e lo stampo a video. Inserendolo nell'insieme la prossima volta lo trovero' 
e lo saltero'. Ovviamente se il carattere viene trovato allora non stampo a 
video nulla.
<output>
Questa ringcop
Press any key to continue
</output>
Lo stesso algoritmo lo puoi implementare usando un array di caratteri come 
stringa e una tua implementazione veloce di set, ad esempio con un semplice 
array.
Ecco ad esempio scritto in C++ in stile C piu' che C++:
<code>
#include<iostream>
using namespace std;
int main()
{
    char str[] = "Questa stringa contiene caratteri ripetuti";
    unsigned char used[256] = {0};
    for(int i=0; i<sizeof(str); ++i){
        unsigned char c = str[i];
        if(!used[c]){
            ++used[c];
            cout << c;
        }
    }
    cout << endl;
}
</code>
La versione in stile C se non hai familiarita' con string e set e' molto 
piu' semplice da leggere e visto la brevita' e la semplicita' va anche bene. 
In generale pero', in C++, e' sempre meglio evitare array in stile C se 
possibile.
Nel caso non avessi familiarita' con questa istruzione:
unsigned char used[256] = {0};
crea used, un array di 256 caratteri (da 0 a 255) e inizializza tutti i 256 
elementi a 0.
un unsigned char ha 8 bits, quindi puo' contenere valori da 0 a 255.
if(!used[c]) invece esegue il corp dell'if se il l'array nella posizione del 
carattere contiene il valore 0. Puo' essere riscritto come
if( used[c] == 0)
se preferisci.
L'output e' lo stesso.
In questo caso e' stato semplice emulare set in quanto lavoriamo con numeri. 
Tieni conto pero che un:
set<string>
o ancora peggio un
set<mia_classe_fatta_da_me>
non si riesce piu' ad emulare con un semplice array (se ti interessano le 
prestazioni).
Infatti un array, all'intero di [] prende solo un indice numerico, non puo' 
prendere una stringa ne una classe definita dall'utente.
Set invece e' piu' flessibile e meno error-prone (non rischi mai di andare 
oltre alla fine dell'array, cosa semplice in C basta scrivere used[400] con 
used dichiarato come used[256]).
Beh, in questi casi set va emulata con qualche cosa di piu' complesso tipo 
una hash table, se ti interessa la velocita' di esecuzione, o un semplice 
array di stringhe se proprio non ti interessa la velocita' di escuzione. In 
questo secondo caso pero' per sapere se c'e' l'elemento o meno, invece di 
richiedere tempo O(1) il tempo diventa O(n) in quanto devi scorrere tutta la 
lista (array) di stinghe o di classi definite dall'utente per vedere se 
l'elemento c'e'.
Beh, inutile elogiare le caratteristiche del C++ e di STL....
Spero ti sia di aiuto,
Tommaso

             ++used[c];
Cosi' e' counting, ma andrebbe benissimo anche:
used[c] = true;
trasformandolo in bool ed evitando ogni sorta di problema di overflow.
Per concludere, la cosa migliore e' non contare ed usare bool. Se vuoi
contare usa un tipo abbastanza grande da non creare problemi, int
dovrebbe andare benone (unsigned char un pochino stretto forse ;-)
Tommaso 
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Cosi' e' counting, ma andrebbe benissimo anche:
Ahah! Il lunedi' mattina e' meglio che io faccia altro, almeno prima di
aver preso almeno un paio di caffe... (il lunedi' e' sveglia alle 4am e
3 ore di autostrada)...
Non e' mai stato counting e non c'e' mai stato rischio di overflow.
Ad ogni modo bool ha piu' senso piuttosto che unsigned char!
Scusate per il messaggio scritto mezzora fa.
