Eliminare elemento con valore max da una lista...Help!

di Anonimizzato24130 il
6 risposte
/
Anonimizzato24130
Utente anonimizzato
Salve, chiedo un aiuto riguardo a questo pezzo di codice di un programma che carica una lista in coda e che deve eliminare l'elemento max, la traccia dell'esercizio mi limita a scorrere la lista una sola volta...
Quando avvio il programma e digito una semplice lista "1,2,3,4,5", mi vede come max=1 e mi stampa la lista modificata come "2,3,4,5".
Potete aiutarmi? 

struct elem* elimina(struct elem *top){
    struct elem *c=top, *pre_elem, *pre, *tmp;
    int max=0;
 
    if(c->valore>max){
        max=c->valore;
        tmp=c;
    }else{
    c=top->next;
    pre=top;
    while(c!=NULL){
        if(c->valore>max){
        max=c->valore;
        pre_elem=pre;
        tmp=c;
        }
        pre=c;
        c=c->next;
        }
    }
    if(tmp==top){
        top=tmp->next;
        free(tmp);
    }
    if(tmp!=top){
    pre_elem->next=tmp->next;
    free(tmp);
    }
    printf("Max: %d", max);
    return top;
}

6 Risposte

  • Avatar di Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi
    1224
    Potresti postare il codice intero?

    Per il momento ho letto solo le prime 3 righe di codice. Qualche osservazione:
    - c'è qualcosa che non va nella dichiarazione della funzione. Indizio: cosa succede se il massimo è il primo elemento della lista?;*
    - potresti spiegarmi qual è lo scopo di ognuno dei 4 puntatori che hai dichiarato?
    - ipotizziamo di avere la seguente lista: -1, -2, -3. Sei ancora sicuro che la variabile max vada inizializzata a 0?

    EDIT:
    *Mi correggo, può andare bene. Leggendo superficialmente non ho prestato attenzione al tipo di ritorno, dando per scontato che fosse void.
  • Avatar di Unqualunque
    Utente Attivo
    Iscritto da
    gen, 2018
    Messaggi
    122
    Poiché spesso è più facile scrivere una funzione da nuovo anziché cercare di capire cosa non funziona in qualcosa scritto da un'altro, io ho scritto la mia funzione per eliminare l'elemento con valore massimo, e poi ho modificato il codice per utilizzare la tua notazione. Il risultato è che è uguale identica alla tua tranne per la prima istruzione if(c->valore>max)...else, che in effetti non comprendo per quale motivo tu l'abbia scritta.
    typedef struct tag_Node {
	int val;
	struct tag_Node *next;
} _Node;

_Node * DeleteMax(_Node *top)
{
	_Node *c = top, *pre_elem, *pre, *tmp;
	int max = 0;
 
	while ( c )
	{
		if ( c->val > max )
		{
			max = c->val;
			pre_elem = pre;	// Salva l'indirizzo dell'elemento precedente a quello da eliminare.
			tmp = c;			// Salva l'indirizzo dell'elemento da eliminare
		}

		pre = c;
		c = c->next;
	}

	if ( tmp == top )	// Se da eliminare è la testa della lista...
	{
		top = tmp->next;
		free(tmp);
	}
	else // ( tmp != top )
	{
		pre_elem->next = tmp->next;
		free(tmp);
	}

	printf("Max: %d", max);
	return top;
}

	// Alla chiamata:
	m_pHead = DeleteMax(m_pHead);
    Testato, a me funziona correttamente, anche mettendo il valore massimo nell'elemento in testa o nell'elemento in coda.
  • /
    Anonimizzato24130
    Utente anonimizzato

    Unqualunque ha scritto:

    Poiché spesso è più facile scrivere una funzione da nuovo anziché cercare di capire cosa non funziona in qualcosa scritto da un'altro, io ho scritto la mia funzione per eliminare l'elemento con valore massimo, e poi ho modificato il codice per utilizzare la tua notazione. Il risultato è che è uguale identica alla tua tranne per la prima istruzione if(c->valore>max)...else, che in effetti non comprendo per quale motivo tu l'abbia scritta.
    typedef struct tag_Node {
	int val;
	struct tag_Node *next;
} _Node;

