Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Liste: non capisco alcune operazioni
Forum - C/C++ - Liste: non capisco alcune operazioni

Avatar
alfox (Normal User)
Newbie


Messaggi: 6
Iscritto: 28/05/2012

Segnala al moderatore
Postato alle 11:16
Lunedì, 28/05/2012
Ciao ragazzi
mi aiutate per favore con le operazioni sulle liste alcune non le capisco
Anzitutto vi posto l'intestazione

Codice sorgente - presumibilmente C++

  1. [CODE]
  2. // LISTADI1.H : Implementazione dinamica della struttura astratta lista
  3. //                              realizzata con libreria di funzioni. File di SPECIFICA
  4.  
  5. #ifndef _LISTA_H_                               // Compilazione condizionale
  6. #define _LISTA_H_
  7.  
  8.  
  9. typedef int E;                                  // Def. del tipo di el. della lista
  10. struct Record;                                  // Predichiarazione
  11. typedef Record* L;                              // Def. del tipo puntatore a Record
  12. struct Record {                         // Tipo record costituito da
  13.                 E elem;                         // campo informazione
  14.                 L punt;                         // campo puntatore al prossimo nodo della lista
  15. };
  16.  
  17. void start(L& l);                                               // Inizializza la lista                                                        
  18. bool empty(const L& l);                 // Test di lista vuota
  19. bool full(const L& l);                          // Test di lista piena
  20. void insert(L& l, const E & e);                 // Inserimento in coda
  21. bool erase(L& l, const E & e);              // Cancellazione di un elemento specificato
  22. bool inlist(const L& l, const E & e);   // Vera se e e' presente nella lista
  23. void print(const L &l);                 // Stampa la lista
  24. void clear(L & l);                      // Distrugge la lista
  25.                                                                        
  26. #endif
  27.  
  28.  
  29. [/CODE]


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

