Programma CODA C++

di il
16 risposte

Programma CODA C++

Buonasera a tutti, ho realizzato un programma in c++ che simula il funzionamento di una coda la quale segue l’algoritmo FIFO (FIRST IN FIRST OUT), dunque, il primo elemento immesso è il primo ad uscire.
I due puntatori che ho utilizzato per gestire la coda sono END E BEGIN, entrambi inizializzati a 0. Il puntatore END viene incrementato nel momento in cui viene richiesta la PUSH (quindi di immettere il dato) mentre il puntatore BEGIN viene incrementato quando si richiede la POP(estrazione del dato)

SPIEGO IL MIO RAGIONAMENTO
Ho utilizzato una variabile temporanea “Tempend” che punta alla prima cella vuota , e l’ho incrementata progressivamente insieme ad END, nel momento in cui supera la dimensione massima della coda (MAX+1) si è verificato un overflow e non posso piu immettere dati.
La dimensione della coda sarebbe MAX+1 perché appunto tempend punta alla prima cella vuota.
Quando Begin e End si trovano allo stesso indice, VALE A DIRE CHE LA CODA RISULTA ESSERE VUOTA, e dunque non è possibile estrarre dati perché non ce ne sono. Quando invece tempend==begin la coda risulterà piena, si è verificato dunque un overflow.
In questa prima versione del programma riscontro solo un problema…quando end supera il massimo viene settato di nuovo a 0. Però poi se si verifica ciò, ho problemi perche il ciclo for della stampa scorre da begin a end e dato che end è settato a 0 begin risulterà essere maggiore di quest’ultimo.
SCRIVO IL CODICE DELLA PRIMA VERSIONE DEL PROGRAMMA

#include <iostream>
using namespace std;
 const int MAX = 3; //dimensione massima della coda 
 int Coda[MAX]; // array per la coda 
 int END,BEGIN;
// prototipi delle funzioni
void SvuotaCoda();
void Pop();
void Push();
void ScriviCoda();
void PresentaMenu();
// funzione principale
int main()
{
 int scelta; // scelta nel menu
SvuotaCoda();
 do {
 do {
 PresentaMenu();
 cout << "Inserisci la tua scelta =>";
 cin >> scelta;
 } while (scelta<1 || scelta>5);
 switch(scelta) {
 case 1:
 SvuotaCoda();
 break;
 case 2:
 Pop();
 break;
 case 3:
 Push();
 break;
 case 4:
 ScriviCoda();
 break;
 }
 } while (scelta != 5);
 return 0;
}
// inizializzazione della pila
void SvuotaCoda()
{
 BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
 END =0; //inizializziamo il puntatore END ( da muovere con la PUSH)
 cout << "Coda vuota" << endl;
}

void Pop() // funzione POP = estrazione di un elemento dalla coda
{
 if (BEGIN == END) //Se begin e end si trovano allo stesso indice la coda sarà vuota e dunque non ci sono elementi da estrarre
 cout << "Non ci sono elementi da estrarre!" << endl;
 else {
 	cout << "Elemento estratto = " << Coda[BEGIN] << endl; //altrimenti si estrae il dato
 	BEGIN++; if(BEGIN>MAX) BEGIN=0; //dopo aver immesso il dato, begin lo incrementiamo e se è maggiore di MAX ritorna a 0 
 	}
}
void Push()
{
	int dato,tempend; // elemento da inserire
	tempend=END+1;  if(tempend>MAX) tempend=0;
	if (tempend==BEGIN){
		cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;}
 	else {
 		cout << "Dato da inserire = ";
 		cin >> dato;
 		Coda[END] = dato;
 		END=tempend;
 	}
} // Push
 
void ScriviCoda()
{
 cout << "INIZIO CODA" << endl;
 for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
 cout << "FINE CODA" << endl;
 cout << " VALORE END " << END<<endl;
cout << "VALORE BEGIN " <<BEGIN<< endl;
} 
// menu delle scelte
void PresentaMenu()
{
 cout << endl;
 cout << "1. SVUOTA CODA" << endl;
 cout << "2. ESTRAI DATO (POP)" << endl;
 cout << "3. IMMETTI DATI (PUSH)" << endl;
 cout << "4. VISUALIZZA CODA " << endl;
 cout << "5. FINE PER TERMINARE" << endl;
}
Inoltre il professore ci ha chiesto di modificare il programma e invece di utilizzare la variabile tempfin ci ha chiesto di gestire l’overflow e la situazione di “coda vuota” con un flag.
Ho provato a modificarlo, dichiarando una variabile booleana coda_piena nella funzione push e coda_vuota nella funzione pop .Eliminando dunque tempend la dimensione della coda non sarà piu pari a MAX +1 bensi a MAX.
Però, utilizzando la variabile temporanea nella prima versione del programma end si riavvolgeva senza alcun problema, utilizzando il flag non mi si riavvolge correttamente. Esempio:
Faccio 3 PUSH E 3 POP . Se voglio continuare a immettere i dati il programma me lo dovrebbe far fare, settando end di nuovo a 0 e facendolo ripartire, ma entra invece nella condizione di coda piena non permettendomi piu di inserire dati.

