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

[wingman87]

Originariamente inviato da Bandit

// 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

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]

Originariamente inviato da wingman87

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




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.

Originariamente inviato da Bandit

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.

Originariamente inviato da Bandit

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;
}