liste in C

[devilman83]

Ciao a tutti

ho un problema con le liste: devo confrontare un elemento passato come parametro con uno della lista, scandendo tutta la lista.

Grazie

Ciao

devilman83

[VegetaSSJ5]

devilman non mi sembra difficile anzi... cerca di fare uno sforzo per farlo da solo, almeno fai un tentativo e scrivilo qui e vediamo come va.

[mjordan]

Ciao.
Ti ho creato un programma completo che crea una lista, confronta un valore nella lista e stampa se lo ha trovato. Poi libera tutta la memoria deallocando i nodi, prima di uscire. Funziona, ma non l'ho testato granche' quindi qualche leak o qualche errorino ci potrebbe essere.
Questo e' il codice:

/* -*-linux-c-*- */
#include <stdio.h>
#include <stdlib.h>

#define NUM_NODES 10 /* Il numero di nodi nella lista. */
#define VALUE 5 /* Il valore da confrontare */

/*
 * Semplice macro per controllare la corretta allocazione di malloc()
 */
#define MALLOC_CHECK(ptr) \
        if (!(ptr)){\
                fprintf(stderr, "Errore di allocazione!\n");\
                exit(EXIT_FAILURE);\
        }

/*
 * La lista e' piena o e' vuota? 
 */
#define LIST_IS_EMPTY(ptr) (!(ptr))

/*
 * Il nodo di una lista. `next' e' il prossimo nodo. `user_data' e' il valore intero del nodo
 */
typedef struct _list_node {
              struct _list_node * next;
              int user_data;
} list_node;

/*
 * La testa della lista. Contiene un puntatore ad una lista,
 * un puntatore all'ultimo nodo della lista e un campo che contiene
 * il numero totale di nodi della lista.
 */
typedef struct _list_head {
              struct _list_node * list;
              struct _list_node * last;
              unsigned long int no_nodes;
} list;

/*
 * Costruiamo una lista inserendo i nodi. 
 */
list * 
list_insert_head(list * head, int data)
{
	list_node * tmp = NULL;
	tmp = (list_node *)malloc(sizeof(list_node));

	MALLOC_CHECK(tmp);

	if (LIST_IS_EMPTY(head)) {
		head = (list *)malloc(sizeof(list));
		tmp->next = NULL;
		tmp->user_data = data;
	        head->list = tmp;
	        head->last = tmp;
	        head->no_nodes = 1;
	}
	else {
		tmp->next = head->list;
		head->list = tmp;
		tmp->user_data = data;
		head->no_nodes++;
	}

	return head;
}

/*
 * Confrontiamo un valore con i valori contenuti nei nodi della lista. 
 */
void
list_compare(list * head, int data)
{
	list_node * tmp = NULL;

	if (LIST_IS_EMPTY(head)) {
		fprintf(stderr, "Non confrontero' i nodi di una lista vuota!\n");
		exit(EXIT_FAILURE);
	}
	else {
		tmp = head->list;

		for (unsigned long int i = 1; i <= head->no_nodes; i++) {
			if (tmp->user_data == data)
				printf("Elemento %d trovato!\n", data);
			tmp = tmp->next;
		}
	}

	return;
}

/* 
 * Distruggiamo una lista. 
 */
void
list_free(list * head)
{
       list_node * tmp = NULL;

       if (LIST_IS_EMPTY(head)) {
               fprintf(stderr, "Lista vuota. Niente da liberare!\n");
               exit(EXIT_FAILURE);
       }

       while (head->list != NULL) {
               tmp = head->list;
               head->list = tmp->next;
               free(tmp);
       }

       free(head);
       puts("Lista distrutta, memoria liberata!");

       return;
}

int
main(void)
{
       list * my_list = NULL;
 
       /* Costruiamo una lista. */
       for (int i = 0; i < NUM_NODES; i++)
               my_list = list_insert_head(my_list, i);

       list_compare(my_list, VALUE);
       list_free(my_list);

       return 0;
}

Per scorrere la lista ho usato due metodi: un ciclo for() che si incrementa in base al numero totale di nodi presenti nella lista (determinati in fase di costruzione della lista, nella funzione list_compare() ) e il classico ciclo while() che scorre la lista fino a quando non trova un puntatore NULL (nella funzione list_free() ). Sono due metodi diversi per determinare quando una lista e' terminata usati intenzionalmente per farti vedere le differenze. Il primo metodo e' piu' "professionale" nel senso che consente di effettuare diverse operazioni su liste singolarmente concatenate in tempo costante, il secondo e' piu' "accademico", cioe' usato su liste minimali.
Nota che la testa della lista contiene anche un campo puntatore che punta all'ultimo nodo della lista. Anche questo e' intenzionale. Questo ti consente di fare delle variazioni sulla lista, per esempio per inserire in coda anziche in testa, sempre in tempo costante anziche' lineare

Ti allego il file, visto che questo dannato tag code sembra non funzionare piu' come una volta. E' una maledizione Non avere esitazione nel chiedere.
Ciao.

PS: Rinomina il file 'lista.txt' in 'lista.c' e compila. Questo e' stato l'ultimo pezzo di codice della mia giornata. Vado a nanna anche io
Byez.

[devilman83]

Grazie per l'aiuto.

Vegeta, non è che non mi va di farlo, è che il C lo conosco poco e per quanto riguarda le liste quasi niente.

Ho chiesto aiuto proprio per questo.

Mi dispiace avervi fatto perdere tempo per questa sciocchezza.

Grazie ancora

devilman83

[mjordan]

Altro che sciocchezza, le strutture di dati sono piu' importanti del conoscere un linguaggio di programmazione, a momenti!!!
Nessun programma degno di questo nome puo' fare a meno di una struttura di dati, quindi dacci sotto!!! Le liste non sono difficili da capire, ma per implementarle correttamente, specie in C o C++, devi aver capito bene il concetto di puntatore, quindi rimane uno dei migliori esercizi attualmente concepibili.

Quindi e' una bella idea sviluppare una serie di programmi che implementano varie operazioni sulle liste. Nel programma che ti ho fatto io ti ho implementato l'inserimento, lo scorrimento con comparazione e la distruzione di una lista. Sarebbe inteessante anche implementare l'inserimento in coda (che da come ti ho progettato la lista e' immediato ), il concatenamento di due liste, l'inversione, lo split di una lista in un determinato punto, la fusione di due liste, ecc. ecc. Quante se ne possono fare... Tutti esercizi utilissimi, non solo a livello "accademico" ma anche pratico. Dacci dentro.