/* File: listeord.c */ /* Time-stamp: "2002-05-20 18:52:57 calvanes" */ /* Scopo: funzioni non-elementari sulle liste che necessitano di effettuare il confronto di ordinamento tra elementi */ /* Richiede le seguenti definizioni preliminari: typedef ... TipoElemLista; struct StructLista { TipoElemLista info; struct StructLista *next; }; typedef struct StructLista TipoNodoLista; typedef TipoNodoLista *TipoLista; boolean UgualeElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } boolean MinoreElemento(TipoElemLista elem1, TipoElemLista elem2) { ... } */ 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 iterativa. Utilizza nodo generatore. */ { TipoLista corr, /* usato per la scansione della lista */ aux; /* creazione del nodo generatore */ aux = malloc(sizeof(NodoLista)); aux->next = *plis; *plis = aux; /* ricerca della posizione in cui inserire il nuovo elemento */ corr = *plis; while (corr->next != NULL && MinoreElemento(corr->next->info, elem)) corr = corr->next; /* concatenazione del nuovo elemento */ aux = malloc(sizeof(NodoLista)); /* 1 */ aux->info = elem; /* 2 */ aux->next = corr->next; /* 3 */ corr->next = aux; /* 4 */ /* eliminazione del nodo generatore */ aux = *plis; *plis = aux->next; free(aux); } /* 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 */