[C] - le liste, qualcuno ne sa qualcosa?

ci risiamo, testi fatti male, dispense peggio.. lucidi non parliamone..

non riesco a capire una beneamata mazza delle liste in C
qualcuno ne sa qualcosa? vi prego

hai già guardato qui?
Introduzione alle Liste | Guida C | Programmazione.HTML.it

html.it secondo me ha delle ottime guide, almeno io con java mi sono trovato molto molto bene, più del libro :)

si.. già letta tutta.. ma non è affatto chiara.. cioè.. in teoria è ottima ma non da spiegazioni al perchè fa determinate cose.. al "come si fa" insomma :087:
sto in crisi..

nello specifico non capisco come riempire dinamicamente una lista.. ovvero senza numero di valori di partenza.. ma fermandosi ad un determinato evento.. mi sono perso tra le allocazioni dinamiche e l'inizializzazione dei nuovi puntatori a struttura :cry:

Hai presente come è fatto a spanne un array? Se sì, immagina un array di char e immagina un array di struct. Ecco, non cambia nulla, se non che un array di char è automaticamente concatenato (data la natura della variabile) mentre un "array di struct" (ovvero la tua lista) deve essere strutturato in modo che ogni elemento dell'array (della lista) punti al successivo e al precedente. Per farlo, nell'implementazione del typedef della tua struttura, devi semplicemente definire un puntatore allo stesso tipo di struttura. Ovviamente, il tuo array è dato dal puntatore al primo elemento della lista, e tramite il puntatore "head" puoi puntare all'elemento successivo. Una volta puntato all'elemento successivo, potrai accedere all'indirizzo del terzo elemento, e così via.
Tutto qui =)
Se non ti è chiaro e vuoi del codice chiedi pure, è che sono arrugginito sul C e non vorrei scrivere boiate per nulla.

Ah dimenticavo: siccome funziona come un array, devi allocare con la funzione malloc() per poter creare un nuovo elemento. Una volta creato, assegni il valore del puntatore appena creato al puntatore alla prossima struttura presente nell'elemento che vuoi della lista. Prima di far questo, però, devi sganciare l'elemento che è gia referenziato come successivo, assegnado il valore del suo indirizzo al puntatore all'elemento successivo della nuova struttura che hai allocato con malloc.

Prova a dare un'occhiata qui: http://it.wikipedia.org/wiki/Lista_(informatica)

si fin qui c'ero.. solo una cosa.. con i vettori me la cavo bene..
alloco tranquillamente utilizzando il puntatore

quello che non riesco a fare è ad esempio una lista che si riempie man mano (non necessariamente in maniera ordinata basta un numero dietro l0altro come in un vettore) fin quando non accade un evento.. ad esempio fin quando il dato in input non è 5..

ecco.. la funzione che dovrebbe fare sta cosa non mi è affatto chiara e ogni esercizio che provo a fare mi da un BUS ERROR , un errore che inizio ad odiare.. faccio casino coi puntatori credo

Innanzitutto assicurati che appena allochi spazio per una struttura, il puntatore alla struttura successiva sia NULL. Per la funzione di cui parli, dipendi da cos'hai fatto prima che l'utente inserisce il numero da tastiera.

1. leggi numero
2. se == 5 esci
3. altrimenti alloca un puntatore temporaneo (e.g.: tmp)
4. assegna al puntatore alla struttura successiva della struttura appena allocata un NULL (tmp->next = NULL;).
5. assegna al tuo puntatore lista corrente il puntatore temporaneo appena creato (lista->next = tmp;)


PS: tutto il giochetto del NULL lo puoi evitare assegnandolo direttamente nel typedef della tua struct, in testa al programma... dovrebbe funzionare

posso approfittare della tua pazienza?
cosa c'è di sbagliato in questo programma :087:
non fa nulla di che.. chiede quanti valori vogliamo inserire.. e tramite una funzione crea e aggiunge valori alla lista e tramite una seconda li stampa.. dovrebero essere i primi rudimenti delle liste.. eppure gira ma non mi stampa nulla-.-

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

typedef struct nodo{
int dato;
struct nodo *succ;
}nodo;

void creanuovo(nodo *T);
void stampa(nodo *T);
int main(){
nodo *testa;
testa=NULL;
int n, i=0;
printf("\nNUM ELEM : ");
scanf("%d", &n);

while(i<n){
creanuovo(testa);
i++;
}

printf("\nLISTA : \n");

stampa(testa);

printf("\nEND\n");
return 0;
}

