Caricamento e stampa di una lista legata semplice

Materie:	Appunti
Categoria:	Informatica
Voto:	1 (2)
Download:	97
Data:	12.09.2001
Numero di pagine:	11
Formato di file:	.doc (Microsoft Word)

LISTA LEGATA SEMPLICE.
16/11/2000
Caricamento e stampa di una lista legata semplice.
Si dice lista legata semplice una successione di componenti ognuno dei quali contiene due tipi di informazioni diverse, inserite in due scomparti.
Esempio di lista, 4 elementi.
Info punt. Info punt. Info punt. Info punt.
p0 = puntatore
di inizio 1° elemento 2° elemento 3° elemento 4° elemento
Ogni nodo è composto minimo da 2 campi.
⇒ Questo nodo possiamo implementarlo con un vettore, se entrambi i campi
contengono elementi omogenei.
Se mi occorre però un nodo che contenga delle informazioni eterogenee, utilizzerò un record.
p0 In p0, abbiamo l’ indirizzo della casella.
FUNZIONE DI BIBLIOTECA new(p).
TYPE
Link = ^ nodo; { “^” Questo simbolo dice al computer che stiamo lavorando con dei
puntatori}
nodo = record
info : char ;
next : link ;
end;
VAR
p1, b : link; { p1 e b sono due variabili di tipo puntatore }
ch : char;
PROCEDURA PER IL CARICAMENTO DI UNA LISTA LEGATA SEMPLICE.
NIL = Parola riservata e serve per dire che la lista è terminata.
Procedure caricamento;
begin
b : = NIL;
for i : = 1 to 4 do
begin
new(p);
readln(ch);
p1^ .info : = ch;
p1^ .next := b;
b := p;
end;
end.
Supponiamo di dover inserire in memoria centrale la parola ZAGO.
Variabili
Indirizzi
b
1
p
2
i
3
ch
7
T. C. B.
Memoria Centrale
6
5
4
3
2
1
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V0: memoria vuota.

6
5
4
3
2
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V1: b: = NIL (Cambiamento di stato per modifica)
1) Ciclo for: Il valore dell’ indice i, assume il valore 1.

6
5
4
3
i = 1
2
p
1
b = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V2: i assume valore 1(cambiamento di stato per modifica)
2) Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

6
5
4
3
i = 1
2
p
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Supponiamo che la 1° locuzione libera sia la n° 4.
3) Adesso il nodo viene collocato nella locuzione n° 4 della memoria centrale.

6
5
4
3
i = 1
2
p
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V3: Collocazione del nodo nella cella n° 4 (cambiamento di stato per aggiunta)
4) Il puntatore p assume il valore 4, che è l’indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

6
5
4
3
i = 1
2
p := 4
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V4: p assume il valore 4(cambiamento di stato per modifica)
4
p4

info puntatore

5) Adesso viene eseguita l’ istruzione di lettura della ch, “readln(ch)”.
Supponiamo di inserire la prima lettera, che è la Z.
Stato V5: Lettura ch (modifica)
6) Dopo di che viene eseguita l’ istruzione p1^ .info : = ch;

6
5
4
Z
3
i = 1
2
p := 4
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
4
p4
Stato V6: p1^ .info : =ch (cambiamento di stato per aggiunta).
7) Adesso c’ è l’ istruzione di assegnazione p1^ .next := b;

6
5
4
Z NIL
3
i = 1
2
p := 4
1
b : = NIL
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
4
p4
info puntatore

p^
Stato V7: Assegnazione di b al puntatore (cambiamento di stato per modifica)
8) Il problema desso, è quello di non perdere il puntatore 4 quindi viene salvato in b, e nella locuzione di memoria non avremo più NIL, ma 4.

6
5
4
Z NIL
3
i = 1
2
p := 4
1
b : = 4
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V8: Salvataggio dell’ indirizzo 4 in b (cambiamento di stato per modifica)
9) END.
10) Ciclo for: Il valore dell’ indice i, assume il valore 2.

6
5
4
Z NIL
3
i = 2
2
p := 4
1
b : = 4
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25

Stato V9: i assume valore 2(cambiamento di stato per modifica)
11) Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

6
5
4
Z NIL
3
i = 2
2
p := 4
1
b : = 4
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Supponiamo che l’ altra locuzione libera sia la n° 8.
12) Adesso il nodo viene collocato nella locuzione n° 8 della memoria centrale.

6
5
4
Z NIL
3
i = 2
2
p := 4
1
b : = 4
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V10: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)
13) Il puntatore p assume il valore 8, che è l’indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

6
5
4
Z NIL
3
i = 2
2
p := 8
1
b : = 4
12
11
10
9
8
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V11: p assume il valore 8(cambiamento di stato per modifica)
8
p8

info puntatore

14) Adesso viene eseguita l’ istruzione di lettura della ch, “readln(ch)”.
Supponiamo di inserire la seconda lettera, che è la A.
Stato V12: lettura ch (modifica)
15) Esecuzione dell’ istruzione p1^ .info : = ch

6
5
4
Z NIL
3
i = 2
2
p := 8
1
b : = 4
12
11
10
9
8
A
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
8
p8
Stato V13: p1^ .info : = ch (cambiamento di stato per aggiunta).
16) Adesso c’ è l’ istruzione di assegnazione p1^ .next := b;

