[C] Strutture dati : sclero.

[The-Revenge]

Scusate ragazzi, questa è la mia unica spiaggia non so a cui rivolgermi. L'incubo finirà a gennaio, intanto vi dovete sorbire i miei 3d a decine, perchè purtroppo ho un prof incompetente e non so a chi chiedere. Dopo aver perso ore a capire le strutture dati, sono riuscito a fare un programma basato sulle strutture dati che "su carta", coi disegnini dei mattonici ecc, funziona, ma nel programma no.
Mi sapete dire dove sbaglio?
Questo è il codice :

#include<stdio.h>
#include<stdlib.h>
struct lis {
       int inf;
       struct lis *pun;
       };
       
struct lis *genLista();
void stampaLista(struct lis *);
struct lis *cancNum(struct lis *);

int main(){
    struct lis lista;
    struct lis *puntalista;
    puntalista=genLista();
    stampaLista(puntalista);
    puntalista=cancNum(puntalista);
    stampaLista(puntalista);
    system("PAUSE");
    return(0);
}

struct lis *genLista(){
       struct lis *p,*paus;
       int n;
       p=(struct lis *)malloc(sizeof(struct lis));
       printf("\nInserisci numero elementi lista : ");
       scanf("%d",&n);
       printf("\nInserisci 1o elemento : ");
       scanf("%d",&p->inf);
       paus=p;
       for(int i=2;i<=n;i++){
               paus->pun=(struct lis *)malloc(sizeof(struct lis));
               paus=paus->pun;
               printf("\nInserisci %do elemento: ",i);
               scanf("%d",&paus->inf);
               }
               paus->pun=NULL;
               return(p);
               }
               
void stampaLista(struct lis *p){
     printf("\nLA LISTA E' :\n");
     while(p!=NULL){
     printf("%d",p->inf);
     printf("-->");
     p=p->pun;
     }
     printf("FINE LISTA");
     printf("\n\n");
     }
     
struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL))p=p->pun;
        paus=p;
        while(paus!=NULL){
        if(((paus->inf)%2==0)){
        paus2=paus->pun;
        paus->pun=NULL;
        paus=paus2;
        continue;
        }
        paus=paus->pun;
        }
    return(p);
                    }

piccolo commento sul codice, vabbè sulla generazione e stampa nulla da dire, il compito della funzione cancNum è di cancellare i numeri pari della lista.
Quello che ho fatto è dividire la cancellazione se il numero è il primo della lista, o se è successivo al primo della lista.
Se è il primo della lista, la cancellazione mi riesce bene. Non posso mettere tutto in uno altrimenti perdere il puntatore alla testa della lista, e perderei di conseguenza la possibilità di stampa.
Comunque, il rpoblema viene quando devo trovare i successivi elementi pari da eliminare; uso 2 puntatori ausiliari, che scorrono la lista e eliminano il numero pari se c'è, se non c'è l'if non viene fatto e il primo puntatore ausiliario viene spostato di 1 mattoncino, mentre se l'if viene fatto avviene la cancellazione, ma il continue evita che il primo puntatore ausiliario si sposti di un mattoncino.
Dove sbaglio?

[wingman87]

Gli errori sono sostanzialmente due:
immagina la lista come una catena: quando cancelli un nodo è come se eliminassi un anello della catena, per far sì che la catena resti insieme devi legare tra loro l'anello che precedeva l'anello eliminato e il successivo. Quello che fai qui:

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL))p=p->pun;
        paus=p;
        while(paus!=NULL){
        if(((paus->inf)%2==0)){
        paus2=paus->pun;
        paus->pun=NULL;
        paus=paus2;
        continue;
        }
        paus=paus->pun;
        }
    return(p);
                    }

è cancellare un nodo, senza legare i due che gli stavano intorno.
Il secondo errore è che non deallochi la memoria allocata.

[The-Revenge]

Originariamente inviato da wingman87

Gli errori sono sostanzialmente due:
immagina la lista come una catena: quando cancelli un nodo è come se eliminassi un anello della catena, per far sì che la catena resti insieme devi legare tra loro l'anello che precedeva l'anello eliminato e il successivo. Quello che fai qui:

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL))p=p->pun;
        paus=p;
        while(paus!=NULL){
        if(((paus->inf)%2==0)){
        paus2=paus->pun;
        paus->pun=NULL;
        paus=paus2;
        continue;
        }
        paus=paus->pun;
        }
    return(p);
                    }

