{ File: liste.pas } { Scopo: operazioni su liste collegate semplici: - operazioni elementari - versione iterativa delle operazioni non elementari che non richiedono confronti tra elementi } { Richiede le seguenti definizioni preliminari: type TipoElemLista = ...; TipoLista = ^TipoRecordLista; TipoRecordLista = record info : TipoElemLista; next : TipoLista end; } procedure InitLista (var lis: TipoLista); { Inizializza lis alla lista vuota. } begin lis := NIL end; { InitLista } function TestListaVuota (lis: TipoLista): boolean; { Restituisce TRUE se lis e` la lista vuota, FALSE altrimenti. } begin TestListaVuota := (lis = NIL) end; { TestListaVuota } procedure InserisciTestaLista (var lis: TipoLista; elem: TipoElemLista); { Inserisce l'elemento elem in testa alla lista lis. } var paux : TipoLista; begin new(paux); { 1 } paux^.info := elem; { 2 } paux^.next := lis; { 3 } lis := paux { 4 } end; { InserisciTestaLista } procedure TestaLista (lis: TipoLista; var elem: TipoElemLista); { Restituisce in elem l'elemento in testa alla lista lis. } begin if lis <> NIL then elem := lis^.info end; { TestaLista } procedure RestoLista (var lis: TipoLista); { Aggiorna lis al resto di lis. La memoria occupata dal primo elemento non viene rilasciata. } begin if lis <> NIL then lis := lis^.next end; { RestoLista } procedure CancellaPrimoLista (var lis: TipoLista); { Cancella il primo elemento dalla lista lis. } var paux : TipoLista; begin if lis <> NIL then begin paux := lis; { 1 } lis := lis^.next; { 2 } dispose(paux) { 3 } end end; { CancellaPrimoLista } procedure InserisciCodaLista (var lis: TipoLista; elem: TipoElemLista); { Inserisce l'elemento elem in coda alla lista lis. Versione iterativa. } var ultimo, { puntatore usato per la scansione } paux : TipoLista; begin { creazione del record che contiene il nuovo elemento } new(paux); { 1 } paux^.info := elem; paux^.next := NIL; { il record sara` l'ultimo della lista } if lis = NIL then lis := paux else begin ultimo := lis; while ultimo^.next <> NIL do ultimo := ultimo^.next; { concatenazione del nuovo record in coda alla lista } ultimo^.next := paux { 2 } end end; { InserisciCodaLista } procedure CancellaLista (var lis: TipoLista); { Pone lis uguale alla lista vuota e rende disponibile la memoria occupata. Versione iterativa. } var paux : TipoLista; begin while lis <> NIL do begin paux := lis; lis := lis^.next; dispose(paux) end end; { CancellaLista } procedure CopiaLista (lis: TipoLista; var copia: TipoLista); { Restituisce in copia una copia della lista lis. Versione iterativa. Utilizza record generatore. } var prec : TipoLista; { puntatore all'elemento precedente } begin { creazione del record generatore } new(prec); { scansione e copia della lista } copia := prec; while lis <> NIL do begin { copia dell'elemento corrente di lis } new(prec^.next); prec := prec^.next; prec^.info := lis^.info; lis := lis^.next end; prec^.next := NIL; { chiusura della lista } { eliminazione del record generatore } prec := copia; copia := copia^.next; dispose(prec) end; { CopiaLista } procedure InvertiLista (var lis: TipoLista); { Inverte la lista lis. Versione iterativa. } var prec, { puntatore all'elemento precedente a quello corrente } suc : TipoLista; { puntatore all'elemento successivo a quello corrente } begin prec := NIL; while lis <> NIL do begin suc := lis; lis := lis^.next; suc^.next := prec; prec := suc end; lis := prec end; { InvertiLista }