[C] Risoluzione compito

[smartmouse]

Salve, vi chiedo se è possibile di scrivermi la soluzione di questo compito, perchè sono riuscito a fare solo il main e le due funzioni per creare e stampare la lista... e nemmeno funzionano! Spero nel vostro aiuto! Mi è di vitale importanza in vista di un appello d'esame!!


Problema:
Sequenza massima tra nodi uguali

Traccia:
main chiama una funzione che legge n numeri interi e li inserisce in una lista. main tramite una funzione stampa la lista. main quindi chiama una funzione che controlla se nella lista vi sono numeri ripetuti. In caso positivo la funzione individua e stampa la sottolista di lunghezza massima compresa tra due numeri uguali. Infine main stampa la lunghezza L della sottolista o segnala l’assenza di numeri ripetuti.

Esempi:

LISTA
1) 7 -> 9 -> 3 -> 5 -> NULL
2) 9 -> 5 -> 3 -> 5 -> 7 -> NULL
3) 6 -> 2 -> 3 -> 2 -> 6 -> 8 -> NULL
4) 8 -> 7 -> 4 -> 7 -> 6 -> 7 -> NULL

SOTTOLISTA
1) non ci sono numeri ripetuti
2) 5 -> 3 -> 5 L=3
3) 6 -> 2 -> 3 -> 2 -> 6 L=5
4) 7 -> 4 -> 7 -> 6 -> 7 L=5

[smartmouse]

Questo è quello che sono riuscito a fare:

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

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

lista * crealista();
void stampalista(lista *p);
//int trovarip(lista *p);

main() {
       lista *el, *start;
       int numrip=0;
       
       start=crealista();
       stampalista(start);
       
       //numrip=trovarip(el);
       
       if (numrip>0)
           printf("L = %d\n", numrip);
       else
           printf("Non ci sono numeri ripetuti\n");
           
       system("pause");
       return 0;
       }

lista * crealista() {
     int n, x, i;
     lista *start, *last, *punt;
     
     do {
         printf("Inserire numero nodi della lista: ");
         scanf("%d", &n);
         } while (n<=0);
     
     for (i=0;i<n; i++) {
         punt = (lista *)malloc(sizeof(lista));
         
         if(i==0)
             start = punt;
         else
             last->succ = punt;    
             
         printf("Inserire valore: ");
         scanf("%d", &x);
         
         punt->valore=x;
         last=punt;
         punt->succ=NULL;
         }
     return start;
     }
     
void stampalista(lista *p) {
     while (p!=NULL) {
           printf("%d\t", p->valore);
           p = p->succ;
           }
     return;
     }

Potresti farmi vedere come implementare la funzione trovarip() ?

[Rggb1]

Hai usato liste concatenate, la traccia non era così esplicita e con un array ti semplificavi la vita [oppure te lo hanno richiesto proprio così?]

Comunque, direi almeno di implementare una funzione di "cerca nodo" che, dato in ingresso un valore e un puntatore lista, ti scorre la lista e ti torna il numero di nodi attraversati se trova il valore in un nodo, oppure 0. Poi richiami questa funzione all'interno di un ciclo che scorre tutti i nodi.
Il ciclo può terminare, con un opportuno controllo, anche prima di aver scandito tutta la lista, ma devi avere per comodità l'informazione "numero di nodi" da qualche parte. Pertanto toglierei la richiesta di "n" numero dalla funzione di creazione e la metterei in main, passando poi n come parametro alla funzione di creazione.

[smartmouse]

"Rggb":Hai usato liste concatenate, la traccia non era così esplicita e con un array ti semplificavi la vita [oppure te lo hanno richiesto proprio così?]

Comunque, direi almeno di implementare una funzione di "cerca nodo" che, dato in ingresso un valore e un puntatore lista, ti scorre la lista e ti torna il numero di nodi attraversati se trova il valore in un nodo, oppure 0. Poi richiami questa funzione all'interno di un ciclo che scorre tutti i nodi.
Il ciclo può terminare, con un opportuno controllo, anche prima di aver scandito tutta la lista, ma devi avere per comodità l'informazione "numero di nodi" da qualche parte. Pertanto toglierei la richiesta di "n" numero dalla funzione di creazione e la metterei in main, passando poi n come parametro alla funzione di creazione.