è cancellare un nodo, senza legare i due che gli stavano intorno.
Il secondo errore è che non deallochi la memoria allocata.

bhè, entrambe le cose che mi hai detto mi erano note : deallocare la memoria (penso tu intenda con free) lo volevo fare ma sl in un secondo momento, dato che era solo per ottimizzare il programma, e non mi interessa più di tanto visto che è ad uso didattico...per quanto riguarda le catene, è propio ciò che ho tentato di fare usando paus2...per non lasciare nessun nodo fluttante e per ricollegare il nodo precedente a quello distrutto...
mi potresti dire cosa ho sbagliato esattamente?

[wingman87]

Originariamente inviato da The-Revenge

mi potresti dire cosa ho sbagliato esattamente?

Il problema è che al passo generico stai confrontando un nodo ma non hai memoria del precedente e quindi non ti è possibile risanare la catena

while(paus!=NULL){
        if(((paus->inf)%2==0)){
        paus2=paus->pun;
        paus->pun=NULL;
        paus=paus2;
        continue;
        }

Vedi, qui controlli se paus è uno dei nodi da cancellare ma se è effettivamente così come fai a collegare il suo precedente (di cui il tuo algoritmo non ha memoria) con il successivo (paus->pun)?

[The-Revenge]

l'ho corretto e sembra funzionare. Capito dove sbagliavo : andavo di pari passo ad una cella, senza poter ritornare alla precedente, invece ora lascio idnietro paus1, porto avanti paus2 e poi creo il ponte tra paus1 e il successivo e scollego paus2.
Per la deallocazione, dealloco paus1 e 2 alla fine del while? cosi?

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL))p=p->pun;
        paus=p;
        while(paus!=NULL){
                          paus2=paus->pun;
                          if(((paus2->inf)%2==0)){
        paus->pun=paus2->pun;
        paus2->pun=NULL;
        }
        paus=paus->pun;
        }
        free(paus);
        free(paus2);
    return(p);
                    }

[BlackAuron]

Codice PHP:

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

struct lis {
    int inf;
    struct lis *pun;
};

struct lis *genLista();
void stampaLista(struct lis *);
struct lis *cancNum(struct lis *);

int main() {
    struct lis *puntalista;
    puntalista = genLista();
    stampaLista(puntalista);
    puntalista = cancNum(puntalista);
    stampaLista(puntalista);
    return (0);
}

struct lis *genLista() {
    struct lis *p, *paus;
    int n, i;
    // Allochi lo spazio di struct lis e lo casti come puntatore ... le due
    // dimensioni sono differenti. Tra l'altro, il cast nel C non è necessario
    p = malloc(sizeof (struct lis));
    printf("\nInserisci numero elementi lista : ");
    scanf("%d", &n);
    printf("\nInserisci 1o elemento : ");
    scanf("%d", &p->inf);
    paus = p;
    for (i = 2; i <= n; i++) {
        //stesso discorso di prima. Allochi patate e casti pere.
        paus->pun = malloc(sizeof (struct lis));
        paus = paus->pun;
        printf("\nInserisci %do elemento: ", i);
        scanf("%d", &paus->inf);
    }
    paus->pun = NULL;
    return (p);
}

void stampaLista(struct lis *p) {
    printf("\nLA LISTA E' :\n");
    while (p) {
        printf("%d", p->inf);
        printf("-->");
        p = p->pun;
    }
    printf("FINE LISTA");
    printf("\n\n");
}

struct lis *cancNum(struct lis *p) {
    struct lis *paus = NULL,*tmp,*head = NULL;
    while(p){
        if(!(p->inf % 2)){
            tmp = p->pun;
            free(p);
            p = tmp;
        }
        else{
            if(!head )
                head = p;
            else
                paus->pun = p;
            paus = p;
            p = p->pun;
        }

    }
    if(paus)
        paus->pun = NULL;
    return (head);
} 


Non è la soluzione ottima, ma funziona teoricamente si potrebbe fare a meno della variabile paus, e andare direttamente ad eliminare i successori di p.

[wingman87]

Originariamente inviato da The-Revenge

l'ho corretto e sembra funzionare. Capito dove sbagliavo : andavo di pari passo ad una cella, senza poter ritornare alla precedente, invece ora lascio idnietro paus1, porto avanti paus2 e poi creo il ponte tra paus1 e il successivo e scollego paus2.
Per la deallocazione, dealloco paus1 e 2 alla fine del while? cosi?

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL))p=p->pun;
        paus=p;
        while(paus!=NULL){
                          paus2=paus->pun;
                          if(((paus2->inf)%2==0)){
        paus->pun=paus2->pun;
        paus2->pun=NULL;
        }
        paus=paus->pun;
        }
        free(paus);
        free(paus2);
    return(p);
                    }

