Ordinamento alfabetico stringhe->Risultati imprevisti (urgente:Progetto d'esame :S)

[KevinMoore]

Salve a tutti, chiedo scusa per la brutalità con cui, da neoiscritto, mi trovoimmediatamente a postare i miei problemi in cerca di soluzione, ma a giorni ci sarà un esame e devo finire questo progetto prima possibile. Passo ad esporre la parte di questo progetto che mi da problemi...

Sostanzialmente ho un array bidimensionale su cui sono salvate 10'000 stringhe, precedentemente generate in modo totalmente casuale dal calcolatore. Ora... mi si richiede di ordinarle seguendo il classico ordine alfabetico, ma sebbene tale ordinamento (realizzato sostanzialmente con un bubblesort) sia riuscito in termini pratici, a livello di formattazione, nel file di uscita txt la lista delle stringhe correttamente ordinate è preceduta da un paio di migliaia di "andate a capo"a vuoto. Ora... poiché il ciclo di stampa viene eseguito 10.000 volte, il fatto che parte di queste 10'000 venga impiegato per stampare spazi vuoti, si traduce in un troncamento delle stringhe effettivamente stampate (da 10'000 che erano a 8'087 circa, se non ricordo male).

Premetto che provando a stampare l'array senza ordinarlo vi è UN solo rigo vuoto nel file di output, quello che segue l'ultima stringa, dato che ogni stringa contiene un "\n" per l'andata a capo, e non sono presenti stringhe di dimensioni inferiori ai 2 caratteri, né superiori a 20. Quindi mi pare evidente che l'errore sembra stare nei cicli for del bubblesort, che copio integralmente:

int alpha; /*Variabile in cui raccolgo il risultato di strcmp*/
for (g=0; g<cont; g++){/*cont è la macro, sta per 10'000*/
for (j=g; j<cont; j++){
alpha=strcmp(stringhe[g],stringhe[j]); /*stringhe è l'array bidimensionale (char stringhe[cont][21])*/
if(alpha>0)
swap (&stringhe[g], &stringhe[j]); /*Funzione di scambio*/
}
}

Per completezza inserisco anche il codice della funzione swap. Non escludo che il mio sbaglio possa risiedere anche qui, perché è la prima volta che mi trovo a scambiare intere stringhe, e probabilmente ho sbagliato qualcosa a livello di sintassi...

void swap(int *a, int*b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}


Spero che qualcuno sappia darmi delucidazioni :(

[ndakota]

Perchè la funzione swap è tra interi? Mi sembra che tu gli passi due stringhe no?
Inoltre se si tratta di due stringhe non c'è bisogno della & nella chiamata di swap. In ogni caso penso mi sfugga qualcosa perchè da come dici questo codice dovrebbe compilare.

[KevinMoore]

Ti ringrazio molto, siccome nello stesso programma riordino anche dei numeri avevo già programmato la funzione swap tra interi e dato il sonno non mi ero accorto che erano di tipo int... ad ogni modo non ho risolto, anzi...

Se prima il problema era che pur riordinandoli in ordine alfabetico metteva 2mila righe vuote all'inizio (e perdevo qunidi 2000 stringhe stampate), cambiando i tipi di dato in input della funzione swap (che ho ricopiato chiamandola swapstr) e togliendo le & nel punto in cui passo le stringhe a swapstr accade questo:

- Le stringhe vengono stampate SENZA venire riordinate
- Viene lasciato un rigo tra una stringa e l'altra
- La prima lettera di ogni stringa viene perduta per motivi a me ignoti

Se può essere d'aiuto copio l'intero codice:



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#define cont 10000


/*Prototipo funzione di scambio variabili SWAP*/
void swap(int *a, int*b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void swapstr(char *a, char *b){
char temp;
temp=*a;
*a=*b;
*b=temp;
}

/*Prototipo funzione per la generazione di caratteri casuali*/
char rand_char(){
char lettere[] = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz", c;
c = lettere[rand()%strlen(lettere)];
return c;
}


/*Inizio Funzione Main*/
int main() {

int i, j, lungstring;
char *v;
FILE *fn, *fs;

v = (char *) malloc(cont*sizeof(char));
srand(time(0));

/*GENERO IL FILE "NUMERI.TXT"*/
fn = fopen("numeri.txt", "w");
for (i=0; i < cont; i++) {
fprintf(fn, "%d", rand() %100000);
if (i<cont-1){ /*Se l'elemento stampato è il decimillesimo non andare a capo*/
fprintf(fn, "\n");
}
}
fclose(fn);

/*GENERO IL FILE "STRINGHE.TXT"*/
fs = fopen("stringhe.txt", "w");
for (i=0; i < cont; i++){
lungstring = (rand()%20)+2;
for (j=0; j < lungstring; j++){
v[j] = rand_char();
}
v[lungstring]='\0';

fprintf(fs, "%s", v);
if (i<cont-1){
fprintf(fs, "\n");
}
}

fclose(fs);

/***********************************************************/
/*************OPERAZIONI SUL FILE NUMERI.TXT****************/
/***********************************************************/

/************LETTURA DA FILE*****************/
fn = fopen("numeri.txt", "r");
int n[cont];
for (i=0; i<cont; i++){
fscanf(fn, "%d", &n[i]);
}
fclose(fn);

/************************************************BACKUP************************************/
int backup[cont]; /*Array di copia dell'array letto da file*/
for (i=0; i<cont; i++)
backup[i]=n[i];

/*************************************************************ALGORITMO BUBBLESORT**************************************************/
clock_t start, finish;
start=clock();

int g;
for (g=0; g<cont; g++){
for (j=g; j<cont; j++){
if(n[g]>n[j])
swap (&n[g], &n[j]);
}
}

/**STAMPA SU FILE DA BUBBLESORT**/
FILE *ordinati;
ordinati=fopen("numeri ordinati.txt", "w");
fprintf(ordinati, "Elenco dei numeri riordinati in ordine crescente:\n");
for (i=0; i<cont; i++)
fprintf(ordinati, "%d\n", n[i]);
fclose(ordinati);
/***************************RIPRISTINO ARRAY ****************************/
for (i=0; i<cont; i++)
n[i]=backup[i];
/***************************TEMPO***************************/

finish=clock();
double tempo;
tempo=(finish-start);
ordinati=fopen("numeri ordinati.txt", "a");
fprintf(ordinati, "Il tempo di esecuzione dell'algoritmo bubblesort su 10'000 elementi e' %f", tempo/(double)CLOCKS_PER_SEC);
fclose(ordinati);



/************************************************OPERAZIONI SUL FILE STRINGHE.TXT***************************************************************/



/*Apro il file "stringhe.txt"*/
fs = fopen("stringhe.txt", "r");
char stringhe[cont][21]; /*Vettore bidimensionale per memorizzare le stringhe*/

/*Leggo le righe del documento e salvo le stringhe in un array*/
for (i=0; i<cont; i++){
fgets(stringhe[i], 21, fs);
}
fclose(fs);
/*************************BACKUP*******************************/

char strbackup[cont][21];
for (i=0; i<cont; i++)
strcpy(strbackup[i], stringhe[i]);
int alpha;
start=clock();
for (g=0; g<cont; g++){
for (j=g; j<cont; j++){
alpha=strcmp(stringhe[g],stringhe[j]);
if(alpha>=0)
swapstr (stringhe[g], stringhe[j]);
}
}




FILE *strord;
strord=fopen("stringhe ordinate.txt", "w");
for (i=0;i<cont;i++){
fputs(stringhe[i], strord);
}
finish=clock();
tempo=(finish-start);
fprintf(strord,"Il tempo di esecuzione dell'algoritmo su 10'000 stringhe è %f", tempo/(double)CLOCKS_PER_SEC);
fclose(strord);

system("pause");
return 0;

}

[ndakota]

Le stringhe in C si confrontano con la funzione strcmp. E penso che in molti casi dove te assegni dovresti usare invece strcpy. Non sono fresco di C ma inizieri a vedere queste due cose.

[dr_kabuto]

Ciao,
nella parte in gui leggi le stringhe dal file e nella parte in cui effettui l'ordinamento, dimensiona le stringhe a 23 caratteri invece di 21. Manca infatti lo spazio per lo '\0' (terminatore di stringa) e il carattere di fine riga '\n'.