/* File: liste.c */ /* Time-stamp: "2002-05-20 18:33:09 calvanes" */ /* Scopo: funzioni elementari sulle liste e funzioni non elementari realizzate in modo iterativo */ /* Richiede le seguenti definizioni preliminari: typedef ... TipoElemLista; struct nodoLista { TipoElemLista info; struct nodoLista *next; }; typedef struct nodoLista NodoLista; typedef NodoLista *TipoLista; */ void InitLista(TipoLista *plis) /* Inizializza lis alla lista vuota. */ { *plis = NULL; } /* InitLista */ bool TestListaVuota(TipoLista lis) /* Restituisce TRUE se lis e` la lista vuota, FALSE altrimenti. */ { return (lis == NULL); } /* TestListaVuota */ void InserisciTestaLista(TipoLista *plis, TipoElemLista elem) /* Inserisce l'elemento elem in testa alla lista lis. */ { TipoLista aux; aux = malloc(sizeof(NodoLista)); /* 1 */ aux->info = elem; /* 2 */ aux->next = *plis; /* 3 */ *plis = aux; /* 4 */ } /* InserisciTestaLista */ void TestaLista(TipoLista lis, TipoElemLista *pelem) /* Restituisce in elem l'elemento in testa alla lista lis. */ { if (lis != NULL) *pelem = lis->info; } /* TestaLista */ void RestoLista(TipoLista *plis) /* Aggiorna lis al resto di *plis. La memoria occupata dal primo elemento non viene rilasciata. */ { if (*plis != NULL) *plis = (*plis)->next; } /* RestoLista */ void CancellaPrimoLista(TipoLista *plis) /* Cancella il primo elemento dalla lista *plis. */ { TipoLista aux; if (*plis != NULL) { aux = *plis; /* 1 */ *plis = (*plis)->next; /* 2 */ free(aux); /* 3 */ } } /* CancellaPrimoLista */ void InserisciCodaLista(TipoLista *plis, TipoElemLista elem) /* Inserisce l'elemento elem in coda alla lista *plis. Versione iterativa. */ { TipoLista ultimo; /* puntatore usato per la scansione */ TipoLista aux; /* creazione del record che contiene il nuovo elemento */ aux = malloc(sizeof(NodoLista)); /* 1 */ aux->info = elem; aux->next = NULL; /* il record sara` l'ultimo della lista */ if (*plis == NULL) *plis = aux; else { ultimo = *plis; while (ultimo->next != NULL) ultimo = ultimo->next; /* concatenazione del nuovo record in coda alla lista */ ultimo->next = aux; /* 2 */ } } /* InserisciCodaLista */ void CancellaLista(TipoLista *plis) /* Pone *plis uguale alla lista vuota e rende disponibile la memoria occupata. Versione iterativa. */ { TipoLista aux; while (*plis != NULL) { aux = *plis; *plis = (*plis)->next; free(aux); } } /* CancellaLista */ void CopiaLista(TipoLista lis, TipoLista *pcopia) /* Restituisce una copia della lista lis. Versione iterativa. Utilizza nodo generatore. */ { TipoLista prec; /* puntatore all'elemento precedente */ prec = malloc(sizeof(NodoLista)); /* creazione del nodo generatore */ /* scansione e copia della lista */ *pcopia = prec; while (lis != NULL) { /* copia dell'elemento corrente di lis */ prec->next = malloc(sizeof(NodoLista)); prec = prec->next; prec->info = lis->info; lis = lis->next; } prec->next = NULL; /* chiusura della lista */ /* eliminazione del nodo generatore */ prec = *pcopia; *pcopia = (*pcopia)->next; free(prec); } /* CopiaLista */ void InvertiLista(TipoLista *plis) /* Inverte la lista *plis. Versione iterativa. */ { TipoLista prec = NULL; /* puntatore all'elemento che precede quello corrente */ TipoLista succ; /* puntatore all'elemento successivo a quello corrente */ while (*plis != NULL) { succ = *plis; *plis = (*plis)->next; succ->next = prec; prec = succ; } *plis = prec; } /* InvertiLista */