No, dovresti deallocare di volta in volta il nodo che scolleghi, così invece deallochi solo l'ultimo che hai scollegato

[BlackAuron]

Codice PHP:

struct lis *cancNum(struct lis *p) {
    struct lis *tmp,*head = p;
    while(p->pun){
        if(!((p->pun)->inf % 2)){
            tmp = (p->pun)->pun;
            free(p->pun);
            p->pun = tmp;
        }
        else{
            if(!(head->inf % 2))
                head = p;
            p = p->pun;
        }
    }
    if(p)
        p->pun = NULL;
    return (head);
} 


Ecco la versione dove risparmi una variabile... vedi tu quale preferisci, questa concettualmente è relativamente più incasinata, ma è più efficente.

[The-Revenge]

Originariamente inviato da BlackAuron

Codice PHP:

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

struct lis {
    int inf;
    struct lis *pun;
};

struct lis *genLista();
void stampaLista(struct lis *);
struct lis *cancNum(struct lis *);

int main() {
    struct lis *puntalista;
    puntalista = genLista();
    stampaLista(puntalista);
    puntalista = cancNum(puntalista);
    stampaLista(puntalista);
    return (0);
}

struct lis *genLista() {
    struct lis *p, *paus;
    int n, i;
    // Allochi lo spazio di struct lis e lo casti come puntatore ... le due
    // dimensioni sono differenti. Tra l'altro, il cast nel C non è necessario
    p = malloc(sizeof (struct lis));
    printf("\nInserisci numero elementi lista : ");
    scanf("%d", &n);
    printf("\nInserisci 1o elemento : ");
    scanf("%d", &p->inf);
    paus = p;
    for (i = 2; i <= n; i++) {
        //stesso discorso di prima. Allochi patate e casti pere.
        paus->pun = malloc(sizeof (struct lis));
        paus = paus->pun;
        printf("\nInserisci %do elemento: ", i);
        scanf("%d", &paus->inf);
    }
    paus->pun = NULL;
    return (p);
}

void stampaLista(struct lis *p) {
    printf("\nLA LISTA E' :\n");
    while (p) {
        printf("%d", p->inf);
        printf("-->");
        p = p->pun;
    }
    printf("FINE LISTA");
    printf("\n\n");
}

struct lis *cancNum(struct lis *p) {
    struct lis *paus = NULL,*tmp,*head = NULL;
    while(p){
        if(!(p->inf % 2)){
            tmp = p->pun;
            free(p);
            p = tmp;
        }
        else{
            if(!head )
                head = p;
            else
                paus->pun = p;
            paus = p;
            p = p->pun;
        }

    }
    if(paus)
        paus->pun = NULL;
    return (head);
} 


Non è la soluzione ottima, ma funziona teoricamente si potrebbe fare a meno della variabile paus, e andare direttamente ad eliminare i successori di p.

si bhè ma il mio prof credo gli basti come l'ho fatto io, d'altronde non voglio diventare programmatore è solo un esame...mi diresti come fare il free giusto per il mio programma? grazie

[The-Revenge]

Originariamente inviato da BlackAuron

Codice PHP:

struct lis *cancNum(struct lis *p) {
    struct lis *tmp,*head = p;
    while(p->pun){
        if(!((p->pun)->inf % 2)){
            tmp = (p->pun)->pun;
            free(p->pun);
            p->pun = tmp;
        }
        else{
            if(!(head->inf % 2))
                head = p;
            p = p->pun;
        }
    }
    if(p)
        p->pun = NULL;
    return (head);
} 


Ecco la versione dove risparmi una variabile... vedi tu quale preferisci, questa concettualmente è relativamente più incasinata, ma è più efficente.

eh si...preferisco quelle concettualmente più semplici, per ora, che è i primo esercizio che faccio sulle strutture dati.
Comunque per il fatto del casting che mi hai fatto notare, c'è scritto sul libro di fare cosi..nn so.
Comunque ho qualche problema a capire la deallocazione

[The-Revenge]

