Gestione dinamica di una lista - Altervista · Implementazione di una lista con una struttura...

Implementazione di una lista con una struttura dinamica di dati

Gestione dinamica di una lista a cura del Prof. Salvatore DE GIORGI pag. 1

Gestione dinamica di una lista

La lista lineare è una struttura astratta di dati a lunghezza variabile in cui

l'inserimento di un nuovo elemento e l'estrazione di un elemento può essere effettuata in una qualsiasi posizione : in testa, in coda, intermedia.

.

Ogni elemento della lista (nodo) è costituito da due campi : un campo (inf) contenente l’informazione (dato) e un campo (psucc) contenente il puntatore (indirizzo) dell’elemento successivo. Ogni nodo è accessibile mediante il suo puntatore (p) :

I due campi sono, convenzionalmente, indicati e distinti da : p -> inf per il campo informazione e da p -> psucc per il campo contenente il puntatore all’elemento successivo.

Una lista lineare può essere, quindi, graficamente rappresentata nel seguente

modo :

dove :

è l’ultimo nodo della lista

è un qualsiasi nodo intermedio

è il primo nodo della lista

e dove :

inf1,inf2,inf3,….infN rappresentano il campo informazione del nodo;

p1, p2,p3,… rappresentano il puntatore al nodo successivo;

null è un valore simbolico del puntatore che individua la fine della lista;

TDL è un puntatore esterno che individua il primo elemento della lista.



Operazioni con la lista

Operazione di Inserimento in testa

Data la lista :

per effettuare un inserimento in testa si devono effettuare i seguenti passi : 1) creare un nuovo nodo :

dove : pnuovo è il nuovo puntatore assegnato al nodo.

2) assegnare opportunamente i valori ai puntatori in modo che il campo puntatore del nuovo nodo prenda il valore di TDL (inizio della lista) e TDL prenda il valore (pnuovo) del puntatore del nodo da inserire.

Usando la precedente convenzione, i due passi possono essere realizzati mediante

le seguenti istruzioni :

pnuovo -> psucc = TDL TDL = pnuovo



Operazione di Inserimento in coda

Data la lista :

per effettuare un inserimento in coda si devono effettuare i seguenti passi : 1) creare un nuovo nodo :


2) assegnare opportunamente i valori ai puntatori in modo che il puntatore del nuovo nodo (pnuovo) venga assegnato alla parte puntatore dell’ultimo nodo della lista. Per fare questo occorre, partendo dal primo nodo, scorrere tutta la lista fino ad arrivare all’ultimo nodo in cui la parte puntatore è uguale a null e, quindi, effettuare l’assegnazione precedentemente indicata.

Operazione di Inserimento intermedio

Data la lista :

per effettuare un inserimento fra due nodi qualsiasi (indicati con X e Y) si devono effettuare i seguenti passi :

1) creare un nuovo nodo :




2) assegnare opportunamente i valori ai puntatori in modo che il puntatore del nodo Y (pY contenuto nella parte puntatore di X) venga assegnato alla parte puntatore del nuovo nodo ed il puntatore del nuovo nodo (pnuovo) venga assegnato alla parte puntatore del nodo X :

con i passi illustrati, il nodo nuovo è inserito fra i nodi X e Y :



Operazione di Estrazione in testa

Data la lista :

per effettuare una estrazione in testa, si deve semplicemente eliminare il primo nodo della lista. Per fare ciò, è sufficiente che il puntatore di inizio lista (TDL) assuma il valore presente nella parte puntatore del primo nodo (il puntatore al secondo nodo della lista deve diventare il puntatore iniziale) :

TDL = TDL -> psucc

TDL -> psucc è uguale a p1 e, quindi, p1 diventa TDL (il puntatore di inizio lista).

Operazione di Estrazione in coda

Data la lista :

