Imperfezione codice C

[Darèios89]

C'è un esercizio in C che non mi riesce del tutto, è questo:

Scrivere un programma che legga da tastiera una sequenza A di N stringhe di
lunghezza variabile. L'anagramma principale di una stringa S e l'anagram-
ma di S ottenuto ordinando i suoi simboli individualmente. Ad esempio,
l'anagramma principale di abracadabra e aaaaabbcdrr. Notare che l'ana-
gramma principale di una stringa e unico e che stringhe diverse possono avere
lo stesso anagramma principale.
Il programma deve raggruppare le stringhe di A aventi lo stesso anagram-
ma principale e restituire le stringhe di ciascun gruppo in ordine lessicogra-
co non-decrescente. I gruppi devono essere restituiti in ordine lessicograco
non-decrescente del corrispondente anagramma principale.
L'input e formattato nel seguente modo. La prima riga contiene la lun-
ghezza N della sequenza. Si assuma che N sia maggiore di zero. Le righe
successive contengono le N stringhe che compongono la sequenza A, una
per riga. Si puo assumere che le stringhe abbiano lunghezza inferiore a 20
caratteri.
L'output deve contenere solo e soltanto un gruppo di stringhe per riga.
Le stringhe dello stesso gruppo devono essere separate da uno spazio.

Esempio
Input
7
pluto
abra
pippo
raba
baar
oppip
lupto

Output

abra baar raba
oppip pippo
lupto pluto

Il problema è che il mio codice stampa l'output ma lo restituisce in anagramma cioè:

aabr aabr aabr
ioppp ioppp
lupto lupto

Il mio codice è:

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

#define MAXLEN 1000

char **leggi(int *N){
	char **A;
	scanf("%d", N);
	int i;
	A = malloc(sizeof(char*)*(*N));
	for(i=0;i<*N;i++){
	A[i] = malloc((char)sizeof(MAXLEN)+1);
	scanf("%s",A[i]);
	}
	return A;
		}

char *ordina(char *a){
	int i,j,prossimo;
	for(i=0;i<strlen(a);i++){
		prossimo = a[i];
		j = i;
	while((j>0) && (a[j-1]>prossimo)){
		a[j] = a[j-1];
		j--;
		}
	a[j] = prossimo;
	}
	return a;
			}

int anagramma( char *s1, char *s2){
	int i,min;
	s1 = ordina(s1);
	s2 = ordina(s2);
	if (strlen(s1)<strlen(s2)) min = strlen(s1);
	else min = strlen(s2);
	int trovato = 0;
	for(i=0;i<min && !trovato; i++){
		if (s1[i]<s2[i]){ trovato = 1; return -1;}
		else if (s1[i]==s2[i]) i++;
		else { trovato = 1; return 1; }	
		}
	if (trovato == 0) return 0;
					
			}

int compare(const void *s1, const void *s2){
	return anagramma(*(char **)s1,*(char **)s2);
		}

int main(){
	int N,i;
	char **A;
	A = leggi(&N);
	qsort(A,N,sizeof(char *),compare);
	for(i=0;i<N;i++) printf("%s ",A[i]);		
		}

[Frank Lioty]

Mmm...studente di informatica a Pisa?

[Darèios89]

Emh...non esattamente

E' un esercizio di un mio amico che studia informatica a Pisa, anceh tu sei di lì e hai fatto questo esercizio?
Siccome non funziona qualcosa ma io non ho fatto C, non ho saputo aiutarlo, siccome dubito che il professore risponderà alla sua mail, se puoi dirmi cosa è sbagliato mi faresti un favore.
Lui non è registrato sul sito, quindi mi servirebbe sapere il problema e la soluzione esatta per fargliela sapere, so che non funziona così nei forum ma non potendo aiutarlo non posso fare altro che fornirgli la soluzione alla sua imperfezione.
Sapresti aiutarmi?

[simo_85]

Lui non è registrato sul sito, quindi mi servirebbe sapere il problema e la soluzione esatta per fargliela sapere, so che non funziona così nei forum ma non potendo aiutarlo non posso fare altro che fornirgli la soluzione alla sua imperfezione.

Se sai che non funziona così allora perché lo chiedi invece di pensarvela tutti e due.. O perché il tuo amico ti incarica a te di questi compiti? Non lo capisco...

[simo_85]

Mex duplicato... Sorry.

[Darèios89]

Abbiamo provato, solo che lui non sa quale sia il problema, mica si è arreso a primo colpo, poi me ne ha parlato ma io non conosco il Quicksort e nemmeno il C, ho provato ma non sono riuscito a capire quale sia il problema. Lui non utilizza i forum, quindi visto che io sono registrato ho pensato di postare per dargli una mano.... nella speranza che qualcuno individui il problema.
Spero non dia fastidio...

[Frank Lioty]

provo a darci un occhio...ti faccio sapere

[Frank Lioty]

Beh, quando esegui la funzione ordina, tramite Insertion Sort, perdi la stringa originale, sostituendola con il suo anagramma. Quindi se inizialmente l'input era:

pluto
abra
pippo
raba
baar
oppip
lupto

