{ File: listeord.pas } { Scopo: operazioni su liste collegate semplici: - versione iterativa delle operazioni che richiedono confronti di ordinamento tra elementi } { Richiede le seguenti definizioni preliminari: type TipoElemLista = ...; TipoLista = ^TipoRecordLista; TipoRecordLista = record info : TipoElemLista; next : TipoLista end; function UgualeElemento (elem1, elem2: TipoElemLista): boolean; begin ... end; function MinoreElemento (elem1, elem2: TipoElemLista): boolean; begin ... end; } procedure InserisciInListaOrdinata (var lis: TipoLista; elem: TipoElemLista); { 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 record generatore. } var corr, { usato per la scansione della lista } paux : TipoLista; trovato : boolean; { indica se la posizione corretta e` stata trovata } begin { creazione del record generatore } new(paux); paux^.next := lis; lis := paux; { ricerca della posizione in cui inserire il nuovo elemento } corr := lis; trovato := FALSE; while (corr^.next <> NIL) and (not trovato) do if MinoreElemento(corr^.next^.info, elem) then corr := corr^.next else { l'elemento in testa e` maggiore o uguale a elem } trovato := TRUE; { forza il termine della scansione } { concatenazione del nuovo elemento } new(paux); { 1 } { alloca un record per il nuovo elemento } paux^.info := elem; { 2 } paux^.next := corr^.next; { 3 } corr^.next := paux; { 4 } { eliminazione del record generatore } paux := lis; lis := paux^.next; dispose(paux) end; { InserisciInListaOrdinata } function EsisteInListaOrdinata (lis: TipoLista; elem: TipoElemLista): boolean; { Restituisce TRUE se l'elemento elem compare nella lista ordinata lis, FALSE altrimenti. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. } var trovato, { indica se elem e` stato trovato } continua : boolean; { indica se la scansione deve contiuare } begin trovato := FALSE; continua := TRUE; while (lis <> NIL) and continua do if UgualeElemento(lis^.info, elem) then begin trovato := TRUE; { elem e` stato trovato } continua := FALSE { la scansione puo` terminare } end else if MinoreElemento(elem, lis^.info) then continua := FALSE { la scansione puo` terminare in quanto elem non puo` piu` comparire } else lis := lis^.next; EsisteInListaOrdinata := trovato end; { EsisteInListaOrdinata } procedure TrovaElementoListaOrdinata (var lis: TipoLista; elem: TipoElemLista); { Aggiorna lis alla sottolista che ha elem come primo elemento. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. } var trovato : boolean; begin trovato := FALSE; while (lis <> NIL) and (not trovato) do if UgualeElemento(lis^.info, elem) then trovato := TRUE else if MinoreElemento(lis^.info, elem) then lis := NIL else lis := lis^.next end; { TrovaElementoListaOrdinata } procedure CancellaElementoListaOrdinata (var lis: TipoLista; elem: TipoElemLista); { Cancella la prima occorrenza dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa senza utilizzo di record generatore. } var prec, { puntatore usato per la scansione } paux : TipoLista; continua : boolean; { booleano usato per terminare la scansione } begin if lis <> NIL then if UgualeElemento(lis^.info, elem) then begin { cancellazione del primo elemento } paux := lis; lis := lis^.next; dispose(paux) end else begin { scansione della lista e cancellazione dell'elemento } prec := lis; continua := TRUE; while (prec^.next <> NIL) and continua do if UgualeElemento(prec^.next^.info, elem) then begin { cancella l'elemento } paux := prec^.next; prec^.next := paux^.next; dispose(paux); continua := FALSE end else if MinoreElemento(elem, prec^.next^.info) then continua := FALSE else prec := prec^.next end end; { CancellaElementoListaOrdinata }