[C] liste, non ci capisco proprio

[Guts]

sto studiando per l'esame di informatica sul C, ma le liste proprio nn riesco a capirle, proprio il concetto!
qualche anima pia potrebbe spiegarmi brevemente come si usano, passaggio per passaggio? almeno come aggiungere e togliere elementi.
grazie mille

[leadergl]

Che concetto non capisci sulle liste? Il perchè della loro esistenza?
Se hai studiato le liste significa che hai fatto anche le code (queue), bene puoi vedere le liste come delle code evolute in quanto tipicamente le code, dato anche il loro nome, sono di una lunghezza prestabilita e di conseguenza ti possono servire ad memorizzare un determinato numero di informazioni; mentre le liste sono una struttura dinamica che data la loro natura possono essere ampliate, in quanto a numero di elementi, e sono quindi teoricamente "infinite" nel senso che potrai aggiungere o eliminare elementi a piacere.

Per ottenere questo risultato le liste sono una struttura astratta formata da due elementi:
1) un elemento conterrà il dato da memorizzare
2) il secondo elemento sarà un puntatore ad una struttura dello stesso tipo.
La chiave delle liste è l'elemento puntatore che non fa altro che puntare ad una nuova zona di memoria dove verrà creata un'altra struttura di tipo lista:

struct TipoLista
{
	char elemento;
	struct TipoLista *next;
};

questo è la dichiarazione in C della tua struttura.
Nel main per utilizzare questa struttura avrai una dichiarazione di variabile di questo tipo:

int main()
{
	struct TipoLista *lista
	...
	...
}

come puoi ben vedere noi abbiamo dichiarato un puntatore ad una struttura di tipo lista quindi in realtà noi ancora dobbiamo fare nulla in quanto adesso dobbiamo allocare (riservare) memoria per il primo elemento della nostra lista (che sarà puntato dalla nostra variabile lista):

lista=(struct TipoLista *)malloc(sizeof(struct TipoLista));

ora abbiamo riservato in memoria lo uno spazio per il nostro primo elemento, ma siccome ogni elemento della nostra struttura conterrà il nostro valore da memorizzare E un puntatore all'elemento successivo dobbiamo bene inizializzare entrambi i campi:
1) il valore (nel nostro caso un CHAR) magari lo riempiamo col nostro dato
2) il puntatore lo poniamo a NULL in modo da sapere che non ci sono nuovi elementi:

	lista->elemento=...
	lista->next=NULL

così abbiamo creato il primo elemento...ma i "problemi" sorgono nel creare gli altri elementi in quanto noi oltre a creare lo spazio in memoria li dobbiamo accodare al nostro primo elemento e quindi non dobbiamo fare altro che dire a lista->next di non puntare più a NULL ma al nostro nuovo elemento seguendo la stessa procedura di prima, ricapitoliamo:

#include <stdio.h>
struct TipoLista
{
	char elemento;
	struct TipoLista *next;
};

int main()
{
   struct TipoLista *lista;

	//alloco memoria per il primo elemento
	lista=(struct TipoLista *)malloc(sizeof(struct TipoLista));

	//riempio il primo elemento
	lista->elemento='a';
	lista->next=NULL;


	//alloco memoria per il secondo elemento
	lista->next=(struct TipoLista *)malloc(sizeof(struct TipoLista));

	//riempio il secondo elemento
	lista->next->elemento='b';
	lista->next->next=NULL;

	//stampo i primi due elementi
	printf("primo: %c\n", lista->elemento);
	printf("secondo: %c\n", lista->next->elemento);
    
    system("PAUSE");
    return 0;

}

ecco in questo modo possiamo aggiungere tutti gli elementi che vogliamo, la cosa fondamentale da ricordare è che se ci teniamo alla nostra lista è meglio non perdere il puntatore al primo elemento della lista o tutto sarà stato inutile, proprio per questo motivo si usano procedure/funzioni per aggiungere ed eliminare o inizializzare la nostra lista seguendo lo schema di principio appena esposto.

Ovviamente per aggiungere un elemento lo si può fare in due modi:
1) aggiungere i nuovi elementi sempre in testa alla lista (più semplice)
2) aggiungere i nuovi elementi sempre in coda alla lista (più "complicato" in quanto per poterlo aggiungere in coda devi scorrere tutta la lista sino all'ultimo elemento in modo da poter fare l'assegnazione lista->next=...)

Per eliminare un elemento dalla lista invece bisogna:
1) liberare la cella di memoria utilizzare (es: free(lista))
2) porre a NULL il puntatore a next dell'elemento precedente a quello eliminato

    //elimino il secondo elemento dalla lista    
    free(lista->next);
    lista->next=NULL;
    if (lista->next!=NULL)
        printf("secondo: %c\n", lista->next->elemento);

spero di aver almeno in parte chiarito qualche dubbio...

[Guts]

grazie mille mi hai chiarito un bel po' di dubbi.
un'altra domanda, quando uso il malloc
a cosa serve la parte (struct tipolista *) prima di malloc? nel mio libro nn la usa usa direttamente malloc, cosa cambia? da quel che ho capito fa in modo che il puntatore che riceve il risultato di malloc sia un puntatore alla struttura, ma allora perchè nel mio libro nn lo usa?

[beppegrillo]

Originariamente inviato da Guts

