[RISOLTO] Problema logico Queue c++

di il
5 risposte

[RISOLTO] Problema logico Queue c++

Essendo ancora alle basi della programmazione, mi sto esercitando su strutture dati di tipo Queue, Stack e List per poter passare a scrivere algoritimi sempre più complessi. Ho scritto questo semplicissimo programma per la gestione di strutture di tipo Queue (che, per chi non lo sapesse, sono strutture nel quale ogni elemento è collegato tramite puntatore all'elemento inserito successivamente, ogni elemento può essere inserito solo in coda, e può essere estratto solo dalla testa della struttura. Testa e coda sono solo i nomi che si danno al primo e all'ultimo elemento della struttura Queue, e non degli elementi della struttura stessa.).
#include <iostream>
using namespace std;
//Creazione di una struttura di tipo Queue.
typedef struct Q *QueueL;
typedef struct Q 
        {
        float info;
        QueueL link;
        }
        queue;

main(){
//Dichiarazione delle variabili testa(front) e coda(rear).
queue front, rear;
char c;
//Azzeramento della struttura.
front.info=rear.info=0;
front.link=rear.link=NULL;
//Nome label per il "goto" inserito successivamente.
do
{
//Decisione dell'operazione da attuare sulla Queue.    
cout << "1. Inserimento " << endl << "2. Estrazione" << endl << "Selezionare operazione: ";
int op;
cin >> op;       
switch(op)
          {
          case 1:         
               // Creazione di un nuovo nodo della Queue.
               cout<<"Inserire nuovo valore: ";
               queue app;
               cin>>app.info;
               app.link= NULL;
               //Se la Queue è vuota, poniamo il nodo come front e rear. 
               if (front.info==0)
                  front=rear=app;
               //Se la Queue ha un solo elemento, il nuovo diviene rear, e la front punta a questo.
               else if (front.info==rear.info)
                   {
                   front.link=new struct Q;
                   front.link=&app;
                   rear=app;
                   }
               //Altrimenti la rear punta al nuovo elemento, che diviene rear.    
               else
                   {
                   rear.link=new struct Q;
                   rear.link=&app;
                   rear=app;
                   }                
               break;
           case 2:
                 //Estrazione valore di testa.
                 if(front.info==0)
                    cout<<"La coda è vuota!"<<endl;    
                 //Se la Queue non è vuota estraiamo il valore, divedendo i casi in cui vi sia un solo elemento o più di uno.
                 else
                     {
                     queue app=front;
                     if (front.info == rear.info)
                        front.info=rear.info=0;
                     else
                        front=*app.link;
                     delete app.link;
                     cout<< "L'elemento estratto è: "<< app.info<<endl;
                     break;
                     }
           }
//Decidere se continuare a lavorare sul programma oppure no.           
cout<<"Continuare (S/N)?";
cin>> c;
} while (c=='s');
system("PAUSE");
}
Il mio problema è questo: quando vado ad inserire una serie di valori, e poi provo ad estrarli, riesco ad estrarre solo il primo e l'ultimo, come se la testa (front) puntasse sempre e solo alla coda (rear), qualunque sia esse nel momento nel quale estraggo il primo elemento.
Spero di essere stato chiaro al massimo, ma sono sempre pronto per chiarimenti. Ovviamente mi basta una spiegazione su come risolvere il problema, quindi non è necessario che mi riscriviate pezzi di sorgente. Grazie mille a tutti =)