_Node * DeleteMax(_Node *top)
{
	_Node *c = top, *pre_elem, *pre, *tmp;
	int max = 0;
 
	while ( c )
	{
		if ( c->val > max )
		{
			max = c->val;
			pre_elem = pre;	// Salva l'indirizzo dell'elemento precedente a quello da eliminare.
			tmp = c;			// Salva l'indirizzo dell'elemento da eliminare
		}

		pre = c;
		c = c->next;
	}

	if ( tmp == top )	// Se da eliminare è la testa della lista...
	{
		top = tmp->next;
		free(tmp);
	}
	else // ( tmp != top )
	{
		pre_elem->next = tmp->next;
		free(tmp);
	}

	printf("Max: %d", max);
	return top;
}

	// Alla chiamata:
	m_pHead = DeleteMax(m_pHead);
    Testato, a me funziona correttamente, anche mettendo il valore massimo nell'elemento in testa o nell'elemento in coda.

    Ti ringrazio, inserito nel programma e funziona alla perfezione, era quella condizione iniziale che non andava bene...
    Grazie ancora per l'aiuto!
  • Avatar di Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi
    1224
    Ti ringrazio, inserito nel programma e funziona alla perfezione, era quella condizione iniziale che non andava bene...
    Hai capito perchè non andava bene?

    @Unqualunque
    Qualche osservazione sul codice che hai postato:
    - non gestisci il caso di lista vuota;
    - come già detto nel precedente post è sbagliato inizializzare la variabile max a 0... cosa succede se gli elementi della lista sono tutti <=0?
    - credo che 3 puntatori siano sufficienti ai fini del programma. Io farei una cosa del genere: 
    void elimina_max(nodo **testa)
{
    if(*testa)
    {
        int max = (*testa)->valore;
        nodo *prev_max = NULL;
        nodo *ptr_max = *testa;
        nodo *tmp = *testa;
        while(tmp->next)
        {
            if(tmp->next->valore > max)
            {
                max = tmp->next->valore;
                prev_max = tmp;
                ptr_max = tmp->next;
            }
            tmp = tmp->next;
        }
        if(prev_max)
        {
            prev_max->next = ptr_max->next;
        }
        else
        {
            *testa = (*testa)->next;
        }
        free(ptr_max);
    }
}
  • Avatar di Unqualunque
    Utente Attivo
    Iscritto da
    gen, 2018
    Messaggi
    122

    Nippolo ha scritto:

    @Unqualunque
    Qualche osservazione sul codice che hai postato:
    - non gestisci il caso di lista vuota;
    - come già detto nel precedente post è sbagliato inizializzare la variabile max a 0... cosa succede se gli elementi della lista sono tutti <=0?
    - credo che 3 puntatori siano sufficienti ai fini del programma. Io farei una cosa del genere:
    Si, hai ragione, ho pensato corto. Non mi ero accorto che sarebbero sorte un paio di eccezioni. Per la lista vuota ho volutamente omesso (per brevità) una condizione che in realtà utilizzo sempre. Ho corretto l'inizializzazione del valore max e del puntatore tmp, sempre per utilizzare la notazione di AntonioSebastiano. La versione così corretta: 
    _Node * DeleteMax(_Node *top)
{
	if( !top )
		return NULL;

	_Node *c = top;
	_Node *pre_elem = NULL;
	_Node *pre = NULL;
	_Node *tmp = top;

	int max = top->val;
 
	while( c )
	{
		if( c->val > max )
		{
			max = c->val;
			pre_elem = pre;
			tmp = c;
		}

		pre = c;
		c = c->next;
	}

	if ( tmp == top )
		top = tmp->next;
	else // ( tmp != top )
		pre_elem->next = tmp->next;
	free(tmp);

	printf("Max: %d", max);
	return top;
}
    ...sembra risolvere questi problemi, ma il tuo codice è assolutamente più elegante perché hai eliminato un puntatore e qualche passo di troppo. Tuttavia mi sembra che entrambe le nostre versioni eliminano un elemento dalla lista, comunque sia, quando tutti i valori sono tutti uguali.
  • Avatar di Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi
    1224
    Tuttavia mi sembra che entrambe le nostre versioni eliminano un elemento dalla lista, comunque sia, quando tutti i valori sono tutti uguali.
    Esatto e in particolare quando il massimo si ripete più volte è il primo ad essere eliminato (nel caso in cui avessimo usato l'operatore relazionale >= sarebbe stato l'ultimo).
    Un modo per eliminare tutti i valori massimi potrebbe essere quello di scorrere la lista solo per trovare max e poi richiamare (dalla funzione elimina_max()) una funzione elimina_valore(nodo **testa, int n) che elimina dalla lista tutti gli elementi uguali a max.
Devi accedere o registrarti per scrivere nel forum
6 risposte