[C] LIste dinamiche, teoria

[-Ivan-]

Sto studiando le liste e guardando qualche esercizio molto semplice.
Non ho capito se le liste del tipo:

struct lista
{
int valore;
struct lista *succ;
};

sono tipi di dati per implementare delle pile o delle code?
A guardare il codice mi sembra delle pile, altrimenti c'è qualche passaggio che non ho capito.
Purtroppo non ho un libro quindi sto studiando guardando gli esempi.

[Ufo13]

in teoria va bene per entrambe...

più che altro cambiano le operazioni

[andbin]

Originariamente inviato da -Ivan-

Sto studiando le liste e guardando qualche esercizio molto semplice.
Non ho capito se le liste del tipo:

struct lista
{
int valore;
struct lista *succ;
};

sono tipi di dati per implementare delle pile o delle code?
A guardare il codice mi sembra delle pile, altrimenti c'è qualche passaggio che non ho capito.
Purtroppo non ho un libro quindi sto studiando guardando gli esempi.

Sia pile (stack) che code (queue) possono essere gestite con delle liste linkate. La differenza sostanziale tra liste e pile/code è che nelle liste non c'è un accordo ben preciso sulle operazioni che si possono effettuare mentre nelle pile/code c'è un modo di operare ben preciso.
Mi spiego meglio: nelle liste devi decidere tu che operazioni si possono fare. Puoi decidere di avere una funzione che inserisce solo al fondo, solo all'inizio, in mezzo, oppure inserisce in modo "ordinato", ecc... Insomma lo si decide nella implementazione che devi sviluppare.
Le pile/code invece sfruttano un concetto ben preciso. Nelle pile fai entrare ed uscire gli elementi sempre da un solo estremo della lista (LIFO) mentre nelle code fai entrare gli elementi da un estremo e li fai uscire dall'altro estremo della lista (FIFO).

[sottovento]

