[C] tema di difficile comprensione!! aiuto

[PaSteam]

salve a tutti

dovrei realizzare questo progetto non chiedo assolutamente la soluzione
ma solo un interpretazione delle ultime 2,3 righe in quanto sta creando diversi grattacapi a me e a miei compagni

ecco il testo

Sia dato un semplice database che rappresenta un elenco di studenti che hanno sostenuto un esame.
Il database `e organizzato sotto forma di file di testo su 3 colonne contenenti informazioni relative
a (Cognome, Matricola, Voto) come ad esempio:

congnome| matricola | voto
________________________________
bianchi | 21323 | 21
rossi | 34342 | 23
verdi | 21212 | 28
________________________________

Scrivere un programma ANSI C che acquisice il database da file, ne effettua un ordinamento in base alla chiave primaria (Cognome) o alle chiavi secondarie (Matricola, Voto) sulla base della scelta dell’utente e produce in uscita il database ordinato. L’ordinamento sulle chiavi secondarie deve conservare l’ordine relativo prodotto dalla chiave primaria.

abbiamo avute diverse idee come :

"credo che sia necessario usare qualche algoritmo di ordinamento stabile tipo (bubble sort o merge sort da verificare) su un array eventualmente di struttura e usarlo su qualsiasi chiave per cui se ordini l'array prima per una chiave secondaria senza avere preventivamente ordinato sulla chiave primaria ottieni un ordinamento per chiave secondaria che a parità di valori potrebbe non avere le chiavi primarie ordinate in quanto manterebbero la disposizione precedente non ordinata"

vi prego aiutateci a decifrare il testo
grazie

[MinaVagante]

ma non avete capito la consegna??
io ho capito così: voi avete questo file che contiene delle informazioni completamente messe a caso.
se l'utente sceglie di ordinare in base al nome, chiave primaria, il programma creerà un semplice elenco ordinato alfabeticamente, io di c ne so veramente poco, ma un array di strutture penso sia la cosa migliore da fare
se l'utente sceglie di ordinare in base al numero di matricola, anche in questo caso non ci sono grossi problemi, in quanto è impossibile che due studenti abbiamo uno stesso numero di matricola.
più probleematico è il terzo caso, in quanto ci possono essere degli utenti che abbiano lo stesso voto, e qui ci dovrà essere un ordine sulla chiave secondaria ma anche su quella primaria.
esempio
binachi | 21323 | 21
rossi | 32324 | 23
verdi | 34343 | 21
gialli | 35674 | 29

il programma dovrà eseguire se l'utente sceglie l'ordinamento per voto:
bianchi |...| 21
verdi |...| 21
rossi |...| 23
gialli |...|29

almeno io l'ho capita così, può darsi che sia completamente sbagliato

[gugoXX]

Sta chiedendo che ci sia la possibilita' di ottenere in output l'elenco
- Ordinato per cognome
- Ordinato per matricola, cognome
- Ordinato per Voto, Cognome.

Poi il fatto che cognome sia stato assunto come chiave primaria secondo me e' un errore del testo. Piu' naturale sarebbe stata la scelta della matricola.

Non e' necessario un algoritmo stabile di ordinamento.
Se potete usarlo va benissimo la qsort del C standard.
E' sufficiente scrivere la funzione d'ordine tenga conto di 2 campi invece che di 1 solo.

[PaSteam]

Originariamente inviato da MinaVagante

ma non avete capito la consegna??

si è questo il punto abbiamo capito tutti una cosa diversa dall' altra
volevamo pareri di persone sicuramente + esperte di noi anche per vedere chi ci si è avvicinato di + , ti ringrazio per il tuo intervento

Originariamente inviato da gugoXX

Poi il fatto che cognome sia stato assunto come chiave primaria secondo me e' un errore del testo. Piu' naturale sarebbe stata la scelta della matricola
..

in effetti lo penso anche io ma ti assicura che è giusto cosi

Originariamente inviato da gugoXX

Non e' necessario un algoritmo stabile di ordinamento.
Se potete usarlo va benissimo la qsort del C standard.
E' sufficiente scrivere la funzione d'ordine tenga conto di 2 campi invece che di 1 solo
..

no purtroppo qsort non credo che si possa utilizzare altrimenti sarebbe troppo facile

quale funzione di ordianamento sarebbe la più indicata?
dovendo scegliere tra insertsort, selectsort, quicksort , mergesort ed heapsort?

[wizard1993]

il quicksort non è stabile, ma è, a mio avviso, quello più semplicemente implementabile tra gli algoritmi a complessità logaritmica, il merge è, se non mi saglio, l'unico stabile tra i tre, l'heap non lo conosco.
bubble e altri "così" quadratici toglili di torno, ti abbassano di mezzo voto la valutazione come minimo (sempre che il vostro profesore sia tipo quelli che ho io)

[PaSteam]

Originariamente inviato da wizard1993

il quicksort non è stabile, ma è, a mio avviso, quello più semplicemente implementabile tra gli algoritmi a complessità logaritmica, il merge è, se non mi saglio

in effetti il quicksort è il più sensato

cmq se quacuno si vuole cimentare ancora a dare una spiegazione ( a parole)
dell' ultima parte del compito è ben accetto

[wizard1993]

Originariamente inviato da PaSteam

in effetti il quicksort è il più sensato

cmq se quacuno si vuole cimentare ancora a dare una spiegazione ( a parole)
dell' ultima parte del compito è ben accetto

rileggendo però il testo dell'esercizio il quicksort deve essere pensionato in quanto non è stabile e non manitene il precedente ordine delle chiavi ma le ributta ognuna in un posto diverso,
una volta che hai l'array con i dati puoi facilemente far scegliere all'utente quale criterio di ordinamento usare tramite un switch. poi semplicemente rimandi indietro l'array, invece di sovrascrivere il metodo di ordinamento, puoi usare invece solo sovrascrivere i metodi comparatori, in maniera che aderiscano allo stesso formato cioè quello dell strcmp che come vedi qui
http://www.cplusplus.com/reference/c...ng/strcmp.html
prende in input due stringhe e ritorna -1 o minori se la prima è minore, 0 se sono uguali, altrimenti 1 se la prima è maggiore

puoi creare una funzione cmp che accetti o in input due char array o due int (tramite l'overloading) e ritorna il formato sopra detto, per gli char fai ritornare il risultato di string compare (strcmp) per l'int fai ritornare la sottrazione fra il primo e il secondo
poi crei un algoritmo di ordinamento merge sort, che puoi vedere qui
http://en.wikipedia.org/wiki/Mergesort

[gugoXX]

Originariamente inviato da wizard1993

rileggendo però il testo dell'esercizio il quicksort deve essere pensionato in quanto non è stabile e non manitene il precedente ordine delle chiavi ma le ributta ognuna in un posto diverso

Non e' necessario che l'algoritmo di ordinamento sia stabile.
E' sufficiente che si sappia scrivere la funzione di ordinamento su due campi invece che uno solo.
Poi se proprio non ci si fida si usa qualcosa come il mergesort che e' stabile e buonanotte.
Ma stabile o non stabile, se dentro la chiave di ordinamento c'e' anche la chiave primaria (come lo e' per tutte le richieste) allora il risultato sara' sempre lo stesso.

[wizard1993]

forse ho capito male io allora
ma questa o

primaria (Cognome) oalle chiavi secondarie (Matricola, Voto)

non è per caso una congiunzione avversativa che sta a indicare che se una frase è vera l'altra no?

[gugoXX]

Originariamente inviato da wizard1993

forse ho capito male io allora
ma questa o
non è per caso una congiunzione avversativa che sta a indicare che se una frase è vera l'altra no?

Si', hai capito bene, ma gli elementi di ordinamento sono pochi e sono noti.
Con questa clausola

L’ordinamento sulle chiavi secondarie deve conservare l’ordine relativo prodotto dalla chiave primaria.

si puo' risolvere il problema in questi 2 modi:
1. Un algoritmo di ordinamento stabile che accetti in input un campo singolo di ordinamento.
In questo modo le 3 richieste si possono risolvere come segue:
- Ordinamento per Cognome.
- Ordinamento per Cognome e poi ordinamento per matricola
- Ordinamento per Cognome e poi ordinamento per Voto

2. Un algoritmo di ordinamento qualsiasi che accetti in input 1 o 2 campi di ordinamentom, grazie al fatto che in tutte e 3 le richieste c'e' di mezzo l'ordinamento almeno anche per chiave primaria.
In questo modo le 3 richieste si possono risolvere come segue:
- Order By Cognome
- Order By Matricola,Cognome
- Order By Voto,Cognome

Se si deve costruire un algoritmo a mano e non si puo' usare il qsort (permesso dalla 2), allora propongo la 1, cosi' si e' sicuri che il compito vada bene.
A patto di scrivere uno degli algoritmi O(N logN)

[PaSteam]

Originariamente inviato da gugoXX

si puo' risolvere il problema in questi 2 modi:
1. Un algoritmo di ordinamento stabile che accetti in input un campo singolo di ordinamento.
In questo modo le 3 richieste si possono risolvere come segue:
- Ordinamento per Cognome.
- Ordinamento per Cognome e poi ordinamento per matricola
- Ordinamento per Cognome e poi ordinamento per Voto

2. Un algoritmo di ordinamento qualsiasi che accetti in input 1 o 2 campi di ordinamentom, grazie al fatto che in tutte e 3 le richieste c'e' di mezzo l'ordinamento almeno anche per chiave primaria.
In questo modo le 3 richieste si possono risolvere come segue:
- Order By Cognome
- Order By Matricola,Cognome
- Order By Voto,Cognome

Se si deve costruire un algoritmo a mano e non si puo' usare il qsort (permesso dalla 2), allora propongo la 1, cosi' si e' sicuri che il compito vada bene.
A patto di scrivere uno degli algoritmi O(N logN)

ma il fatto che come detto nel testo del compito sia l' utente a scegliere,
fa presupporre che possa scegliere indifferentemente su quale chiave effettuare l' ordinamento e possa farlo quante volte vuole, forse implica
qualcosa di + complesso o sono io che + leggo il testo e + me lo faccio diventare complesso?!?

[wizard1993]

Originariamente inviato da PaSteam

ma il fatto che come detto nel testo del compito sia l' utente a scegliere,
fa presupporre che possa scegliere indifferentemente su quale chiave effettuare l' ordinamento e possa farlo quante volte vuole, forse implica
qualcosa di + complesso o sono io che + leggo il testo e + me lo faccio diventare complesso?!?

secondo me è il primo, per il semplice motivo che uno può prima chiedere che venga ordinato per matricola, poi per nome e infine per voto, creare una variante di un comparatore per ogni permutazione mi sembra un suicidio

[Vincenzo1968]

Ciao,

qui trovi l'implementazione in C.

Se vuoi usare il merge sort, aggiungi questa funzione:

void mergesort(Studenti *a, Studenti *b, int l, int r, int nOrdinaPer)
{
	int i, j, k, m;

	if ( r > l )
	{
		m = (r+l)/2;

		mergesort(a, b, l, m, nOrdinaPer);
		mergesort(a, b, m+1, r, nOrdinaPer);

		for (i = m+1; i > l; i--)
			b[i-1] = a[i-1];

		for(j = m; j < r; j++)
			b[r+m-j] = a[j+1];

		switch ( nOrdinaPer )
		{
		case 'c':
		case 'C':
			for(k = l; k <= r; k++)
				a[k] = (strcmp(b[i].Cognome, b[j].Cognome) < 0) ? b[i++] : b[j--];
			break;
		case 'm':
		case 'M':
			for(k = l; k <= r; k++)
			{
				if ( (b[i].Matricola < b[j].Matricola) )
					a[k] = b[i++];
				else if ( (b[i].Matricola > b[j].Matricola) )
					a[k] = b[j--];
				else
					a[k] = (strcmp(b[i].Cognome, b[j].Cognome) < 0) ? b[i++] : b[j--];
			}
			break;
		case 'v':
		case 'V':
			for(k = l; k <= r; k++)
				if ( (b[i].Voto < b[j].Voto) )
					a[k] = b[i++];
				else if ( (b[i].Voto > b[j].Voto) )
					a[k] = b[j--];
				else
					a[k] = (strcmp(b[i].Cognome, b[j].Cognome) < 0) ? b[i++] : b[j--];
			break;
		}
	}
}

e modifica la funzione main così:

int main(void)
{
	char *szNomeFileIn = "Studenti.txt";
	char *szNomeFileOut = "StudentiOut.txt";
	int c;
	int NumRecords;

	Studenti *pStud, *pStudTemp;

	NumRecords = OttieniNumRecordsDaFileTesto(szNomeFileIn);
	if ( NumRecords <= 0 )
	{
		printf("Il file %s non contiene records.", szNomeFileIn);
		return -1;
	}

	pStud = malloc(NumRecords * sizeof(Studenti));
	if(!pStud)
	{
		printf("Memoria insufficiente.\n");
		return -1;
	}

	pStudTemp = malloc(NumRecords * sizeof(Studenti));
	if(!pStudTemp)
	{
		printf("Memoria insufficiente.\n");
		return -1;
	}

	if ( !LeggiRecords(szNomeFileIn, pStud) )
	{
		printf("Errore nella lettura dei records.\n");
		return -1;
	}

	while ( 1 )
	{
		printf("\n\nInserisci una delle seguenti lettere:\n");
		printf("C -> ordina per Cognome\n");
		printf("M -> ordina per Matricola\n");
		printf("V -> ordina per Voto\n");
		printf("Una qualunque altra lettera per uscire.\n");
		printf("Scelta: ");
		fflush(stdin);
		c = getchar();

		mergesort(pStud, pStudTemp, 0, NumRecords-1, c);
		if ( !ScriviRecords(szNomeFileOut, pStud, NumRecords) )
		{
			printf("Errore nella scrittura dei records.\n");
			return -1;
		}
		else
		{
			switch ( c )
			{
			case 'c':
			case 'C':
				printf("I records, ordinati per cognome, sono stati scritti nel file %s\n", szNomeFileOut);
				break;
			case 'm':
			case 'M':
				printf("I records, ordinati per matricola, sono stati scritti nel file %s\n", szNomeFileOut);
				break;
			case 'v':
			case 'V':
				printf("I records, ordinati per voto, sono stati scritti nel file %s\n", szNomeFileOut);
				break;
			default:
				return 0;
			}
		}
	}

	if ( pStud )
		free(pStud);

	if ( pStudTemp )
		free(pStudTemp);
	
	return 0;
}

[gugoXX]

Originariamente inviato da Vincenzo1968

Ciao,
...

E' vietato (giustamente) postare le soluzioni complete degli esercizi scolastici.

[PaSteam]

ringrazio vincenzo ma sono d'accordo anche io con la filosofia del forum qui.
quindi lo invito ad editare link e post

più che altro io volevo sapere solo come gli utenti del forum avevano interpretato le ultime righe del tema anche perchè la soluzione proposta da vincenzo rimane sempre un' interpretazione personale e magari non quella giusta dato che ce ne possono essere tantissime!!!

[71104]

Originariamente inviato da gugoXX

E' vietato (giustamente) postare le soluzioni complete degli esercizi scolastici.

Originariamente inviato da PaSteam

ringrazio vincenzo ma sono d'accordo anche io con la filosofia del forum qui.
quindi lo invito ad editare link e post

più che altro io volevo sapere solo come gli utenti del forum avevano interpretato le ultime righe del tema anche perchè la soluzione proposta da vincenzo rimane sempre un' interpretazione personale e magari non quella giusta dato che ce ne possono essere tantissime!!!

ma quale soluzione, ha scritto solamente un pietoso menu di scelte in C con interfaccia testuale e non senza un paio di leaks

d'altra parte era ovvio, il programma va scritto utilizzando le funzioni predefinite OttieniNumRecordsDaFileTesto, LeggiRecords, ScriviRecords...

l'unica cosa utile che ha scritto è l'algoritmo del mergesort: inutile visto che hai la funzione qsort

[wizard1993]

Originariamente inviato da 71104

l'unica cosa utile che ha scritto è l'algoritmo del mergesort: inutile visto che hai la funzione qsort

non stabile...
mi pare l'abbiamo abbondantemente detto sopra

[Toni85]

Ostia.... è uguale al compito che devo fare io!!!

[PaSteam]

Originariamente inviato da Toni85

Ostia.... è uguale al compito che devo fare io!!!

questo post si che risolve tutti i nostri dubbi

benvenuto a bordo