Guida [Source] Gestione liste dinamiche

ManHunter

Utente Jade
14 Settembre 2009
985
111
780
818
Ultima modifica da un moderatore:
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
      C:
      #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
      C:
      #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...
      C:
      #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;
      }
 
  • Mi piace
Reazioni: guy92 e alu
Posto anche la versione in c++ fatta tra l'altro ieri l'altro :asd:
PHP:
#include <iostream>
using namespace std;
class nodo{
    private:
        int info; 
        nodo *pnext; 
    public: 
        nodo(){info=0; pnext=NULL;}
        nodo(int i){info=i; pnext=NULL;} 
        nodo(int i, nodo* p){info=i; pnext=p;}
        int getInfo(){return info;}
        nodo* getPnext(){return pnext;}
        void setInfo(int i){info=i;}
        void setPnext(nodo *p){pnext=p;}
        void set(int i, nodo *p){info=i; pnext=p;}
};

class lista {
private:
nodo *p0;
public:
lista(); //costruttore di default
lista(int el); //costruttore con parametri
lista(lista &l);    //costruttore copia
~lista(); //distruttore
nodo* getFront(){return p0;}
int ins_testa(int el); //inserimento in testa
int ins_coda(int el);//inserimento in coda
void scansione();//scansione
int remove(int el);//cancellazione
int empty(); //restituisce 1 se la lista è vuota
    friend ostream& operator<<(ostream &out, lista &l);
};
lista::lista() { p0=NULL; }
lista::lista(int el){ 
  p0=new nodo(el); 
  if (!p0) { cout<<endl<<"Allocazione fallita"; exit(0); }
}
lista::lista(lista &l){
nodo *pa=l.p0;
  p0=NULL;
  while(pa!=NULL)
        { ins_coda(pa->getInfo());
          pa=pa->getPnext(); 
        } 
}
lista::~lista(){ 
  nodo *pa=p0;
  while(p0!=NULL)   //l'uso di pa o p0 per avanzare nella lista è indifferente, 
                    //purchè la cancellazione avvenga sull'altro puntatore
    { p0=p0->getPnext();
      delete pa; 
      pa=p0; }
}
int lista::ins_testa(int el){
  nodo *pn=new nodo(el,p0);
  if (!pn) return 0;
  p0=pn; 
  return 1;
}
int lista::ins_coda(int el){
 nodo *pa, *pn=new nodo(el);
 if (pn==NULL) return 0; //Allocazione fallita
 if (empty()) //Se la lista è vuota, in alternativa a p0==NULL
    p0=pn;
 else{ pa=p0;
       while (pa->getPnext()!=NULL) pa=pa->getPnext();
       pa->setPnext(pn); 
     }
 return 1;
}
void lista::scansione(){
  nodo *pa=p0;
  if (!empty())
     { while (pa!=NULL)
          { cout<<pa->getInfo()<<"  ";
            pa=pa->getPnext(); } 
     }
  else cout<<"La lista e' vuota."<<endl; 
}
int lista::remove(int el){
  nodo *pa,*pc;
 if (!empty()){            //Se la lista non è vuota
  if (p0->getInfo()==el)   //se si deve cancellare il primo elemento
     { pc=p0;
       p0=p0->getPnext();
       delete pc;
       return 1;
     }
  else { pc=p0->getPnext();  //se il primo elemento non deve essere cancellato...
         pa=p0;
         if (pc!=NULL) {     //...e c'è almeno un altro elemento
    while (pc->getInfo()!=el && pc->getPnext()!=NULL){
                pa=pa->getPnext();
         pc=pc->getPnext(); 
}
    if (pc->getInfo()==el){    //se si trova l'elemento, lo si cancella
         pa->setPnext(pc->getPnext());
         delete pc; 
                 return 1;
                }
   }
       }
  }   
  return 0;//se la lista è vuota o l'elemento non è presente
}
int lista::empty(){
  if (p0==NULL) return 1;
  return 0; }
ostream& operator<<(ostream &out, lista &l){
  nodo *pa=l.p0;
  if (l.p0!=NULL)
     { while (pa!=NULL)
          { out<<pa->getInfo()<<"  ";
            pa=pa->getPnext(); } 
     }
  else out<<"La lista e' vuota."<<endl; 
  return out;
}

- - - Updated - - -

è solo una interfaccia, quindi potete utilizzare le 2 classi come base per i vostri proggettini se necessario
 
ma se volessi che le liste restassero salvate? che i dati inseriti restassero in memoria a una seconda apertura del programma?
 
Elimina quel
C:
system("PAUSE");
non si può proprio vedere, oltre a non funzionare sul mio Linux.
Soffermarsi su una sciocchezza del genere è ridicolo, se vuoi fare una critica falla su parti opinabili, non c'è niente di male in questo caso nel fare una syscall. Il file main.c è semplicemente un sorgente di esempio per mostrare come funziona la libreria, non è nemmeno utile, senza quello la libreria funziona lo stesso. Poi, sul "tuo linux" il programma funziona lo stesso, semplicemente appena arriva a quella riga ti da un messaggio del tipo:
Codice:
sh: pause: command not found
Altrimenti se ti da noia puoi molto semplicemente cancellare quella riga
 
  • Mi piace
Reazioni: driverfury e sik0
Soffermarsi su una sciocchezza del genere è ridicolo, se vuoi fare una critica falla su parti opinabili, non c'è niente di male in questo caso nel fare una syscall. Il file main.c è semplicemente un sorgente di esempio per mostrare come funziona la libreria, non è nemmeno utile, senza quello la libreria funziona lo stesso. Poi,
sul tuo linux il programma funziona lo stesso, semplicemente appena arriva a quella riga ti da un messaggio del tipo:
Codice:
sh: pause: command not found
Altrimenti se ti da noia puoi molto semplicemente cancellare quella riga
Quali parti opinabili? Pure io avrei segnalato di levarlo, è qualcosa da poco ma sempre inutile e perciò lo si (dovrebbe) rimuovere per avere un codice più pulito - nella programmazione non si dà nulla per scontato.