Eliminare elementi da una coda

di
enna1713
il
17 risposte
E
enna1713
Pochi posts
Iscritto da
lug, 2021
Messaggi:
36

Eliminare elementi da una coda

Ho una coda Lqueue dalla quale devo rimuovere tutti gli elementi ( di tipo Item ) con una altezza > di 92 e inoltre devo rimuovere tutti gli elementi che hanno una altezza maggiore rispetto all’elemento precedente (non si applica al primo elemento). per esempio se ho :

(United States,127.2) (United States,120.1) (United States,100.2)
(United States,98.8 ) (United States,91.1) (United States,91.5) (United
States,91.6) (United States,126.7) (United States,55.5) (United States,50.6) (United States,48.9) (United States,41.2) (United States,39.1) (United
States,49.4) (United States,46.3) (United States,43.8 )

(United States,91.1) (United States,91.5) (United States,91.6)
(United States,126.7) (United States,55.5) (United States,50.6) (United
States,48.9) (United States,41.2) (United States,39.1) (United States,49.4) (United States,46.3) (United States,43.8 )

per la prima parte ho fatto una dequeue sulla coda Q1 ma facendo poi la stampa , il programma blocca la sua esecuzione, mentre per la seconda parte non ho idea di come si possa risolvere

Item it;

while (Q1.length() > 0) {

if (altezza > '92') {

Item it = Q1.dequeue();

cout << it << " ";
}

}

