Liste: alcune operazione non le capisco

[Bandit]

Ciao ragazzi
mi aiutate per favore con le operazioni sulle liste alcune non le capisco
Anzitutto vi posto l'intestazione


// LISTADI1.H : Implementazione dinamica della struttura astratta lista
// realizzata con libreria di funzioni. File di SPECIFICA

#ifndef _LISTA_H_ // Compilazione condizionale
#define _LISTA_H_


typedef int E; // Def. del tipo di el. della lista
struct Record; // Predichiarazione
typedef Record* L; // Def. del tipo puntatore a Record
struct Record { // Tipo record costituito da
E elem; // campo informazione
L punt; // campo puntatore al prossimo nodo della lista
};

void start(L& l); // Inizializza la lista
bool empty(const L& l); // Test di lista vuota
bool full(const L& l); // Test di lista piena
void insert(L& l, const E & e); // Inserimento in coda
bool erase(L& l, const E & e); // Cancellazione di un elemento specificato
bool inlist(const L& l, const E & e); // Vera se e e' presente nella lista
void print(const L &l); // Stampa la lista
void clear(L & l); // Distrugge la lista

#endif



Da qui capiamo che la struttura record ha 2 campi
-il contenuto (elem )
-puntatore (punt)

ed l di tipo L che è puntatore alla testa della lista


Poi vi metto l'implementazione


// LISTA.CPP : Implementazione dinamica della struttura lista con
// libreria di funzioni. File di IMPLEMENTAZIONE

#include "lista1.h"
#include <iostream>
using namespace std;