Dobbiamo usare le liste, quindi niente array.
So come dovrebbe essere fatta la funzione, più o meno come hai detto tu, ma non riesco proprio a crearla!

[Rggb1]

Ma guarda che è semplice, faccio copiaincolla della tua

void stampalista(lista *p) {
     while (p!=NULL) {
           printf("%d\t", p->valore);
           p = p->succ;
           }
     return;
     }

e la modifico un po': aggiungo un parametro (cosa devo cercare) e ritorno un int:

int scanlista(lista *p, int nodo) {
     int i=0, trovato=0;
     while (p!=NULL) {
           i++;
           if (p->valore == nodo) { trovato=i; break; }
           p = p->succ;
           }
     return trovato;
     }

[smartmouse]

Scusa ma non ho capito cosa fa la tua funzione oppure non hai capito cosa viene chiesto nella traccia...

[Rggb1]

La funzione che ho messo scorre una lista e cerca il valore 'nodo'. Ritorna il numero di nodi attraversati (lunghezza) fino a 'nodo' oppure zero se non lo trova. L'idea era di fare un ciclo per tutti gli elementi della lista, nel quale chiamare la funzione per memorizzare il massimo valore tornato (massima lunghezza di sottolista) con il suo associato nodo iniziale.

L'ho fatta in un minuto, non credevo di dover essere così preciso, era solo per darti l'idea di come procedere.

Visto che ci interessa la sottolista di lunghezza massima, miglioriamola (così evitiamo i controlli a priori), con una semplice modifica: invece di fermarsi al primo nodo, scorre tutta la lista.

int scanlista(lista *p, int nodo) {
     int i=0, trovato=0;
     while (p!=NULL) {
           i++;
           if (p->valore == nodo) trovato=i;
           p = p->succ;
           }
     return trovato;
     }

Da un'altra parte (main? funzione apposta?) fai un ciclo che scorre la lista, e partendo da ogni nodo chiama 'scanlista' passandole il valore del nodo corrente e il puntatore al nodo successivo. Il ciclo serve a cercare la lunghezza massima trovata nonché il puntatore ad essa associato.

[apatriarca]

@Rggb: se osservi il quarto esempio, vedrai che è sbagliato cercare per la prima occorrenza di un valore. Devi cercare l'ultimo. E' inoltre utile restituire oltre che la lunghezza della sottosequenza anche il puntatore finale di questa sequenza.

[Rggb1]

"apatriarca":@Rggb: se osservi il quarto esempio, vedrai che è sbagliato cercare per la prima occorrenza di un valore. Devi cercare l'ultimo.

Infatti l'ho modificata, e ho tolto il break: cerca fino a fine lista.
Comunque, insisto nel dire che le mie sono solo tracce, suggerimenti; non devo fare io il programma... oppure sì?

E' inoltre utile restituire oltre che la lunghezza della sottosequenza anche il puntatore finale di questa sequenza.

Utile certamente, necessario no: dipende dall'approccio. Ribadisco, ho messo solo un esempio di
- "funzione che dice quanto è lunga la (sotto)lista che parte da '*lista' fino all'ultimo nodo di 'val' dato"
sulla base di questa, si può certamente fare una funzione che non solo ti dice quanto è lunga ma qual è l'ultimo nodo, una funzione che stampa la sottolista, e via dicendo.

[apatriarca]

"Rggb":non devo fare io il programma... oppure sì?

Ribadisco, ho messo solo un esempio di
- "funzione che dice quanto è lunga la (sotto)lista che parte da '*lista' fino all'ultimo nodo di 'val' dato"
sulla base di questa, si può certamente fare una funzione che non solo ti dice quanto è lunga ma qual è l'ultimo nodo, una funzione che stampa la sottolista, e via dicendo.

