+- Creare Videogiochi - Game Developer (https://www.making-videogames.net/giochi)
+-- Forum: Programmazione (https://www.making-videogames.net/giochi/Forum-Programmazione)
+--- Forum: Programmazione in C C++ e C# (https://www.making-videogames.net/giochi/Forum-Programmazione-in-C-C-e-C)
+--- Discussione: [Source] Gestione liste dinamiche (/thread-Source-Gestione-liste-dinamiche)
[Source] Gestione liste dinamiche - ManHunter - 16-05-2011
Salve a tutti,
avendo io studiato le liste dinamiche e la loro gestione, ho deciso di condividere con voi le funzioni base per la manipolazione di tale struttura dati...
Nel download che segue troverete il file progetto (sia per Dev-C++ che per Code::Blocks) con un programma di esempio e l'header da includere nei vostri programmi.
Contenuto:
- liste.h
Codice PHP:#ifndef LISTE_H
#define LISTE_H
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
//<----------------------STRUTTURA----------------------->
//Definizione del tipo tInfo
typedef int tInfo;
//Definizione struttura di un nodo
struct tagNode{
tInfo info;
struct tagNode* link;
};
//Definizione del tipo tNode come struttura di un nodo
typedef struct tagNode tNode;
//Definizione del tipo tList come puntatore a tNode. Esso individua l'inizio di una lista
typedef tNode* tList;
//<-----------------FUNZIONI--------------------->
//Funzioni che agiscono su nodi
tNode* nodeCreate( tInfo );/*Crea e alloca un nodo con informazione info e link che punta a NULL. Ritorna il puntatore al nuovo nodo.*/
void nodeDestroy( tNode* );/*Dealloca il nodo passato come parametro*/
//Funzioni che agiscono su una lista
tList listCreate();/*Crea una lista vuota. Ritorna il riferimento a tale lista.*/
tList listDestroy( tList ); /*Dealloca una lista cancellando ogni elemento contenuto in essa. Restituisce il riferimento alla lista.*/
void printInfo( tInfo );
void listPrint( tList );/*Stampa ogni elemento di una lista*/
bool isEmpty( tList );/*Restituisce TRUE se la lista è vuota e non presenta elementi, FALSE se esistono elementi*/
bool greater( tInfo , tInfo );/*Stabilisce quale tra info1 e info2 è maggiore. Restituisce TRUE se info1 è più grande di info2, FALSE in caso contrario*/
bool equal( tInfo , tInfo );/*Stabilisce se info1 e info2 sono uguali. Restituisce TRUE se info1 è uguale ad info2, FALSE in caso contrario*/
tList listInsert( tList, tInfo ); /*Inserisce all'interno di una lista un nodo contenente l'informazione info mantenendo l'ordinamento. Restituisce il riferimento alla lista.*/
tList listDelete( tList, tInfo ); /*Cancella un elemento dalla lista mantenendo l'ordinamento. Restituisce il riferimento alla lista.*/
tNode* listSearch( tList, tInfo ); /*Ricerca un elemento tInfo all'interno di una lista. Restituisce il riferimento all'elemento trovato*/
#endif - liste.c
Codice PHP:#include "liste.h"
/*Crea e alloca un nodo con informazione info e link che punta a NULL.
Ritorna il puntatore al nuovo nodo.*/
tNode* nodeCreate( tInfo info ){
tNode *newNode;
newNode = ( tNode* ) malloc( sizeof( tInfo ) );
if( newNode == NULL )
return NULL;
newNode->info = info;
newNode->link = NULL;
return newNode;
}
/*Dealloca il nodo passato come parametro*/
void nodeDestroy( tNode* node ){
free( node );
}
/*Crea una lista vuota.
Ritorna il riferimento a tale lista.*/
tList listCreate(){
return NULL;
}
/*Dealloca una lista cancellando ogni elemento contenuto in essa.
Restituisce il riferimento alla lista.*/
tList listDestroy( tList lista ){
tNode *current, *next;
next = NULL;
current = lista;
while( current != NULL ){
next = current->link;
nodeDestroy( current );
current = next;
}
return NULL;
}
void printInfo( tInfo info ){
printf( "\n\t%d\n", info );
}
/*Stampa ogni elemento di una lista*/
void listPrint( tList lista ){
tNode *current;
current = lista;
while( current != NULL ){
printInfo( current->info );
current = current->link;
}
}
/*Restituisce TRUE se la lista è vuota e non presenta elementi, FALSE se esistono elementi*/
bool isEmpty( tList lista ){
if( lista == NULL )
return true;
else
return false;
}
/*Stabilisce quale tra info1 e info2 è maggiore.
Restituisce TRUE se info1 è più grande di info2, FALSE in caso contrario*/
bool greater( tInfo info1, tInfo info2 ){
if( info1 > info2 )
return true;
else
return false;
}
/*Stabilisce se info1 e info2 sono uguali.
Restituisce TRUE se info1 è uguale ad info2, FALSE in caso contrario*/
bool equal( tInfo info1, tInfo info2 ){
if( info1 == info2 )
return true;
else
return false;
}
/*Inserisce all'interno di una lista un nodo contenente l'informazione info mantenendo l'ordinamento.
Restituisce il riferimento alla lista.*/
tList listInsert( tList lista, tInfo info ){
tNode *newNode, *previous, *current;
current = lista;
previous = NULL;
while( current != NULL && greater( info, current->info ) ){
previous = current;
current = current->link;
}
newNode = nodeCreate( info );
if( newNode == NULL )
return lista;
if( previous == NULL ){
newNode->link = current;
return newNode;
}
previous->link = newNode;
newNode->link = current;
return lista;
}
/*Cancella un elemento dalla lista mantenendo l'ordinamento.
Restituisce il riferimento alla lista.*/
tList listDelete( tList lista, tInfo info ){
tNode *current, *previous;
current = lista;
previous = NULL;
if( current == NULL )
return lista;
while( current != NULL && greater( info, current->info ) ){
previous = current;
current = current->link;
}
if( equal( info, current->info ) ){
previous->link = current->link;
nodeDestroy( current );
return lista;
}
}
/*Ricerca un elemento tInfo all'interno di una lista.
Restituisce il riferimento all'elemento trovato*/
tNode* listSearch( tList lista, tInfo info ){
tNode *current;
current = lista;
if( current == NULL )
return NULL;
while( current != NULL && greater( info, current->info ) )
current = current->link;
if( equal( info, current->info ) )
return current;
else
return NULL;
} - main.c Sorgente di esempio di utilizzo delle funzioni...
Codice PHP:#include "liste.h"
int main(){
tList newList;
tNode *nodo;
int sceltaOperazione;
tInfo informazione;
printf( "\tGestione di una lista dinamica\n\n" );
newList = listCreate();
do{
do{
//Menù
printf( "Scegli che operazione eseguire:\n" );
printf( "1) Inserisci elemento\n" );
printf( "2) Cancella elemento\n" );
printf( "3) Ricerca elemento\n" );
printf( "4) Stampa lista\n" );
printf( "5) Cancella lista\n" );
printf( "6) Lista vuota\n" );
printf( "7) Esci\n" );
scanf( "%d", &sceltaOperazione );
}while( sceltaOperazione < 1 || sceltaOperazione > 7 );
//Gestione della scelta
switch( sceltaOperazione ){
case 1:
printf( "\nInserisci l'informazione da inserire\t>" );
scanf( "%d", &informazione );
newList = listInsert( newList, informazione );
break;
case 2:
printf( "\nInserisci l'informazione da cancellare\t>" );
scanf( "%d", &informazione );
newList = listDelete( newList, informazione );
break;
case 3:
printf( "\nInserisci l'informazione da ricercare\t>" );
scanf( "%d", &informazione );
nodo = listSearch( newList, informazione );
if( nodo != NULL )
printf( "\nL'elemento \212 presente nella lista\n" );
else
printf( "\nL'elemento non \212 presente nella lista\n" );
break;
case 4:
listPrint( newList );
break;
case 5:
newList = listDestroy( newList );
break;
case 6:
if( isEmpty( newList ) )
printf( "\nLa lista \212 vuota.\n" );
else
printf( "\nLa lista non \212 vuota.\n" );
break;
case 7:
printf( "\nHai scelto di uscire. Arrivederci!\n\n" );
break;
}
}while( sceltaOperazione != 7 );
system( "PAUSE" );
return EXIT_SUCCESS;
}