è deallocato bene cosi? ho usato la deallocazione sia sul puntalista che sul secondo puntatore ausliario. Credo di aver capito il concetto.

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL)){paus=p;
                                          p=p->pun;
                                          p->pun=NULL;
                                          free(paus);
                                          }
        paus=p;
        while(paus!=NULL){
                          paus2=paus->pun;
                          if(((paus2->inf)%2==0)){
        paus->pun=paus2->pun;
        paus2->pun=NULL;
        free(paus2);
        }
        paus=paus->pun;
        }

    return(p);

[BlackAuron]

Se deallochi, cancelli dalla faccia della terra quello che passi come argomento, devi solo ricordarti che quando lo fai non hai più niente di ciò che era presente nella struttura.
per quanto riguarda l'allocazione..

Codice PHP:

p=(struct lis *)malloc(sizeof(struct lis)); 


resto convinto che sia un errore concettuale. Se dai un sizeof su "struct lis*" e "struct lis", vedrai che le dimensioni sono differenti, presumibilmente struct lis sarà più grande del relativo puntatore.
E' come comprare un garagage dimensione limousine quando hai una smart... non è che non funzioni, è solo uno spreco, concettualmente cannato (oltre che economicamente ) Magari senti il tuo professore a riguardo, o vedi che ti dicono gli altri utenti del forum ...
Ah, come nota trasversale, compilando con gcc -Wall, a me il cast lo segnala pure come warning, visto che in c i cast pare non siano necessari...

[wingman87]

Originariamente inviato da The-Revenge

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while(((p->inf)%2==0)&&(p!=NULL)){paus=p;
                                          p=p->pun;
                                          p->pun=NULL;
                                          free(paus);
                                          }
        paus=p;
        while(paus!=NULL){
                          paus2=paus->pun;
                          if(((paus2->inf)%2==0)){
        paus->pun=paus2->pun;
        paus2->pun=NULL;
        free(paus2);
        }
        paus=paus->pun;
        }

    return(p);

E' quasi tutto giusto, nella condizione del primo while bisogna scambiare le due condizioni, in modo che se p è NULL non viene fatto il controllo p->inf%2==0 che darebbe errore.
La prima assegnazione a NULL è un errore, perché nella istruzione precedente hai assegnato a p il nodo successivo, quindi stai agendo su un nodo che non hai ancora esaminato.
La seconda assegnazione a NULL è inutile perché tanto agisce su memoria che subito dopo deallochi con free.

[The-Revenge]

Originariamente inviato da wingman87

E' quasi tutto giusto, nella condizione del primo while bisogna scambiare le due condizioni, in modo che se p è NULL non viene fatto il controllo p->inf%2==0 che darebbe errore.
La prima assegnazione a NULL è un errore, perché nella istruzione precedente hai assegnato a p il nodo successivo, quindi stai agendo su un nodo che non hai ancora esaminato.
La seconda assegnazione a NULL è inutile perché tanto agisce su memoria che subito dopo deallochi con free.

1)ok
2)si, ho fatto un errore in realtà volevo scrivere paus->pun=NULL. Questo porta allo stesso problema che hai esaminato nel 3 punto
3)qui c'è un problema che hai sollevato e che ho chiesto stamane anche io al mio prof quando spiegava, e mi ès tato risposto in un certo modo ecco xke ho scritto null anche sapendo che dopo deallocavo con free. In pratica paus2->pun punta a un area che ha 2 puntatori quindi posso scollegare paus2. Il mio prof stamattina scollegava sempre paus2->pun prima di deallocare paus2. Io gli ho chiesto se non fosse possibile deallocare direttamente paus2 senza scollegarlo, dato che comunque la parte restante della catena era collegata ad un altro puntatore, e lui mi ha detto che non era sicuro ma che pensava che deallocando direttamente si sarebbe persa anche la restante parte della catena, nonostante fosse collegata ad un altro puntatore. Ecco perchè scollego prima di deallocare, nonostante ero consapevole che avrei deallocato. Quindi mi dite che non c'è bisogno di scollegarlo? Il prof , ripeto, non era sicuro. Stessa cosa nel punto 2, corretto l'errore porterebbe a questo problema.

X blackauron : guarda, sicuramente avrai ragione ma il libro e il prof dicono in quella maniera e, siccome non devo fare nulla di professionale ma solo cose didattiche, preferisco attenermi. Comunque con quel cast io stavo solo dichirando un puntatore che punta a una struttura di tipo lis, e questo puntatore punta a un area di memoria che alloco con malloc , usando sizeof per ricavare la grandezza della struttura di tipo lis. Non vedo dove è l'errore che tu dici

