Lista semplice

di

Puntatore di testa e tre nodi con informazioni A-B-C

image

Dichiarazioni

Type
  tInfo = "qualsiasi";  { le informazioni nel nodo }
  pNodo = ^Nodo;
  Nodo  = Record
    Info: tInfo;
    Succ: pNodo;        ( puntatore in avanti )
  End;
  Lista = pNodo;        { puntatore di testa }

Operazioni

Aggiungere un nodo in TESTA

Procedure AggInTesta(Var L: Lista; X: tInfo);
Var
   P: pNodo;
Begin
   New(P);
   P^.Info:=X;
   P^.Succ:=L;
   L:=P;
End;

Aggiungere un nodo in CODA

Procedure AggInCoda(Var L: Lista; X: tInfo);
Var
   P, Q, R: pNodo;
Begin
   New(P);
   P^.Info:=X;
   P^.Succ:=Nil;
   If(L = Nil) Then
      L:=P              {...aggiungi in testa...}
   Else
      Begin
         Q:=L;           {...aggiungi dopo Q^...}
         R:=L^.Succ;
         While(R <> Nil) do
            Begin
               Q:=R;
               R:=R^.Succ;
            End;
         Q^.Succ:=P;
      End;
End<;

Aggiungere un nodo in ORDINE

Procedure AggInOrdine(Var L: Lista; X: tInfo);
Var
   P, Q, R: pNodo;
Begin
   New(P);
   P^.Info:=X;
   If(L = Nil) Or (X <= L^.Info) Then
      Begin
         P^.Succ:=L;       {...aggiungi in testa...}
         L:=P;
      End
   Else
      Begin
         Q:=L;             {...aggiungi dopo Q^...}
         R:=L^.Succ;
         While(R <> Nil) And (R^.Info < X) Do
            Begin
               Q:=R;
               R:=R^.Succ;
            End;
         Q^.Succ:=P;
         P^.Succ:=R;
      End;
End;

Aggiungere un nodo DOPO un certo nodo

Procedure AggDopo(Var L: Lista; Q: pNodo; X: tInfo);
Var
   P: pNodo;
Begin
   New(P);
   P^.Info:=X;
   P^.Succ:=Q^.Succ;
   Q^.Succ:=P;
End;

Per ipotesi Q esiste.

Eliminare un nodo in TESTA

Procedure EliInTesta(Var L: Lista);
Var
    P: pNodo;
Begin
   If(L <> Nil) Then
      Begin
         P:=L;
         L:=L^.Succ;
         Dispose(P);
      End;
End;

Eliminare un nodo DOPO un certo nodo

Procedure EliDopo(Var L: Lista; Q: pNodo);
Var
   P: pNodo;
Begin
   P:=Q^.Succ;
   If(P <> Nil) Then
      Begin
         Q^.Succ:=Q^.Succ^.Succ;
         Dispose(P);
      End;
End;

Per ipotesi Q esiste mentre Q^.Succ...

Contare i nodi

Function ContaNodi(L: Lista): LongInt;
Var
   Risp: LongInt;
Begin
   Risp:=0;
   While(L <> Nil) Do
      Begin
         Inc(Risp);
         L:=L^.Succ;
      End;
   ContaNodi:=Risp;
End;

Eliminare TUTTI i nodi

Procedure Distruggi(Var L: Lista);
Var
   P: pNodo;
Begin
   While(L <> Nil) Do
      Begin
         P:=L;
         L:=L^.Succ;
         Dispose(P);
      End;
   L:=Nil;
End;

Confronta

Function Confronta(L1, L2: Lista): Boolean;
Begin
   while(L1 <> Nil) And (L2 <> Nil) And (L1^.Info = L2^.Info) Do
      Begin
         L1:=L1^.Succ;
         L2:=L2^.Succ;
      End;
   Confronta:=(L1 = Nil) And (L2 = Nil);
End;

Esercizi

  1. Visualizzare il contenuto della lista
  2. Quanti nodi con una certa informazione?
  3. Ricerca sequenziale (puntatore e/o indice...)
  4. Minimo, massimo, ..., totale, media?
  5. Copiare, appendere, concatenare
  6. Eliminare un nodo con chiave, con puntatore
  7. Scambiare le informazioni di due nodi
  8. Ordinare