/* File: listeric.c */ /* Time-stamp: "2002-05-20 18:48:24 calvanes" */ /* Scopo: funzioni non-elementari sulle liste realizzate in modo ricorsivo */ /* Richiede le seguenti definizioni preliminari: typedef ... TipoElemLista; struct nodoLista { TipoElemLista info; struct nodoLista *next; }; typedef struct nodoLista NodoLista; typedef NodoLista *TipoLista; bool UgualeElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } bool MinoreElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } */ 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 *pelem l'elemento in testa alla lista lis. */ { if (lis != NULL) *pelem = lis->info; } /* TestaLista */ void RestoLista(TipoLista *plis) /* Aggiorna lis al resto di lis. 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 ricorsiva. */ { if (*plis == NULL) { /* restituzione della lista contenente solo elem */ *plis = malloc(sizeof(NodoLista)); (*plis)->info = elem; (*plis)->next = NULL; } else InserisciCodaLista(&(*plis)->next, elem); } /* InserisciCodaLista */ void CopiaLista(TipoLista lis, TipoLista *copia) /* Restituisce una copia della lista lis. Versione ricorsiva. */ { if (lis == NULL) *copia = NULL; else { *copia = malloc(sizeof(NodoLista)); /* copia del primo elemento */ (*copia)->info = lis->info; /* copia del resto */ CopiaLista(lis->next, &(*copia)->next); } } /* CopiaLista */ void CancellaLista(TipoLista *plis) /* Pone *plis uguale alla lista vuota e rende disponibile la memoria occupata. Versione ricorsiva che usa un puntatore ausiliario. */ { TipoLista aux; if (*plis != NULL) { aux = (*plis)->next; /* memorizza il puntatore all'elemento successivo */ free(*plis); /* dealloca il primo elemento */ CancellaLista(&aux); /* cancella il resto della lista */ *plis = NULL; } } /* CancellaLista */ void InvertiLista(TipoLista *plis) /* Inverte la lista *plis. Versione ricorsiva. */ { TipoLista aux; if (*plis != NULL) { if ((*plis)->next != NULL) { aux = *plis; *plis = (*plis)->next; InvertiLista(plis); aux->next->next = aux; aux->next = NULL; } } } /* InvertiLista */ /* Funzioni che necessitano di effettuare il confronto di uguaglianza tra elementi. */ bool EsisteInLista(TipoLista lis, TipoElemLista elem) /* Restituisce TRUE se l'elemento elem compare nella lista lis, FALSE altrimenti. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione ricorsiva. */ { if (lis == NULL) return FALSE; else if (UgualeElemento(lis->info, elem)) return TRUE; else return (EsisteInLista(lis->next, elem)); } /* EsisteInLista */ void TrovaElementoLista(TipoLista *plis, TipoElemLista elem) /* Aggiorna *plis alla sottolista che ha elem come primo elemento. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione ricorsiva. */ { if (*plis != NULL) { if (!UgualeElemento((*plis)->info, elem)) { *plis = (*plis)->next; TrovaElementoLista(plis, elem); } } } /* TrovaElementoLista */ void CancellaElementoLista(TipoLista *plis, TipoElemLista elem) /* Cancella la prima occorrenza dell'elemento elem dalla lista *plis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione ricorsiva. */ { TipoLista aux; if (*plis != NULL) if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */ aux = *plis; *plis = (*plis)->next; free(aux); } else /* cancella elem dal resto */ CancellaElementoLista(&(*plis)->next, elem); } /* CancellaElementoLista */ void CancellaTuttiLista(TipoLista *plis, TipoElemLista elem) /* Cancella tutte le occorrenze dell'elemento elem dalla lista *plis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione ricorsiva. */ { TipoLista aux; if (*plis != NULL) if (UgualeElemento((*plis)->info, elem)) { /* cancellazione del primo elemento */ aux = *plis; *plis = (*plis)->next; free(aux); /* cancellazione di elem dal resto della lista */ CancellaTuttiLista(plis, elem); } else CancellaTuttiLista(&(*plis)->next, elem); } /* CancellaTuttiLista */ /* Funzioni che operano su liste ordinate (versioni ricorsive o iterative). */ void InserisciInListaOrdinata(TipoLista *plis, TipoElemLista elem) /* Inserisce l'elemento elem nella lista *plis ordinata per elementi crescenti, mantenendo l'ordinamento. Chiama MinoreElemento per verificare l'ordinamento tra elementi. Versione ricorsiva. */ { TipoLista aux; if (*plis == NULL) { aux = malloc(sizeof(NodoLista)); aux->info = elem; aux->next = NULL; *plis = aux; } else if (!MinoreElemento((*plis)->info, elem)) { /* l'elemento in testa e` maggiore o uguale a elem */ aux = malloc(sizeof(NodoLista)); aux->info = elem; aux->next = *plis; *plis = aux; } else /* l'elemento in testa e` minore di elem */ InserisciInListaOrdinata(&(*plis)->next, elem); } /* InserisciInListaOrdinata */ bool EsisteInListaOrdinata(TipoLista lis, TipoElemLista elem) /* Restituisce TRUE se l'elemento elem compare nella lista ordinata lis, FALSE altrimenti. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. */ { bool trovato = FALSE; /* indica se elem e` stato trovato */ bool continua = TRUE; /* indica se la scansione deve contiuare */ while (lis != NULL && continua) { if (UgualeElemento(lis->info, elem)) { trovato = TRUE; /* elem e` stato trovato */ continua = FALSE; /* la scansione puo` terminare */ } else if (MinoreElemento(elem, lis->info)) continua = FALSE; /* la scansione puo` terminare in quanto elem non puo` piu` comparire */ else lis = lis->next; } return trovato; } /* EsisteInListaOrdinata */ void TrovaElementoListaOrdinata(TipoLista *plis, TipoElemLista elem) /* Aggiorna *plis alla sottolista che ha elem come primo elemento. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. */ { bool trovato = FALSE; while (*plis != NULL && !trovato) if (UgualeElemento((*plis)->info, elem)) trovato = TRUE; else if (MinoreElemento((*plis)->info, elem)) *plis = NULL; else *plis = (*plis)->next; } /* TrovaElementoListaOrdinata */ void CancellaElementoListaOrdinata(TipoLista *plis, TipoElemLista elem) /* Cancella la prima occorrenza dell'elemento elem dalla lista *plis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa senza utilizzo di nodo generatore. */ { TipoLista prec; /* puntatore usato per la scansione */ TipoLista aux; bool continua; /* usato per terminare la scansione */ if (*plis != NULL) if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */ aux = *plis; *plis = (*plis)->next; free(aux); } else { /* scansione della lista e cancellazione dell'elemento */ prec = *plis; continua = TRUE; while (prec->next != NULL && continua) if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */ aux = prec->next; prec->next = aux->next; free(aux); continua = FALSE; } else if (MinoreElemento(elem, prec->next->info)) continua = FALSE; else prec = prec->next; } } /* CancellaElementoListaOrdinata */