/* File: listealt.c */ /* Time-stamp: "2002-05-20 18:48:01 calvanes" */ /* Scopo: funzioni non-elementari sulle liste realizzate attraverso l'uso delle funzioni elementari */ /* Richiede le seguenti definizioni preliminari: typedef ... TipoElemLista; struct StructLista { TipoElemLista info; struct StructLista *next; }; typedef struct StructLista TipoNodoLista; typedef TipoNodoLista *TipoLista; bool UgualeElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } bool MinoreElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } */ void InitLista(TipoLista *plis) /* Inizializza *plis 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 *plis. */ { 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 *plis 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 CopiaLista(TipoLista lis, TipoLista *pcopia) /* Restituisce una copia della lista lis. Versione che usa le operazioni elementari. */ { TipoElemLista testa; if (TestListaVuota(lis)) InitLista(pcopia); else { /* aggiornamento di lis al resto di lis */ TestaLista(lis, &testa); /* memorizzazione della testa */ RestoLista(&lis); CopiaLista(lis, pcopia); /* copia del resto */ /* inserimento della testa nella copia */ InserisciTestaLista(pcopia, testa); } } /* CopiaLista */ void CancellaLista(TipoLista *plis) /* Pone *plis uguale alla lista vuota e rende disponibile la memoria occupata. Versione che usa le operazioni elementari. */ { if (!TestListaVuota(*plis)) { CancellaPrimoLista(plis); CancellaLista(plis); } } /* CancellaLista */ 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 */ /* 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 che usa altre operazioni. */ { bool trovato = FALSE; /* indica se l'elemento e` stato trovato */ TipoElemLista primo; while (!TestListaVuota(lis) && !trovato) { TestaLista(lis, &primo); /* memorizza in primo la testa */ if (UgualeElemento(primo, elem)) trovato = TRUE; /* forza l'uscita dal ciclo */ else RestoLista(&lis); /* aggiorna lis al resto della lista */ } return trovato; } /* 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 che usa altre operazioni. */ { bool trovato = FALSE; /* indica se l'elemento e` stato trovato */ TipoElemLista primo; while (!TestListaVuota(*plis) && !trovato) { TestaLista(*plis, &primo); if (UgualeElemento(primo, elem)) trovato = TRUE; else RestoLista(plis); } } /* 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 che usa le operazioni elementari. */ { TipoElemLista testa; if (!TestListaVuota(*plis)) { TestaLista(*plis, &testa); /* memorizza la testa della lista */ CancellaPrimoLista(plis); /* cancella la testa */ if (!UgualeElemento(testa, elem)) { CancellaElementoLista(plis, elem); /* cancella elem dal resto */ InserisciTestaLista(plis, testa); /* reinserisce la testa */ } } } /* CancellaElementoLista */ void CancellaTuttiLista(TipoLista *plis, TipoElemLista elem) /* Cancella tutte le occorrenze dell'elemento elem dalla lista *plis. Versione che usa altre operazioni. */ { while (EsisteInLista(*plis, elem)) CancellaElementoLista(plis, elem); } /* CancellaTuttiLista */ /* Funzioni che operano su liste ordinate (versioni iterative o che usano le operazioni elementari). */ 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'ordinameto tra elementi. Versione che usa le operazioni elementari. */ { TipoElemLista testa; if (TestListaVuota(*plis)) InserisciTestaLista(plis, elem); else { TestaLista(*plis, &testa); /* memorizzazione della testa */ if (!MinoreElemento(testa, elem)) InserisciTestaLista(plis, elem); else { /* inserimento di elem nel resto della lista */ CancellaPrimoLista(plis); InserisciInListaOrdinata(plis, elem); InserisciTestaLista(plis, testa); } } } /* 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 */