SCRIVO IL CODICE DELLA SECONDA VERSIONE DEL PROGRAMMA (CON FLAG)

#include <iostream>
using namespace std;
 const int MAX = 3; //dimensione massima della coda 
 int Coda[MAX]; // array per la coda 
 int END,BEGIN;
 bool coda_piena=false;
// prototipi delle funzioni
void SvuotaCoda();
void Pop();
void Push();
void ScriviCoda();
void PresentaMenu();
// funzione principale
int main()
{
 int scelta; // scelta nel menu
SvuotaCoda();
 do {
 do {
 PresentaMenu();
 cout << "Inserisci la tua scelta =>";
 cin >> scelta;
 } while (scelta<1 || scelta>5);
 switch(scelta) {
 case 1:
 SvuotaCoda();
 break;
 case 2:
 Pop();
 break;
 case 3:
 Push();
 break;
 case 4:
 ScriviCoda();
 break;
 }
 } while (scelta != 5);
 return 0;
}
// inizializzazione della pila
void SvuotaCoda()
{
 BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
 END = 0; //inizializziamo il puntatore END ( da muovere con la PUSH)
 cout << "Coda vuota" << endl;
}

void Pop() // funzione POP = estrazione di un elemento dalla coda
{
 	bool coda_vuota=false;
 	if (BEGIN == END){
 		coda_vuota=true;}
 	if(coda_vuota) cout << "NON CI SONO ELEMENTI DA ESTRARRE!" << endl;
 	if(!coda_vuota) {
 		cout << "Elemento estratto = " << Coda[BEGIN] << endl;
 		BEGIN++; 
 		if(BEGIN==MAX) BEGIN=0;	coda_vuota=false;
 		if(END==0) coda_piena=false;
 		}
}
void Push()
{
	int dato; // elemento da inserire
	if (END==MAX){
		coda_piena=true;END=0;}
	if(coda_piena) cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;
 	if(!coda_piena){
 		cout << "Dato da inserire = ";
 		cin >> dato;
 		Coda[END] = dato;
 		END++;
 	}
 	
} // Push
 
void ScriviCoda()
{
 cout << "INIZIO CODA" << endl;
 for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
 cout << "FINE CODA" << endl;
 cout << " VALORE END " << END<<endl;
cout << "VALORE BEGIN " <<BEGIN<< endl;
} 
// menu delle scelte
void PresentaMenu()
{
 cout << endl;
 cout << "1. SVUOTA CODA" << endl;
 cout << "2. ESTRAI DATO (POP)" << endl;
 cout << "3. IMMETTI DATI (PUSH)" << endl;
 cout << "4. VISUALIZZA CODA " << endl;
 cout << "5. FINE PER TERMINARE" << endl;
} 
Spero possiate darmi qualche consiglio, vi ringrazio anticipatamente.

