{ File: listecon.pas } { Scopo: operazioni su liste collegate semplici: - versione iterativa delle operazioni che richiedono confronti di uguaglianza 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 EsisteInLista (lis: TipoLista; elem: TipoElemLista): boolean; { Restituisce TRUE se l'elemento elem compare nella lista lis, FALSE altrimenti. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. } var trovato : boolean; { indica se l'elemento e` stato trovato } begin trovato := FALSE; while (lis <> NIL) and (not trovato) do if UgualeElemento(lis^.info, elem) then trovato := TRUE { forza l'uscita dal ciclo } else lis := lis^.next; EsisteInLista := trovato end; { EsisteInLista } procedure TrovaElementoLista (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; { indica se l'elemento e` stato trovato } begin trovato := FALSE; while (lis <> NIL) and (not trovato) do if UgualeElemento(lis^.info, elem) then trovato := TRUE else lis := lis^.next end; { TrovaElementoLista } procedure CancellaElementoLista (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 all'elemento precedente } corr : TipoLista; { puntatore all'elemento corrente } trovato : boolean; { booleano usato per terminare la scansione } begin if lis <> NIL then if UgualeElemento(lis^.info, elem) then begin { cancellazione del primo elemento } prec := lis; lis := lis^.next; dispose(prec) end else begin { scansione della lista e cancellazione dell'elemento } prec := lis; corr := prec^.next; { 1 } trovato := FALSE; while (corr <> NIL) and (not trovato) do if UgualeElemento(corr^.info, elem) then begin { cancellazione dell'elemento } trovato := TRUE; { forza l'uscita dal ciclo } prec^.next := corr^.next; { 2 } dispose(corr) { 3 } end else begin { avanzamento dei due puntatori } prec := prec^.next; corr := prec^.next { 1 } end end end; { CancellaElementoLista } procedure CancellaTuttiLista (var lis: TipoLista; elem: TipoElemLista); { Cancella tutte le occorrenze dell'elemento elem dalla lista lis. Chiama UgualeElemento per verificare l'uguaglianza tra elementi. Versione iterativa. Utilizza 1 puntatore e record generatore. } var prec, { puntatore usato per la scansione della lista } aux : TipoLista; { puntatore ausiliario } begin { creazione del record generatore } new(prec); { 1 } prec^.next := lis; { 2 } lis := prec; { 3 } { scansione della lista e cancellazione degli elementi } while prec^.next <> NIL do if UgualeElemento(prec^.next^.info, elem) then begin aux := prec^.next; { 4 } prec^.next := aux^.next; { 5 } dispose(aux) { 6 } end else prec := prec^.next; { eliminazione del record generatore } prec := lis; lis := prec^.next; dispose(prec) end; { CancellaTuttiLista }