Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Trasformare lista ordinata in coda, e stamparla a video!
Forum - C/C++ - Trasformare lista ordinata in coda, e stamparla a video!

Avatar
JErikaM (Normal User)
Newbie


Messaggi: 10
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 12:51
Mercoledì, 08/02/2012
Ciao a tutti :) Eccomi di nuovo a chiedere aiuto ç_ç
Questa volta mi trovo davanti a liste ordinate e code..
praticamente io devo creare una coda che mantenga e stampi a video le dieci mosse più veloci compiute nel gioco dagli utenti...
ho pensato allora di fare una lista ordinata con tutte le mosse in ordine crescente di tempo impiegato, poi trasformare questa lista in una coda...solo che nn riesco a fare proprio questo passaggio...:d

questa è la mia dichiarazione di coda

Codice sorgente - presumibilmente C#

  1. struct cella
  2. {
  3. double tempo;
  4. int turno_utente;
  5. int colonna;
  6. struct cella *next;
  7. };
  8. struct Coda{
  9. struct cella *primo;
  10. struct cella *ultimo;
  11. };
  12. struct Coda coda;
  13. coda.primo = NULL;
  14. coda.ultimo = NULL;



e questa è la struttura della mia lista ordinata (che sono riuscita a creare)
Codice sorgente - presumibilmente C#

  1. struct top10_mosse_gioc1_2
  2. {
  3. double tempo;
  4. int colonna;
  5. int turno_utente;
  6. struct top10_mosse_gioc1_2 *next;
  7.  
  8. };
  9. struct top10_mosse_gioc1_2 *testa = NULL;



per far diventare questa lista ordinata una coda come devo fare?

Codice sorgente - presumibilmente C#

  1. push(struct Coda coda*primo, struct top10_mosse_gioc1_2*testa)
  2. {
  3. if (coda.primo == NULL) //nel caso in cui la coda sia vuota
  4. coda.primo = testa;
  5. else
  6. coda.ultimo->next =testa;
  7. coda.ultimo = testa;
  8. }



cioè dentro tratto la testa come se fosse un nuovo elemento?

Grazie in anticipo!! :)

PM Quote
Avatar
Bonny (Member)
Expert


Messaggi: 437
Iscritto: 24/04/2009

Segnala al moderatore
Postato alle 14:01
Mercoledì, 08/02/2012
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

Codice sorgente - presumibilmente C++

  1. typedef struct cella *coda;
  2.  
  3. struct cella{
  4.      int value;
  5.      coda next;
  6. };
  7.  
  8. void insert(coda c,int val){
  9.    
  10.      while(/*scorro la lista fino all'ultimo elemento*/){
  11.          
  12.     }
  13.  
  14.     /*malloc ecc...*/
  15.    /* aggancio il nuovo nodo come successore dell'ultimo nodo della coda*/
  16. }
  17.  
  18. int leggi(coda c){
  19.         int x = c->value;
  20.         coda tmp = c;
  21.         c = c->next;
  22.         free(tmp);
  23.         return x;
  24. }


Ultima modifica effettuata da Bonny il 08/02/2012 alle 14:02
PM Quote
Avatar
JErikaM (Normal User)
Newbie


