/* File: listeord.c */ /* Time-stamp: "2001-05-09 00:46:06 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 *lis, TipoElemLista elem) /* Inserisce l'elemento elem nella lista lis 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 */ paux; /* creazione del nodo generatore */ paux = malloc(sizeof(NodoLista)); paux->next = *lis; *lis = paux; /* ricerca della posizione in cui inserire il nuovo elemento */ corr = *lis; while (corr->next != NULL && MinoreElemento(corr->next->info, elem)) corr = corr->next; /* concatenazione del nuovo elemento */ paux = malloc(sizeof(NodoLista)); /* 1 */ paux->info = elem; /* 2 */ paux->next = corr->next; /* 3 */ corr->next = paux; /* 4 */ /* eliminazione del nodo generatore */ paux = *lis; *lis = paux->next; free(paux); } /* 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 */