08/02/12 13:01
Bonny
Boh forse non ho capito bene il tuo prob...
1) a livello concettuale sai cos'è una lista (ordinata o meno non ha importanza)?
tipo una serie di nodi connessi in serie tra loro con dei puntatori(permettimi l'abuso di linguaggio)
Si può inserire/eliminare un nodo dove ti pare
Scorrere la lista partendo dalla testa o dalla coda (dipende dall'implementazione).
2) ecco la coda si può rappresentare mediante le liste solo l'unica cosa che cambia sono le operazioni
che ti consentono di manipolarla:
-inserimento di un novo nodo per esempio può avvenire in testa e cosi l'estrazione avverrà dalla coda o viceversa ovvero il primo ad entrare è il primo ad uscire!
-ecco questo è un punto cruciale e credo che spesso le persone implementano strutture dati senza conoscerle veramente, intendo la "lettura" degli elementi di una coda,come facciamo per la lista però qui le cose cambiano ovvero ogni qual volta leggi l'elemento in codaquesto viene eliminato dalla coda, spesso per non perdere le info si fa uso di una struttura di appoggio..
Non voglio andare oltre altrimenti ti annoio
Comunque per risolvere il tuo problema basta che prendi la lista e applichi la politica delle code, sulle operazioni di inserzione/delete di un elemento
per esempio
typedef struct cella *coda;
struct cella{
int value;
coda next;
};
void insert(coda c,int val){
while(/*scorro la lista fino all'ultimo elemento*/){
}
/*malloc ecc...*/
/* aggancio il nuovo nodo come successore dell'ultimo nodo della coda*/
}
int leggi(coda c){
int x = c->value;
coda tmp = c;
c = c->next;
free(tmp);
return x;
}
it.wikipedia.org/wiki/…
Ultima modifica effettuata da Bonny 08/02/12 13:02
aaa
08/02/12 14:11
TheKaneB
Una coda i cui elementi sono ordinati si chiama anche Priority Queue.
nel tuo caso basta prendere la lista, rinominare la funzione "inserisci" in "push", e il gioco è fatto :-p
Come funzione "pop" devi semplicemente prendere il primo (o l'ultimo, dipende dalla direzione dell'ordinamento) elemento della lista, cancellarlo e restituire il contenuto.
Occhio che così non è molto efficiente, perchè per ogni inserimento devi potenzialmente scorrere tutta la lista/coda.
Le code con priorità solitamente si implementano tramite alberi bilanciati, per avere una maggiore efficienza di inserimento, che passa da lineare a logaritmica.
Ultima modifica effettuata da TheKaneB 08/02/12 14:14
aaa
08/02/12 17:06
JErikaM
mi son detta, vabbè proviamo a fare la coda senza passare da alcuna lista...
ovvero quando il giocatore sceglie la mossa, creo dal di li una coda e gli passo il turno, colonna e il tempo..
così ho fatto questo codice che dovrebbe crearmi una lista ordinata
void coda_10_mosse(struct Coda *coda, int turno_utente, int colonna, double tempo) //CREO UNA CODA ORDINATA
{
struct cella *nuovo, *temp, *prec;
nuovo = (struct cella*)malloc(sizeof(struct cella));
nuovo -> tempo = tempo;
nuovo -> colonna = colonna;
nuovo -> turno_utente = turno_utente;
nuovo -> next = NULL;
if (coda->primo == NULL)
{
coda->primo = nuovo;
}
else
{
temp = coda->primo;
}
while (temp != NULL)
{
if (temp -> tempo > nuovo -> tempo)
{
nuovo -> next = temp;
if (prec == NULL)
{
coda->primo = nuovo;
}
else
{
prec -> next = nuovo;
break;
}
prec = temp;
temp = temp -> next;
}
if (temp == NULL)
{
prec -> next = nuovo;
coda->ultimo = nuovo;
}
}
return;
}
ecco le mie strutture dati
struct cella{
int turno_utente;
int colonna;
double tempo;
struct cella *next;
};
struct Coda{
struct cella *primo;
struct cella *ultimo;
};
struct Coda coda;
coda.primo = NULL;
coda.ultimo = NULL;
e la chiamata alla funzione è
while(colonna != 0) //while per entrare nella partita
{
time (&start);
printf("\n Turno giocatore %d [%c]: %s \n", turno_utente+1, simbolo[turno_utente], nome_utente[turno_utente] );
printf("Inserire numero colonna e premere invio(per terminare la partita 0): \n");
scanf("%d", &colonna);
time (&end);
tempo = difftime (end,start); //tempo assume il valore della differenza di tempo trascorso tra l'inizio e la fine dell'attesa per inserire la mossa
coda_10_mosse(coda, turno_utente, colonna, tempo); //CHIAMATA FUNZIONE CHE CREA CODA ORDINATA
però alla chiamata mi dice che l'argomento 1 (quindi coda) non è stato passato in modo corretto... allora ho messo &coda ma in questo caso il gioco mi parte ma si blocca al primo inserimento della mossa
Ultima modifica effettuata da JErikaM 08/02/12 17:09
aaa
08/02/12 18:21
Bonny
Allora ma se il tuo problema è questo:
"praticamente io devo creare una coda che mantenga e stampi a video le dieci mosse più veloci compiute nel gioco dagli utenti..."
Questa coda deve contenere le dieci ultime dieci mosse più veloci giusto??
Se te ne servono solo 10 non potresti usare semplicemente un vettore?
Mi spiego meglio.. per esempio ogni giocatore gli associo un vettore di 10 elementi
del tipo:
struct cella{
int turno_utente;
int colonna;
double tempo;
}Cella;
struct miaStruttura{
Cella vettore[10];
int ultimo;//rappresenta l'ultima posizione occupata nel vettore
};
ovvero un vettore di "celle" invece di una lista/coda di celle
a questo punto quando il giocatore si trova alla i-esima mossa dovremo inserire quest'ultima nel vettore quindi:
se ultimo = 9 allora il vettore è pieno quindi
se vettore[ultimo] > tempo_della_nuova_mossa
inserisco la nuova cella al posto dell'ultima cella
altrimenti se ultimo < 9 il vettore ha qualche cella libera quindi
ultimo++;
vettote[ultimo] = nuova_cella_con_il_nuovo_tempo
ordino il vettore da 0 a ultimo basandomi sui tempi
Poi dipende se questo è un esercizio che richiede l'ausilio di una coda implementata mediante le liste devi farlo con la lista e comunque l'algoritmo che ti ho proposto va bene per entrambi i casi
Comunque ti propongo di guardare questo programma che ti aiuterà a capire come ordinare una lista
pierotofy.it/pages/sorgenti/dettagli/18720-Gestione_liste_e_file_binari/
e ti posto un pdf su di un argomento interessante ovvero sulle code con priorità
ciao
Ultima modifica effettuata da Bonny 08/02/12 18:29
aaa
