[C] puntatori liste e via dicendo.....sono ottuso

[TorpedoBlu]

devo fare un progettino in C per l'uni, nello studio dopo le strutture sono fermo alle liste semplici...non mi persuado sulla loro implementazione....forse perchè non mi entra in testa luso dei puntatori (li ho capiti, ma forse non digeriti) please! se non capisco le liste non capirò le liste di adiacenze (che sono la base del mio progettino, visto che devo usare una matrice NxN e un array bidimensionale sarebbe poco furbo)

[Gen.Web]

Originariamente inviato da TorpedoBlu
devo fare un progettino in C per l'uni, nello studio dopo le strutture sono fermo alle liste semplici...non mi persuado sulla loro implementazione....forse perchè non mi entra in testa luso dei puntatori (li ho capiti, ma forse non digeriti) please! se non capisco le liste non capirò le liste di adiacenze (che sono la base del mio progettino, visto che devo usare una matrice NxN e un array bidimensionale sarebbe poco furbo)

allora...faccio direttamente l'esempio di una lista (gli stack e le code non sono altro che liste particolari).
Metti di avere due strutture così fatte:


struct Node {
int x;
int y;
Node *next;
};

struct List {
Node *itshead; //Nodo di testa
Node *itstail; //Nodo di coda
};


La lista è appunto una lista di "nodi", in questo caso una lista di oggetti di tipo Node. Una lista implica che ci sia un nodo di testa e uno di coda, con in mezzo altri nodi tutti connessi uno all'altro tramite il puntatore Node *next (che indica il nodo successivo a quello corrente).


int main() {

Node *K= new Node; // Creiamo un "nodo" (un oggetto) di tipo Node nella heap
Node *S=new Node; // Creiamo un secondo nodo
Node *G=new Node; // Creiamo un terzo nodo
List *Lista=new List; // Creiamo la lista che conterrà i vari nodi
Lista->itshead=K; // Mettiamo come nodo in testa alla lista K
Lista->itshead->next=S; // Il nodo successivo a head impongo che sia S
S->next=G; // Il nodo successivo a S è G
Lista->itstail=S; // S è anche l'ultimo nodo che abbiamo, quindi è la coda della lista
}


Anche se neanche una capra implementerebbe una lista in questo modo, spero sia facile da capire.
Alla fine ti ritrovi ad avere proprio una lista: tutti i nodi sono collegati tra loro, da head a tail.
Infatti ai nodi si può accedere così: Lista->itshead (sarebbe K), Lista->itshead->next(sarebbe S), Lista->itshead->next->next (sarebbe G).
Per esempio Lista->itshead->next->next->x (stessa cosa: Lista->tail->x) ci darebbe il contenuto del campo x dell'oggetto G.

Spero sia stato chiaro.

[TorpedoBlu]

allora, io non conosco il C, ma una cosa del tipo
Node x = new Node

mi sembra più una dichiarazione java che C, sei sicuro? io devo programmare rigorosamente in C con lo standard ANSI ed il compilatore gcc.

come hai implementato il codice è diverso dal mio libro di testo, lui implementa tutto usando un unica struttura "list" e non 2....:muro:

[Zeus84]

Vediamo se posso aiutarti io visto che ci ho sbattuto la testa a lungo anch'io....
Proviamo a fare una lista semplice, in cui ogni nodo contiene un intero e un puntatore naturalmente ad un altro nodo...
Dichiariamo la struttura

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

typedef struct nodo nodo;

In queste due righe credo non ci siano problemi. Ora dovresti precisarmi qual'è il tuo problema per andare avanti..potri scrivere molte righe di codice che sono però totalmente inutili....

[cionci]

Originariamente inviato da TorpedoBlu
allora, io non conosco il C, ma una cosa del tipo

Quello sopra è tutto C++ ;)

Devi mettere la porola struct davanti ogni volta che usi il nome di una struct... Per evitare questo devi usare typedef come spiegto sopra ;)

