D'où proviennent les zéros provenant de ce programme qui imprime la matrice triée par ligne et par colonne dans l'ordre croissant?

Question

J'essaie d'imprimer les éléments matriciels triés par rangées et par colonnes dans l'ordre trié. J'utilise un MIN-HEAP de taille égale à celle du nombre de lignes de MATRIX donné. Je reçois la sortie désirée pour tous mes cas. Sauf que certains zéros se produisent entre la sortie souhaitée. Je ne trouve pas où ces zéros sont réellement insérés dans le tas.

Voici l'exemple d'essai: http://ideone.com/Ctmo91

#include<iostream> 
#include<limits.h> 
using namespace std; 

struct heapnode 
{ 
    int element; 
    int r; 
    int c; 
}; 
class heap 
{ 
public: 
    struct heapnode *harr; 
    int heapsize; 
    int capacity; 

    heap(int n) 
    { 
     harr = new heapnode[n]; 
     heapsize = 0; 
     capacity = n; 
    } 
    void minheapify(int i) 
    { 
     int smallest=i,lchild,rchild; 
     while(1) 
     { 
      lchild = 2*i + 1; 
      rchild = 2*i + 2; 
      if(lchild<heapsize && harr[smallest].element > harr[lchild].element) 
       smallest = lchild; 
      if(rchild<heapsize && harr[smallest].element > harr[rchild].element) 
       smallest = rchild; 
      if(smallest!=i) 
      { 
       swap(harr[i],harr[smallest]); 
       i = smallest; 
      } 
      else 
       break; 
     } 
    } 
    void buildheap(int n) 
    { 
     heapsize = n; 
     for(int i=heapsize/2 -1;i>=0;i--) 
      minheapify(i); 
    } 
}; 
void printSortedMatrix(int **arr,int m,int n) 
{ 
    int k=m; 
    int i,j; 
    heap H(m); 
    struct heapnode hr; 
    int count =0; 
    while(1) 
    { 
     //cout<<count<<endl; 
     if(count < k-1) 
     { 
      //cout<<count<<" "<<k<<endl; 
      H.harr[count] = {arr[count][0],count,0}; 
     } 
     else 
     { 
      if(count==k-1) 
      { 
       H.harr[count] = {arr[count][0],count,0}; 
       H.buildheap(k); 
      } 
      if(H.harr[0].element==999) 
       break; 

      cout<<H.harr[0].element<<" "; 

      hr = H.harr[0]; 
      if(hr.c==n) 
       H.harr[0] = {999,0,0}; 
      else 
       H.harr[0] = {arr[hr.r][hr.c+1],hr.r,hr.c+1}; 
      H.minheapify(0); 
     } 
     count++; 
    } 
    cout<<endl; 
} 

int main() 
{ 
    //code 
    int t,N,**arr,i,j,M; 
    cin>>t; 
    while(t--) 
    { 
     cin>>M; 
     N = M; 
     arr = new int*[M]; 
     for(i=0;i<M;i++) 
      arr[i] = new int[N]; 
     for(i=0;i<M;i++) 
      for(j=0;j<N;j++) 
       cin>>arr[i][j]; 
     printSortedMatrix(arr,M,N); 
    } 
    return 0; 
} 

Answer 1

a finalement trouvé le bogue. Je poussais en fait un élément supplémentaire dans chaque rangée.

if(hr.c==n) 
    H.harr[0] = {999,0,0}; 
else 
    H.harr[0] = {arr[hr.r][hr.c+1],hr.r,hr.c+1}; 

Comme on pouvait remarquer, le programme vérifie pour le numéro de colonne à n, alors qu'il peut aller du à n-1.

if(hr.c==n-1)    //The change 
    H.harr[0] = {999,0,0}; 
else 
    H.harr[0] = {arr[hr.r][hr.c+1],hr.r,hr.c+1};