/* File: listecon.c */ /* Time-stamp: "2002-05-20 18:21:58 calvanes" */ /* Scopo: funzioni non-elementari sulle liste che necessitano di effettuare il confronto di uguaglianza tra elementi */ /* Richiede le seguenti definizioni preliminari: typedef ... TipoElemLista; struct nodoLista { TipoElemLista info; struct nodoLista *next; }; typedef struct nodoLista NodoLista; typedef NodoLista *TipoLista; boolean UgualeElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } */ 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 iterativa. */ { bool trovato = FALSE; /* indica se l'elemento e` stato trovato */ while (lis != NULL && !trovato) if (UgualeElemento(lis->info, elem)) trovato = TRUE; /* forza l'uscita dal ciclo */ else lis = lis->next; return trovato; } /* EsisteInLista */ void TrovaElementoLista(TipoLista *plis, 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; /* indica se l'elemento e` stato trovato */ while (*plis != NULL && !trovato) if (UgualeElemento((*plis)->info, elem)) trovato = TRUE; else *plis = (*plis)->next; } /* TrovaElementoLista */ void CancellaElementoLista(TipoLista *plis, 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 all'elemento precedente */ TipoLista corr; /* puntatore all'elemento corrente */ bool trovato; /* usato per terminare la scansione */ if (*plis != NULL) if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */ prec = *plis; *plis = (*plis)->next; free(prec); } else { /* scansione della lista e cancellazione dell'elemento */ prec = *plis; corr = prec->next; /* 1 */ trovato = FALSE; while (corr != NULL && !trovato) if (UgualeElemento(corr->info, elem)) { /* cancella l'elemento */ trovato = TRUE; /* forza l'uscita dal ciclo */ prec->next = corr->next; /* 2 */ free(corr); /* 3 */ } else { /* avanzamento dei due puntatori */ prec = prec->next; corr = prec->next; /* 1 */ } } } /* CancellaElementoLista */ void CancellaElementoLista_1p_NoRG(TipoLista *plis, 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 corr; /* puntatore ausiliario */ bool trovato; /* booleano usato per terminare la scansione */ if (*plis != NULL) if (UgualeElemento((*plis)->info, elem)) { /* cancella il primo elemento */ corr = *plis; *plis = (*plis)->next; free(corr); } else { /* scansione della lista e cancellazione dell'elemento */ prec = *plis; trovato = FALSE; while (prec->next != NULL && !trovato) if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */ trovato = TRUE; /* forza l'uscita dal ciclo */ corr = prec->next; /* 1 */ prec->next = corr->next; /* 2 */ free(corr); /* 3 */ } else prec = prec->next; } } /* CancellaElementoLista */ void CancellaElementoLista_RG(TipoLista *plis, TipoElemLista elem) /* Cancella la prima occorrenza dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa con utilizzo di nodo generatore. */ { TipoLista prec; /* puntatore usato per la scansione della lista */ TipoLista corr; /* puntatore ausiliario */ bool trovato = FALSE; /* usato per terminare la scansione */ /* creazione del nodo generatore */ prec = malloc(sizeof(NodoLista)); prec->next = *plis; *plis = prec; /* scansione della lista e cancellazione dell'elemento */ while (prec->next != NULL && !trovato) if (UgualeElemento(prec->next->info, elem)) { /* cancella l'elemento */ trovato = TRUE; /* forza l'uscita dal ciclo */ corr = prec->next; prec->next = corr->next; free(corr); } else prec = prec->next; /* eliminazione del nodo generatore */ prec = *plis; *plis = prec->next; free(prec); } /* CancellaElementoLista */ void CancellaTuttiLista(TipoLista *plis, TipoElemLista elem) /* Cancella tutte le occorrenze dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. Utilizza 1 puntatore e nodo generatore. */ { TipoLista prec; /* puntatore usato per la scansione della lista */ TipoLista corr; /* puntatore ausiliario */ /* creazione del nodo generatore */ prec = malloc(sizeof(NodoLista)); /* 1 */ prec->next = *plis; /* 2 */ *plis = prec; /* 3 */ /* scansione della lista e cancellazione degli elementi */ while (prec->next != NULL) if (UgualeElemento(prec->next->info, elem)) { corr = prec->next; /* 4 */ prec->next = corr->next; /* 5 */ free(corr); /* 6 */ } else prec = prec->next; /* eliminazione del nodo generatore */ prec = *plis; *plis = prec->next; free(prec); } /* CancellaTuttiLista */