[c] quicksort per ordinare parole

[Death By Stereo]

Salve a tutti, sono molto inesperto in materia quindi vi chiedo un piccolo aiuto. Dovrei creare un programma in c che riceve dallo standard input (la tastira credo) una serie di parole, intese come array di caratteri e usando la funzione quicksort le dovrebbe stampare in ordine alfabetico. Qualcuno mi saprebbe dare qualche dritta in merito?

Grazie ciao

[andbin]

Originariamente inviato da Death By Stereo

Salve a tutti, sono molto inesperto in materia quindi vi chiedo un piccolo aiuto. Dovrei creare un programma in c che riceve dallo standard input (la tastira credo) una serie di parole, intese come array di caratteri e usando la funzione quicksort le dovrebbe stampare in ordine alfabetico. Qualcuno mi saprebbe dare qualche dritta in merito?

Facciamo qualche premessa:
1) Devi poter inserire un numero arbitrario di parole senza alcun limite prefissato oppure al massimo un tot di parole o ancora chiedere all'utente quante parole vuole inserire?
2) Da quello che hai detto non ho capito se l'algoritmo 'quicksort' devi implementarlo tu oppure se ti basta sfruttare la ben nota funzione standard qsort().

Come sviluppare il programma, dipende molto dalle risposte a queste due questioni.

[yorkeiser]

Per l'inserimento delle parole puoi utilizzare un ciclo con una fgets, prendi spunto da queste righe di codice che ti posto

char* stringa[MAX_STRINGHE];

for (i=0;i<10;i++)
{
stringa[i] = (char*) malloc (MAX_LENGTH);
fgets(stringa[i],MAX_LENGTH,stdin);
}

Per il quicksort:
http://it.wikipedia.org/wiki/Quicksort

Guardati anche la funzione strcmp, che ti può tornare utile nel definire l'ordinamento tra stringhe

[Death By Stereo]

Originariamente inviato da andbin

Facciamo qualche premessa:
1) Devi poter inserire un numero arbitrario di parole senza alcun limite prefissato oppure al massimo un tot di parole o ancora chiedere all'utente quante parole vuole inserire?
2) Da quello che hai detto non ho capito se l'algoritmo 'quicksort' devi implementarlo tu oppure se ti basta sfruttare la ben nota funzione standard qsort().

Come sviluppare il programma, dipende molto dalle risposte a queste due questioni.

1) sarebbe meglio poter inserire parole senza alcun limite prefissato anche se non vorrei complicarmi troppo la vita visto che comunque credo che le esigenze pratiche non superino mai le 1000-2000 parole.

2) l'algoritmo quicksort lo devo implementare io, mi è stato espressamente vietato l'uso della funzione già fatta (sapete è un compito dell'università )

Grazie mille

[andbin]

Originariamente inviato da Death By Stereo

1) sarebbe meglio poter inserire parole senza alcun limite prefissato anche se non vorrei complicarmi troppo la vita visto che comunque credo che le esigenze pratiche non superino mai le 1000-2000 parole.

Ok, allora iniziamo col dire che devi usare un array di puntatori a char. Ogni elemento in questo array è un puntatore di tipo char* che punta ad una stringa.

Se si volesse mettere un limite prefissato, si potrebbe fare ad esempio:

char *stringhe[50];

Se le stringhe sono davvero tante o se si vuole fare in modo da poter "allungare" l'array a tempo di esecuzione, è necessario dichiarare l'array in questo modo:

char **stringhe;

stringhe = (char**) calloc (1000, sizeof (char*));

(ho usato calloc perché così almeno la memoria viene inizializzata a 0, i puntatori in pratica sono messi a NULL).

Avendo allocato dinamicamente l'array si potrebbe, durante l'esecuzione, aumentare facilmente la dimensione dell'array.

Comunque una volta che hai l'array, fai un ciclo for al cui interno allochi spazio per ogni singola stringa e poi effettui l'input ad esempio con la funzione fgets().

Originariamente inviato da Death By Stereo