Comunque vi ringrazio per l'aiuto e per li speigazione, mi siete stati di grande aiuto

Alla fine dovrebbe essere cosi

struct lis *cancNum(struct lis *p){
        struct lis *paus,*paus2;
        while((p!=NULL)&&((p->inf)%2==0)){paus=p;
                                          p=p->pun;
                                          paus->pun=NULL;
                                          free(paus);
                                          }
        paus=p;
        while(paus!=NULL){
                          paus2=paus->pun;
                          if(((paus2->inf)%2==0)){
        paus->pun=paus2->pun;
        paus2->pun=NULL;
        free(paus2);
        }
        paus=paus->pun;
        }

    return(p);

[wingman87]

Riguardo l'assegnazione a NULL confermo che è inutile, la free semplicemente dealloca un blocco di memoria precedentemente allocato, se facesse quello che dice il prof dovrebbe inferire i campi della struttura puntata dal puntatore passato come parametro (cosa impossibile) e a quel punto deallocare a cascata i vari puntatori.

Non ho invece capito la questione del cast, cioè, non ho capito di cosa state parlando.

[The-Revenge]

Originariamente inviato da wingman87

Riguardo l'assegnazione a NULL confermo che è inutile, la free semplicemente dealloca un blocco di memoria precedentemente allocato, se facesse quello che dice il prof dovrebbe inferire i campi della struttura puntata dal puntatore passato come parametro (cosa impossibile) e a quel punto deallocare a cascata i vari puntatori.

Non ho invece capito la questione del cast, cioè, non ho capito di cosa state parlando.

ok, capisco. Allora la mia domanda al prof era stata lecita , e la sua riasposta, anche se comunque con riserva, non corretta
Per quanto riguarda la questione del cast lui intende questo :

p=(struct lis *)malloc(sizeof(struct lis));

sinceramente questa dichirazione l'ha usata il prof, è scritta cosi come è scritta qui sul libro di C, ed è anche spiegata come l'ho detto io sopra....non ho capito bene l'errore logico che l'utente mi voleva fare notare...

[BlackAuron]

con il cast fai in modo che in p ci stia un puntatore a struct lis, mentre allochi uno spazio di dimensione struct lis.
In parole povere, faccio un esempio

1) sizeof(struct lis) = 10 bytes
2) sizeof(sruct lis *) = 4 bytes

( ricordiamoci che struct lis* contiene solo un indirizzo di memoria, quindi lo spazio di cui necessita è esiguo)

3) malloc(sizeof(struct lis)) creo uno spazio in memoria di dimensione 10 bytes
4) ( struct lis*)malloc(sizeof(struct lis)) do ai 10 bytes la forma di un puntatore a struct lis, che richiede solo 4 bytes. I restanti 6 bytes sono memoria sprecata.

PS: i valori li ho sparati a caso, giusto per far capire il concetto

[wingman87]

Originariamente inviato da BlackAuron

4) ( struct lis*)malloc(sizeof(struct lis)) do ai 10 bytes la forma di un puntatore a struct lis, che richiede solo 4 bytes. I restanti 6 bytes sono memoria sprecata.

Non funziona così: malloc alloca un'area di memoria della dimensione desiderata (quella passata come parametro) e restituisce un puntatore a quell'area di memoria. Dovendo il valore restituito essere generico viene restituito un puntatore a void. Il cast esplicito serve ad evitare un warning del compilatore (non so se ci siano anche compilatori che danno errore) che avvertirebbe del fatto che si sta assegnando un valore "void*" a una variabile di tipo diverso, in questo caso "struct lis*"

[The-Revenge]

Originariamente inviato da wingman87

Non funziona così: malloc alloca un'area di memoria della dimensione desiderata (quella passata come parametro) e restituisce un puntatore a quell'area di memoria. Dovendo il valore restituito essere generico viene restituito un puntatore a void. Il cast esplicito serve ad evitare un warning del compilatore (non so se ci siano anche compilatori che danno errore) che avvertirebbe del fatto che si sta assegnando un valore "void*" a una variabile di tipo diverso, in questo caso "struct lis*"

esatto, è la stessa indentica cosa che c'è scritta sul libro...

[BlackAuron]

eh si, mi sa che ieri ero particolarmente in aria:leggevo *p e nella mia testa pensavo a **p ... pazienza
Resta il fatto che a me il warning lo da solo se il cast lo metto...