C++ Huffman Tree et Pointers

Je crée un Huffman Tree et pour ce faire j'ai commencé par faire un tas Min. Le tas est mis en place et fonctionne en triant les valeurs par fréquence dans le document mais mon problème vient quand j'essaye de commencer à créer l'arbre. Je fais sauter les deux premiers éléments du tas et place un nœud au-dessus d'eux et réinsère dans le tas. Le tas est basé sur un tableau de sorte qu'il ne touche pas les pointeurs * gauche et * droit des nœuds. Quand le tas est à un seul nœud cependant les deux pointeurs de gauche et de droite sont null donc je crois que cela peut être un problème avec mes pointeurs ...? Je suis nouveau au C++ de Java pour donner mes erreurs stupides.C++ Huffman Tree et Pointers

while(theHeap.getheapSize() > 1) 
    { 
     Node top; 
     Node *min1=new Node(theHeap.topandPop()); 
     Node *min2=new Node(theHeap.topandPop()); 
     top.left=min1; 
     top.right=min2; 
     top.freq=min1->freq+min2->freq; 
     theHeap.insert(top); 
    } 
    Node r=theHeap.topAndPop(); //null pointers for left and right children 

-------------------------------------- 
    //code for heap. arr is in the header file is Node *arr; 

void Heap::insert(Node c) 
{ 
    if (heapSize != arrSize) 
    { 
     heapSize=heapSize+1; 
     arr[heapSize - 1] = c; //does this call copy constructor??? 
     percolateUp(heapSize - 1); 
    } 
} 
void Heap::percolateUp(int nodeIndex) { 

    int parentIndex; 
    Node tmp; 
    if (nodeIndex != 0) 
    { 
     parentIndex = getParentPos(nodeIndex); 
     if (arr[parentIndex].freq > arr[nodeIndex].freq) 
     { 
      tmp = arr[parentIndex]; 
      arr[parentIndex] = arr[nodeIndex]; 
      arr[nodeIndex] = tmp; 
      percolateUp(parentIndex); 

     } 
    } 
}

Source

2010-09-23 Westin

Avez-vous envisagé d'utiliser 'std :: priority_queue' pour le tas? –

C'est un devoir et nous ne sommes pas autorisés à utiliser la bibliothèque standard. – Westin

Juste pour être sûr que 'top' est hors de portée, alors heureusement' insert() 'appelle un constructeur de copie au lieu de simplement prendre une adresse? – Reinderien

Premièrement, je recommanderais de ne pas mélanger des instances et des pointeurs, votre tâche sera beaucoup plus simple si vous en choisissez une. Dans ce cas, je pense qu'il serait approprié de stocker un pointeur sur un nœud dans le tas, plutôt qu'une instance, l'avantage supplémentaire est que les pointeurs se comportent plus comme vous êtes habitué à Java, pas besoin de s'inquiéter de la construction et de l'assignation . Vous avez seulement besoin de vous rappeler de les supprimer (contrairement à Java), quelque chose qui peut être fait dans le dtor de Heap. Deuxièmement, pour répondre à la question dans votre commentaire de code: Non, la copie ctor n'est pas invoquée dans Heap :: insert(), mais plutôt l'opérateur d'affectation est appelé. Que ce soit un problème ou non dépend de ce à quoi ressemble votre classe Node.

Source

2010-09-23 07:33:37

C++ Huffman Tree et Pointers

Répondre

Questions connexes