Messaggi: 10
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 14:08
Mercoledì, 08/02/2012
Prima di tutto grazie per la risposta :)
Si, le liste semplici o ordinate che siano so crearle, stamparle, cercare valori etc...il problema ce l'ho con le code, ciò non riesco bene a gestire push e pop..creare dal nulla una coda inserendo solo valori numerici posso arrivarci, ma in questo caso devo avere una coda che mi tenga traccia delle 10 mosse più veloci fatte...
quindi io ho fatto una lista ordinata (l'ho stampata x controllare che mi funzioni, e funziona) e ho pensato "ora passo mediante push questa lista creando una coda, poi quest'ultima la vado a stampare mediante pop". Non dovrei infatti in questo caso utilizzare push e pop? è quello il problema...

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 15:11
Mercoledì, 08/02/2012
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 il 08/02/2012 alle 15:14
PM Quote
Avatar
JErikaM (Normal User)
Newbie


Messaggi: 10
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 18:06
Mercoledì, 08/02/2012
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

Codice sorgente - presumibilmente C#

  1. void coda_10_mosse(struct Coda *coda, int turno_utente, int colonna, double tempo) //CREO UNA CODA ORDINATA
  2. {
  3. struct cella *nuovo, *temp, *prec;
  4. nuovo = (struct cella*)malloc(sizeof(struct cella));
  5.  
  6. nuovo -> tempo = tempo;
  7. nuovo -> colonna = colonna;
  8. nuovo -> turno_utente = turno_utente;
  9. nuovo -> next = NULL;
  10. if (coda->primo == NULL)
  11.     {
  12.      coda->primo = nuovo;
  13.      }
  14.    else
  15.    {
  16.     temp = coda->primo;
  17.      }
  18.     while (temp != NULL)
  19.     {
  20.     if (temp -> tempo > nuovo -> tempo)
  21.     {
  22.      nuovo -> next = temp;
  23.          
  24.         if (prec == NULL)
  25.         {
  26.         coda->primo = nuovo;
  27.          }    
  28.          else
  29.          {
  30.           prec -> next = nuovo;
  31.           break;
  32.            }
  33.       prec = temp;
  34.      temp = temp -> next;
  35.      }
  36.     if (temp == NULL)
  37.      {
  38.     prec -> next = nuovo;
  39.       coda->ultimo = nuovo;
  40.       }
  41.  }
  42. return;
  43. }



ecco le mie strutture dati

Codice sorgente - presumibilmente C#

  1. struct cella{
  2. int turno_utente;
  3. int colonna;
  4. double tempo;
  5. struct cella *next;
  6. };
  7. struct Coda{
  8. struct cella *primo;
  9. struct cella *ultimo;
  10. };
  11. struct Coda coda;
  12.  
  13.  
  14. coda.primo = NULL;
  15. coda.ultimo = NULL;



e la chiamata alla funzione è

Codice sorgente - presumibilmente Plain Text

  1. while(colonna != 0) //while per entrare nella partita
  2.                 {
  3.              time (&start);
  4.          printf("\n Turno giocatore %d [%c]: %s \n", turno_utente+1, simbolo[turno_utente], nome_utente[turno_utente] );
  5.          printf("Inserire numero colonna e premere invio(per terminare la partita 0): \n");
  6.          scanf("%d", &colonna);
  7.          time (&end);
  8.          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
  9.         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 :d

Ultima modifica effettuata da JErikaM il 08/02/2012 alle 18:09
PM Quote
Avatar
Bonny (Member)
Expert


Messaggi: 437
Iscritto: 24/04/2009

Segnala al moderatore
Postato alle 19:21
Mercoledì, 08/02/2012
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:
Codice sorgente - presumibilmente C#

  1. struct cella{
  2. int turno_utente;
  3. int colonna;
  4. double tempo;
  5. }Cella;
  6. struct miaStruttura{
  7.    Cella vettore[10];
  8.    int ultimo;//rappresenta l'ultima posizione occupata nel vettore
  9. };


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
http://www.pierotofy.it/pages/sorgenti/dettagli/18720-Gest ...
e ti posto un pdf su di un argomento interessante ovvero sulle code con priorità
ciao:)

Ultima modifica effettuata da Bonny il 08/02/2012 alle 19:29
PM Quote
Avatar
JErikaM (Normal User)
Newbie


Messaggi: 10
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 20:11
Mercoledì, 08/02/2012
per obbligo d'esercizio devo avere una coda...non mi interessa se ci passo i valori da una lista o no...l'importante è che io abbia una coda con le mosse più veloci e poi le possa stampare a video :)
e la lista ordinata l'ho anche fatta e funziona..ma io devo d'obbligo fare una coda :S

PM Quote
Avatar
JErikaM (Normal User)
Newbie


Messaggi: 10
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 16:50
Giovedì, 09/02/2012
allora allora...
ho la mia lista ordinata (funzionante) con le mosse dalla più veloce alla più lenta...
devo creare appunto la coda che poi mi stampa a video le dieci mosse più veloci...quindi ho pensato di fare una coda di sole 10 "caselle" così da mantenere solo 10 mosse!
sono arrivata a questo codice..

Codice sorgente - presumibilmente C++

  1. void coda_10_mosse(struct coda coda, struct top10_mosse_gioc1_2*testa)
  2. {
  3.   struct nodo*nuovo;
  4.   struct top10_mosse_gioc1_2 *temp;
  5.   temp = testa;
  6.   int i;
  7.   for(i=0;i<=10;i++)
  8.   {
  9.   nuovo=(struct nodo*)malloc(sizeof(struct nodo));
  10.   nuovo->tempo = temp->tempo;
  11.   nuovo->colonna = temp->colonna;
  12.   nuovo->turno_utente = temp->turno_utente;
  13.   nuovo->next= NULL;
  14.  
  15.   if(coda.primo==NULL)
  16.   {
  17.     coda.primo=nuovo;
  18.   }
  19.   else
  20.   {
  21.    coda.ultimo->next=nuovo;
  22.    coda.ultimo=nuovo;
  23.    }          
  24.    temp=temp->next;
  25.    }    
  26.    stampa_coda(coda);
  27.    
  28.  return;
  29. }



praticamente se tolgo il for la funzione mi stampa una cella (la mossa più veloce quindi il suo lavoro lo fa) però visto che io voglio che me ne stampi dieci ho messo questo for....però il programma crasha in questo caso! come mai? .-.

PM Quote