Liste Concatenate

di il
8 risposte

Liste Concatenate

Ho questo esercizio:
Un utente prende in input un numero, finchè non inserisce 0, poi prende un altro intero n e, tramite una funzione, elimina tutti i multipli di n dalla lista. Alla fine, stampa la lista pulita.
Struct:
struct nodo
{
    int info;
    nodo *next;
};
typedef struct nodo NewNode;
Sono sincero, non ho proprio la minima idea di come scrivere la funzione per eliminare i multipli.
Vi chiedo disperatamente una mano (non intendo un codice fatto, ma magari un aiuto per ragionare perchè veramente non ho idee).

8 Risposte

  • Re: Liste Concatenate

    LASCIA perdere, l'implementazione in C, per il momento

    Ti basta ragionare in termini di programmazione ""procedurale"" (while o for/if/sequenza di statement) e ""sequenza di valori"" INDIPENDENTEMENTE dal fatto di scriverlo in C.

    Quindi, in questo caso, come faresti?
  • Re: Liste Concatenate

    Vai per piccoli passi ...

    come si determina se un valore è multiplo di un altro?

    come si scorre una lista?

    come si elimina un elemento di una lista (se è il primo, se è uno in mezzo, se è l'ultimo)?
  • Re: Liste Concatenate

    Allora ho provato a rileggere un po' il libro e penso di aver capito questi "tre problemi",
    Per eliminare il primo elemento bisogna, salvare l'indirizzo della Testa in un'altra variabile, la Testa punta al successivo e si elimina la variabile
    NewNode *temp = Testa;
    Testa = Testa->next;
    delete temp;
    Per eliminare l'ultimo elemento, bisogna farlo puntare a NULL
    NewNode *temp = Testa;
    while(temp->next->next != NULL)
    	temp = temp->next;
    delete temp->next;
    temp->next = NULL;
    Per eliminare un elemento in mezzo, bisogna "saltarlo"
    NewNode *temp = Testa;
    if(temp->next != NULL && temp->next->info % n == 0) //Elemento successivo a temp, in questo caso direttamente il secondo
    {
    	NewNode *temp2 = temp->next->next;
    	delete temp->next;
    	temp = temp2;
    }
  • Re: Liste Concatenate

    Ragazzi, scusate se per un po' non ho scritto nulla.
    Ho saltato quell'esercizio e ne ho fatti altri. Alla fine ci sono riuscito
    Codice:
    #include <iostream>
    using namespace std;
    
    struct nodo
    {
        int info;
        nodo *next;
    };
    typedef struct nodo New;
    
    New *lista(New *head, int n)
    {
        if(head == NULL)
        {
            head = new New;
            head->info = n;
            head->next = NULL;
        }
        else
        {
            New *temp = head;
            while(temp->next != NULL)
                temp = temp->next;
            temp->next = new New;
            temp = temp->next;
            temp->info = n;
            temp->next = NULL;
        }
        return head;
    }
    
    void print(New *head)
    {
        New *temp = head;
        while(temp != NULL)
        {
            cout<<"["<<temp->info<<"] -> ";
            temp = temp->next;
        }
        cout<<"NULL";
    }
    
    New *newL(New *head, int n)
    {
        New *temp = head;
        while(temp != NULL)
        {
            if(temp==head && temp->info%n == 0)
            {
                New *suc = temp->next;
                delete head;
                head = suc;
                temp = head;
            }
            else if(temp->next != NULL)
            {
                if(temp->next->info%n == 0)
                {
                    New *temp2 = temp->next->next;
                    delete temp->next;
                    temp->next = temp2;
                }
                else
                    temp = temp->next;
            }
            else
                temp = temp->next;
        }
        return head;
    }
    
    
    int main()
    {
        int n = 1;
        New *head1 = NULL;
        while(n!=0)
        {
            cout<<"Numero: ";
            cin>>n;
            if(n!=0)
                head1 = lista(head1, n);
        }
    
    
        print(head1);
        cout<<"\n\nInserisci multiplo: ";
        cin>>n;
        head1 = newL(head1, n);
        print(head1);
        
        return 0;
    }
    
  • Re: Liste Concatenate

    Alcune considerazioni:
    - in generale nel C++ si utilizza nullptr al posto di NULL;
    - a cosa serve quel typedef? Inoltre che senso ha rinominare struct nodo come New?
    - nella funzione print(), considerando il concetto di passaggio per copia, ti renderai conto che la variabile temp risulta superflua;
    - nel main() il messaggio Inserisci multiplo è concettualmente sbagliato, al massimo avresti potuto scrivere Inserisci divisore;
    - nella funzione lista() mischi i concetti di aggiunta in testa e in coda, che sarebbe invece meglio tenere separati;
    - infine la funzione newL() può essere notevolmente semplificata utilizzando i puntatori doppi. Per esempio puoi implementare una funzione
    void elimina_nodo(nodo **p);
    da utilizzare in
    void elimina_multipli(nodo **p, int n)
    {
        while(*p)
        {
            if(!((*p)->info % n))
            {
                elimina_nodo(p);
            }
            else
            {
                p = &(*p)->next;
            }
        }
    }
  • Re: Liste Concatenate

    -Sorry, studiando dal libro ho utilizzato NULL, poi cercando vari video ho notato che in C++ si usa nullptr.
    -Senza il typedef, per dichiarare un nodo avrei dovuto scrivere struct *nodo Testa ?
    -Sistemato la funzione print(), hai ragione D: (anche questa cosa l'ho vista da libro).
    -In che senso mischio i concetti? In pratica avevo pensato, per aggiungere un elemento, di controllare se era nullptr (quindi aggiungere head), altrimenti scorrere con temp e allocare temp->next ecc.
    -Non ho la minima idea di cosa sia un puntatore doppio (argomento che non viene trattato proprio, ho controllato), penso che cercherò un po' online.
  • Re: Liste Concatenate

    Ho provato senza typedef, praticamente uguale la cosa.
    Quindi la mia domanda rimane una:
    -In che senso mischio i concetti? In pratica avevo pensato, per aggiungere un elemento, di controllare se era nullptr (quindi aggiungere head), altrimenti scorrere con temp e allocare temp->next ecc.
  • Re: Liste Concatenate

    NewBie12_ ha scritto:


    Ho provato senza typedef, praticamente uguale la cosa.
    Nel C++, a differenza del C, la dichiarazione di una struttura comporta la creazione di un nuovo tipo, ed è proprio per questo motivo che l'utilizzo del typedef risulta superfluo. Del resto avresti anche potuto dedurlo dal fatto che, prima del typedef, hai dichiarato il membro next senza anteporre la parola chiave struct. Per esempio in C quel codice non avrebbe mai potuto compilare, e infatti avresti dovuto scrivere:
    struct nodo
    {
        int info;
        struct nodo *next;
    };
    
    typedef struct nodo Nodo;

    NewBie12_ ha scritto:


    Quindi la mia domanda rimane una:
    -In che senso mischio i concetti? In pratica avevo pensato, per aggiungere un elemento, di controllare se era nullptr (quindi aggiungere head), altrimenti scorrere con temp e allocare temp->next ecc.
    Il mio consiglio è quello di implementare due differenti funzioni: una per l'aggiunta di un elemento in testa alla lista ed una per l'aggiunta in coda.
Devi accedere o registrarti per scrivere nel forum
8 risposte