Certamente.

[smartmouse]

Ho aggiunto la funzione che mi hai suggerito, ottenendo così questo codice:

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

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

lista * crealista();
void stampalista(lista *p);
int trovarip(lista *p, int nodo);

main() {
       lista *el, *start;
       int numrip=0;
       
       start=crealista();
       stampalista(start);
       
       numrip=trovarip(el, el->valore);
       
       if (numrip>0)
           printf("L = %d\n", numrip);
       else
           printf("Non ci sono numeri ripetuti\n");
           
       system("pause");
       return 0;
       }

lista * crealista() {
     int n, x, i;
     lista *start, *last, *punt;
     
     do {
         printf("Inserire numero nodi della lista: ");
         scanf("%d", &n);
         } while (n<=0);
     
     for (i=0;i<n; i++) {
         punt = (lista *)malloc(sizeof(lista));
         
         if(i==0)
             start = punt;
         else
             last->succ = punt;    
             
         printf("Inserire valore: ");
         scanf("%d", &x);
         
         punt->valore=x;
         last=punt;
         punt->succ=NULL;
         }
     return start;
     }
     
void stampalista(lista *p) {
     while (p!=NULL) {
           printf("%d\t", p->valore);
           p = p->succ;
           }
     return;
     }
     
int trovarip(lista *p, int nodo) {
     int i=0, trovato=0;
     while (p!=NULL) {
           i++;
           if (p->valore == nodo) trovato=i;
           p = p->succ;
           }
     return trovato;
     }      

Ma non funziona...

Cos'è che devo passare esattamente alla funzione oltre alla lista?

"Rggb":Comunque, insisto nel dire che le mie sono solo tracce, suggerimenti; non devo fare io il programma... oppure sì?

Ehm... mi faresti una grande cortesia!

[apatriarca]

La funzione che ti è stata suggerita, non risolve il problema. Lo scopo della funzione è infatti quello di verificare se un particolare nodo compare nella lista e non di trovare la più lunga sottolista racchiusa tra nodi dello stesso valore. Ma quella funzione può essere usata per risolvere il tuo problema verificando, per ogni nodo della lista, quanto è lontano l'ultimo nodo con il valore cercato.

Ho l'impressione che tu non abbia capito le liste e che le funzioni e le strutture che hai scritto siano frutto di memorizzazione e non di comprensione dei concetti coinvolti. Non sono quindi certo che postarti la soluzione sia la cosa giusta da fare. Preferisco quindi descriverlo a voce lasciandoti i dettagli implementativi.

La soluzione naif alla quale ho fatto brevemente cenno nel primo capoverso richiede la memorizzazione di due valori, la lunghezza della massima sottolista e il puntatore al primo nodo di questa sottolista. Devi iterare su tutti gli elementi della lista. Il codice per farlo è già presente in molte delle funzioni che hai scritto e in quella che ti è stata presentata e non dovrebbe quindi darti problemi. A questo punto devi verificare se il nodo corrente è l'inizio della sottolista di lunghezza massima. Per farlo chiami la funzione che ti è stata suggerita passando p->next come primo argomento e p->valore come secondo (supponendo che p sia il nodo corrente). Se il valore restituito dalla funzione è maggiore del massimo allora aggiorni il massimo e il puntatore al primo elemento della sottolista massimale. Passi quindi all'elemento successivo. Una volta trovata la sottolista la puoi stampare abbastanza facilmente (ma non puoi usare la funzione stampalista...) e restituisci quindi la lunghezza della sottolista massima.

[smartmouse]

"apatriarca":La funzione che ti è stata suggerita, non risolve il problema. Lo scopo della funzione è infatti quello di verificare se un particolare nodo compare nella lista e non di trovare la più lunga sottolista racchiusa tra nodi dello stesso valore. Ma quella funzione può essere usata per risolvere il tuo problema verificando, per ogni nodo della lista, quanto è lontano l'ultimo nodo con il valore cercato.