//------------------------------------------------------------
void start(L& l) {
l=0;
}
//------------------------------------------------------------
bool empty(const L& l) {
return (l==0);
}
//------------------------------------------------------------
bool full(const L& l) {
return false;
}
//------------------------------------------------------------
void push(L& l,const E & e) {
L q=new Record; //alloca spazio
q->elem=e; //vi pone e
q->punt=l; //lega al resto della lista
l=q; //lo mette in testa alla lista
}
//------------------------------------------------------------
// insert versione iterativa
void insert(L& l,const E & e) {
if(l==0 || l->elem>e) push(l,e); //l'elemento va inserito in testa
else { //l'elemento va inserito al centro o in coda
L prec=l, succ;
//alloca ed inizializza il nuovo elemento
L q=new Record;
q->elem=e;
q->punt=0;
while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
// collega il nuovo elemento al resto della lista (anche in coda se è il caso)
q->punt=succ;
prec->punt=q;
}
//------------------------------------------------------------
void pop(L& l,E& e) { //oppure: bool pop(L& l,E& e)
e=l->elem; // copia in e il primo elemento
L p=l; // salva il valore di l
l=l->punt; //aggiorna l
delete p; // dealloca il primo elemento
}
//------------------------------------------------------------
// lastpop versione iterativa
void lastpop(L& l,E& e) { //oppure: bool lastpop(L& l,E& e)

if(l->punt==0) pop(l,e);
else {
L temp=l;
while(temp->punt->punt) temp=temp->punt; //scorre la lista, si ferma sul penultimo elemento
e=temp->punt->elem; // copia in e l'ultimo elemento
L p=temp->punt; // salva l'indirizzo dell'ultimo elemento
temp->punt=0; // "stacca" l'ultimo elemento dalla lista
delete p; // dealloca l'ultimo elemento
}
}
//------------------------------------------------------------
// inlist: ricerca sequenziale versione iterativa
bool inlist(const L& l,const E & e) {
L temp=l;
bool trovato=false;
while (temp && !trovato) {
if (e==temp->elem) trovato=true;
else
temp=temp->punt;
}
return trovato;
}
//------------------------------------------------------------
// stampa versione iterativa
void print(const L & l) {
L temp=l;
while(temp) {
cout << temp->elem;
cout << "\t";
temp=temp->punt;
}
}


Andiamo con ordine ragionando sull'operazione di push (inserimento in testa)
//------------------------------------------------------------
void push(L& l,const E & e) {
L q=new Record; //alloca spazio
q->elem=e; //vi pone e
q->punt=l; //lega al resto della lista
l=q; //lo mette in testa alla lista
}
//------------------------------------------------------------
questa mi crea un record con puntatore q di tipo L. Accedo a questo record con q-> (che equivale a *q), ed in particolare accedo ai campi due record ponendovi "e" "l" .
Poi assegno q ad l, in modo tale che il puntatore alla testa della lista punti al nuovo record creato



poi la funzione inserimento

// insert versione iterativa
void insert(L& l,const E & e) {
if(l==0 || l->elem>e) push(l,e); //l'elemento va inserito in testa
else { //l'elemento va inserito al centro o in coda
L prec=l, succ;
//alloca ed inizializza il nuovo elemento
L q=new Record;
q->elem=e;
q->punt=0;
while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
// collega il nuovo elemento al resto della lista (anche in coda se è il caso)
q->punt=succ;
prec->punt=q;

qui non ci incomincio a capire.....
if (il puntatore alla testa della lista è =0 oppure il campo elemento acceduto dal puntatore alla testa della lista è >e valore presente nel campo elemento del record) fai push mettendo il record in testa.

else
considera il puntatore a record "prec" inizializzato a quello di testa, e un altro puntatore a record "succ"
crea nuovo record, puntato da q , ed assegna ai due campi del nuovo record "e" e "0".
while( prec accede a punt ,secondo campo del record, e prec accede a punt che accede ad elemento del record successivo che sia < e ) cioè faccio scorrere prec, giusto? assegna a prec il puntatore e a succ il puntatore acceduto con prec.



assegna al secondo campo acceduto da q (quella del nuovo record) "succ"
e al campo punt acceduto da prec assegna q.
queste non le ho capite.
Mi aiutate per favore :muro:

[wingman87]

// insert versione iterativa
void insert(L& l,const E & e) {
if(l==0 || l->elem>e) push(l,e); //l'elemento va inserito in testa
else { //l'elemento va inserito al centro o in coda
L prec=l, succ;
//alloca ed inizializza il nuovo elemento
L q=new Record;
q->elem=e;
q->punt=0;
while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
// collega il nuovo elemento al resto della lista (anche in coda se è il caso)
q->punt=succ;
prec->punt=q;

qui non ci incomincio a capire.....
if (il puntatore alla testa della lista è =0 oppure il campo elemento acceduto dal puntatore alla testa della lista è >e valore presente nel campo elemento del record) fai push mettendo il record in testa.

else
considera il puntatore a record "prec" inizializzato a quello di testa, e un altro puntatore a record "succ"
crea nuovo record, puntato da q , ed assegna ai due campi del nuovo record "e" e "0".
while( prec accede a punt ,secondo campo del record, e prec accede a punt che accede ad elemento del record successivo che sia < e ) cioè faccio scorrere prec, giusto? assegna a prec il puntatore e a succ il puntatore acceduto con prec.



assegna al secondo campo acceduto da q (quella del nuovo record) "succ"
e al campo punt acceduto da prec assegna q.
queste non le ho capite.
Mi aiutate per favore :muro:
Ti scrivo le cose che potresti non aver capito:
Non essendoci le parentesi graffe dopo il while, l'istruzione che viene ripetuta è solo quella immediatamente successiva.
Inoltre la condizione prec->punt è equivalente a scrivere prec->punt != 0 (cioè prec->punt != null).
while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
// collega il nuovo elemento al resto della lista (anche in coda se è il caso)
q->punt=succ;
prec->punt=q;
Le tre istruzioni successive si svolgono quindi al termine del ciclo while e semplicemente inseriscono l'elemento che volevamo inserire tra prec e succ.

[Bandit]

Ti scrivo le cose che potresti non aver capito:
Non essendoci le parentesi graffe dopo il while, l'istruzione che viene ripetuta è solo quella immediatamente successiva.
Inoltre la condizione prec->punt è equivalente a scrivere prec->punt != 0 (cioè prec->punt != null).
while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec

quindi mi stai dicendo che quella roba significa scorre la lista poichè
" prec->punt è equivalente a scrivere prec->punt != 0 " che sta a significare che finchè prec non accede al puntatore di coda?

però non dovrebbe essere quello scritto nella parentesi del while a scorrere la lista?
il problema credo che sia proprio qui: non capisco le parentesi del while e le due istruzioni precedenti
prec=prec->punt;
succ=prec->punt;


cmq in generale quindi le cose che ho scritto per le cose che ho sottolineato vanno bene? devo solo capire a cosa servono ognuna

[wingman87]

Secondo me stai ragionando troppo a basso livello. Ok capire le istruzioni però dopo che hai capito quello che fanno devi capire cosa fanno nel complesso. Quello che fa la funzione di insert è un inserimento ordinato, ad esempio nella lista
13 -> 45 -> 107 -> 112
Voglio inserire 53
la funzione inizialmente mette in prec la testa della lista, dopodiché il ciclo mette in prec gli elementi successivi, finché non giungo o alla coda (è la condizione prec->succ != null) o ad un elemento maggiore dell'elemento che voglio inserire (è la condizione prec->punt->elem<e).
Nell'esempio, alla fine del ciclo prec conterrà il riferimento a 45.
succ=prec->punt;
q->punt=succ;
prec->punt=q;
Le 3 istruzioni successive:
- metto in succ l'elemento successivo (se prec punta alla coda prec->punt varrà null). Nell'esempio succ punta a 107
- imposto succ come successore dell'elemento che sto inserendo
- imposto l'elemento che sto inserendo come successore di prec

Risultato:
13 -> 45 -> 53 -> 107 -> 112

[Bandit]

il fatto è che se lo devo riprodurre lo devo capire
e purtroppo non l'ho capito ancora.


Come mi immagino prec e succ?

il primo è un puntatore che inizializzo alla testa della lista.
il secondo che ne faccio? come si muove?

il while () mi dice che : mentre il puntatore prec accede ai secondi campi dei record, e fino a che questi puntano ad un primo campo del record < del primo campo del nuovo record. concordi?

finchè avviene tutto ciò, " prec=prec->punt " cioè assegno a prec i secondi campi dei record che son diversi da zero

e con " succ=prec->punt " assegno a succ i secondi campi dei record.
E da qui nasce la domanda: come si differenziano i due puntatori prec e succ? dopo questa istruzione non sono uguali?

però poi le due ultime istruzioni :
-assegnano succ al secondo campo del record nuovo
-assegnano q al secondo campo del record nuovo
cmq non mi torna


Provo ad inserire questae append che inserisce in coda avendo un il solo puntatore temp ma cmq non mi è tanto chiaro

// append versione iterativa
void append(L& l,const E & e) {
if(l==0) push(l,e);
else {
L temp=l;
L q=new Record; //alloca spazio
q->elem=e; //vi pone e
q->punt=0; // e' l'ultimo elemento della lista
while(temp->punt) temp=temp->punt; //scorre la lista, si ferma sull'ultimo elemento
temp->punt=q; //lo mette in coda alla lista
} //fine if
}


se il puntatore in testa alla lista è pari a 0 allora fai un'operazione di push
oppure
inizializza un altro puntatore a record "temp" al puntatore in testa, e crea un altro record q nel quale setto i due suoi campi a "e" e "0"; mentre "temp" accede al secondo campo dei record, assegna a temp il secondo campo dei record. Ma che vuol dire questo? nei commenti c'è scritto che si ferma all'ultimo elemento e perchè?

assegna q (il puntatore del nuovo record) a temp, in modo da metterlo in coda

[wingman87]

Tanto per cominciare ti consiglio di chiamare i campi del record con i loro nomi: elem e punt. Sai che elem è il valore dell'elemento della lista, mentre punt è il puntatore all'elemento successivo (se ce n'è uno). Purtroppo la scelta dei nomi dei campi non è stata particolarmente felice... In modo più chiaro avresti potuto chiamarli value e next (o valore e successivo).
Poi mi sembra di capire che non hai compreso ancora come si legge il while.
In generale il while è fatto così:
while(condizione)
{
istruzioni //Questo è il corpo del ciclo (ciò che viene ripetuto finché condizione è vera)
}

Nel codice che hai postato però non ci sono le graffe, questo significa che il corpo del ciclo è solo l'istruzione successiva
while(prec->punt && prec->punt->elem<e )
prec=prec->punt;
succ=prec->punt;
q->punt=succ;
prec->punt=q;
Per meglio intenderci, avresti potuto scrivere in modo equivalente
while(prec->punt && prec->punt->elem<e )
{
prec=prec->punt;
}
succ=prec->punt;
q->punt=succ;
prec->punt=q;
Le tre istruzioni successive quindi non fanno parte del ciclo while e vengono eseguite solo quando questo termina.

prec e succ sono variabili di utilità: nella prima vorresti avere il puntatore all'elemento che precederà quello che stai inserendo:
L prec=l; //prec viene inizializzato alla testa
while(prec->punt && prec->punt->elem<e )
{
prec=prec->punt; //prec si sposta in avanti finché è necessario
}
in succ vorresti avere il puntatore al successivo:
succ=prec->punt;
Una volta che hai questi due valori esegui queste istruzioni:
q->punt=succ;
prec->punt=q;
Cioè fai in modo che l'elemento che stai inserendo abbia come successore succ e fai in modo che prec abbia come successore l'elemento che stai inserendo.

Provo a spiegarti ancora una volta il ciclo while perché rileggendo meglio il tuo post mi sembra che non hai capito una cosa fondamentale:
Poniamo di avere la lista
13 -> 45 -> 107 -> 112
Voglio inserire 53
Simuliamo passo passo cosa fa il codice seguente, ponendo che l è il puntatore alla testa (cioè all'elemento che contiene 13) e che e sia il valore intero 53.
L prec=l; //prec viene inizializzato alla testa
while(prec->punt && prec->punt->elem<e )
{
prec=prec->punt; //prec si sposta in avanti finché è necessario
}
succ=prec->punt;
- In prec viene messo il puntatore a 13 (in realtà all'elemento che lo contiene ma per non essere troppo verboso lasciami scrivere così)
- Viene controllata la condizione del while:

prec->punt != null ? Sì perché punta a qualcosa (l'elemento successivo, cioè 45)
prec->punt->elem < e ? Sì perché 45 < 53

- Viene eseguito il corpo del while, quindi in prec viene messo prec->punt. Al termine di questa istruzione prec non punta più a 13 ma a 45.
- Viene controllata la condizione del while:

prec->punt != null ? Sì perché punta a qualcosa (l'elemento successivo a 45, cioè 107)
prec->punt->elem < e ? No perché 107 non è < 53

- Il ciclo while termina e si passa all'istruzione successiva
- In succ viene messo prec->punt, quindi al termine di questa istruzione succ punterà a 107. prec continuerà a puntare a 45.

[Bandit]

- In succ viene messo prec->punt, quindi al termine di questa istruzione succ punterà a 107. prec continuerà a puntare a 53.


questa frase è sbagliata la corretta è
- In succ viene messo prec->punt, quindi al termine di questa istruzione succ punterà a 107. prec continuerà a puntare a 45.
giusto?

[wingman87]

Hai ragione, è un errore. Ora ho corretto.
Ora ti è più chiaro quel codice?

[Bandit]

Credo di si

:D :D


allora
ricapitolo solo a parole

considero 5 -10- 15- 20
e voglio inserire 12


in prec metto il puntatore all'elemento che contiene 5 (testa della lista)

Ora metre prec accede ai punt e e mentre accede a punt che accedono ai campi elem < 12 , fai accedere prec ai punt (cioè scorri la lista)

Arrivati a 12, si ricontrolla il while ed una condizione viene meno poichè 15<12 e quindi termina ciclo while e succ punta a 10.

In succ (che è una variabile puntatore) metto puntatore al successivo rispetto a quello che voglio inserire (succ lo faccio puntare a 15).


faccio in modo che l'elemento che voglio inserire abbia come punt, succ
|12 | succ|

faccio in modo che l'elem che viene puntato da prec (10) abbia come punt q
cioè |10|q|

[wingman87]

Anche se non mi piace molto come lo hai descritto mi sembra che hai capito.

Ora metre prec accede ai punt e e mentre accede a punt che accedono ai campi elem < 12 , fai accedere prec ai punt (cioè scorri la lista)

Qui avrei detto: finché prec ha un successore e il valore di questo successore è minore di e, fai avanzare prec.

Arrivati a 12, si ricontrolla il while ed una condizione viene meno poichè 15<12 e quindi termina ciclo while e succ punta a 10.

E qui avrei detto: quando prec giunge a 10 una condizione viene meno poichè 15<12 (15 è prec->punt->elem) e quindi termina il ciclo while con prec che punta a 10.

[Bandit]

non ho usato il termine successore, poichè il si potrebbe confondere con succ.
così facendo chiamando il secondo campo col suo nome (punt) mi è + chiaro


grazie mille
il tuo aiuto è stato prezioso

[Bandit]

ciao Wing
ti posso richiedere una manina su una parte di programma che prevede l'uso di una coda che permetta all'utente di inserire una transazione, eliminarla e stampare la sequenza di transazioni?

questa è l'intestazione e non ci son problemi

first è il puntatore alla coda
che viene posizionato alla testa della coda dal costruttore della classe CodaTransazioni

#ifndef _CODATRANSAZIONI_H_
#define _CODATRANSAZIONI_H_
#include "Soggiorno.h"

struct Nodo
{
Transazione*T; //il nodo composto da due campi: T e next
Nodo*next;
};

class CodaTransazioni
{
private:
Nodo*first;
public:
CodaTransazioni(){first=0;}
bool Empty(){return first==0;}
bool Append(Transazione*);
bool Pop();
bool StampaCoda();
bool MemorizzaTransazioni();
~CodaTransazioni();
};
#endif





1

Questa funzione inserisce una transazione nella coda
e mi dice che:

SE la coda è diversa da vuota allora
-crea un altro puntatore alla struttura Nodo e lo inizializza a first, in modo da puntare alla testa della coda.
-while (questo puntatore temp accede al campo next diverso da 0, quindi non elemento di fine coda) , fai accedere tempo ai prossimi campi next


-temp che accede al campo next ponilo come nuovo nodo??? (questa è strana)

-setta i campi di questo nuovo nodo con next =0 e T=Tr dove Tr è il parametro passato alla funzione Append stessa
-poni vero in esito, cioè è avvenuto l'inserimento


questo insomma fa l'inserimento in cosa, giusto?


OPPURE

-crea nuovo nodo e mettilo in first
-setta i campi del nuovo nodo con tr e 0
-esito è positivo , poichè è avvenuto l'inserimento.

questo fa l'inserimento del primo elemento nella coda giusto?



#include "CodaTransazioni.h"

bool CodaTransazioni::Append(Transazione*Tr)
{
bool esito=false;
if(!Empty())
{
Nodo*temp=first;
while(temp->next!=0) temp=temp->next;
temp->next=new Nodo;
temp->next->next=0;
temp->next->T=Tr;
esito=true;
}
else
{
first=new Nodo;
first->next=0;
first->T=Tr;
esito=true;
}
return esito;
}



2

SE la coda è diversa da vuota

-crea un puntatore a Nodo, e lo inizializza a first (testa della coda)

-mette in first, first che accede ai successivi elementi (questa è strana)

-cancella temp

io non ho capito a che serve instanziare temp





bool CodaTransazioni::Pop()
{
if(!Empty())
{
Nodo*temp=first;
first=first->next;
delete temp;
return true;
}
else return false;
}







3

-crea sempre il solito puntatore temp a nodo, inizializzato alla testa della coda
-while (temp è diverso da 0, cioè non accede alla fine della coda , giusto?)

questa non l'ho capita

CodaTransazioni::~CodaTransazioni()
{
Nodo*temp=first;
while(temp!=0)
{
temp=first->next;
delete first;
first=temp;
}
first=0;
}



4

questa dovrebbe accedere tramite temp al campo T degli elementi della coda , e tramite T che è oggetto della classe Transazioni, richiamare la funzione stampaDati della classe transazioni.
Però non ho capito perchè dopo aver richiamato la funzione c'è una tal funzione
temp=temp->next;


bool CodaTransazioni::StampaCoda()
{
if(!Empty())
{
Nodo*temp=first;
while(temp!=0)
{
temp->T->StampaDati();
temp=temp->next;
}
return true;
}
else return false;
}


5

questa funzione secondo il testo dovrebbe essere una funziona che invocata su un oggetto di classe coda, scrive su file di tipo testo i dati relativi a tutte le transizioni in coda......questa me ne preoccuperei dopo



bool CodaTransazioni::MemorizzaTransazioni()
{
if(!Empty())
{
Nodo*temp=first;
while(temp!=0)
{
temp->T->StampaSuFile();
temp=temp->next;
}
return true;
}
else return false;
}