Codice sorgente - presumibilmente C++

  1. [CODE]
  2. // LISTA.CPP : Implementazione dinamica della struttura lista con
  3. //                         libreria di funzioni. File di IMPLEMENTAZIONE
  4.  
  5. #include "lista1.h"
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. //------------------------------------------------------------
  10. void start(L& l) {
  11.         l=0;
  12. }
  13. //------------------------------------------------------------
  14. bool empty(const L& l) {
  15.         return (l==0);
  16. }
  17. //------------------------------------------------------------
  18. bool full(const L& l) {
  19.         return false;
  20. }
  21. //------------------------------------------------------------
  22. void push(L& l,const E & e) {
  23. L q=new Record; //alloca spazio
  24.         q->elem=e;      //vi pone e
  25.         q->punt=l;      //lega al resto della lista
  26.         l=q;            //lo mette in testa alla lista
  27. }
  28. //------------------------------------------------------------
  29. // insert versione iterativa
  30. void insert(L& l,const E & e) {
  31.    if(l==0 || l->elem>e) push(l,e);  //l'elemento va inserito in testa
  32.    else {                            //l'elemento va inserito al centro o in coda
  33.       L prec=l, succ;                            
  34.     //alloca ed inizializza il nuovo elemento
  35.       L q=new Record;
  36.       q->elem=e;
  37.       q->punt=0;  
  38.       while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
  39.       succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
  40.       // collega il nuovo elemento al resto della lista (anche in coda se è il caso)
  41.       q->punt=succ;
  42.       prec->punt=q;
  43. }
  44. //------------------------------------------------------------
  45. void pop(L& l,E& e) {       //oppure: bool pop(L& l,E& e)
  46.                 e=l->elem;      // copia in e il primo elemento
  47.                 L p=l;                  // salva il valore di  l
  48.                 l=l->punt;              //aggiorna l
  49.                 delete p;               // dealloca il primo elemento
  50. }
  51. //------------------------------------------------------------
  52. // lastpop versione iterativa
  53. void lastpop(L& l,E& e) {      //oppure: bool lastpop(L& l,E& e)
  54.  
  55.    if(l->punt==0) pop(l,e);
  56.    else     {
  57.      L temp=l;
  58.      while(temp->punt->punt) temp=temp->punt; //scorre la lista, si ferma sul penultimo elemento
  59.      e=temp->punt->elem;  // copia in e l'ultimo elemento
  60.      L p=temp->punt;     // salva l'indirizzo dell'ultimo elemento
  61.      temp->punt=0;       // "stacca" l'ultimo elemento dalla lista
  62.      delete p;          // dealloca l'ultimo elemento
  63.   }
  64. }
  65. //------------------------------------------------------------
  66. // inlist: ricerca sequenziale versione iterativa
  67. bool inlist(const L& l,const E & e) {
  68.     L temp=l;
  69.     bool trovato=false;
  70.         while (temp && !trovato) {
  71.       if (e==temp->elem) trovato=true;
  72.       else
  73.       temp=temp->punt;
  74.     }
  75.     return trovato;
  76. }
  77. //------------------------------------------------------------
  78. // stampa versione iterativa
  79. void print(const L & l) {
  80.     L temp=l;
  81.         while(temp) {
  82.           cout << temp->elem;
  83.       cout <<  "\t";
  84.       temp=temp->punt;
  85.         }
  86. }
  87. [/CODE]



Andiamo con ordine ragionando sull'operazione di push (inserimento in testa)
Codice sorgente - presumibilmente C/C++

  1. Codice sorgente - presumibilmente C/C++

    //------------------------------------------------------------
  2. void push(L& l,const E & e) {
  3. L q=new Record; //alloca spazio
  4.         q->elem=e;      //vi pone e
  5.         q->punt=l;      //lega al resto della lista
  6.         l=q;            //lo mette in testa alla lista
  7. }
  8. //------------------------------------------------------------


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
Codice sorgente - presumibilmente C#

  1. [CODE]
  2. // insert versione iterativa
  3. void insert(L& l,const E & e) {
  4.    if(l==0 || l->elem>e) push(l,e);  //l'elemento va inserito in testa
  5.    else {                            //l'elemento va inserito al centro o in coda
  6.       L prec=l, succ;                            
  7.     //alloca ed inizializza il nuovo elemento
  8.       L q=new Record;
  9.       q->elem=e;
  10.       q->punt=0;  
  11.       while(prec->punt && prec->punt->elem<e ) prec=prec->punt; //determina prec
  12.       succ=prec->punt; //determina succ, se l'inserimento è in coda succ deve valere 0
  13.       // collega il nuovo elemento al resto della lista (anche in coda se è il caso)
  14.       q->punt=succ;
  15.       prec->punt=q;
  16. [/CODE]


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".

queste non le ho capite. Il problema secondo me sono le parentesi del while e le due successive operazioni.


Provo a spiegarmi la funzione insert con questa funzione append che inserisce in coda ma cmq non mi è tanto chiaro
Codice sorgente - presumibilmente C#

  1. // append versione iterativa
  2. void append(L& l,const E & e) {
  3.    if(l==0) push(l,e);
  4.    else     {
  5.      L temp=l;
  6.      L q=new Record;    //alloca spazio
  7.      q->elem=e; //vi pone e
  8.      q->punt=0; // e' l'ultimo elemento della lista
  9.      while(temp->punt) temp=temp->punt; //scorre la lista, si ferma sull'ultimo elemento
  10.      temp->punt=q;              //lo mette in coda alla lista
  11.   }  //fine if
  12. }


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 capo dei record. Ma che vuol dire questo?  nei commenti c'è scritto che si ferma all'ultimo elemento.

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

Ultima modifica effettuata da alfox il 28/05/2012 alle 11:19
PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 15:09
Lunedì, 28/05/2012
ma perchè sta scritto tutto in maniera così complicato? .-.
cioè si potrebbe utilizzare il tradizionale c++ senza complicarsi troppo la vita..


Bha!!!
PM Quote
Avatar
alfox (Normal User)
Newbie


Messaggi: 6
Iscritto: 28/05/2012

Segnala al moderatore
Postato alle 16:16
Lunedì, 28/05/2012
ma perchè non è scritto in c++?
io quello sto studiando

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 22:26
Lunedì, 28/05/2012
Sintatticamente e' C++, progettualmente... beh... e' un approccio procedurale tipico del C ma non del C++ dove l'utilizzo di una classe probabilmente aiuterebbe a costruire una soluzione piu' pulita. La nomenclatura delle variabili poi rende il tutto ancora meno comprensibile (agli inizi pensare di usare variabili come e, L, q, n, g sembra una buona idea perche' cosi' le usano i matematici, ma imparerai presto che programmazione != matematica).

Se hai preso questo codice da qualche parte e lo stai usando per imparare, io ti consiglierei di buttarlo via e cercare un'altra implementazione... e' veramente scritto male.

http://www.codeproject.com/Articles/24684/How-to-create-Li ...

Ultima modifica effettuata da pierotofy il 28/05/2012 alle 22:28


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 16:34
Mercoledì, 30/05/2012
In più ti consiglierei questo sito che da una buona base sulle liste :)
http://www.science.unitn.it/~brunato/labpro1/lista.html


Bha!!!
PM Quote
Avatar
alfox (Normal User)
Newbie


Messaggi: 6
Iscritto: 28/05/2012

Segnala al moderatore
Postato alle 23:56
Mercoledì, 13/06/2012
ragazzi mi scuso per il ritardo
ma ho lasciato stare le liste ed il c++, per l'imminenza di un altro esame.
Cmq grazie mille, per i links che mi avete segnalati.

ciao e grazie ancora

PM Quote