DOMANDA Pseudocodifica

[Fab996]

Devo fare la pseudocodifica per trovare l'elemento massimo in una lista, ecco la mia soluzione
Dove l è la lista e l.head è il riferimento al primo nodo della lista:

massimo(l)
    max = l.head.info
    l.head = l.head.next
    while l.head!=NULL
        if l.head.info>max
            max = l.head.info
       l.head = l.head.next
     return max

Solo la soluzione del mio prof è :

massimo(l)
    max = l.head.info
    x = l.head
    while x!=NULL
        if max<x.info
            max = x.info
        x = x.next
    return max

Non capisco se ho fatto qualche errore, però i due codici sono piuttosto simili, tranne che nel secondo si fa uso di una variabile di appoggio, però dato che devo trovare un elemento in una lista (quindi non modificarla) a cosa mi serve una variabile di appoggio che punta al primo nodo della lista? Potrebbe servire se dovessi modificare la lista per esempio eliminando un nodo e mantenere il riferimento al primo nodo quando scorro la lista...

 

[DispatchCode]

Ti rispondo da cell, quindi non riesco a dilungarmi.
Il tuo modifica la head. In pratica se accedessi alla head al termine di tutto non avresti più la testa perché hai alterato il puntatore.
Il tuo prof , come hai giustamente detto, usa una variabile d'appoggio, così non modifica il puntatore originale.
In una caso "reale" o comunque "didatticamente reale" , perderesti il puntatore al primo elemento originale.

 

[Fab996]

Il tuo modifica la head. In pratica se accedessi alla head al termine di tutto non avresti più la testa perché hai alterato il puntatore.
In una caso "reale" o comunque "didatticamente reale" , perderesti il puntatore al primo elemento originale.

Grazie per la risposta, però in un esercizio di ricerca è inutile utilizzare una variabile d'appoggio per non perdere il riferimento alla testa della lista, dato che poi vado a ritornare un valore e non una lista. Mentre in un esercizio di eliminazione di un nodo per esempio, dato che modifico la lista, devo utilizzare una variabile d'appoggio proprio perchè poi ritorno una lista e almeno non perdo il riferimento alla testa. Giusto ?

 

[DispatchCode]

Di solito non viene implementata solo la ricerca del massimo, quindi la modifica alla testa sicuramente andrebbe ad incidere. Quando userete del codice difficilmente vi verrà consentito di svolgerlo in quel modo, in quanto sarebbe (ed è) comunque concettualmente e praticamente errato un algoritmo che per trovare il massimo perde la testa della lista.

Per l'eliminazione di un nodo, se la lista è globale, non servirà restituire nulla, se non magari un valore booleano per indicare successo o eventuali errori .

 

[Fab996]

Quando userete del codice difficilmente vi verrà consentito di svolgerlo in quel modo, in quanto sarebbe (ed è) comunque concettualmente e praticamente errato un algoritmo che per trovare il massimo perde la testa della lista.

Per esempio questa è la mia implementazione in C

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

typedef struct elem {
    int info;
    struct elem *next;
} elist;

typedef elist* plist;

void stampa(plist);
int massimo(plist);

int main() {
    plist a,b,c,d;
    a = (plist)malloc(sizeof(elist));
    b = (plist)malloc(sizeof(elist));
    c = (plist)malloc(sizeof(elist));
    d = (plist)malloc(sizeof(elist));
    plist e;
    d->info = 400; d->next = NULL;
    c->info = 40; c->next = d;
    b->info = 80; b->next = c;
    a->info = 4; a->next = b;
    e = a;
    stampa(e);
    printf("Il massimo è %d\n",massimo(e));
    return 0;
}

int massimo(plist l) {
    int max = l->info;
    l = l->next;
    if(l==NULL)
        max = 0;
    else {
        while(l!=NULL) {
            if(max<l->info)
                max = l->info;
            l = l->next;
        }
    }
    return max;
}

e in questo caso comunque non perdo il riferimento alla testa perchè all'atto della chiamata del metodo "massimo" avrei una situazione come quella che ho disegnato nel grafico in allegato, quindi siccome faccio scorrere l non perdo la testa

 

[DispatchCode]

Ed aggiungo, inoltre, che per vedere se hai alterato il valore iniziale dovresti come minimo stampare di nuovo o almeno svolgere altre operazioni.

 

[Fab996]

Eh sisi, proprio per questo non perdo il riferimento alla testa

si, infatti ho fatto un'altra stampa dopo che nel codice che ho postato ho omesso, però ero già abbastanza sicuro che non modificavo la lista perchè per capire meglio le liste mi aiuto con quei grafici..

 

[rodhellas]

Avevo scritto un commento che poi ho appurato essere sbagliato ( e quindi l'ho rimosso). Andando a fare una %p sul puntatore 'e' dà sempre lo stesso indirizzo di memoria anche dopo la chiamata alla funzione massimo

 

[DispatchCode]

@Fab996 mi sto riguardando il tuo codice da PC.
La prima cosa che noto è che il tuo if-else è evitabile, tanto la verifica avviene sul while. Inoltre non mi sembra corretto restituire il valore 0. Se l ha valore N, ed l->next = NULL, dovresti restituire N, non 0. Potresti piuttosto usare un controllo di sicurezza prima di accedere al puntatore in caso di l = NULL.

Visto che typedef elist* plist; puoi anche evitare l'utilizzo di plist e, e passare direttamente a. Alla fine e ed a puntano alla stessa memoria per forza di cose, quindi è un assegnamento inutile.

 

[1nd33d]

Puoi anche optare per qualcosa di ricorsivo:

massimo(l, max = NULL):
   if l == NULL:
      return max
   if l.info > max:
      return massimo(l.next, l.info)
   else:
      return massimo(l.next, max)

la cui traduzione in C è pressapoco coincidente.

ps: nella tua funzione dici che se la lista è vuota il massimo è 0. Secondo me non è un buon modo di gestire il caso, piuttosto scriverei "lista vuota, nessun valore da cercare" o qualcosa di simile. Il valore zero potrebbe benissimo essere il valore massimo di una lista valida.

 

[Fab996]

Grazie mille per i suggerimenti:)