Ho l'impressione che tu non abbia capito le liste e che le funzioni e le strutture che hai scritto siano frutto di memorizzazione e non di comprensione dei concetti coinvolti. Non sono quindi certo che postarti la soluzione sia la cosa giusta da fare. Preferisco quindi descriverlo a voce lasciandoti i dettagli implementativi.

Azz, sgamato!

La soluzione naif alla quale ho fatto brevemente cenno nel primo capoverso richiede la memorizzazione di due valori, la lunghezza della massima sottolista e il puntatore al primo nodo di questa sottolista. Devi iterare su tutti gli elementi della lista. Il codice per farlo è già presente in molte delle funzioni che hai scritto e in quella che ti è stata presentata e non dovrebbe quindi darti problemi. A questo punto devi verificare se il nodo corrente è l'inizio della sottolista di lunghezza massima. Per farlo chiami la funzione che ti è stata suggerita passando p->next come primo argomento e p->valore come secondo (supponendo che p sia il nodo corrente). Se il valore restituito dalla funzione è maggiore del massimo allora aggiorni il massimo e il puntatore al primo elemento della sottolista massimale. Passi quindi all'elemento successivo. Una volta trovata la sottolista la puoi stampare abbastanza facilmente (ma non puoi usare la funzione stampalista...) e restituisci quindi la lunghezza della sottolista massima.

Ora mi applico un pò e vediamo cosa riesco a fare!

[smartmouse]

"smartmouse":Ora mi applico un pò e vediamo cosa riesco a fare!

Con l'aiuto di un amico siamo riusciti a far funzionare il programma, ma in modo diverso:

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

         // Nodo della lista
struct nodo {
       int valore;          // Valore del nodo
       struct nodo *succ;   // Puntatore al nodo successivo
       };
       
typedef struct nodo lista;  // Definizione tipo di dato lista;

lista * crealista();        // Funzione per la creazione della lista. Torna il puntatore al primo nodo della lista
void stampalista(lista *p); // Funzione per la stampa della lista. Riceve il puntatore al primo nodo
int trovarip(lista *p);     // Funzione che trova le sequenze massime di numeri ripetuti. Riceve il puntatore al primo nodo e torna la lunghezza della sequenza, 0 se non vi sono elementi ripetuti

    /*    MAIN   */
main() {
       lista *start;        // Puntatore a lista
       int numrip=0;        // Lunghezza della sequenza tra due elementi uguali
       start=crealista();   // Chiamata alla funzione per creare la lista
       stampalista(start);  // Chiamata alla funzione per stampare la lista
       numrip=trovarip(start); // Chiamata alla funzione trovarip    
       if (numrip>0)
           printf("\n lunghezza sottolista massima :  %d\n", numrip+1);
       else
           printf("\n la lista non contiene elementi uguali \n");   
       system("pause");
       return 0;
}


   /*   Definizione delle funzioni   */
lista * crealista() {
     int n, x, i;   // Dimensione, elemento e contatore
     lista *start, *last, *punt;  
     start = punt = last = NULL;
           
     do { // Ciclo per controllo inserimento numero elementi > 0
         printf("Inserire numero nodi della lista: ");
         scanf("%d", &n);
     } while (n<=0);

     for (i=0;i<n; i++) { // Ciclo richiesta valori ed inserimento nella lista
         punt = (lista *)malloc(sizeof(lista));  // Allocazione memoria per il nodo
         if(i==0)
             start = punt;   // Puntatore al primo nodo
         else
             last->succ = punt;          
         printf("\n Inserire valore: ");
         scanf("%d", &x);
         punt->valore=x;
         last=punt;
         punt->succ=NULL;
         }
     return start;
     }
     
     
void stampalista(lista *p) {
     while (p!=NULL) {
           printf("%d -->", p->valore);
           p = p->succ;
     }
     printf("\n\n");
     return;
}
     