grazie mille mi hai chiarito un bel po' di dubbi.
un'altra domanda, quando uso il malloc
a cosa serve la parte (struct tipolista *) prima di malloc? nel mio libro nn la usa usa direttamente malloc, cosa cambia? da quel che ho capito fa in modo che il puntatore che riceve il risultato di malloc sia un puntatore alla struttura, ma allora perchè nel mio libro nn lo usa?

E' una conversione di tipo, in alcuni casi è implicita ad esempio (int,char,ecc)

[Guts]

ok, come inserire i dati dovrei averlo capito, ma ora nn capisco come farglieli stampare, a me pare di far giusto ma nn viene.
date un'occhiata pls
grazie

 

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

struct elenco{  int elem; 
                struct elenco *prox;};

typedef struct elenco lista;

void inizializza(lista *pointer);
void inserisci(lista *pointer,int elemento);
void stampa(lista *pointer);
main()
{
int a,b,i;
lista *lista1;
inizializza(lista1);
printf("quanti elementi vuoi inserire?"    ); scanf("%d",&a);

for (i=0;i<a;i++)
{
    printf("inserire elemento     ");
    scanf("%d",&b);
    inserisci(lista1,b);
}
for (i=0;i<a;i++)
{
    stampa(lista1);
}

getch();
return 0;    
}

void inizializza(lista *pointer)
{pointer=NULL;}

void inserisci(lista *pointer,int elemento)
{
lista *punt;
punt=malloc(sizeof(lista));
punt->elem=elemento;
punt->prox=pointer;
pointer=punt;    
}

void stampa(lista *pointer)
{
lista *punt;
punt=pointer;
printf("%d\n",punt->elem);
punt=punt->prox;    
}

[The_Matrix_Coder]

La funzione di stampa da tè implementata è sostanzialmente giusta, manca l'inserimento di un ciclo while che controlli quando finisca la lista.
Per cui la funzione di stampa è la seguente :
void stampa(lista *pointer)
{
lista *punt;
punt=pointer;

while (punt!=NULL)
{
printf("%d\n",punt->elem);
punt=punt->prox;
}
}
Se hai altri problemi fammi sapere!

Consiglio: commenta il codice in quanto puoi avere delle difficoltà future per codici + complicati.

[Guts]

quindi mi crashava perchè nn mettendo il while alla fine punt andava a puntare una zona di memoria che nn poteva puntare?
grazie dell'aiuto

[Guts]

ho messo la funzione con dentro il while, ma crasha lo stesso. come la devo usare nel main? chiamarla una volta sola o usare un for cmq? in entrambi i casi crasha!

[VegetaSSJ5]

Originariamente inviato da The_Matrix_Coder

La funzione di stampa da tè implementata...

non sapevo che questo sapesse pensare e implementare....

[leadergl]

Originariamente inviato da Guts

ho messo la funzione con dentro il while, ma crasha lo stesso. come la devo usare nel main? chiamarla una volta sola o usare un for cmq? in entrambi i casi crasha!

prova in questo modo:

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

// Dichiarazione Struttura Lista
typedef struct TipoLista
{  
    int elem; 
    struct TipoLista *next;
}list;

// Prototipi delle funzioni
list *inserisci(list *pointer,int elemento);
int stampa(list *pointer, int pos);

// Main del programma
main()
{
 int a,b,i;
 list *lista;

    lista=(list *)malloc(sizeof(list));

    printf("Quanti elementi vuoi inserire?"); 
    scanf("%d",&a);
    printf("\n"); 

    for (i=0;i<a;i++)
    {
        printf("Inserire elemento %i: ",(i+1));
        scanf("%d",&b);
        lista=inserisci(lista,b);
    }

    printf("\n"); 
    for (i=0;i<a;i++)
    {
        printf("Estraggo elemento %i: %i \n", i+1, stampa(lista,i) );
    }
    
    getch();
    return 0;    
}

// Procedura inserimento in lista
list *inserisci(list *pointer,int elemento)
{
 list *punt=(list *)malloc(sizeof(list));

    punt->elem=elemento;
    punt->next=pointer;
    return punt; 
    // test sull'inserimento
    printf("Ho correttamente inserito: %i\n\n", pointer->elem);   
}

// Procedura per estrarre i numeri gli elementi da una lista
int stampa(list *pointer, int pos)
{
 list *punt;
 
    punt=pointer;
    
    while(pos>0)
    {
        punt=punt->next;
        pos--;
    }

    return punt->elem;
}

[Guts]

ok quello che mi hai postato va. mi fate capire cosa nn va bene in quello che facevo io pls. grazie

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

struct el{int elem;
          struct el *prox;};
typedef struct el lista;

void inizializza(lista *pointer);
void inserisci(lista *pointer,int a);
void stampa(lista *pointer);

main()
{
lista *lista1;
int a,i,b;
    inizializza(lista1);
    printf("numero di elementi:    "); scanf("%d",&b);
    for (i=0;i<b;i++)
    {
        printf("inserire elemento   "); scanf("%d",&a);
        inserisci(lista1,a);   
    }    
stampa(lista1);    
}


void inizializza(lista *pointer)
{pointer=NULL;}

void inserisci(lista *pointer,int a)
{
    lista *punt;
    punt=(lista*)malloc(sizeof(lista));
    punt->elem=a;
    punt->prox=pointer;
    pointer=punt;    
}

void stampa(lista *pointer)
{    
    lista *punt; //cursore
    punt=pointer;
    while(punt!=NULL){
    printf("%d", punt->elem);
    punt=punt->prox;}
}