void creanuovo(nodo *T){
nodo* new;
int val;

new=(nodo *)malloc(sizeof(nodo));
new->succ=NULL;

printf("ins val : ");
scanf("%d",&val);

while(T!=NULL){
T=T->succ;
}

new->dato=val;
T=new;

return;
}

void stampa(nodo *T){
int i=0;

while(T!=NULL){
printf("%d-->", T->dato);
T=T->succ;
i++;
}

return;
}

Devi lavorare con due puntatori. Uno lo usi come indice, l'altro come prossimo elemento, in modo da lasciare intoccato il puntatore della testa. Se modifichi quello, perdi l'indirizzo in memoria del punto di partenza della tua lista! Cmq ora sto dando un'occhiata, e sembra che il problema sia proprio la funzione creanuovo().
Purtroppo sono arrugginito su queste cose, non le guardo più da tempo.. se riesco ti faccio sapere ;)

ti ringrazio, ma un puntatore di tipo struttura? o un puntatore a un intero?

Quote:

---

Originariamente inviata da Technics

ti ringrazio, ma un puntatore di tipo struttura? o un puntatore a un intero?

---

Puntatore a struttura, nel tuo caso puoi pensare a qualcosa di simile:

nodo *next;
nodo *current;


Il concetto è che una generica funzione di inserimento e di stampa di una qualsiasi lista, ha come parametro il puntatore alla testa e non deve assolutamente andarne a toccare l'indirizzo.
Purtroppo ho un esame domani e non ho tempo oggi di aiutarti, anche se ho già iniziato a toccare il source qua e là, ma se riesco te lo mando. Hai fretta?

ho l'esame il 16 e mi mancano questi argomenti qui che a detta di molti sono semplicissimi.. ma certe vole mi sento così stupido.. comunque preiser grazie mille non preoccuparti non voglio toglierti tempo allo studio.. in bocca al lupo.. posto qui eventuali risvolti :D

:P prego! Non sono cose semplici, soprattutto se è la prima volta che le vedi. Quello della lista è però un concetto fondamentale. Per capirlo devi avere bene in mente come funzionano i puntatori e cosa accade in memoria a ogni assegnamento/allocazione che fai. Per esperienza personale, è già tanto se te le spiegano in università... ne ho imparate di più alle superiori che non lì... cmq ora provo a riscrivere da zero la funzioncina, ma non ti garantisco tempi rapidi :P buono studio anche a te!

Ok, ho leggermente modificato il tuo codice. Non ci sono commenti perché non ho molto tempo, gh! Mi dispiace.. comunque spero si capisca. Se hai problemi chiedi pure ;)
Ti dico solo che ci sono vari approci alle liste, e vari modi di portarsi dietro i puntatori. Ho deciso di fare due typedef. Il primo coincide con il tuo typedef, mentre il secondo è un passo ulteriore, e serve a definire il puntatore a struttura come tipo di dato. In questo modo eviti ogni volta di scrivere "nodo *".
La modifica principale che ho apportato è il valore restituito dalla funzione creanuovo(): ritorna la testa della lista.

codice:

---

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

struct nodo{
    int dato;
    struct nodo *succ;
};


typedef struct nodo elemento;
typedef elemento *lista;



lista creanuovo(lista myList, int value);
void stampa(lista myList);

int main()
{
    lista myList = NULL;
    int n, i, value;
    printf("\nNUM ELEM : ");
    scanf("%d", &n);
   
    for(i=0; i<n; i++)
    {
        printf("Inserire valore: ");
        fflush(stdin);
        scanf("%d", &value);
        myList = creanuovo(myList, value);
    }   
    printf("\nLISTA : \n");
   
    stampa(myList);
   
    printf("\nEND\n");
    return 0;
}

lista creanuovo(lista myList, int value)
{
    lista new = NULL;
    lista current = NULL;
   
    new = (lista)malloc(sizeof(elemento));
    new->succ = NULL;
    new->dato = value;
   
    if(myList == NULL)
    {
        myList = new;
        myList->succ = NULL;
    }
    else
    {
        current = myList;
        while(current->succ != NULL)
            current = current->succ;
        current->succ = new;
    }
    return myList;
}

void stampa(lista myList)
{
    int i=0;
    lista tmp = myList;
   
    while(tmp != NULL)
    {
        printf("%d) %d-->", i,tmp->dato);
        tmp=tmp->succ;
        i++;
    }
   
    return;
}

