Programmazione Mod. B - prof.
Burattini - Cap 17
1
LISTE E PUNTATORI
Una lista può essere vista come un array.
Una lista può anche essere vista come una serie di elementi gli uni
collegati agli altri attraverso un sistema di puntatori.
a
b
c
d
e
Le strutture a,b,…., possono essere di type integer, stringa, record, etc.
Programmazione Mod. B - prof.
Burattini - Cap 17
2
Una linear linked list ( o lista legata lineare) è una collezione di variabili dinamiche
formate da un campo item e un campo puntatore. Ogni puntatore punta alla
variabile successiva nell’ambito della struttura considerata.
item puntatore
puntatore
Variabile dinamica
Pt
Emma
P1
Luca
P2
Ugo
P3
?
nodo
Lista Ind. Nome
Mem
puntatore
10000100
11100100
10000110
Pt
P1
P2
Type
Programmazione Mod. B - prof.
Burattini - Cap 17
rec
rec
rec
Nome
valore
Variabile
Pt^
P1^
P2^
Emma P1
Luca P2
Ugo P3
3
Pt
Item
Emma Px
Next
?
Stringa di 20 caratteri
CONST
NullItem= ' ' ;
{controllo di eventuali errori }
TYPE
ItemType= STRING20[20]
LNodeP=^LNodeType
{puntatore a un nodo della lista}
LNodeType = RECORD
Item:ItemType;
Notare che l’identificatore
Next:LNodeP
LNodeP è definito prima del
END;
record dinamico LNodeType.
VAR
Px:LNodeP;
Questa è una eccezione rispetto
allo standard del Pascal in cui si
riferimento a un Type che 4
Programmazione Mod. Bfa
- prof.
Burattini - Cap 17precede e non che segue.
Next
Px
Emma
P1
Luca
P2
Ugo
P3
NIL
Item
Px^.Item
Emma
Px^.Next^.Item
Luca
Px^.Next^.Next^.Item
Ugo
Px^.Next^.Next ^.Next^.NextNIL
Item
CONST
NullItem= ' ' ;{controllo di eventuali errori }
TYPE
ItemType= STRING20[20]
LNodeP=^LNodeType
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
END;
Next
VAR
Programmazione Mod. B - prof.
Px:LNodeP;
Burattini - Cap 17
5
ESERCIZIO
Assegnata due liste legate L1 e L2 contenenti numeri interi, fondere le
due liste in un’unica lista in cui nella prima parte ci siano solo i numeri
dispari e nella seconda parte solo i numeri pari.
Es.
L1=[2,5,1,6,8]
L2=[12,3,10,7,9]
L3=[5,1,3,7,9,2,6,8,12,10]
Programmazione Mod. B - prof.
Burattini - Cap 17
6
LISTE GENERALIZZATE
Vediamo come è possibile aggiungere o eliminare nodi dalla lista in un qualunque suo
punto.
Programmazione Mod. B - prof.
Burattini - Cap 17
7
CONST
NullItem= ' ' ;
{controllo di eventuali errori }
TYPE
ItemType= STRING[20]
LNodeP=^LNodeType
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
END;
ListType = RECORD
First:LNodeP
END;
VAR AList:ListType;
Programmazione Mod. B - prof.
Burattini - Cap 17
8
PROCEDURE MakeList(VAR AList:ListType);
{Crea una nuova lista vuota}
PROCEDURE InsertNode(AnItem:ItemType; PrevNodeP:LNodeP; VAR AList:ListType);
{Inserisce un Node con campo AnItem nella lista Alist. Il nodo è inserito subito dopo il nodo che ha
come puntatore PrevNodeP. Se AListFirst=NIL allora il nodo sarà il primo della lista}
PROCEDURE DeleteNode(PrevNodeP:LNodeP; VAR AList:ListType);
{Cancella il Nodo che nella lista segue quello puntato da PrevNodeP . Se PrevNodeP è Alist.First,
viene cancellato il primo nodo. Se la lista è vuota o PrevNodeP=NIL allora non succede nulla }
PROCEDURE KillNode(VAR Node:LNodeP);
{Constructor :se Node non è NIL, dispose la memoria allocata per il Node e poi pone il Node a NIL. }
Alist
First
Alist.First
CONST
NullItem= ' ' ;
{controllo di eventuali errori }
ListType
TYPE
ItemType= STRING[20]
LNodeP=^LNodeType
LNodeType = RECORD
NullItem
Next
Item:ItemType;
Next:LNodeP
END;
ListType = RECORD
First:LNodeP
LNodeType
END;
Programmazione Mod.
B
prof.
9
VAR
Burattini - Cap 17
AList:ListType;
FUNCTION FirstNode(AList:ListType) :LNodeP;
{ritorna il puntatore del primo nodo della lista }
FUNCTION EmptyList(AList:ListType) :boolean;
{ritorna TRUE se la lista è vuota }
FUNCTION CercaPrevP(Px:LNodeP; AList:ListType):LNodeP;
{dato il puntatore di un nodo Px fornisce il valore del puntatore del nodo che lo precede}
FUNCTION LPos(AList:ListType; SearchItem:ItemType):LNodeP;
{Fornisce il puntatore di un preassegnato nodo SearchItem}
FUNCTION Seleziona(AList:ListType;Index:integer):ItemType;
{Fornisce il nome del nodo che si trova al posto Index}
Alist
First
Alist.First
CONST
NullItem= ' ' ;
{controllo di eventuali errori }
TYPE
ItemType= STRING[20]
ListType
LNodeP=^LNodeType
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
NullItem
Next
END;
ListType = RECORD
First:LNodeP
END;
Programmazione VAR
Mod. B - prof.
10
LNodeType
AList:ListType;
Burattini - Cap 17
PROCEDURE MakeList(VAR AList:ListType);
{Crea una nuova lista vuota mettendo nei campi di First
rispettivamente NullItem e NIL }
BEGIN
Alist.First:=NIL
END;
PROCEDURE KillNode(VAR Node:LNodeP);
BEGIN
IF Node <> NIL THEN
BEGIN
dispose(Node);
Node:=NIL
END
END;
FUNCTION FirstNode(AList:ListType) :LNodeP;
{ritorna il puntatore del primo nodo della lista }
BEGIN
FirstNode:=AList.First
END;
CONST
NullItem= ' ' ;{controllo di eventuali errori }
TYPE
ItemType= STRING[20]
LNodeP=^LNodeType
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
END;
ListType = RECORD
First:LNodeP
END;
VAR
AList:ListType;
Alist
First
Alist.First
FUNCTION EmptyList(AList:ListType) :boolean;
{ritorna TRUE se la lista è vuota }
BEGIN
EmptyList:=AList.First=NIL
Programmazione Mod. B - prof.
END;
Burattini - Cap 17
ListType
NullItem
Next
LNodeType
11
PROCEDURE InsertNode(AnItem:ItemType;VAR PrevNodeP:LNodeP;VAR AList:ListType);
{Inserisce un Node con campo AnItem nella lista Alist. Il nodo è inserito subito dopo il nodo che ha
come puntatore PrevNodeP. Se PrevNodeP=NIL allora il nodo sarà il primo della lista}
VAR
Temp:LNodeP;
Temp
BEGIN
MakeNode(AnItem,Temp);
IF PrevNodeP=NIL THEN
BEGIN
PrevNodeP:=Temp;
Temp^.Next:=AList.First;
AList.First:=Temp;
END
ELSE
BEGIN
Temp^.Next:=PrevNodeP^.Next;
PrevNodeP^.Next:=Temp;
PrevNodeP:=Temp;
END;
Item
Next
AList.First
NIL
Temp
Item
Temp
Item
NIL
Next
END;
PrevNodeP
AListFirst
Item
Item
Next
Next
Item
Programmazione Mod.Item
B - prof.
PrevNodeP
Burattini - Cap 17
PrevNodeP
Next
Next
Item
Item
Next
Next
12
Pseudo codice per cancellare un nodo
• Controllare se la lista è vuota.
• Controllare che non si cerchi di cancellare un puntatore che vale NIL.
• Cancellare il nodo indicato dal puntatore del nodo che lo precede, e far puntare
quest’ultimo sul nodo succesivo a quello da cancellare.
AListFirst
NullItem Next
Item
Next
Item
Next
Item
Next
PrevNodeP
Programmazione Mod. B - prof.
Burattini - Cap 17
13
PROCEDURE DeleteNode(PrevNodeP:LNodeP;VAR AList:ListType);
VAR
Temp:LNodeP;
BEGIN
IF PrevNodeP<>NIL THEN
Temp:=PrevNodeP^.Next { il nodo da cancellare non è il primo}
ELSE
Temp:=AList.First; { il nodo da cancellare è il primo}
IF Temp<>NIL THEN
IF PrevNodeP<>NIL THEN
PrevNodeP^.Next:=Temp^.Next
ELSE
AList.First:=Temp^.Next;
KillNode(Temp)
END;
END;
Programmazione Mod. B - prof.
Burattini - Cap 17
14
PrevNodeP
AListFirst
PrevNodeP
<>
NIL
NullItemNext
Item Next
<>
Item Next
Item Next
Temp= PrevNodeP^.Next
PrevNodeP.Next
=
Potrebbe essere un qualunque
nodo o l’ultimo nodo
Temp= Alist.First
Potrebbe essere un qualunque
nodo o il primo della lista
lista vuota
Ultimo nodo
<>
Temp
<>
NIL
PrevNodeP
<>
NIL
E’ un nodo qualunque
<>
PrevNodeP^.Next:=Temp^.Next
=
=
AList.First:=Temp^.Next
E’ il primo della lista
Programmazione Mod. B - prof.
KillNode(Temp)
Burattini - Cap
17
15
FUNCTION CercaPrevP(Px:LNodeP; VAR AList:ListType):LNodeP;
{dato il puntatore di un nodo Px fornisce il valore del puntatore del nodo che lo precede}
VAR
CandP,Temp:LNodeP;
BEGIN
IF Px=AList.First THEN
CercaPrevP:=NIL
ELSE
BEGIN
CandP:=Alist.First;
WHILE (CandP <> Px) AND (CandP<>NIL) DO
BEGIN
Temp:=CandP;
CandP:=CandP^.Next
END;
CercaPrevP:=Temp
END
END;
Programmazione Mod. B - prof.
Burattini - Cap 17
16
Introduciamo due funzioni che permettono la gestione delle liste invece che attraverso i
puntatori, attraverso la posizione dei singoli nodi nella lista.
FUNCTION Seleziona(AList:ListType;Index:integer):ItemType;
{Data una lista resituisce l'Item che si trova nella posizione Index}
BEGIN
CONST
IF Index<=0 THEN Seleziona:=NullItem
NullItem= ' ' TYPE
ELSE
ItemType= STRING[20]
Seleziona:=Ennesimo(AList.First^.Next,Index)
LNodeP=^LNodeType
END;
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
END;
ListType =
RECORD
First:LNodeP
END;
VAR
AList:ListType;
FUNCTION Ennesimo(P:LNodeP;n:integer):ItemType;
{ricorsivamente cerca l'ennesimo elemento della lista}
VAR
AnItem:ItemType;
BEGIN
IF n=1 THEN
BEGIN
ItemValue(P,AnItem);
Ennesimo:=AnItem;
END
ELSE
Ennesimo:= Ennesimo(NextNode(P),n-1)
{funzione ricorsiva}
Programmazione Mod. B - prof.
END;
Burattini - Cap 17
17
Introduciamo una funzione che permette la ricerca del puntatore di un nodo di cui è noto l’item.
FUNCTION LPos(List:ListType; SearchItem:ItemType):LNodeP;
VAR
CandNode: LNodeP;
CandItem:ItemType;
BEGIN
CandNode:=FirstNode(List); {il primo item nella lista o NIL}
ItemValue(CandNode,CandItem);
WHILE (CandItem <> NullItem) AND (CandItem <> SearchItem) DO
BEGIN
CandNode:=NextNode(CandNode);
ItemValue (CandNode,CandItem);
END;
IF CandItem=SearchItem THEN
Lpos:=CandNode
ELSE
Lpos:=NIL ;
END;
Riscrivere questa funzione in forma ricorsiva
Programmazione Mod. B - prof.
Burattini - Cap 17
18
PROGRAM TestListe;
VAR
Lista:ListType;
Nome,Nome2:ItemType;
Indice:integer;
Nodo,Nodo1, Px,PrevPx,LastNode:LNodeP;
BEGIN
writeln(' CREA LISTA');
MakeList(Lista);
writeln;
{Inserisci Dati}
Nodo1:=Lista.First;
writeln(' Dammi un nome');
readln(Nome);
WHILE Nome<> NullItem DO
BEGIN
InsertNode(Nome,Nodo1,Lista);
writeln(' Dammi un nome');
readln(Nome);
END;
writeln('Lista iniziale');
ShowList(FirstNode(Lista));
Programmazione Mod. B - prof.
Burattini - Cap 17
19
{CancellaNome}
writeln(' Quale nome vuoi cancellare ');
readln(Nome);
writeln;
Px:=Lpos(Lista,Nome);
PrevPx:=CercaPrevP(Px,Lista);
DeleteNode(PrevPx,Lista);
writeln('Lista dopo la cancellazione');
ShowList(FirstNode(Lista));
readln;
{InserisciRandom}
writeln('Inserisci un nodo dopo l''item ');
readln(Nome);
writeln('Nuovo nodo ');
readln(Nome2);
Nodo1:=LPos(Lista,Nome);
InsertNode(Nome2,Nodo1 ,Lista);
writeln('Lista dopo inserimento di un nodo');
ShowList(FirstNode(Lista));
readln;
Programmazione Mod. B - prof.
Burattini - Cap 17
20
{CancellaPos}
writeln('Cancella il nodo n. ');
readln(Indice);
Nome:=Seleziona(Lista,Indice);
Px:=Lpos(Lista,Nome);
PrevPx:=CercaPrevP(Px,Lista);
DeleteNode(PrevPx,Lista);
writeln('Lista dopo la cancellazione del nodo n. ',Indice);
ShowList(FirstNode(Lista));
readln;
END.
Programmazione Mod. B - prof.
Burattini - Cap 17
21
Programmazione Mod. B - prof.
Burattini - Cap 17
22