Per l'allocazione non si usa la new, ma malloc...una funzione definita in stdlib.h...

La malloc si usa così:

pippo *p;

p = (pippo *) malloc(sizeof(pippo));

p->membro per accedere ai membri della struct puntata da p...

Per liberare la memoria allocata:

free(p);

[Gen.Web]

scusate, ma sn abituato al c++. E cmq l'obbiettivo era capire le liste, no? :)

[TorpedoBlu]

Originariamente inviato da Zeus84
Vediamo se posso aiutarti io visto che ci ho sbattuto la testa a lungo anch'io....
Proviamo a fare una lista semplice, in cui ogni nodo contiene un intero e un puntatore naturalmente ad un altro nodo...
Dichiariamo la struttura

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

typedef struct nodo nodo;

In queste due righe credo non ci siano problemi. Ora dovresti precisarmi qual'è il tuo problema per andare avanti..potri scrivere molte righe di codice che sono però totalmente inutili....

dunque, qui ci sono, ma poi non so continuare, come faccio ad esempio a riempire una lista con degli elementi? e se voglio diciamo fare operazioni su tale lista? mi fate esempi?

[cionci]

Ad esempio:

Inserimento in testa (con la struttura sopra)...


nodo *inserisci_in_testa(nodo *testa, in valore)
{
nodo *tmp = (nodo *) malloc (sizeof(nodo));
tmp->valore = valore; /*equivale a (*tmp).valore = valore;*/
tmp->next = testa;
return tmp;
}

...
nodo *lista = NULL; /*lista vuota*/
....
....
lista = inserisci_in_testa(lista, 10);
lista = inserisci_in_testa(lista, 8);
lista = inserisci_in_testa(lista, 80);
....

[TorpedoBlu]

ok, in questo caso creo la lista vuota e la riempio, quali altre proprietà\operazioni? ad esempio se voglio cercare il dato + piccolo?

[TorpedoBlu]

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


int main(void){


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



struct nodo *inserisciInTesta(struct nodo *testa, int valore){
struct nodo *tmp = (nodo *) malloc (sizeof(testa));
tmp->valore = valore; /*equivale a (*tmp).valore = valore;*/
tmp->next = testa;
return tmp;
}


struct nodo *lista = NULL; /*lista vuota*/
lista = inserisciInTesta(lista, 10);
lista = inserisciInTesta(lista, 8);
lista = inserisciInTesta(lista, 80);

return 0;
}