---

ti ringrazio sto vedendo di capirci qualcosa..
ecco una cosa che il mio libro non spiega è cosa significa mettere lista tra parentesi prima di malloc :roll:

fflush(stdin) :| non l'ho mai visto.. nemmeno a lezione! :|

Quote:

---

Originariamente inviata da Technics

fflush(stdin) :| non l'ho mai visto.. nemmeno a lezione! :|

---

In due parole:

char un_carattere;
int un_intero;
un_intero = (int) un_carattere;

Ecco, (int) un_carattere è un typecast, ovvero una conversione di tipo. Chiedo al compilatore di assegnare alla varabile un_intero il valore di un_carattere "convertito" in intero.
La funzione malloc() ti restituisce un indirizzo (di tipo void, ovvero di nessun tipo in particolare) e tu lo devi tipizzare, dicendogli che è del tipo lista.

Poi, fflush() è una funzione che svuota il buffer di quello che gli passi come argomento. Ogni volta che chiami scanf, devi fare fflush(stdin), ovvero devi svuotare il buffer di tastiera, altrimenti il tuo programma non ti fila di striscio nessuno scanf e tu non riesci a dargli in input nulla tranne il primo input che gli hai dato.

Quote:

---

Originariamente inviata da §¤PREISER¤§

In due parole:

char un_carattere;
int un_intero;
un_intero = (int) un_carattere;

Ecco, (int) un_carattere è un typecast, ovvero una conversione di tipo. Chiedo al compilatore di assegnare alla varabile un_intero il valore di un_carattere "convertito" in intero.
La funzione malloc() ti restituisce un indirizzo (di tipo void, ovvero di nessun tipo in particolare) e tu lo devi tipizzare, dicendogli che è del tipo lista.

---

cerchi cattedra? vieni alla sapienza. hai spiegato perfettamente in tre righe quello che non ho capito per un anno intero :lolll:

Quote:

---

Originariamente inviata da §¤PREISER¤§

Poi, fflush() è una funzione che svuota il buffer di quello che gli passi come argomento. Ogni volta che chiami scanf, devi fare fflush(stdin), ovvero devi svuotare il buffer di tastiera, altrimenti il tuo programma non ti fila di striscio nessuno scanf e tu non riesci a dargli in input nulla tranne il primo input che gli hai dato.

---

però non l'ho mai usato ed è sempre andata liscia.. anzi.. ora l'ho escluso ponendolo come commento e gira lo stesso :roll:

Quote:

---

Originariamente inviata da Technics

cerchi cattedra? vieni alla sapienza. hai spiegato perfettamente in tre righe quello che non ho capito per un anno intero :lolll:

---

ahah :P se cerchi spiegazioni chiare a informatica, fai meglio a rassegnarti. Sono abituati a interagire col computer e con persone che ragionano come computer.. la didattica lascia spesso a desiderare. Ho passato l'esame di info1 con le conoscenze pregresse delle superiori, ma per il semplice fatto che a lezione non spiegavano NIENTE che avesse a che vedere con l'informatica. Info2 invece è stato l'opposto, un casino immane.. un robot era più umano del prof... ma ormai è acqua passata :080:

Quote:

---

però non l'ho mai usato ed è sempre andata liscia.. anzi.. ora l'ho escluso ponendolo come commento e gira lo stesso :roll:

---

Dipende, generalmente non funziona, esperienza personale, sia su linux che su win. Per sicurezza, tu mettilo, perché poi ti trovi all'esame o in lab che non riesci ad andare avanti per una simile banalità.

ma non bisognerebbe rilasciare la mem allocata? :roll:
io non lo faccio mai :roll: perchè non saprei QUANDO farlo

Quote:

---

Originariamente inviata da Technics

ma non bisognerebbe rilasciare la mem allocata? :roll:
io non lo faccio mai :roll: perchè non saprei QUANDO farlo

---

Ti riferisci al fflush(stdin)? Ogni volta che schiacci un tasto, il suo valore viene riposto in un buffer. Quando tu chiami scanf(), è come se andassi a leggere il contenuto di tale buffer, ma niente ti assicura che il buffer venga svuotato quando richiami scanf(). Se non viene svuotato (e capita spesso) scanf() legge lo stesso valore di prima, e tu sei punto a capo =) Adesso stai usando gcc su OS X o su linux? O stai usando win? Perché il funzionamento di scanf non sempre è lo stesso...