17 Risposte

  • Weierstrass
    Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi:
    2248

    Re: Eliminare elementi da una coda

    while (Q1.length() > 0) {
    Quando esci da questo while se la lista non è vuota? Se hai un elemento solo alto 80?

    '92' che cos'è? Il numero intero è 92 e quello a virgola mobile 92.0, mentre la stringa è "92" ma non la puoi confrontare con >

    Come tieni conto degli elementi precedenti della lista?

    Sai ciclare sui next degli elementi della lista fino a quando arrivi a NULL?
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    92 , codice , dalla definizione che ne ho fatto nella classe item è un float. La mia idea era:
    Scorrere la coda
    Estrarre a mano a mano gli elementi dalla coda ( chiamandoli it )
    Se l’elemento estratto it ha un campo codice (it.getcodice() ) < 92.0 allora passo all’elemento successivo
    In caso contrario eseguo una dequeue

    questo però è il metodo che utilizzerei se fossi in una lista. Essendo in una coda non capisco come scorrerla per intero. Se fossi in una lista utilizzerei un ciclo for. Ma nel caso della coda non so come farlo. Inoltre , sempre se fossi in una lista , per passare all’elemento successivo dovrei usare un next ma nel caso delle code invece non so come può essere sostituito. Per farei secondo punto invece , nelle liste , subito dopo aver estratto un elemento , dovrei fare una next e poi estrarre il secondo per effettuare il confronto ma poi sarei bloccata. In una coda ancora peggio
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    Ciao,
    mi ha incuriosito la tua distinzione tra coda e lista e mi è sorto un dubbio, quindi per poterti aiutare avrei bisogno di capire meglio com'è la tua struttura dati e sopratutto quali operazioni sono consentite.

    Ipotizzando che sia implementata tramite puntatori, puoi scorrere gli elementi leggendone il contenuto? Oppure per leggere il contenuto devi per forza estrarre l'elemento all'estremo della coda?
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    In questo caso questo esercizio ( del quale non ho la soluzione ) andrebbe svolto con quella che a lezione abbiamo chiamato classe lqueue e le operazioni consentite sono :
    enqueue ( inserimento di un elemento , ma dalla testa ) , dequeue ( rimozione di un elemento , dalla coda ) , length ( che indica la lunghezza della coda ) , frontValue ( che indica il primo elemento della coda ) , clear per cancellare tutti gli elementi presenti nella coda.

    Questo è quello che io ho studiato dalla teoria ma non so se mi mancano all’appello altre funzioni che possano aiutarmi in questo caso. Lo chiedo perché nelle liste invece facendo 
     for (L.moveToStart(); L.currPos()<L.length(); L.next())
    riuscivo a scorrere tutti gli elementi mentre qui non saprei come fare.

    facendo delle prova per scorrere la coda ho provato ad utilizzare un ciclo for ma non mi esce nulla di logico. nel senso che mi stampa una parte , nemmeno tutta, di tutti gli elementi che invece dovrei togliere. 
    
for (int i = 0; i < Q1.length(); i++) {

	if (temp.getcodice() < '92') {

		Q1.dequeue();

	}
}
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    L'esercizio è fattibile utilizzando una sola struttura dati, la coda appunto, che consenta di conoscere la lunghezza, l'inserimento di un elemento da un lato della coda e l'estrazione (con possibile lettura) di un elemento dalla parte opposta.
    Un possibile pseudocodice è il seguente
    
l = length(Q)
t = 0
min = 92
i = dequeue
j = dequeue

while t < l
  if i > min and j > min
    i = dequeue
    j = dequeue
    l = l - 2
    t = t + 2
    loop
    
  if i > min and j < i
    enqueue j
    i = j
    j = dequeue
    l = l - 1
    t = t - 1
    loop
    
  if i < min and j > i
    enqueue i
    i = j
    j = dequeue
    l = l - 1
    t = t - 1
    loop
    
  enqueue i
  enqueue j
  i = dequeue
  j = dequeue
  t = t + 2
    In pratica esamino i casi di esclusione dei singoli elementi prendendoli due a due. Se li elimino entrambi, riduco la lunghezza della coda di due, se ne elimino uno solo rimetto in coda l'altro. Se non ne elimino nessuno li rimetto in coda entrambi. Il contatore t mi dice quando ho girato su tutta la coda.

    Potrei aver sbagliato qualche dettaglio ma la logica dovrebbe essere corretta.
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    Perdonate il ritardo con cui rispondo ma ho avuto diversi problemi di salute e riprendo in mano tutto solo oggi. Non riesco molto bene a capire la logica del secondo e terzo step. Nel senso, nel secondo punto :

    Se i > 92 e se j < i allora significa che ho estratto due elementi dalla coda , i e j , e che i < 92 e che j < di i stesso ( dove i e j rappresentano il campo altezza dell’item). essendo i < 92 allora andrà eliminato dalla coda. J , invece , per essere eliminato dalla coda deve essere > del campo altezza del primo estratto , rappresentato proprio da i. Quindi in questo caso j non andrebbe eliminato .Non riesco bene a capire i tre passaggi che si fanno dopo :
    Inserire j in testa alla coda
    Porre gli elementi estratti dalla coda , i e j , uguali
    Porre j uguale all’elemento tolto

    Grazie e scusate ancora !
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    Ciao,
    prendiamo il secondo caso: 
    
  if i > min and j < i
    enqueue j
    i = j
    j = dequeue
    l = l - 1
    t = t - 1
    loop
    In questa circostanza devo eliminare solo i e non j, quindi rimetto j in testa alla coda 
    enqueue j
    Assegno a i il valore di j perché i sarà l'elemento che utilizzerò nel successivo ciclo (del while) come confronto per verificare se sia minore del futuro j (che in tal caso scarterò). Infine, siccome ho eliminato un solo elemento riduco la lunghezza della coda di 1 
    l = l-1
    Avendo analizzato un solo elemento, riduco t di 1
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    La logica che sta dietro al codice ora penso di averla finalmente capita. ho provato a scrivere il codice in c , con tutte le indicazioni che mi hai dato. e ne è uscito questo:
    

int l = Q1.length();
	int	t = 0;
	int	min = 92;
	Item i;
	Item j;

		for (int k = 0; k < Q1.length(); k++) {

			
				 i = Q1.dequeue();
				 j = Q1.dequeue();

			
		}


		while (t < l) {
			if (i.getcodice() > min && j.getcodice() > min) {
				i = Q1.dequeue();
				j = Q1.dequeue();
				l = l - 2;
				t = t + 2;
			}


			if (i.getcodice() > min && j.getcodice() < i.getcodice()) {
				Q1.enqueue(j);
				i = j;
				j = Q1.dequeue();
				l = l - 1;
				t = t - 1;
		}

			if (i.getcodice() < min && j.getcodice() > i.getcodice()) {
				Q1.enqueue(i);
				i = j;
					j = Q1.dequeue();
					l = l - 1;
					t = t - 1;
			}

			else {
				Q1.enqueue(i);
				Q1.enqueue(j);
				i = Q1.dequeue();
				j = Q1.dequeue();
				t = t + 2;
			}


		}




  Lqueueprint(Q1);

    quello che stampa è corretto ma incompleto , perchè mancano molti item nella coda finale. forse ho fatto qualche pasticcio io quando ho inserito il ciclo for per scorrere tutta la coda e , a mano a mano , togliere gli elementi che poi considererò come i e j. inoltre al posto di mettere i e j ho messo invece l'accesso al campo codice dei due item, perchè è proprio su quei campi che devo svolgere il confronto. spero ci sia qualcosa di sensato
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    A primo acchito direi che quel ciclo for all'inizio non c'entra nulla, direi di toglierlo
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    È tutta la mattina che ci impazzisco sopra e tra i vari tentativi ho tolto il ciclo. In quel caso succede l’opposto. Ovvero tutti gli item corretti vengono stampati , ma ne stampa anche qualcuno in più i suoi poi sono ordinati ma per quello pensavo di inserire una qualsiasi funzione di ordinamento e ristampare , solo dopo , la coda ordinata. Poi ho una domanda.. il ciclo si può cancellare perché in base al ragionamento del tuo codice , i e j si aggiornano automaticamente all’interno dei cicli giusto ?
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    enna1713 ha scritto:

    è tutta la mattina che ci impazzisco sopra e tra i vari tentativi ho tolto il ciclo. In quel caso succede l’opposto. Ovvero tutti gli item corretti vengono stampati , ma ne stampa anche qualcuno in più
    Se mostri l'input della coda e il conseguente output potremmo cercare di capire se ci sia qualche errore nel codice, come ho detto all'inizio non posso escludere di averne commesso qualcuno.

    enna1713 ha scritto:

    i suoi poi sono ordinati ma per quello pensavo di inserire una qualsiasi funzione di ordinamento e ristampare , solo dopo , la coda ordinata.
    I suoi di chi?

    enna1713 ha scritto:

    Poi ho una domanda.. il ciclo si può cancellare perché in base al ragionamento del tuo codice , i e j si aggiornano automaticamente all’interno dei cicli giusto ?
    Il ciclo while scorre tutti gli elementi della coda, non ha senso un ciclo for precedente ad esso.
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    Per suoi intendo lo screenshot dell’ output che dovrei avere. Per ogni tema di esame vecchio ci sono gli output che dovremmo ottenere. Non abbiamo invece il codice che è stato scritto per ottenere quell’output. È solo così che posso controllare se scrivo cose senza senso ora posto L’ output che dovrei ottenere
  • E
    enna1713
    Pochi posts
    Iscritto da
    lug, 2021
    Messaggi:
    36

    Re: Eliminare elementi da una coda

    Partendo da q1: (1,Kingda Ka,United States,127.2) (2,Top Thrill Dragster,United States,120.1) (3,Superman,United States,100.2)
    (4,Fury 325,United States,98 . (7,Intimidator 305,United States,91.1) (8,Millennium Force,United States,91.5) (9,Orion,United
    States,91.6) (10,Superman 2,United States,126.7) (14,El Toro,United States,55.5) (15,Goliath,United States,50.6) (17,The
    Voyage,United States,48.9) (18,Hades 360,United States,41.2) (21,American Eagle,United States,39.1) (22,Outlaw Run,United
    States,49.4) (23,The Boss,United States,46.3) (24,The Beast,United States,43. 8 )

    dovrei ottenere degli elementi. Stampare le code q1 e q2.
    (7,Intimidator 305,United States,91.1) (8,Millennium Force,United States,91.5) (9,Orion,United States,91.6)
    (10,Superman 2,United States,126.7) (14,El Toro,United States,55.5) (15,Goliath,United States,50.6) (17,The Voyage,United
    States,48.9) (18,Hades 360,United States,41.2) (21,American Eagle,United States,39.1) (22,Outlaw Run,United States,49.4) (23,The
    Boss,United States,46.3) (24,The Beast,United States,43.

    mentre io ottengo in più il (1,Kingda Ka,United States,127.2) e (4,Fury 325,United States,98.
  • S
    settantatre
    Utente Attivo
    Iscritto da
    lug, 2021
    Messaggi:
    53

    Re: Eliminare elementi da una coda

    Sì ok, ti mancano i loop alla fine degli if. Se non torni subito al ciclo successivo rischi di riprendere elementi scartati. Controlla il mio codice
Devi accedere o registrarti per scrivere nel forum
17 risposte