NON FUNZIONA :(

[cionci]

Avevo sbagliato a scrivere la malloc...

Se non usi il typedef devi scrivere così:

struct nodo *tmp = (struct nodo *) malloc (sizeof(struct nodo));

[TorpedoBlu]

15 C:\Documents and Settings\Giamma\Desktop\liste.c two or more data types in declaration of `inserisciInTesta'


ho messo la riga della malloc, ma non funziona ancora

[cionci]

;)


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

struct nodo *inserisciInTesta(struct nodo *testa, int valore){
struct nodo *tmp = (struct nodo *) malloc (sizeof(struct nodo));
tmp->valore = valore; /*equivale a (*tmp).valore = valore;*/
tmp->next = testa;
return tmp;
}




int main(void){


struct nodo *lista = NULL; /*lista vuota*/
lista = inserisciInTesta(lista, 10);
lista = inserisciInTesta(lista, 8);
lista = inserisciInTesta(lista, 80);

return 0;
}

[TorpedoBlu]

13 C:\Documents and Settings\Giamma\Desktop\liste.c
: two or more data types in declaration of `inserisciInTesta'

ancora un errore

[Zeus84]

Originariamente inviato da TorpedoBlu
13 C:\Documents and Settings\Giamma\Desktop\liste.c
: two or more data types in declaration of `inserisciInTesta'

ancora un errore

non riesco a vedere l'errore....:muro:

comunque visto che state pubblicando le operazioni da fare sulla lista, questa ad esempio la stampa

void stampa_lista(struct nodo* start){
if (start!=NULL){
do
printf("%d", start->valore);
while((start=start->next)!=NULL);
}
}

[TorpedoBlu]

dunque, come mai mi da quel mex di errore? chi mi aiuta?

[Zeus84]

a volte non si sa..comunque prova a scrivere

(struct nodo *) inse....

ovvero metti tra () il tipo di ritorno della funzione

[TorpedoBlu]

provato... praticamente non prende "struct nodo" come dichiarazione della funzione....

[Zeus84]

Originariamente inviato da TorpedoBlu
provato... praticamente non prende "struct nodo" come dichiarazione della funzione....

ma funziona o no? ti continua a segnalare errori?

[cionci]

Manca il ; dopo la dichiarazione della struct...

Ora non è che possiamo dirti quali sono le possibili operazioni su una lista...perchè bene o male ci puoi fare tutto...

Sulle liste puoi operare su un singolo elemento (anche non in testa, ricercando ad esempio il valore) in maniera iterativa...oppure in maniera ricorsiva...

Ti faccio vedere come si opera in entrambi i modi...

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

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

struct nodo *inserisci_in_testa(struct nodo *testa, int valore)
{
struct nodo *tmp = (struct nodo *) malloc (sizeof(struct nodo));
tmp->valore = valore; /*equivale a (*tmp).valore = valore;*/
tmp->next = testa;
return tmp;
}

void stampa_lista(struct nodo* start)
{
if (start!=NULL)
{
do
printf("%d\n", start->valore);
while((start=start->next)!=NULL);
}
}

struct nodo *elimina_elemento(struct nodo *elem)
{
struct nodo *tmp;
if(elem) /*equivale a if(elem != NULL)*/
{
tmp = elem;
elem = elem->next;
free(tmp);
}
return elem;
}


void svuota_lista(struct nodo *testa)
{
while(testa)
testa = elimina_elemento(testa);
}

void svuota_lista2(struct nodo *elem)
{
if(elem)
svuota_lista2(elimina_elemento(elem));
}

int main(void)
{


struct nodo *lista = NULL; /*lista vuota*/
lista = inserisci_in_testa(lista, 10);
lista = inserisci_in_testa(lista, 8);
lista = inserisci_in_testa(lista, 10);
lista = inserisci_in_testa(lista, 80);
lista = inserisci_in_testa(lista, 8);
lista = inserisci_in_testa(lista, 80);
lista = inserisci_in_testa(lista, 8);
lista = inserisci_in_testa(lista, 80);
lista = inserisci_in_testa(lista, 10);
lista = inserisci_in_testa(lista, 8);
lista = inserisci_in_testa(lista, 10);
lista = inserisci_in_testa(lista, 80);

lista = elimina_elemento(lista); /*elimino l'elemento in testa: 80*/

stampa_lista(lista);

svuota_lista(lista);

return 0;
}

[TorpedoBlu]

ringrazio tutti per la pazienza, il fatto è che devo fare un progetto in C, ma a volte si hanno dei blocchi che sembrano insuperabili.
Il progetto dovrà gestire una matrice NxN di celle che a piacere del prof saranno riempite o meno e poi dovrà fare operazioni del tipo capire dove sono ammassi di celle piene, svuotare celle e via dicendo.
Mi hanno suggerito di usare una lista di adiacenze invece di un'array bidimensionale (appunto perchè la matrice non dovrà avere una dimensione precisa e fissata, ma in teoria infinita).
Ora che ho capito le liste qualcuno sa dirmi cosa sono le liste di adiacenze??

[TorpedoBlu]

:mc:

[TorpedoBlu]

dai un ultimo aiutino!

[Zeus84]

non so proprio cosa sono le liste delle adiacenze

[TorpedoBlu]

per rappresentare un piano NxN di dimensione non definita