*dimenticavo, in conclusione usi fflush(stdin) prima di ogni scanf() o subito dopo, in modo da garantire che alla prossima chiamata di scanf il buffer sia vuoto. Se lo fai prima di chiamare scanf, sei sicuro al 100% che il buffer sia vuoto ;)

no ,perdonami.. mi sono piegato male mi riferivo al free()

ma non ti sto facendo studiare? :087:

sto usando OS X cmq uso quasi sempre mac per studiare.. o al max linux.. mai provato un dev C su win

su os x il problema si presenta e non si presenta, dipende.. cmq per sicurezza usa fflush ;)
Il free lo usi quando deallochi, ovvero quando non ti serve più un elemento e, per tenere tutto più ordinato e dar spazio all'efficienza, lo elimini dalla memoria (sbianchi un pezzettino di ram :P ).

preiser dopo un pomeriggio intero devo inchinarmi.. sto man mano facendo mie le liste.. e stano diventando meno ostiche di quanto credevo che fossero.. grazie, grazie grazie e grazie..
ho ancora solo una domanda per il momento..

perchè scriviamo ad esempio
lista=NULL
e non
lista->succ=NULL
?

In C, come in ogni altro linguaggio, appena dichiari una variabile, inizializzala, altrimenti vai incontro a inconvenienti. In generale i compilatori inizializzano le variabili a dei valori "standard": gli int a 0, i char a 0, i float a 0, ma i puntatori.. eheh, dipende!
Fai una prova (se vuoi) col codice che ti posto. A me, su OS X, ha dato risultati diversi a ogni chiamata di printf. Se tu avessi usato il puntatore senza assegnarli NULL, avresti fatto un grosso errore!
Regola d'oro del C: inizializza tutto subito!

PS: cosa succede se utilizzi un puntatore non inizializzato? Semplicemente, non sai cosa può accadere, nel senso che il puntatore può puntare ad una qualsiasi area di memoria che (nel 99.9999% dei casi) non contiene quel che ti serve. In sunto, il programmino crasha ;)

codice:

---

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

int main()
{
    char *pointer;
    printf("Indirizzo a cui punta il puntatore: %d", pointer);
    pointer = NULL;
    printf("\nIndirizzo a cui punta il puntatore dopo l'inizializzazione: %d", pointer);
    pointer = (char *)malloc(sizeof(char));
    printf("\nIndirizzo a cui punta il puntatore dopo il malloc(): %d", pointer);
    return 0;
}

---

si si, questo lo sapevo.. infatti in genere punta ad un indirizzo che nemmeno può aprire e crasha.. la mia domanda era..

lista è un puntatore
lista->succ è un puntatore

perchè inizializziamo lista così
lista=NULL
e non inizializziamo lista->succ così
lista->succ=NULL
?

il secondo caso genera un errore

Quote:

---

Originariamente inviata da Technics

si si, questo lo sapevo.. infatti in genere punta ad un indirizzo che nemmeno può aprire e crasha.. la mia domanda era..

lista è un puntatore
lista->succ è un puntatore

perchè inizializziamo lista così
lista=NULL
e non inizializziamo lista->succ così
lista->succ=NULL
?

il secondo caso genera un errore

---

Uhm, sono un po' fuso, forse non ho capito bene io o forse non l'ho spiegato prima. Appena creai un puntatore, qualunque esso sia, o lo inizializzi con un valore o lo setti subito a NULL. Io per abitudine, scrivo così:
char *puntatore = NULL;
puntatore = (char *) malloc(12345 * sizeof(char));

o così:
char *puntatore = (char *)malloc(12345 * sizeof(char));

sono entrambi equivalenti, ma l'importante è che non lo lasci in sospeso. Facciamo lista->succ = NULL così tappiamo subito il puntatore al prossimo elemento, perché in quel punto del codice non è detto che sai già se esisterà o meno un prossimo elemento.
Poi dimmi se non ho capito a cosa ti riferisci, sorry ;)

Ah aspetta, forse ho capito. Ti riferisci proprio alle prima righe del codice?

lista myList = NULL;

e mi chiedi come mai non facciamo
myList->succ = NULL;

? Se sì, non lo possiamo proprio fare, perché myList non punta da nessuna parte, e non avendo allocato spazio per una nuova struttura (e non avendo neanche l'indirizzo di memoria in cui è allocata questa struttura) non possiamo puntare a succ.

aaaaaaah ok ok ci sono .. :lolll: