Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - traccia esame
Forum - C/C++ - traccia esame

Avatar
il-david (Normal User)
Newbie


Messaggi: 10
Iscritto: 22/12/2009

Segnala al moderatore
Postato alle 11:08
Martedì, 22/12/2009
Buongiorno a tutti. Sono uno studente di Ing. dell'Informazione e tra 3 settimane circa ho l'esame di Fondamenti. Sto sbattendo da un pò di giorni su questa traccia d'esame:
1- Esercizio in C che ho posta qui-> http://www.pierotofy.it/pages/extras/forum/viewtopic.php?i ...=

2- Scrivere il codice C++ per la realizzazione dei una classe che implementa un heap di massimo 127 elementi float. Prevedere costruttore che crea heap vuoto, costruttore che riceve array di float e numero di float e crea l'heap con gli stessi elementi dell'array, funzione di inserimento ed estrazione, distruttore, costruttore di copia ed eventuali funzioni necessarie al funzionamento.

Questa è una mia bozza:
Codice sorgente - presumibilmente C++
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class heap {
  5.    int num_el, j;
  6.    float *p_el, new_el;
  7.    public:
  8.       heap() {cout<<"Costruttore\n"; num_el=0; p_el=NULL; }
  9.       ~heap() {cout<<"Distruttore\n"; if(num_el>0 && num_el<=127) delete []p_el; }
  10.       heap(const heap &s);
  11.       void heapify(int i, int l, int r);
  12.       heap(int n, float p) : num_el(n), p_el(p) {
  13.          for(j=0; j<num_el; j++) {
  14.             p_el[++num_el] = new_el;
  15.             heapify(num_el, 1, num_el);
  16.          }
  17.       }
  18. };
  19.  
  20. void heap::heapify (int i, int l, int r) {
  21.    int child;
  22.    float *temp;
  23.    temp=p_el[i];
  24.    while (i>=l && temp<p_el[i/2]) {
  25.       p_el[i]=p_el[i/2];
  26.       i/=2;
  27.    }
  28.    p_el[i]=temp;
  29.    while (i<=r/2) {
  30.       child=2*i;
  31.       if (child+1<=r && p_el[child+1]<p_el[child])
  32.          child++;
  33.       if (temp<=p_el[child]) break;
  34.       p_el[i]=p_el[child];
  35.       i=child;
  36.       }
  37.    p_el[i]=temp;
  38. }
  39.  
  40. heap::heap(const heap &s)
  41. {
  42.         try{
  43.                 p_el=new int[s.num_el];
  44.         }
  45.         catch(bad_alloc xa){
  46.                 cout<<"Errore allocazione in costruttore copie!\n";
  47.                 num_el=0;
  48.                 return;
  49.         }
  50.         num_el=s.num_el;
  51.         for(int i=0;i<num_el;i++)p_el[i]=s.p_el[i];
  52. }
  53.  
  54.  
  55. int main()
  56. {
  57.    int num, i;
  58.    float *ptr;
  59.    
  60.    cout<<"num. el:";
  61.    cin>>num;
  62.    if(num>0 && num<=127) {
  63.       ptr = new float[num];
  64.       cout<<endl;
  65.       for(i=0; i<num; i++) {
  66.          cout<<"ins. el:";
  67.          cin>>ptr[i];
  68.          cout<<endl;
  69.       }
  70.    heap H(num, ptr);
  71.    
  72.    system("pause");
  73.    return 0;
  74. }


L'ho scritta inserendo materiale reperito qua e la, ma i concetti non mi sono chiari, mi servirebbe una spiegazione coscienziosa vista l'imminenza dell'esame.
Vi ringrazio di cuore e vi auguro buone feste:k:

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 17:40
Martedì, 22/12/2009
Uno heap si comporta esattamente come un binary tree, con la differenza che è più flessibile (il binary tree impone che il nodo child a sinistra sia più piccolo del nodo parent e quello di destra più grande, mentre uno heap impone semplicemente che entrambi i nodi child siano più piccoli - o più grandi dipendentemente dal fatto che tu stia implementando un max heap o un min heap - del nodo parent).

http://en.wikipedia.org/wiki/Heap_(data_structure)

Il codice è piuttosto ingarbugliato... vi hanno spiegato il concetto di usare identificatori descrittivi e l'importanza dei commenti?

Il mio blog: https://piero.dev
PM Quote
Avatar
il-david (Normal User)
Newbie


Messaggi: 10
Iscritto: 22/12/2009

Segnala al moderatore
Postato alle 14:50
Giovedì, 24/12/2009
Ho modificato il codice, ed ora va tutto bene. Solo non ho capito il funzionamento del costruttore di copia...

Codice sorgente - presumibilmente C++
  1. #include <iostream>
  2. #define MAX 127
  3. using namespace std;
  4.  
  5. class heap {
  6.    int num_el, j;
  7.    float *p_el;
  8.    public:
  9.       int ArraySize, HeapSize;
  10.       heap() {cout<<"Costruttore\n"; num_el=0; p_el=NULL; }
  11.       ~heap() {cout<<"Distruttore\n"; if(num_el>0 && num_el<=127) delete []p_el; }
  12.       heap(const heap &s);
  13.       void BuildHeap(float A[MAX]);
  14.       void HeapSort(float A[MAX]);
  15.       void heapify(float A[MAX], int i);
  16.       int left(int i) { return 2*i+1;}
  17.       int right(int i) { return 2*i+2;}
  18.       int parent (int i) {return (i-1)/2;}
  19.       void swap(float A[MAX], int i, int j);
  20. };
  21.  
  22. void heap::swap(float A[MAX], int i, int j) {
  23.    float tmp = A[i];
  24.    A[i] = A[j];
  25.    A[j] =tmp;
  26. }
  27.  
  28. void heap::HeapSort(float A[MAX])
  29. {
  30.    int i;
  31.    BuildHeap(A);
  32.    for (i=ArraySize-1; i>=1; i--) {
  33.       swap(A, 0, i);
  34.       HeapSize--;
  35.       heapify(A, 0);
  36.    }
  37. }
  38.  
  39. void heap::BuildHeap(float A[MAX])
  40. {
  41.    int i;
  42.    HeapSize = ArraySize;
  43.    for (i=ArraySize/2; i>=0; i--)
  44.       heapify(A, i);
  45. }
  46.  
  47. void heap::heapify(float A[MAX], int i)
  48. {
  49.    int l,r,largest;
  50.    l = left(i);
  51.    r = right(i);
  52.    if (l < HeapSize && A[l] > A[i])
  53.       largest = l;
  54.    else largest = i;
  55.    if (r < HeapSize && A[r] > A[largest])
  56.       largest = r;
  57.    if (largest != i) {
  58.       swap(A, i, largest);
  59.       heapify(A, largest);
  60.    }
  61. }
  62.  
  63. heap::heap(const heap &s)
  64. {
  65.         try{
  66.                 p_el=new float[s.num_el];
  67.         }
  68.         catch(bad_alloc xa){
  69.                 cout<<"Errore allocazione in costruttore copie!\n";
  70.                 num_el=0;
  71.                 return;
  72.         }
  73.         num_el=s.num_el;
  74.         for(int i=0;i<num_el;i++)p_el[i]=s.p_el[i];
  75. }
  76.  
  77.  
  78. int main()
  79. {
  80.    int num, i, k;
  81.    float ptr[MAX];
  82.    heap Heap; //istanzio un oggetto della classe astratta heap
  83.    
  84.    cout<<"num. el:";
  85.    cin>>num;
  86.    if(num>0 && num<=127) {
  87.       cout<<endl;
  88.       for(i=0; i<num; i++) {
  89.          cout<<"ins. el:";
  90.          cin>>ptr[i];
  91.          cout<<endl;
  92.       }
  93.    }
  94.    Heap.HeapSize=Heap.ArraySize=num;
  95.    Heap.HeapSort(ptr);
  96.    for (k=0;k<num;k++)
  97.       cout<<ptr[k]<<" ";
  98.    cout<<endl;
  99.    
  100.    system("pause");
  101.    return 0;
  102. }

PM Quote
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2765
Iscritto: 21/09/2007

Segnala al moderatore
Postato alle 0:34
Venerdì, 25/12/2009

il costruttore copia è il costruttore che viene chiamato quando si crea una nuova istanza copiando da un'altra istanza. In questo caso bisogna copiare i buffer interni di memoria dinamica in modo da non incorrere in problemi dopo la deallocazione del primo oggetto.




PM Quote