16 Risposte

  • Re: Programma CODA C++

    Praticamente hai fatto
    
    PUSH 1
    	BEGIN = 0
    	END = 1
    PUSH 2
    	BEGIN = 0
    	END = 2
    PUSH 3
    	BEGIN = 0
    	END = 3	
    POP 1
    	BEGIN = 1
    	END = 3
    POP 2
    	BEGIN = 2
    	END = 3
    POP 3
    	BEGIN = 3 --> BEGIN = MAX ---> BEGIN = 0
    	END = 3	
    PUSH 4
    	BEGIN = 0
    	END = 3 ---> END = MAX ---> END = 0 e massaggio coda piena
    
    Quindi quello che hai scritto è sbagliato. Ragiona bene su come deve funzionare una coda prima di scriverne il codice
    Inoltre l'analisi sullo status della coda (piena o vuota) deve essere fatto evidentemente a fine operazioni, non all'inizio
  • Re: Programma CODA C++

    Ciao, @Weirestrass.
    Ho riscritto il codice riportato di seguito, ora funziona:
    
    #include <iostream>
    using namespace std;
     const int MAX = 3; //dimensione massima della coda 
     int Coda[MAX]; // array per la coda 
     int END,BEGIN;
     bool coda_piena=false;
    // prototipi delle funzioni
    void SvuotaCoda();
    void Pop();
    void Push();
    void ScriviCoda();
    void PresentaMenu();
    // funzione principale
    int main()
    {
     int scelta; // scelta nel menu
    SvuotaCoda();
     do {
     do {
     PresentaMenu();
     cout << "Inserisci la tua scelta =>";
     cin >> scelta;
     } while (scelta<1 || scelta>5);
     switch(scelta) {
     case 1:
     SvuotaCoda();
     break;
     case 2:
     Pop();
     break;
     case 3:
     Push();
     break;
     case 4:
     ScriviCoda();
     break;
     }
     } while (scelta != 5);
     return 0;
    }
    // inizializzazione della pila
    void SvuotaCoda()
    {
     BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
     END = 0; //inizializziamo il puntatore END ( da muovere con la PUSH)
     cout << "Coda vuota" << endl;
    }
    
    void Pop() // funzione POP = estrazione di un elemento dalla coda
    {
     	bool coda_vuota=false;
     	if (BEGIN==END and (BEGIN==0 and END==0) ){//controllo se BEGIN e END sono uguali, ed entrambi hanno valore 0
     		coda_vuota=true;}
     	if(coda_vuota) cout << "NON CI SONO ELEMENTI DA ESTRARRE!" << endl; 
     	if(!coda_vuota) {
     		cout << "Elemento estratto = " << Coda[BEGIN] << endl;
     		BEGIN++; 
     		}
     	if(BEGIN>=MAX){BEGIN=0;} //se begin èmaggiore del massimo o uguale, setto sia END che BEGIN a zero, in quanto la coda è piena e non ci sono elementi da estrarre
    	if(BEGIN<MAX and BEGIN!=0 and END==MAX) END=0; coda_piena=false;//setto END  a zero, e la coda diventa vuota
    }
    void Push()
    {
    	int dato; // elemento da inserire
    	if (END==MAX){
    		coda_piena=true;}
    	if(BEGIN==END and (BEGIN!=0 and END!=0) ) coda_piena=true; //caso in cui END e BEGIN possano accavalarsi, e magari sovrascrivere i dati ancora non estratti.
    	if(coda_piena) cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;
     	if(!coda_piena){
     		cout << "Dato da inserire = ";
     		cin >> dato;
     		Coda[END] = dato;
     		END++;
     	}
     	
    } // Push
     
    void ScriviCoda()
    {
    	if(BEGIN>END){
    		cout << "INIZIO CODA" << endl;
     		for (int i=END-1 ; i<=BEGIN; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
     		cout << "FINE CODA" << endl;
     		cout << " VALORE END " << END<<endl;
    		cout << "VALORE BEGIN " <<BEGIN<< endl;
    	}
    	else{
     	cout << "INIZIO CODA" << endl;
     	for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
    	 cout << "FINE CODA" << endl;
     	cout << " VALORE END " << END<<endl;
    	cout << "VALORE BEGIN " <<BEGIN<< endl;}
    } 
    // menu delle scelte
    void PresentaMenu()
    {
     cout << endl;
     cout << "1. SVUOTA CODA" << endl;
     cout << "2. ESTRAI DATO (POP)" << endl;
     cout << "3. IMMETTI DATI (PUSH)" << endl;
     cout << "4. VISUALIZZA CODA " << endl;
     cout << "5. FINE PER TERMINARE" << endl;
    } // PresentaMenu
    
    L' unico problema, si presenta con la stampa, soltanto in questo caso:
    prendiamo come riferimento questo esempio : CODA INIZIALE: 5,6,8 POP DI 5 —-> PUSH 9 POP 6—> CODA FINALE: 9,6,8

    Come vedi quando l'utente inserisce 4, in modo da visualizzare la coda, quest'ultima dovrebbe presentarsi in questo modo: 9,8, in quanto l'elemento 6 è già stato estratto( ma in un certo senso noi lo facciamo in modo fittizio l'estrazione, cioè non lo togliamo effettivamente dall' array). Ecco, la domanda è: esiste un modo per saltare il 6, affinchè la stampa sia corretta?
  • Re: Programma CODA C++

    Ma è FIFO o LIFO quello che cerchi?

    Inoltre la tua descrizione push di... pop di...
    È sbagliata
  • Re: Programma CODA C++

    FIFO
  • Re: Programma CODA C++

    Il tuo codice non compila ("and" non esiste in C)

    Li sai fare gli indirizzi modulari?
    Quando aggiungi, END deve diventare (END + 1) % MAX. La coda è piena quando END = BEGIN - 1 oppure quando END = MAX - 1 e BEGIN = 0.
    Quando togli, BEGIN deve diventare (BEGIN + 1) % MAX. La coda è vuota quando BEGIN = END.
  • Re: Programma CODA C++

    Il programma non è in c bensì in c++. And si può usare e il mio codice si compila perfettamente senza alcun errore
  • Re: Programma CODA C++

    Grazie, lo vedo bene che è in C++. Cambia qualcosa per quello che ho detto? Hai definito una macro "and"? Perché
    if(BEGIN==END and (BEGIN!=0 and END!=0) ) non è C né C++

    Ma a parte questo, hai compreso il suggerimento?
  • Re: Programma CODA C++

    @Weierstrass, si credo di aver capito ciò che mi hai suggerito.
    Quando effettuo la push non devo incrementare semplicemente END come ho fatto bensì devo fare (END + 1) % MAX e stessa cosa devo fare con la POP (BEGIN + 1) % MAX.

    Inoltre la coda risulta essere piena quando soddisfa una di queste condizioni END = BEGIN - 1 oppure quando END = MAX - 1 e BEGIN = 0. devo quindi levare le condizioni che avevo imposto io ossia if (END==MAX)
    if(BEGIN==END and (BEGIN!=0 and END!=0) )

    È invece vuota quando begin==end.
    Giusto?
  • Re: Programma CODA C++

    Prova con il codice
  • Re: Programma CODA C++

    Si in serata provo e ti aggiorno. Potresti spiegarmi però perché hai fatto (END + 1) % MAX e la stessa cosa con begin?
  • Re: Programma CODA C++

    Per fare un array ciclico: la posizione dopo [MAX - 1] è [0]. Puoi usare anche un if al posto del modulo
  • Re: Programma CODA C++

    @Weierstrass, ho provato ad eseguire le modifiche al mio codice, ma non funziona correttamente. Esempio, quando inserisco i dati poi non me li fa estrarre nonostante end sia maggiore di begin. Ti scrivo il codice
    
    #include <iostream>
    using namespace std;
     const int MAX = 3; //dimensione massima della coda 
     int Coda[MAX]; // array per la coda 
     int END,BEGIN;
     bool coda_piena=false;
    // prototipi delle funzioni
    void SvuotaCoda();
    void Pop();
    void Push();
    void ScriviCoda();
    void PresentaMenu();
    // funzione principale
    int main()
    {
     int scelta; // scelta nel menu
    SvuotaCoda();
     do {
     do {
     PresentaMenu();
     cout << "Inserisci la tua scelta =>";
     cin >> scelta;
     } while (scelta<1 || scelta>5);
     switch(scelta) {
     case 1:
     SvuotaCoda();
     break;
     case 2:
     Pop();
     break;
     case 3:
     Push();
     break;
     case 4:
     ScriviCoda();
     break;
     }
     } while (scelta != 5);
     return 0;
    }
    // inizializzazione della pila
    void SvuotaCoda()
    {
     BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
     END = 0; //inizializziamo il puntatore END ( da muovere con la PUSH)
     cout << "Coda vuota" << endl;
    }
    
    void Pop() // funzione POP = estrazione di un elemento dalla coda
    {
     	bool coda_vuota=false;
     	if (BEGIN==END ){//controllo se BEGIN e END sono uguali, ed entrambi hanno valore 0
     		coda_vuota=true;}
     	if(coda_vuota) cout << "NON CI SONO ELEMENTI DA ESTRARRE!" << endl; 
     	if(!coda_vuota) {
     		cout << "Elemento estratto = " << Coda[BEGIN] << endl;
     		(BEGIN+1)%MAX; 
     		}
     	
    }
    void Push()
    {
    	int dato; // elemento da inserire
    	if (END==BEGIN-1 || END==MAX-1 && BEGIN==0){
    		coda_piena=true;}
    	if(coda_piena) cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;
     	if(!coda_piena){
     		cout << "Dato da inserire = ";
     		cin >> dato;
     		Coda[END] = dato;
     		(END+1)%MAX;
     	}
     	
    } // Push
     
    void ScriviCoda()
    {
    	if(BEGIN>END){
    		cout << "INIZIO CODA" << endl;
     		for (int i=BEGIN ; i<=END-1; i--) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
     		cout << "FINE CODA" << endl;
     		cout << " VALORE END " << END<<endl;
    		cout << "VALORE BEGIN " <<BEGIN<< endl;
    	}
    	else{
     	cout << "INIZIO CODA" << endl;
     	for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO 
    	 cout << "FINE CODA" << endl;
     	cout << " VALORE END " << END<<endl;
    	cout << "VALORE BEGIN " <<BEGIN<< endl;}
    } 
    // menu delle scelte
    void PresentaMenu()
    {
     cout << endl;
     cout << "1. SVUOTA CODA" << endl;
     cout << "2. ESTRAI DATO (POP)" << endl;
     cout << "3. IMMETTI DATI (PUSH)" << endl;
     cout << "4. VISUALIZZA CODA " << endl;
     cout << "5. FINE PER TERMINARE" << endl;
    } // PresentaMenu
    
  • Re: Programma CODA C++

    A parte altri errori, che vediamo dopo


    Ma cosa vuol dire:
    (BEGIN+1)%MAX;
    ?
  • Re: Programma CODA C++

    Prova a ragionarci da solo, uno degli errori è quello che ti hanno indicato

    Una possibile soluzione è questa
    
    #include <iostream>
    
    using namespace std;
    
    const int MAX = 4; // dimensione massima della coda + 1
    
    int Coda[MAX]; // array per la coda 
    int END,BEGIN; // = 0 di default perche' variabili globali
    bool coda_vuota = true;
    bool coda_piena; // false di default perche' variabile globale
    
    // prototipi delle funzioni
    void SvuotaCoda();
    void Pop();
    void Push();
    void ScriviCoda();
    void PresentaMenu();
    
    // funzione principale
    int main(){
     int scelta; // scelta nel menu
     // SvuotaCoda(); non serve 
     do {
        do {
            PresentaMenu();
            cout << "Inserisci la tua scelta => ";
            cin >> scelta;
        } while (scelta<1 || scelta>5);
        switch(scelta) {
            case 1:
            SvuotaCoda();
            break;
            case 2:
            Pop();
            break;
            case 3:
            Push();
            break;
            case 4:
            ScriviCoda();
            break;
        }
     } while (scelta != 5);
     return 0;
    }
    
    void SvuotaCoda(){
        BEGIN = END; 
        coda_vuota = true;
        coda_piena = false;
        cout << "Coda vuota" << endl;
    }
    
    void Pop(){
     	if(coda_vuota) cout << "NON CI SONO ELEMENTI DA ESTRARRE!" << endl; 
     	else {
     		cout << "Elemento estratto = " << Coda[BEGIN] << endl;
     		BEGIN = (BEGIN+1)%MAX; 
     		if(BEGIN == END)
     		    coda_vuota = true;
     		coda_piena = false;
     	}
    }
    
    void Push(){
    	if(coda_piena) cout << "Coda piena!!! NON E' POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;
     	else {
     	    int dato; // elemento da inserire
     		cout << "Dato da inserire = ";
     		cin >> dato;
     		Coda[END] = dato;
    		END = (END+1)%MAX; 		
    		coda_vuota = false;
     		if(END==BEGIN-1 || END==MAX-1 && BEGIN==0)
    		    coda_piena = true;
     	}
    } 
    
    void ScriviCoda(){
    	cout << "INIZIO CODA" << endl;
     	for (int i=BEGIN; i!=END; i = (i+1)%MAX) 
     	    cout << Coda[i] << endl;
     	cout << "FINE CODA" << endl;
     	cout << "VALORE END " << END  <<endl;
    	cout << "VALORE BEGIN " << BEGIN << endl;
    } 
    // menu delle scelte
    void PresentaMenu(){
     cout << endl;
     cout << "1. SVUOTA CODA" << endl;
     cout << "2. ESTRAI DATO (POP)" << endl;
     cout << "3. IMMETTI DATI (PUSH)" << endl;
     cout << "4. VISUALIZZA CODA " << endl;
     cout << "5. FINE PER TERMINARE" << endl;
    } 
    
Devi accedere o registrarti per scrivere nel forum
16 risposte