per effettuare una estrazione in coda, si deve eliminare l’ultimo nodo della lista. Per fare ciò si deve scorrere l'intera lista ed arrivare all'ultimo nodo (la cui parte puntatore è NULL) conservando il puntatore del nodo precedente, in cui si deve inserire la costante NULL nella sua parte puntatore.

Per scorrere la lista si devono usare due puntatori di comodo : il puntatore p che

punta al nodo attuale ed il puntatore pprec che punta a quello precedente. Quando la parte puntatore di p è NULL (ultimo nodo)

si deve inserire nella parte puntatore di pprec la costante NULL. In questo modo il penultimo nodo diventa l’ultimo nodo della lista :



Operazione di Estrazione intermedia

Data la lista :

per effettuare l’estrazione di un nodo (indicato con E) inserito fra due nodi qualsiasi (indicati con X e Y) si deve assegnare la parte puntatore (pY) del nodo da estrarre alla parte puntatore del nodo precedente (pE).

In questo modo nella parte puntatore di X viene inserito il puntatore (pY) di Y che

diventa successivo ad X, eliminando dalla lista il nodo E :



Programma in C++ per la gestione dinamica di una lista

Il programma per la gestione dinamica di una lista lineare deve prevedere,

almeno, le seguenti funzioni :

creazione di un nodo; controllo lista vuota; inserimento in testa di un nodo; inserimento in coda di un nodo; inserimento ordinato di un nodo; inserimento di un nodo in una data posizione; estrazione in testa di un nodo; estrazione in coda di un nodo; estrazione di un determinato nodo; visualizzazione lista completa; ricerca di un nodo; eliminazione della lista.

da realizzare, per es., mediante il seguente menù :



Analisi dei dati

Identificatore Descrizione Tipo Input Output Lavoro

nodo

struttura dati contenente : inf tipo intero psucc puntatore a nodo

struttura

numero dato da inserire nel nodo della lista

intero si

tdl puntatore al primo elemento della lista puntatore si

pnuovo puntatore del nuovo nodo creato

puntatore si

p puntatore di comodo per scorrere la lista (è il puntatore del nodo attuale)

puntatore si

pprec puntatore del nodo precedente a quello attuale

puntatore

dati contenuti nei nodi della lista

Definizione ed inizializzazione delle variabili

