/* File: listealt.c */ /* Time-stamp: "2001-05-08 19:28:03 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 *lis) /* Inizializza lis alla lista vuota. */ { *lis = NULL; } /* InitLista */ bool TestListaVuota(TipoLista lis) /* Restituisce TRUE se lis e` la lista vuota, FALSE altrimenti. */ { return (lis == NULL); } /* TestListaVuota */ void InserisciTestaLista(TipoLista *lis, TipoElemLista elem) /* Inserisce l'elemento elem in testa alla lista lis. */ { TipoLista paux; paux = malloc(sizeof(TipoNodoLista)); /* 1 */ paux->info = elem; /* 2 */ paux->next = *lis; /* 3 */ *lis = paux; /* 4 */ } /* InserisciTestaLista */ void TestaLista(TipoLista lis, TipoElemLista *elem) /* Restituisce in elem l'elemento in testa alla lista lis. */ { if (lis != NULL) *elem = lis->info; } /* TestaLista */ void RestoLista(TipoLista *lis) /* Aggiorna lis al resto di lis. La memoria occupata dal primo elemento non viene rilasciata. */ { if (*lis != NULL) *lis = (*lis)->next; } /* RestoLista */ void CancellaPrimoLista(TipoLista *lis) /* Cancella il primo elemento dalla lista lis. */ { TipoLista paux; if (*lis != NULL) { paux = *lis; /* 1 */ *lis = (*lis)->next; /* 2 */ free(paux); /* 3 */ } } /* CancellaPrimoLista */ void InserisciCodaLista(TipoLista *lis, TipoElemLista elem) /* Inserisce l'elemento elem in coda alla lista lis. Versione iterativa. */ { TipoLista ultimo; /* puntatore usato per la scansione */ TipoLista paux; /* creazione del record che contiene il nuovo elemento */ paux = malloc(sizeof(TipoNodoLista)); /* 1 */ paux->info = elem; paux->next = NULL; /* il record sara` l'ultimo della lista */ if (*lis == NULL) *lis = paux; else { ultimo = *lis; while (ultimo->next != NULL) ultimo = ultimo->next; /* concatenazione del nuovo record in coda alla lista */ ultimo->next = paux; /* 2 */ } } /* InserisciCodaLista */ void CopiaLista(TipoLista lis, TipoLista *copia) /* Restituisce una copia della lista lis. Versione che usa le operazioni elementari. */ { TipoElemLista testa; if (TestListaVuota(lis)) InitLista(copia); else { /* aggiornamento di lis al resto di lis */ TestaLista(lis, &testa); /* memorizzazione della testa */ RestoLista(&lis); CopiaLista(lis, copia); /* copia del resto */ /* inserimento della testa nella copia */ InserisciTestaLista(copia, testa); } } /* CopiaLista */ void CancellaLista(TipoLista *lis) /* Pone lis uguale alla lista vuota e rende disponibile la memoria occupata. Versione che usa le operazioni elementari. */ { if (!TestListaVuota(*lis)) { CancellaPrimoLista(lis); CancellaLista(lis); } } /* CancellaLista */ void InvertiLista(TipoLista *lis) /* Inverte la lista lis. Versione iterativa. */ { TipoLista prec = NULL; /* puntatore all'elemento che precede quello corrente */ TipoLista suc; /* puntatore all'elemento successivo a quello corrente */ while (*lis != NULL) { suc = *lis; *lis = (*lis)->next; suc->next = prec; prec = suc; } *lis = 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 *lis, TipoElemLista elem) /* Aggiorna lis 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(*lis) && !trovato) { TestaLista(*lis, &primo); if (UgualeElemento(primo, elem)) trovato = TRUE; else RestoLista(lis); } } /* TrovaElementoLista */ void CancellaElementoLista(TipoLista *lis, TipoElemLista elem) /* Cancella la prima occorrenza dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione che usa le operazioni elementari. */ { TipoElemLista testa; if (!TestListaVuota(*lis)) { TestaLista(*lis, &testa); /* memorizza la testa della lista */ CancellaPrimoLista(lis); /* cancella la testa */ if (!UgualeElemento(testa, elem)) { CancellaElementoLista(lis, elem); /* cancella elem dal resto */ InserisciTestaLista(lis, testa); /* reinserisce la testa */ } } } /* CancellaElementoLista */ void CancellaTuttiLista(TipoLista *lis, TipoElemLista elem) /* Cancella tutte le occorrenze dell'elemento elem dalla lista lis. Versione che usa altre operazioni. */ { while (EsisteInLista(*lis, elem)) CancellaElementoLista(lis, elem); } /* CancellaTuttiLista */ /* Funzioni che operano su liste ordinate (versioni iterative o che usano le operazioni elementari). */ void InserisciInListaOrdinata(TipoLista *lis, TipoElemLista elem) /* Inserisce l'elemento elem nella lista lis 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(*lis)) InserisciTestaLista(lis, elem); else { TestaLista(*lis, &testa); /* memorizzazione della testa */ if (!MinoreElemento(testa, elem)) InserisciTestaLista(lis, elem); else { /* inserimento di elem nel resto della lista */ CancellaPrimoLista(lis); InserisciInListaOrdinata(lis, elem); InserisciTestaLista(lis, 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 *lis, TipoElemLista elem) /* Aggiorna lis alla sottolista che ha elem come primo elemento. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. */ { bool trovato = FALSE; while (*lis != NULL && !trovato) if (UgualeElemento((*lis)->info, elem)) trovato = TRUE; else if (MinoreElemento((*lis)->info, elem)) *lis = NULL; else *lis = (*lis)->next; } /* TrovaElementoListaOrdinata */ void CancellaElementoListaOrdinata(TipoLista *lis, TipoElemLista elem) /* Cancella la prima occorrenza dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa senza utilizzo di nodo generatore. */ { TipoLista prec; /* puntatore usato per la scansione */ TipoLista paux; bool continua; /* usato per terminare la scansione */ if (*lis != NULL) if (UgualeElemento((*lis)->info, elem)) { /* cancella il primo elemento */ paux = *lis; *lis = (*lis)->next; free(paux); } else { /* scansione della lista e cancellazione dell'elemento */ prec = *lis; continua = TRUE; while (prec->next != NULL && continua) if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */ paux = prec->next; prec->next = paux->next; free(paux); continua = FALSE; } else if (MinoreElemento(elem, prec->next->info)) continua = FALSE; else prec = prec->next; } } /* CancellaElementoListaOrdinata */