INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.

Prima pagina Caricare document Cerca documento Contatto

Architettura Biologia Diritto Economia Educazione fisica Filosofia Generale Geografia Italiano Letteratura Marketing Medicina Scienze Chimica Fisica Geometria Informatica Matematica Ricerche Scienze della materia Scienze della terra Storia Tecnica

Non ricordi la password?  ››  Iscriviti gratis

LISTA LEGATA SEMPLICE - Caricamento e stampa di una lista legata semplice

informatica

ALTRI DOCUMENTI IL QUICKTIME VIRTUAL REALITY (QTVR) INFORMATICA - ISTRUZIONI HTML ANALISI - PROGETTAZIONE Programmazione STL TEORIA DEI FUZZY SETS LA RETE INFORMATICA Database (DB) - DATA BASE MANAGEMENT SYSTEM DATA BASE PHP e MySQL

LISTA LEGATA SEMPLICE

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.

p = 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 p , abbiamo l' indirizzo della casella.

FUNZIONE DI BIBLIOTECA new(p).

TYPE

Link = ^ nodo;

nodo = record

info : char ;

next : link ;

end;

VAR

p1, b : link;

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
p
i
ch

T. C. B.

Memoria Centrale

Stato V0: memoria vuota.

					b : = NIL

Stato V1: b: = NIL (Cambiamento di stato per modifica)

1) Ciclo for: Il valore dell' indice i, assume il valore 1.

			i = 1	p	b  = NIL

Stato V2: i assume valore 1(cambiamento di stato per modifica)

Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

			i = 1	p	b : = NIL

Supponiamo che la 1° locuzione libera sia la n° 4.

Adesso il nodo viene collocato nella locuzione n° 4 della memoria centrale.

			i = 1	p	b : = NIL

Stato V3: Collocazione del nodo nella cella n° 4 (cambiamento di stato per aggiunta)

Il puntatore p assume il valore 4, che è l'indirizzo di memoria dove e collocato il nodo. (il valore  che p assume è automatico)

			i = 1	p := 4	b : = NIL

Stato V4: p assume il valore 4(cambiamento di stato per modifica)

p

info puntatore

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;

		Z	i = 1	p := 4	b : = NIL

4

Z

  p4

Stato V6: p1^ .info : =ch (cambiamento di stato per aggiunta)

Adesso c' è l' istruzione di assegnazione p1^ .next := b;

		Z NIL	i = 1	p := 4	b : = NIL

Z   NIL

 

p4

info puntatore

p^

Stato V7: Assegnazione di b al puntatore (cambiamento di stato per modifica)

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.

		Z NIL	i = 1	p := 4	b : = 4

Stato V8: Salvataggio dell' indirizzo 4 in b (cambiamento di stato per modifica)

END.

Ciclo for: Il valore dell' indice i, assume il valore 2.

		Z NIL	i = 2	p := 4	b : = 4

Stato V9: i assume valore 2(cambiamento di stato per modifica)

Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

		Z NIL	i = 2	p := 4	b : = 4

Supponiamo che l' altra locuzione libera sia la n° 8.

Adesso il nodo viene collocato nella locuzione n° 8 della memoria centrale.

		Z NIL	i = 2	p := 4	b : = 4

Stato V10: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)

Il puntatore p assume il valore 8, che è l'indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

		Z NIL	i = 2	p := 8	b : = 4

Stato V11: p assume il valore 8(cambiamento di stato per modifica)

p

info puntatore

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)

Esecuzione dell' istruzione p1^ .info : = ch

		Z NIL	i = 2	p := 8	b : = 4
				A

8

A

  p8

Stato V13: p1^ .info : = ch (cambiamento di stato per aggiunta)

Adesso c' è l' istruzione di assegnazione p1^ .next := b;

		Z NIL	i = 2	p := 8	b : = 4
				A 4

A 4

 

p8

info puntatore

p^

Stato V14: Assegnazione di b al puntatore (cambiamento di stato per modifica)

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.

		Z NIL	i = 2	p := 8	b : = 8
				A 4

Stato V15: Salvataggio dell' indirizzo 8 in b (cambiamento di stato per modifica)

END.

Ciclo for: Il valore dell' indice i, assume il valore 3.

		Z NIL	i = 3	p := 8	b : = 8
				A 4

Stato V16: i assume valore 3(cambiamento di stato per modifica)

Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

		Z NIL	i = 3	p := 8	b : = 8
				A 4

Supponiamo che l' altra locuzione libera sia la la n° 10.

Adesso il nodo viene collocato nella locuzione n° 10 della memoria centrale.

		Z NIL	i = 3	p := 8	b : = 8
				A 4

Stato V17: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)

Il puntatore p assume il valore 10, che è l'indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

		Z NIL	i = 3	p := 10	b : = 8
				A 4

Stato V18: p assume il valore 10(cambiamento di stato per modifica)

p

info puntatore

Adesso viene eseguita l' istruzione di lettura della ch, "readln(ch)".

Supponiamo di inserire la terza lettera, che è la G.

Stato V19: Readln (ch).

Esecuzione dell' istruzione p1^ .info : = ch;

		Z NIL	i = 3	p := 10	b : = 8
		G		A 4

10

G

Stato V20:p1^ .info : = ch (cambiamento di stato per aggiunta)

Adesso c' è l' istruzione di assegnazione p1^ .next := b;

G 8

p

info puntatore

p^

Stato V21: Assegnazione di b al puntatore (cambiamento di stato per modifica)

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.

Stato V22: Salvataggio dell' indirizzo 4 in b (cambiamento di stato per modifica)

END.

Ciclo for: Il valore dell' indice i, assume il valore 4.

Stato V23: i assume valore 4(cambiamento di stato per modifica)

Esecuzione della new(p). La new(p), Fa ricercare al sistema una locuzione vuota nella memoria, per inserire il nodo.

Supponiamo che l' altra locuzione libera sia la la n° 12.

Adesso il nodo viene collocato nella locuzione n° 12 della memoria centrale.

Stato V24: Collocazione del nodo nella cella n° 8 (cambiamento di stato per aggiunta)

Il puntatore p assume il valore 12, che è l'indirizzo di memoria dove e collocato il nodo. (il valore che p assume è automatico)

Stato V25: p assume il valore 12(cambiamento di stato per modifica)

p

info puntatore

Adesso viene eseguita l' istruzione di lettura della ch, "readln(ch)".

Supponiamo di inserire l'ultima lettera che è la O.

Stato V26: readln(ch).

Esecuzione dell' istruzione p1^ .info := ch;

12

O

Stato V27: p1^ .info : = ch (cambiamento di stato per aggiunta)

Adesso c' è l' istruzione di assegnazione p1^ .next := b;

O 10

p

info puntatore

p^

Stato V28: Assegnazione di b al puntatore (cambiamento di stato per modifica)

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.

Stato V29: Salvataggio dell' indirizzo 12 in b (cambiamento di stato per modifica)

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.

Copyright InfTub.com 2024