6
5
4
Z NIL
3
i = 2
2
p := 8
1
b : = 4
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
8
p8
info puntatore

p^
Stato V14: Assegnazione di b al puntatore (cambiamento di stato per modifica)
17) Il problema desso, è quello di non perdere il puntatore 8 quindi viene salvato in b, e nella locuzione di memoria non avremo più 4, ma 8.

6
5
4
Z NIL
3
i = 2
2
p := 8
1
b : = 8
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V15: Salvataggio dell’ indirizzo 8 in b (cambiamento di stato per modifica)
18) END.
19) Ciclo for: Il valore dell’ indice i, assume il valore 3.

6
5
4
Z NIL
3
i = 3
2
p := 8
1
b : = 8
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25

Stato V16: i assume valore 3(cambiamento di stato per modifica)
20) Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

6
5
4
Z NIL
3
i = 3
2
p := 8
1
b : = 8
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Supponiamo che l’ altra locuzione libera sia la la n° 10.
19) Adesso il nodo viene collocato nella locuzione n° 10 della memoria centrale.

6
5
4
Z NIL
3
i = 3
2
p := 8
1
b : = 8
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V17: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)
20) Il puntatore p assume il valore 10, che è l’indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

6
5
4
Z NIL
3
i = 3
2
p := 10
1
b : = 8
12
11
10
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V18: p assume il valore 10(cambiamento di stato per modifica)
10
p10

info puntatore

21) Adesso viene eseguita l’ istruzione di lettura della ch, “readln(ch)”.
Supponiamo di inserire la terza lettera, che è la G.
Stato V19: Readln (ch).
22) Esecuzione dell’ istruzione p1^ .info : = ch;

6
5
4
Z NIL
3
i = 3
2
p := 10
1
b : = 8
12
11
10
G
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
10
p10
Stato V20:p1^ .info : = ch (cambiamento di stato per aggiunta).
23) Adesso c’ è l’ istruzione di assegnazione p1^ .next := b;

6
5
4
Z NIL
3
i = 3
2
p := 10
1
b : = 8
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
10
p10
info puntatore

p^
Stato V21: Assegnazione di b al puntatore (cambiamento di stato per modifica)
24) Il problema desso, è quello di non perdere il puntatore 10 quindi viene salvato in b, e nella locuzione di memoria non avremo più 8, ma 10.

6
5
4
Z NIL
3
i = 3
2
p := 10
1
b : = 10
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V22: Salvataggio dell’ indirizzo 4 in b (cambiamento di stato per modifica)
25) END.
26) Ciclo for: Il valore dell’ indice i, assume il valore 4.

6
5
4
Z NIL
3
i = 4
2
p := 10
1
b : = 10
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25

Stato V23: i assume valore 4(cambiamento di stato per modifica)
27) Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

6
5
4
Z NIL
3
i = 4
2
p := 10
1
b : = 10
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Supponiamo che l’ altra locuzione libera sia la la n° 12.
28) Adesso il nodo viene collocato nella locuzione n° 12 della memoria centrale.

6
5
4
Z NIL
3
i = 4
2
p := 10
1
b : = 10
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V24: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)
29) Il puntatore p assume il valore 12, che è l’indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

6
5
4
Z NIL
3
i = 4
2
p := 12
1
b : = 10
12
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V25: p assume il valore 12(cambiamento di stato per modifica)
12
p12

info puntatore

30) Adesso viene eseguita l’ istruzione di lettura della ch, “readln(ch)”.
Supponiamo di inserire l’ultima lettera che è la O.
Stato V26: readln(ch).
31) Esecuzione dell’ istruzione p1^ .info := ch;

6
5
4
Z NIL
3
i = 4
2
p := 12
1
b : = 10
12
O
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
12
p12
Stato V27: p1^ .info : = ch (cambiamento di stato per aggiunta).
32) Adesso c’ è l’ istruzione di assegnazione p1^ .next := b;

6
5
4
Z NIL
3
i = 4
2
p := 12
1
b : = 10
12
O 10
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
12
p12
info puntatore

p^
Stato V28: Assegnazione di b al puntatore (cambiamento di stato per modifica)
33) Il problema desso, è quello di non perdere il puntatore 12 quindi viene salvato in b, e nella locuzione di memoria non avremo più 10, ma 12.

6
5
4
Z NIL
3
i = 4
2
p := 12
1
b : = 12
12
O 10
11
10
G 8
9
8
A 4
7
18
17
16
15
14
13
24
23
22
21
20
19
30
29
28
27
26
25
Stato V29: Salvataggio dell’ indirizzo 12 in b (cambiamento di stato per modifica)
32) END.
PROCEDURA DI STAMPA.
Procedure stampa;
begin
while p NIL do
begin
writeln(p^ .info);
p: = p^ .next;
end;
end;
Con questa procedura di stampa, noi otterremo la parola inserita precedentemente in memoria, stampata al contrario sullo schermo, perché attualmente p punta all’ ultima casella , quindi fa il percorso a ritroso, per questo troveremo stampato OGAZ.

1