struct nodo { int inf; // parte informazione del nodo (un solo dato) struct nodo *psucc; // dato di tipo puntatore alla struttura stessa // contiene l'indirizzo (puntatore) all'elemento // successivo della struttura // nodo *psucc; // dichiarazione semplificata alternativa }; nodo *tdl = NULL; // puntatore al primo elemento della lista nodo *pnuovo = NULL; // puntatore del nuovo nodo creato nodo *p = NULL; // puntatore di comodo per scorrere la lista nodo *pprec = NULL; // puntatore del nodo precedente a quello attuale // (per inserimenti ed estrazioni intermedie)



Creazione di un nodo

FunzioneCreaNodo

Return

alloca (pnuovo)

numeroI

pnuovo->inf= numero

pnuovo->psucc=NULL

void CreaNodo(void) { int numero; cout<<"\nDigita il valore da inserire nel nodo...: "; cin>>numero; pnuovo = new nodo; // dall'area heap viene prelevato un indirizzo // ed associato al nodo creato pnuovo->inf=numero; // il numero inserito è posto nella parte // informazione del nodo pnuovo->psucc=NULL; // nella parte puntatore del nodo viene // inserita la costante NULL return; }



Controllo lista vuota

FunzioneListaVuota

Return vuota

tdl = NULLV

Lista vuota

O

F

vuota = T

vuota = F

bool ListaVuota() { bool vuota = true; if (tdl == NULL) // se il punt. di inizio lista è nullo la lista è vuota { cout <<" ATTENZIONE !! Lista vuota. "<<endl; vuota = false; } return vuota; }



Operazione di scorrimento di una lista

Lo scorrimento di una lista per effettuare elaborazioni sulla parte informativa dei

nodi o per effettuare operazioni di inserimenti e/o estrazioni intermedie si può eseguire in due differenti modi :

1) Il seguente ciclo, usando un puntatore di comodo p, consente di scorrere, partendo

dal nodo iniziale (il cui puntatore è tdl), tutta la lista fino all’ultimo nodo : p = tdl; per partire dal primo nodo p diventa uguale al puntatore di inizio lista while (p!= NULL) si controlla se p è diventato NULL ovvero se è stato elaborato anche l'ultimo nodo { istruzioni; p = p->psucc; p assume il valore presente nella parte puntatore del nodo attuale, ovvero il puntatore al nodo successivo } all'uscita del ciclo il puntatore p è uguale a NULL, quindi non punta a nessun

nodo (attenzione !! non è il puntatore dell'ultimo nodo).

p = tdl

V

p = p->psucc

p ≠ NULL

istruzioni

F

2) Il seguente ciclo, usando un puntatore di comodo p, consente di scorrere, partendo dal nodo iniziale (il cui puntatore è tdl), tutta la lista fino all’ultimo nodo :

p = tdl; per partire dal primo nodo p diventa uguale al puntatore di inizio lista while (p->psucc != NULL) si controlla se la parte puntatore del nodo è NULL, ovvero se si tratta dell'ultimo nodo { istruzioni; p = p->psucc; p assume il valore presente nella parte puntatore del nodo attuale, ovvero il puntatore al nodo successivo }



all'uscita del ciclo siamo arrivati all'ultimo nodo in cui la parte puntatore è NULL e, quindi, non esiste un nodo successivo. In questo caso l'ultimo nodo deve essere ancora sottoposto all'elaborazione interessata (per esempio la visualizzazione dell'intera lista) utilizzando la sua parte informativa (p->inf).

p = tdl

V

p = p->psucc

p->psucc ≠ NULL

istruzioni

F

In genere quando si devono effettuare elaborazioni sulla parte informativa del

nodo è necessario ricorrere al ciclo 1) mentre quando si effettuano operazioni sulla lista (inserimento intermedio, eliminazione in coda o intermedio) è necessario utilizzare il ciclo 2).



Inserimento di un nodo in testa

FunzioneInserimentoT

Return

CreaNodo()

pnuovo->psucc=tdl

tdl = pnuovo

tdl ≠ NULLVF

void InserimentoT(void) { CreaNodo(); if (tdl != NULL) // se la lista non è vuota { pnuovo->psucc=tdl; // il punt. di inizio lista viene inserito nella // parte punt. del nuovo nodo } tdl = pnuovo; // il punt. del nuovo nodo diventa, comunque, il // punt. di inizio lista return; }



Inserimento di un nodo in coda

FunzioneInserimentoC

Return

CreaNodo()

tdl = pnuovo

tdl = NULLVF

F

p = tdl

p->psucc ≠ NULL

p = p->psucc

V

p->psucc=pnuovo

void InserimentoC(void) { CreaNodo(); if (tdl == NULL) // se la lista è vuota il nodo viene inserito in testa { tdl=pnuovo; // il nuovo puntatore diventa il puntatore di inizio lista } else { // se la lista è piena si scorre fino all'ultimo nodo ed il nuovo puntatore viene inserito // nella parte puntatore dell'ultimo nodo (che diventa il penultimo) p = tdl; // tdl viene assegnato al puntatore di comodo while (p->psucc != NULL) // ciclo per scorrere la lista fino all’ultimo nodo { p=p->psucc; // per scorrere la lista } // fino ad arrivare all'ultimo nodo in cui nella parte // puntatore si inserisce il puntatore del nuovo nodo p->psucc=pnuovo; } return; }



Inserimento ordinato di un nodo

L’algoritmo proposto consente di ottenere una lista i cui nodi risultano ordinati in

senso crescente rispetto alla parte informativa.

FunzioneInserimento_Ordinato

Return

CreaNodo()

tdl = pnuovo

tdl = NULLVF

F

p = tdl

p ≠ NULL ANDpnuovo->inf > p->inf

pprec= p

V

pnuovo->psucc=p

tdl->inf ≥pnuovo->inf

pnuovo->psucc = tdl

tdl = pnuovo

VF

p = p->psucc

pprec->psucc = pnuovo



void Inserimento_Ordinato(void) { CreaNodo(); if (tdl == NULL) // se la lista è vuota il nodo inserito diventa {tdl = pnuovo;} // il primo nodo else{ // se il nodo da inserire con puntatore pnuovo è minore o uguale // al primo nodo della lista, si inserisce in tdl ovvero come primo nodo if (tdl->inf >= pnuovo->inf) { pnuovo->psucc=tdl; tdl = pnuovo; } else{ // si scorre la lista fino alla fine e finché il nodo pnuovo risulta maggiore del // nodo corrente. Se si arriva alla fine della lista o si trova un nodo maggiore // di quello pnuovo, si procede all'inserimento p = tdl; while ((p!= NULL) && (pnuovo->inf > p->inf)) { pprec = p; // si salva il puntatore corrente p = p->psucc; // per scorrere la lista } pnuovo->psucc = p; //inserimento intermedio pprec->psucc = pnuovo; } } }



Inserimento intermedio di un nodo in una data posizione

FunzioneInserimento_Nodo

Return

CreaNodo()

tdl = pnuovo

tdl = NULLVF

F

p = tdl

p ≠ NULL ANDx < pos

pprec= p

V

pnuovo->psucc=p

pos = 1

pnuovo->psucc = tdl

tdl = pnuovo

VF

p = p->psucc

pprec->psucc = pnuovo

posI

x = x + 1

x = 1



Nota 1 : Inserimento intermedio di un nodo

per inserire un nodo nuovo (puntatore pnuovo) fra due nodi qualsiasi occorre gestire il puntatore del primo nodo (pprec) ed il puntatore del secondo nodo (p). L'inserimento viene ottenuto inserendo il puntatore (p) del secondo nodo nella parte puntatore del nodo nuovo (pnuovo->psucc) ed inserendo il puntatore (pnuovo) del nuovo nodo nella parte puntatore del primo nodo (pprec->psucc).

void Inserimento_Nodo(void) { int pos; // posizione richiesta int x; // per contare i nodi della lista CreaNodo(); cout<<"\nDigitare la posizione in cui inserire il nodo nella lista...: "; cin>>pos; if (tdl == NULL) // se la lista è vuota il nodo inserito diventa {tdl = pnuovo;} // il primo nodo else { if (pos==1) // per la prima posizione si effettua l'inserimento in testa { pnuovo->psucc=tdl; tdl = pnuovo; } else { x=1; p=tdl; /* si effettua un ciclo per scorrere la lista fino alla posizione richiesta e finchè la lista è piena. Se la posizione richiesta supera il numero di nodi presenti nella lista, il nodo viene inserito in coda. */ while (x < pos && p != NULL) { pprec = p; // si salva il puntatore corrente p = p->psucc; // per scorrere la lista ++x; // si contano i nodi } pnuovo->psucc = p; //inserimento intermedio : vedi Nota1 pprec->psucc = pnuovo; } } }



Estrazione di un nodo in testa

FunzioneEstrazioneT

Return

p = tdl

dealloca (p)

ListaVuota()= TVF

p->psucc = NULL

tdl = NULL

V

tdl = p->psucc

F

void EstrazioneT(void) { if (ListaVuota() == true) { p = tdl; // p puntatore di comodo // se la lista è costituita da un solo nodo si elimina l'intera lista if (p->psucc == NULL) {tdl = NULL;} else {tdl = p->psucc;} delete p; } return; }



Estrazione di un nodo in coda

FunzioneEstrazioneC

p = tdl

ListaVuota()= TVF

V

p = p->psucc

p->psucc ≠ NULL

pprec=NULL

pprec = p

Return

p=tdl

F

dealloca(p)

F V

tdl=NULLpprrec->psucc=NULL



void EstrazioneC(void) { if (ListaVuota() == true) { p = tdl; // p puntatore di comodo per scorrere la lista // è il puntatore del nodo attuale pprec = NULL; // puntatore del nodo precedente a quello // attuale puntato dal puntatore p // il ciclo serve per scorrere l'intera lista ed arrivare all'ultimo nodo // conservando il puntatore del nodo precedente, in cui si deve // inserire la costante NULL nella sua parte puntatore while (p->psucc != NULL) { pprec = p; // si salva il puntatore corrente p = p->psucc; // per scorrere la lista } delete p; // se la lista è costituita da un solo nodo si elimina l'intera lista if (p == tdl) {tdl = NULL;} else {pprec->psucc = NULL;} } return; }



Estrazione di un determinato nodo (estrazione intermedia)



Nota 2 : Estrazione intermedia di un nodo

per estrarre dalla lista un nodo posto fra due nodi qualsiasi occorre gestire il puntatore del nodo (pprec) precedente a quello da estrarre ed il puntatore del nodo da estrarre (p). L'estrazione viene ottenuta inserendo la parte puntatore del nodo da estrarre (p->psucc) nella parte puntatore del nodo precedente (pprec->psucc). In questo nodo viene così inserito il puntatore del nodo successivo a quello estratto.

void Estrazione_Nodo(void) { int cerca; bool flag; if (ListaVuota() == true) { cout<<"Digitare il nodo da eliminare dalla lista...: "; cin>>cerca; p = tdl; pprec = NULL; if (p->inf == cerca) // il nodo da eliminare è il primo { tdl = p->psucc; delete p; } else { flag = false; while (p != NULL && flag == false) { if (p->inf == cerca) { pprec->psucc = p->psucc; // vedi Nota2 delete p; flag=true; } else { pprec = p; // si salva il puntatore corrente p = p->psucc; // per scorrere la lista } } if (flag==false) { cout << "Nodo inesistente nella lista"<<endl; } } } }



Visualizzazione lista completa

FunzioneVisualizzazione

Return

p = tdl

ListaVuota()= TVF

V

p = p->psucc

Fp ≠ NULL

p -> infO

void Visualizzazione(void) { if (ListaVuota() == true) { p = tdl; // p (puntatore di comodo) parte da tdl per scorrere tutta la lista while (p != NULL) { cout <<p->inf<<endl; p = p->psucc; } } return; }



Ricerca di un nodo

FunzioneRicerca

p = tdl

ListaVuota()= TVF

V

p = p->psucc

F

p ≠ NULL and

flag= F

cercaI

flag= F

p->inf=cerca

flag= T

V

Return

trovatoO

flag = T

F

non trovato O

VF



Eliminazione della lista

Nota : il programma completo si può consultare (e scaricare) nella sezione :

Informatica quarto anno/Programmi in C++/Gestione dinamica delle strutture di dati (lista, coda, pila)/Gestione di una lista

oppure direttamente da :

http://francy59.altervista.org/pagine/informatica_4anno/programmiC++/liste/gestione_lista.cpp

void Ricerca(void) { int cerca; bool flag=false; if (ListaVuota() == true) { cout<<"\n Digita il nodo da ricercare .....: "; cin>>cerca; p = tdl; while (p != NULL && flag == false) { if (p->inf == cerca) { flag=true; } else { p = p->psucc; // per scorrere la lista } } if (flag == true) {cout << "\n Nodo trovato !!\n";} else {cout << "\n Nodo non trovato\n";} } return; }

if (ListaVuota() == true) { tdl = NULL; // per eliminare la lista è sufficiente // che il puntatore iniziale diventi NULL cout<<"\n Lista eliminata !!\n"; }

Gestione dinamica di una lista - Altervista · Implementazione di una lista con una struttura...

Documents

Transcript of Gestione dinamica di una lista - Altervista · Implementazione di una lista con una struttura...