dopo l'ordinamento ti ritrovi in corrispondenza:

loptu
aabr
ioppp
aabr
ioppp
loptu

(in realtà contemporaneamente ci sarebbe anche l'ordinamento del qsort, che ho volutamente ignorato).

Ti conviene usare un altro array di stringhe dove memorizzare gli anagrammi per poter poi appoggiartici per i vari ordinamenti (così non perderesti le stringhe originali).

Io ho risolto in questo modo (per comodità ho messo le due stringhe, quella che contiene la parola e quella che contiene il corrispettivo anagramma. in una struct):

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

#define LENGTH_STRINGA 20

typedef struct {

char parola[LENGTH_STRINGA];

char anagramma[LENGTH_STRINGA];

} vocabolo;

/*-----------------------------------------------*/

int compare1 (const void *p1, const void *p2) {

vocabolo *s1 = (vocabolo *)p1;
vocabolo *s2 = (vocabolo *)p2;


int n = strcmp(s1->anagramma, s2->anagramma);

return n;

}

/*-----------------------------------------------*/

int compare2 (const void *p1, const void *p2) {

vocabolo *s1 = (vocabolo*)p1;
vocabolo *s2 = (vocabolo*)p2;


return strcmp(s1->parola, s2->parola);

}

/*-----------------------------------------------*/
void *ordina(char *a){
	int i,j,prossimo;
	for(i=0;i<strlen(a);i++){
		prossimo = a[i];
		j = i;
	while((j>0) && (a[j-1]>prossimo)){
		a[j] = a[j-1];
		j--;
		}
	a[j] = prossimo;
	}
	return;
			}

/*-----------------------------------------------*/

int dimensione_anagramma (vocabolo *array_stringhe, int numero_stringhe, int j) {

int dim = 1;
int compare = strcmp(array_stringhe[j].anagramma, array_stringhe[j+1].anagramma); 

while ((j-1<numero_stringhe) && (!compare)) {
j++;
dim++;
compare = strcmp(array_stringhe[j].anagramma, array_stringhe[j+1].anagramma);
}

return dim;

}

/*-----------------------------------------------*/
int main () {

int numero_stringhe;
vocabolo *array_stringhe;


int i;
int j =0;
int stringhe_stesso_anagramma;

scanf("%i", &numero_stringhe);

array_stringhe=(vocabolo*)malloc(numero_stringhe*sizeof(vocabolo));

for (i=0; i<numero_stringhe; i++) {
scanf("%s", array_stringhe[i].parola);
strcpy(array_stringhe[i].anagramma, array_stringhe[i].parola);
/*crea l'anagramma */
ordina(array_stringhe[i].anagramma);
}

/*raggruppa i vocaboli per anagramma*/
qsort(array_stringhe, numero_stringhe, sizeof(vocabolo), compare1);

/*ordina lessicograficamente i vocaboli dello stesso gruppo*/

while (j < numero_stringhe) {
stringhe_stesso_anagramma = dimensione_anagramma (array_stringhe, numero_stringhe, j);
qsort(&(array_stringhe[j]), stringhe_stesso_anagramma, sizeof(vocabolo), compare2);
j +=stringhe_stesso_anagramma;
}
return 0;

}

Praticamente faccio questo:
- creo l'array
- con la scanf inserisco le varie parole
- copio la stringa parola in quella anagramma
- tramite la funzione ordina, anagrammo la stringa anagramma (ora ho realmente l'anagramma)
- ordino le parole per anagramma (ora le stringhe sono raggruppate per anagramma)
- non mi resta che ordinare le stringhe dei singoli gruppi di anagrammi. Per fare ciò: mi ricavo l'indice di inizio di ogni gruppo di stringhe ed il numero di elementi per gruppo di anagramma
- con il qsort riordino i singoli gruppi

manca la stampa ma l'implementazione è immediata (ho controllato il contenuto delle singole stringhe in fase di debugging).

Avrei invece una domanda per gli esperti del forum:

avevo provato a crearmi l'anagramma tramite qsort, ma finiva per mettere in testa tutti gli '\000' degli elementi della stringa rimasti vuoti (questo perché, suppongo io, tramite scanf la stringa non viene "chiusa" tramite il classico carattere finale '\0'). Esiste un modo per evitarsi di dover riscrivere manualmente una funzione di ordinamento e sfruttare il qsort? Avevo provato a specializzare la funzione compare, senza successo.

[Darèios89]

Gli ho fatto sapere...ti ringrazio.

[Alex'87]

Originariamente inviato da Frank Lioty
Avrei invece una domanda per gli esperti del forum:

avevo provato a crearmi l'anagramma tramite qsort, ma finiva per mettere in testa tutti gli '\000' degli elementi della stringa rimasti vuoti (questo perché, suppongo io, tramite scanf la stringa non viene "chiusa" tramite il classico carattere finale '\0').

La scanf chiude correttamente l'array di char. Se qsort ordinava anche i caratteri vuoti è perché tu gli hai detto di farlo.. Come la invochi? Gli passi la lunghezza totale dell'array o solo la lunghezza effettiva della stringa?