2) l'algoritmo quicksort lo devo implementare io, mi è stato espressamente vietato l'uso della funzione già fatta (sapete è un compito dell'università )

Ok, allora ti sarà sicuramente molto utile il link che ti è già stato segnalato su Wikipedia.

[Death By Stereo]

Originariamente inviato da andbin

Ok, allora iniziamo col dire che devi usare un array di puntatori a char. Ogni elemento in questo array è un puntatore di tipo char* che punta ad una stringa.

Se si volesse mettere un limite prefissato, si potrebbe fare ad esempio:

char *stringhe[50];

Se le stringhe sono davvero tante o se si vuole fare in modo da poter "allungare" l'array a tempo di esecuzione, è necessario dichiarare l'array in questo modo:

char **stringhe;

stringhe = (char**) calloc (1000, sizeof (char*));

(ho usato calloc perché così almeno la memoria viene inizializzata a 0, i puntatori in pratica sono messi a NULL).

Avendo allocato dinamicamente l'array si potrebbe, durante l'esecuzione, aumentare facilmente la dimensione dell'array.

Comunque una volta che hai l'array, fai un ciclo for al cui interno allochi spazio per ogni singola stringa e poi effettui l'input ad esempio con la funzione fgets().

Ok, allora ti sarà sicuramente molto utile il link che ti è già stato segnalato su Wikipedia.

Ok, più o meno ci sono anche se non credo di poter usare la funzione fgets() perchè ho delle limitazioni per il fatto che è un compito.
Quell'articolo di wikipedia l'avevo già letto ma non mi sono molto chiare le modifiche che dovrei fare per passare da un ordinamento di int a un ordinamento di char.
Cioè, con gli int mi basta inserire n interi e poi con > e < li potrei ordinare.
Con le parole il discorso è più complicato, come posso fare a dire al computer che la lettera "b" và dopo la "a"?


Grazie ancora...

[andbin]

Originariamente inviato da Death By Stereo

Ok, più o meno ci sono anche se non credo di poter usare la funzione fgets() perchè ho delle limitazioni per il fatto che è un compito.

Ah beh, puoi anche usare scanf.

Originariamente inviato da Death By Stereo

Quell'articolo di wikipedia l'avevo già letto ma non mi sono molto chiare le modifiche che dovrei fare per passare da un ordinamento di int a un ordinamento di char.
Cioè, con gli int mi basta inserire n interi e poi con > e < li potrei ordinare.
Con le parole il discorso è più complicato, come posso fare a dire al computer che la lettera "b" và dopo la "a"?

È molto semplice. Prendiamo l'esempio di quicksort in "C" che trovi su quella pagina di Wikipedia.

Viene passato alla funzione un array di int (int array[]). Quindi in array[i] hai un intero. Ora passiamo alle stringhe, quello che dovrai passare è un array di stringhe (char **array) in cui array[i] è un puntatore ad una stringa.

Mentre per gli interi puoi fare comparazioni semplicemente con < >, con le stringhe usi la funzione strcmp().
Quando devi scambiare di posizione due elementi, scambierai semplicemente i due puntatori alle stringhe.

[Death By Stereo]

provo poi ti dico

Ti ringrazio

[eolo11]

allora.. credo che tu sia uno studente del bernardinello come me^^
e ti dico che non basta sapere che la B va dopo la A... ma bisogna anche fargli capire come ordinare l'intera parola
ovvero... albero e aceto... entrambe iniziano con la A... però dopo il controllo della prima lettera deve controllare anche le altre^^

e bisogna evitare che al controllo della seconda lettera non porti sopra una parola posta più in basso
esempio... albero e cane... almeno viene prima per l'iniziale... ma per la seconda lettera viene dopo

[andbin]

Originariamente inviato da eolo11

non basta sapere che la B va dopo la A... ma bisogna anche fargli capire come ordinare l'intera parola
ovvero... albero e aceto... entrambe iniziano con la A... però dopo il controllo della prima lettera deve controllare anche le altre^^

strcmp()

[eolo11]

grazie

[XSonic]

Mi sono sempre chiesto...
char *nome[5]

* sta per...? E il doppio**?

Grazie

[andbin]

Originariamente inviato da XSonic

Mi sono sempre chiesto...
char *nome[5]

Un "array di 5 puntatori a char".

Originariamente inviato da XSonic

* sta per...?

Puntatore a ....

Originariamente inviato da XSonic

E il doppio**?

Puntatore a puntatore a ...

[Death By Stereo]

Originariamente inviato da eolo11

credo che tu sia uno studente del bernardinello come me^^

[XSonic]

Originariamente inviato da andbin

Un "array di 5 puntatori a char".

Puntatore a ....

Puntatore a puntatore a ...

Più o meno so a cosa serve un puntatore ma mi sa che per capire questo doppio puntatore dovrei leggermi qualche definizione

[Veon]

Originariamente inviato da eolo11

allora.. credo che tu sia uno studente del bernardinello come me^^

No ma và!! nessuno lo è qua...

Che gruppo sei te?

[eolo11]

grubbo B