Cercare sottosequenza di numeri consecutivi in una lista..

di
LuigiC++
il
3 risposte
L
LuigiC++
Pochi posts
Iscritto da
apr, 2018
Messaggi:
31

Cercare sottosequenza di numeri consecutivi in una lista..

Salve a tutti, scrivo (nuovamente) per un aiuto su una funzione per le liste. Qualcuno forse si ricorderà del precedente post dove chiedevo aiuti e generalità sulle liste (eliminazione, inserimento, etc...)..Bene, quella parte mi è finalmente chiara, e come consigliato da qualcuno, ho eliminato le dichiarazioni con i typedef, e mi è risultato tutto più semplice oserei dire.
Ora ho "risolto" questo esercizio, che, data una lista di tot elementi, cerca all'interno di essa una sequenza di numeri consecutivi e li somma, lasciando poi il nodo della loro somma.
Esempio: 10 5 3 2 1
Risultato: 10 5 6
Il mio esercizio funziona, in quanto spostando il puntatore gli faccio "saltare" 2 e 1 e al posto del 3 ci piazzo 6, ma non sono riuscito a utilizzare free per liberare la memoria, quindi, praticamente, perso ogni collegamento al nodo 2 e al nodo 1, essi rimangono smarriti in memoria, giusto?

Ora vi chiedo, va bene lo stesso? Posso incappare in errori? Con le prove che ho effettuato finora non ne ho riscontrati., tuttavia a occhi più esperti potrebbero saltar fuori problemi legati al fatto che non libero effettivamente memoria.

struct nodo {
	int valore;
	struct nodo *next;
};


struct nodo * sequenza(struct nodo * testa)
{	
	printf("Ora cerco sottosequenze di numeri consecutivi e sommo tali numeri.\n");
	struct nodo * current, *app;

	if(testa == NULL || testa->next == NULL) { //chiaramente se la testa ha 0 o al massimo 1 elemento, non cerco sottosequenze
		return testa;
	}

	else
	{
		current = testa;
		
		while(current && current->next) {
			app = current;
			while((app && app->next) && (app->valore +1 == app->next->valore)) {
				current->valore += (app->next->valore);
				app = app->next;
			}
			
			if(current != app) current->next = app->next;
			current = current->next;
		}
	}

	return testa;		
}

3 Risposte

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

    Re: Cercare sottosequenza di numeri consecutivi in una lista..

    La programmazione a "memory leak" va bene se sai che comunque il tuo programma non occuperà mai più un tot numero di byte nello heap e tale limite è basso rispetto alla RAM a disposizione.
    Sembra il caso del tuo programma.
    Tuttavia nella applicazioni reali è molto probabile che tu abbia bisogno di fare una gestione corretta della memoria, quindi tanto vale provare adesso con gli esercizi semplici
  • L
    LuigiC++
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    31

    Re: Cercare sottosequenza di numeri consecutivi in una lista..

    Ho capito..vorrà dire che dovrò continuare a ragionare..
    Perchè avevo provato così ma non andava:
    Vi lascio solo il while di sopra modificato, con in più la variabile tmp che mi serve per deallocare.
    
		while(current && current->next) {
			app = current;
			while((app && app->next) && (app->valore +1 == app->next->valore)) {
				current->valore += (app->next->valore);
				
				tmp = app;
				app = app->next;
				free(tmp);	
			}
			
			if(current != app) current->next = app->next;
			current = current->next;
		}
  • Weierstrass
    Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi:
    2245

    Re: Cercare sottosequenza di numeri consecutivi in una lista..

    E' meglio se strutturi il programma in modo da localizzare i punti dove allochi e deallochi, di modo da svincolarti da tutto il resto.

    Tipo così (non è l'esercizio completo - manca da individuare l'inizio e la fine delle sequenze)

    C 
    
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct nodo {
    int valore;
    struct nodo *next;
};

void stampa(struct nodo *testa){
    struct nodo * ptr = testa;
    while (ptr){
        printf("%d -> ", ptr->valore);
	ptr = ptr->next;
    }
    printf("FINE\n");        
}

void inserisci_prima(struct nodo **testa, unsigned int posizione, int valore){
    struct nodo *n = *testa;        
    if (n == NULL || !posizione){
        n = (struct nodo *)malloc(sizeof(struct nodo));
        n->valore = valore;
        n->next = *testa;
        *testa = n;   
    }
    else{
        while(n->next != NULL && --posizione)      
            n = n->next;
        struct nodo *nuovo =(struct nodo*)malloc(sizeof(struct nodo)); 
        nuovo->valore = valore; 
        nuovo->next = n->next;  
        n->next = nuovo;   
    }
}

void inserisci_dopo(struct nodo **testa, unsigned int posizione, int valore){
    inserisci_prima(testa, posizione + 1, valore);
}

void push(struct nodo **testa, int valore){
    inserisci_prima(testa, 0, valore);
}

void push_back(struct nodo **testa, int valore){
    inserisci_prima(testa, UINT_MAX, valore);
}

void erase(struct nodo **testa, unsigned int posizione){
    if (*testa == NULL) 
        return; 
    struct nodo *precedente = *testa;     
    if (!posizione) { 
        *testa = precedente->next;
        free(precedente);
        return; 
    } 
    while(precedente != NULL && --posizione)      
        precedente = precedente->next;
    if (precedente == NULL || precedente->next == NULL) 
        return; 
    struct nodo *successivo = precedente->next->next; 
    free(precedente->next);
    precedente->next = successivo;
}

int valore(struct nodo **testa, unsigned int posizione){
    struct nodo *n = *testa;        
    while(n != NULL && posizione--)      
        n = n->next;
    if (n == NULL)
        return INT_MIN; 
    else
        return n->valore;
}

int main(void){
	struct nodo *lista = NULL;
          
	push_back(&lista, 10); stampa(lista);       
	push_back(&lista,  5); stampa(lista);  
	push_back(&lista,  3); stampa(lista);  
	push_back(&lista,  2); stampa(lista);         
        push_back(&lista,  1); stampa(lista);    
        push_back(&lista, 42); stampa(lista);   
        
        int start_address = 2;
        int stop_address  = 4;
        int somma, i;
        for(somma = 0, i = start_address; i <= stop_address; i++){
            somma += valore(&lista, start_address);
            erase(&lista, start_address);
        }
        inserisci_prima(&lista, start_address, somma);   
	stampa(lista);          
        
	return 0;
}
    C++ 
    
#include <iostream>
#include <vector> 

using namespace std;

void stampa(vector<int> l){
        for (auto it = l.begin(); it != l.end(); it++)
            cout << *it << " -> ";
        cout << "FINE" << endl;   
} 

int main (void) {
    vector<int> lista; 
    
    lista.push_back(10); stampa(lista);
    lista.push_back( 5); stampa(lista);
    lista.push_back( 3); stampa(lista);
    lista.push_back( 2); stampa(lista);
    lista.push_back( 1); stampa(lista);
    lista.push_back(42); stampa(lista);
    
    int start_address = 2;
    int stop_address  = 4;
    int somma, i;
    for(somma = 0, i = start_address; i <= stop_address; i++){
        somma += lista.at(start_address);
        lista.erase(lista.begin() + start_address);
    }
    lista.insert(lista.begin() + start_address, somma);
    stampa(lista);     

    return 0;
}
Devi accedere o registrarti per scrivere nel forum
3 risposte