5 Risposte

  • Re: [RISOLTO] Problema logico Queue c++

    (che, per chi non lo sapesse, sono strutture nel quale ogni elemento è collegato tramite puntatore all'elemento inserito successivamente, ogni elemento può essere inserito solo in coda, e può essere estratto solo dalla testa della struttura. Testa e coda sono solo i nomi che si danno al primo e all'ultimo elemento della struttura Queue, e non degli elementi della struttura stessa.)
    Una coda è una coda: puoi implementarla anche senza tutti questi puntatori (che complicano inutilmente la gestione). Vedi ad es.
    Volendo essere pignoli e immaginando che il tuo non sia solo un esercizio ma una vera applicazione: dove deallochi (delete) i vari elementi all'uscita?
    Se sei alle basi di programmazione, vai a vedere l'esempio che ti ho dato, che è molto più istruttivo.
    Se invece vuoi intestardirti con i puntatori allora ti consiglio di predisporre una funzione che stampa il contenuto della coda e di richiamare questa funzione per verificare ogni step in cui si modifica la struttura.
  • Re: [RISOLTO] Problema logico Queue c++

    Secondo me ti conviene trattare tutto (anche front e rear) come puntatori
  • Re: [RISOLTO] Problema logico Queue c++

    Scusate se rispondo con tutto questo ritardo, ma ho avuto molto da fare, in ogni caso oggi ho rimesso mano al programma, e lo ho modificato in questo modo, trattando rear e front come puntatori secondo il suggerimento e implementando la funzione di stampa per il controllo.
    
    #include <iostream>
    using namespace std;
    //Creazione di una struttura di tipo Queue.
    typedef struct Q *QueueL;
    typedef struct Q 
            {
            float info;
            QueueL link;
            }
            queue;
            
    void print(queue Testa,queue Coda, int n);
    void Push (queue *front, queue *rear);
    void Pop (queue *front, queue *rear);
    
    main(){
    //Dichiarazione delle variabili testa(front) e coda(rear), che puntano al primo e all'ultimo elemento della Queue.
    queue *front, *rear;
    front= new struct Q;
    rear= new struct Q;
    char c;
    //Azzeramento della struttura.
    (*front).info=(*rear).info=0;
    (*front).link=(*rear).link=NULL;
    //Inizio del ciclo do..while per la ripetizione delle operazioni sulla struttura queue.
    do
    {
    //Decisione dell'operazione da attuare sulla Queue.    
    cout << "1. Inserimento " << endl << "2. Estrazione" << endl << "Selezionare operazione: ";
    int option;
    cin >> option;       
    switch(option)
              {
              case 1:         
                   Push(front, rear);
                   break;
               case 2:
                   Pop(front, rear);
                   break;    
               }
               //Decidere se continuare a lavorare sul programma oppure no.    
               print(*front, *rear, 4);       
               cout<<"Continuare (S/N)?";
               cin>> c;
    } while (c=='s');
    delete rear;
    delete front;
    system("PAUSE");
    }
    
    
    
    void print(queue Testa,queue Coda, int n){
           cout<<"L'elemento di testa al passo "<< n<< " è: "<< Testa.info<<endl;
           cout<<"L'elemento di testa al passo "<< n<< " è: "<< Coda.info <<endl;
           }
           
           
    void Push (queue *front, queue *rear){
                   // Creazione di un nuovo nodo (app) della Queue.
                   cout<<"Inserire nuovo valore: ";
                   queue app;
                   cin>>app.info;
                   app.link= NULL;
                   print(*front, *rear, 1);
                   //Se la Queue è vuota, poniamo il nodo come front e rear. 
                   if ((*front).info==0)
                      {
                      print(*front, *rear, 2);
                      front=rear=&app;
                      print(*front, *rear, 3);
                      }
                   //Se la Queue ha un solo elemento, il nuovo nodo diviene rear, e la front punta a questo.
                   else if ((*front).info==(*rear).info)
                       {
                       print(*front, *rear, 2);
                       (*front).link=new struct Q;
                       (*front).link=&app;
                       rear=&app;
                       print(*front, *rear, 3);
                       }
                   //Altrimenti la rear punta al nuovo elemento, che diviene rear.    
                   else
                       {
                       print(*front, *rear, 2);
                       (*rear).link=new struct Q;
                       (*rear).link=&app;
                       rear=&app;
                        print(*front, *rear, 3);
                       }   
    }             
         
         
         
    void Pop (queue *front, queue *rear){
                     //Estrazione valore di testa.
                     if((*front).info==0)
                        cout<<"La coda è vuota!"<<endl;    
                     //Se la Queue non è vuota estraiamo il valore, divedendo i casi in cui vi sia un solo elemento o più di uno.
                     else
                         {
                         queue app=*front;
                         if ((*front).info == (*rear).info)
                            (*front).info=(*rear).info=0;
                         else
                            front=&(*(app.link));
                         delete app.link;
                         cout<< "L'elemento estratto è: "<< app.info<<endl;
                         }
    }
    Lanciando il programma, l'errore è palese, una volta terminata la funzione mi azzera le variabili *front e *rear, come se la funzione non fosse entrata in funzione, a questo punto immagino che l'errore sia nel passaggio delle varibili, ma non riesco a capire perchè dato che mi sembra estremamente corretto.. Help me
    Ps: so di non aver inserito un default e che la selezione del carattere per continuare è un po' barbara come scelta xD
  • Re: [RISOLTO] Problema logico Queue c++

    Se devi modificare un puntatore tramite una funzione devi passare il suo puntatore.
    Puoi farlo tramite "&" oppure dichiarano un doppio puntatore nella funzione "funzione(QueueL* elem)"

    Effettuare i controlli sul valore di info non e' una grande idea: se front e rear hanno lo stesso valore ( ma sono due elementi distinti ) li gestisce come una Queue di un solo elemento.
    Piuttosto usa NULL e fai i controlli sui puntatori, così il programma non potrà mai "sbagliare".

    Stampare a video "info" quando chiami pop() senza salvarlo non ti permette di usare efficacemente il contenitore. Ad esempio puoi ritornarlo o passare a pop() una variabile predisposta.

    "app" così creato cessa di esistere al termine della funzione. Dichiaralo come puntatore e allocalo, così non "sparisce"

    Per non confondere la tua struttura con "queue" della Standart Template Library, l'ho rinominata "Queue"

    Se hai usato il typedef per nominarla "QueueL", non capisco perchè scrivi "queue *elem"

    Manca <stdlib.h> per usare "system()"



    Tutte le correzioni da me PROPOSTE sono in questo codice
    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    typedef struct Q *QueueL;
    //Creazione di una struttura di tipo Queue.
    typedef struct Q
    {
        float info;
        QueueL link;
    }
    Queue;
    
    void print(Queue Testa,Queue Coda);
    void Push (QueueL &front, QueueL &rear);
    float Pop (QueueL &front, QueueL &rear);
    
    main()
    {
    //Dichiarazione delle variabili testa(front) e coda(rear), che puntano al primo e all'ultimo elemento della Queue.
        QueueL front, rear;
        front= NULL;
        rear= NULL;
        char c;
    
    //Inizio del ciclo do..while per la ripetizione delle operazioni sulla struttura queue.
        do
        {
    //Decisione dell'operazione da attuare sulla Queue.
            cout << "1. Inserimento " << endl << "2. Estrazione" << endl << "Selezionare operazione: ";
            int option;
            cin >> option;
            switch(option)
            {
                case 1:
                    Push(front, rear);
                    break;
                case 2:
                    cout << "\n\n Elemento estratto = " << Pop(front, rear) << endl << endl;
                    break;
            }
            //Decidere se continuare a lavorare sul programma oppure no.
            if(front!=NULL && rear!=NULL)   print(*front, *rear);
            else                            cout << "\n\n Coda vuota!\n\n";
    
            cout<<"Continuare (S/N)?";
            cin>> c;
        }
        while (c=='s');
    
        delete rear;
        delete front;
    
        system("PAUSE");
    }
    
    
    
    void print(Queue Testa,Queue Coda)
    {
        cout << "///////////////////////////////////////////////////" << endl;
        cout<<"L'elemento di testa è: "<< Testa.info<<endl;
        cout<<"L'elemento di coda è: "<< Coda.info <<endl;
        cout << "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"<<endl;
    }
    
    
    void Push (QueueL &front, QueueL &rear)
    {
        // Creazione di un nuovo nodo (app) della Queue.
        cout<<"Inserire nuovo valore: ";
        QueueL app=new Queue;
        cin>>app->info;
        app->link= NULL;
    
        //Se la Queue è vuota, poniamo il nodo come front e rear.
        if (front==NULL)
        {
            cout << "\n\n<la coda e' vuota>\n\n";
            front=rear=app;
            print(*front,*rear);
        }
        //Se la Queue ha un solo elemento, il nuovo nodo diviene rear, e la front punta a questo.
        else if (front==rear)
        {
            front->link=app;
            rear=app;
            print(*front, *rear);
        }
        //Altrimenti la rear punta al nuovo elemento, che diviene rear.
        else
        {
            rear->link=app;
            rear=app;
            print(*front, *rear);
        }
    }
    
    
    
    float Pop (QueueL &front, QueueL &rear)
    {
        //Estrazione valore di testa.
        if(front==NULL){
             cout<<"La coda è vuota!"<<endl;
             return -1;
        }
        //Se la Queue non è vuota estraiamo il valore, divedendo i casi in cui vi sia un solo elemento o più di uno.
        else
        {
            float el_estratto=front->info;
            if (front==rear){
                delete front;
                front=rear=NULL;
            }
            else{
                QueueL app=front->link;
                delete front;
                front=app;
            }
    
            return el_estratto;
        }
    }

    PS: Dato che ho scoperto cos'è e come funziona una Queue circa 15 min fa per risponderti, forse ho sbagliato la sua logica ottenendo un'altro tipo di struttura. E' giusta così

    Ciao
  • Re: [RISOLTO] Problema logico Queue c++

    ale99 ha scritto:


    se devi modificare un puntatore tramite una funzione devi passare il suo puntatore.
    Puoi farlo tramite "&" oppure dichiarano un doppio puntatore nella funzione "funzione(QueueL* elem)"

    Effettuare i controlli sul valore di info non e' una grande idea: se front e rear hanno lo stesso valore ( ma sono due elementi distinti ) li gestisce come una Queue di un solo elemento.
    Piuttosto usa NULL e fai i controlli sui puntatori, così il programma non potrà mai "sbagliare".

    Stampare a video "info" quando chiami pop() senza salvarlo non ti permette di usare efficacemente il contenitore. Ad esempio puoi ritornarlo o passare a pop() una variabile predisposta.

    "app" così creato cessa di esistere al termine della funzione. Dichiaralo come puntatore e allocalo, così non "sparisce"

    Per non confondere la tua struttura con "queue" della Standart Template Library, l'ho rinominata "Queue"

    Se hai usato il typedef per nominarla "QueueL", non capisco perchè scrivi "queue *elem"

    Manca <stdlib.h> per usare "system()"

    Tutte le correzioni da me PROPOSTE sono in questo codice

    PS: Dato che ho scoperto cos'è e come funziona una Queue circa 15 min fa per risponderti, forse ho sbagliato la sua logica ottenendo un'altro tipo di struttura. E' giusta così

    Ciao
    Grazie mille, grazie alle tue correzioni sono riuscito a far partire alla perfezione il programma, anche se ho preferito lasciare la funzione pop un void. Veramente grazie mille, ci stavo perdendo la testa appresso al programma xD. Unico accorgimento: il system("pause") lo riesco ad usare benissimo anche senza la <stdlib.h>.
    Si può chiudere.
Devi accedere o registrarti per scrivere nel forum
5 risposte