int trovarip(lista *p) {
    lista *pmax, *psucc;    // Puntatori a lista, psucc avanza nella lista, pmax mantiene la posizione di inizio sequenza della sottolista
    int cont, l, lmax;      // Contatore, lunghezza temporanea, lunghezza massima
    pmax = psucc = NULL;
    lmax = 0;

    while(p != NULL ) {     // Ciclo sul primo puntatore
            cont = 0;
            l = 0;
            psucc = p->succ;    // Avanzamento psucc al nodo successivo 

     while (psucc != NULL) {    // Ciclo sul puntatore psucc, sino a fine lista
           cont++;
           if (p->valore == psucc->valore) {   // Valori uguali
               l = cont;                       // Aggiornamento l
               if (l > lmax) {                 // Aggiorno lmax e pmax
                     lmax = l;
                     pmax = p;
                 }
            }
            psucc = psucc->succ;    // Avanzamento psucc al nodo successivo
       }
       p = p->succ;             // Avanzamento puntatore iniziale al nodo successivo
    }

  if (pmax != NULL) {           // Se pmax è diverso da NULL vuol dire che vi sono elementi uguali e stampo la sottolista
      for (l = 0; l <= lmax; l++) {
          printf("%d -->",pmax->valore);
          pmax = pmax->succ;
          }
      return(lmax);
      }
  else
      return 0;
}

Non è proprio come dicevi tu, ma funziona!
Precisamente come avresti implementato la funzione trovarip?

[Rggb1]

Precisamente come avresti implementato la funzione trovarip?

Ma guarda che mi sembra apatriarca ed io te lo abbiamo già detto.

... Da un'altra parte (main? funzione apposta?) fai un ciclo che scorre la lista, e partendo da ogni nodo chiama 'scanlista' passandole il valore del nodo corrente e il puntatore al nodo successivo. Il ciclo serve a cercare la lunghezza massima trovata nonché il puntatore ad essa associato.

... Devi iterare su tutti gli elementi della lista. Il codice per farlo è già presente in molte delle funzioni che hai scritto e in quella che ti è stata presentata e non dovrebbe quindi darti problemi. A questo punto devi verificare se il nodo corrente è l'inizio della sottolista di lunghezza massima. Per farlo chiami la funzione che ti è stata suggerita passando p->next come primo argomento e p->valore come secondo (supponendo che p sia il nodo corrente). Se il valore restituito dalla funzione è maggiore del massimo allora aggiorni il massimo e il puntatore al primo elemento della sottolista massimale. Passi quindi all'elemento successivo. Una volta trovata la sottolista la puoi stampare abbastanza facilmente

Questo ultimo intervento in particolare mi sembra molto chiaro ed è scritto in buon italiano. Si tratta poi di una cosa molto semplice, direi quasi elementare.

Dunque, cosa è che non hai capito?

[apatriarca]

"smartmouse":
Non è proprio come dicevi tu, ma funziona!
Precisamente come avresti implementato la funzione trovarip?

Anche se nel tuo codice non fai ricorso alla funzione che ti era stata proposta, l'algoritmo è esattamente lo stesso. Il ciclo con psucc è infatti praticamente uguale a quello della funzione di Rggb, con l'unica differenza di aggiornare anche il puntatore al nodo dal quale parte la sottolista.

Il codice sarebbe stato comunque qualcosa tipo il seguente (non ho provato il codice):

int trovarip(lista *p)
{
    int i, nmax = 0;
    lista *q, *pmax = NULL;

    while (NULL != p) {
        int n = trova(p->next, p->valore); /* cerca p->valore nella lista che inizia da p->next. */

        if (n > nmax) {
            nmax = n;
            pmax = p; 
        }

        p = p->succ;
    }

    q = pmax;
    for (i = 0; i <= nmax; ++i) {
        printf("%d -->", q->valore);
        q = q->succ;
    }

    return nmax;
}

int trova(lista *p, int v)
{
    int i = 0, max = 0;
    while (NULL != p) {
        ++i;
        if (p->valore == v) {
            max = i;
        }
        p = p->succ;
    }
    return max;
}