Le risposte che sono state postate sono perfette.
C'e' solo un problema pratico: nel caso tu voglia usare questa struttura per implementare una coda (quindi introduci da una parte ed estrai dall'altra), pur essendo fattibile ti troveresti un po' nelle canne ad implementare una delle due operazioni. O meglio, la implementeresti scandendo tutte le volte la lista, cosa poco efficiente.

Supponi, per esempio, di introdurre in testa. L'operazione e' semplicissima. Dovresti pero' estrarre dalla coda, quindi potresti tenere un puntatore all'ultimo elemento.
Dopo averlo eliminato, pero', il penultimo si trova a diventare l'ultimo e ti troveresti senza un puntatore ad esso. Saresti dunque costretto a partire dal puntatore di testa e cercare l'elemento il cui succ e' NULL...
In questo caso ti consiglio di utilizzare strutture piu' efficienti

High Flying
Sottovento

[andbin]

Ecco la gestione di una queue in "C" che ho buttato giù in pochi minuti (e testato).

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

typedef struct
{
    int valore;
} queue_data;

typedef struct queue_item_s
{
    queue_data           data;
    struct queue_item_s *prev;
    struct queue_item_s *next;
} queue_item;

typedef struct
{
    queue_item *head;
    queue_item *tail;
} queue;


void queue_init (queue *q)
{
    memset (q, 0, sizeof (queue));
}

void queue_free (queue *q)
{
    queue_item *i, *t;
    
    i = q->head;

    while (i != NULL)
    {
        t = i->next;
        free (i);
        i = t;
    }

    queue_init (q);
}

void queue_insert (queue *q, queue_data *d_in)
{
    queue_item *item;

    item = (queue_item *) malloc (sizeof (queue_item));

    memcpy (&item->data, d_in, sizeof (queue_data));

    item->prev = NULL;
    item->next = q->head;

    if (q->head != NULL)
        q->head->prev = item;

    q->head = item;

    if (q->tail == NULL)
        q->tail = q->head;
}

int queue_extract (queue *q, queue_data *d_out)
{
    queue_item *i;

    if (q->tail == NULL)
        return 0;  /* Nessun elemento disponibile! */

    memcpy (d_out, &q->tail->data, sizeof (queue_data));

    i = q->tail;

    q->tail = q->tail->prev;

    if (q->tail != NULL)
        q->tail->next = NULL;
    else
        q->head = NULL;

    free (i);

    return 1;
}

int main (void)
{
    int        i;
    queue      q;
    queue_data d;

    queue_init (&q);

    for (i=1; i<=10; i++)
    {
        d.valore = i;
        printf ("Inserimento: %d\n", d.valore);
        queue_insert (&q, &d);
    }

    for (i=0; i<12; i++)
    {
        if (queue_extract (&q, &d))
            printf ("Estrazione: %d\n", d.valore);
        else
            printf ("Estrazione: nessun elemento!\n");
    }

    queue_free (&q);

    return 0;
}

Carina, vero? Spero che possa esservi utile. Ciao.

[-Ivan-]

Sono tornato finalmente online, grazie andbin per il codice.


Allora se io ho questo codice e lo devo modificare per farlo divemtare una coda come devo fare?

//dichiarazione della struttura
struct mossaP1//contiene i dati della partita del giocatore1
{
     int bonusPresoP1;
     float tempoImpiegatoP1;
     int tiroEffettuatoP1;
     struct mossaP1 *nextP1;
};

//dichiarazione variabili di tipo mossaP1
struct mossaP1 *testaP1;//puntatore al primo elemento della coda delle mosse del giocatore1
struct mossaP1 *temp1;//puntatore temporaneo per non perdere la testa della coda
struct mossaP1 *nuovoElementoP1;//puntatore all'ultimo elemento della coda

//utilizzo dentro il programma della pila
nuovoElementoP1 = (struct mossaP1*)malloc(sizeof(struct mossaP1));
nuovoElementoP1-> bonusPresoP1=bonusP1;
nuovoElementoP1-> tempoImpiegatoP1=difftime(t2,t1);
nuovoElementoP1-> tiroEffettuatoP1=n1;
nuovoElementoP1->nextP1 = testaP1;
testaP1 = nuovoElementoP1;


//stampa della pila
     temp1=testaP1;
     printf("\n Elenco delle mosse del giocatore 1:\n");
     while (temp1 != NULL)
     {
         printf("%d.   \t%.2f     \t\t",count,temp1->tempoImpiegatoP1);
         printf("%d     \t\t",temp1->tiroEffettuatoP1);
         printf("\n");
         temp1 = temp1->nextP1;
         count++;
     }

Pensavo di mettere nella struttura anche un struct mossaP1 *startP1 che punti sempre al primo elemento, solo che poi mi incasino un po' con gli altri puntatori.
Qualcuno mi sa delucidare?

[andbin]

Originariamente inviato da -Ivan-

grazie andbin per il codice.

Di nulla! Anzi colgo l'occasione per segnalare che bisognerebbe mettere un #include <string.h> per la memset/memcpy che ho usato. L'ho compilato e testato su Linux e ho dimenticato, per la fretta, di mettere l'include ma me lo ha compilato lo stesso senza problemi.

Originariamente inviato da -Ivan-

Allora se io ho questo codice e lo devo modificare per farlo divemtare una coda come devo fare?

Ho letto il tuo codice. La tua è una lista linkata a senso unico (hai soltanto un next).
Dalla parte di codice che alloca/inserisce un elemento vedo che inserisci sempre in testa alla lista. In pratica testaP1 punta sempre all'ultimo elemento inserito.
Come è già stato detto in questo thread, una coda ha un comportamento ben preciso: si inseriscono gli elementi da un lato della coda e si estraggono gli elementi dall'altro lato della coda.
Questo vuol dire che tu dovresti scansionare tutta la tua lista per trovare l'ultimo elemento (che è stato il primo inserito). In pratica: l'ultimo elemento della lista è quello che devi estrarre/ottenere e nel penultimo elemento devi mettere NULL su next in modo da togliere l'ultimo dalla lista. E così via ...

Originariamente inviato da -Ivan-

Pensavo di mettere nella struttura anche un struct mossaP1 *startP1 che punti sempre al primo elemento, solo che poi mi incasino un po' con gli altri puntatori.
Qualcuno mi sa delucidare?

Uhm ... direi che non va affatto bene. Sia dal punto di vista concettuale che dal punto di vista pratico. A livello concettuale non ha molto senso mettere un puntatore alla testa all'interno di ogni elemento. Dal punto di vista pratico poi dovresti ogni volta andare ad aggiornare il puntatore su tutti gli elementi.

Nel mio esempio ho usato una lista linkata a doppio senso (ho un next e un prev) ed ho usato una struttura queue che è l'oggetto principale della coda, che contiene i puntatori all'elemento iniziale e finale della lista. In questo modo non devo scansionare tutta la lista.