c++ - 这个按升序打印按行和按列排序的矩阵的程序的零在哪里？

Question

我正在尝试按排序顺序打印按行和按列排序的矩阵元素。我使用的 MIN-HEAP 大小等于给定 MATRIX 的行数。我的所有案例都获得了所需的输出。 除了一些零，出现在所需输出之间。我似乎没有找到这些零实际插入到堆中的位置。

这里是试运行的例子: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

终于找到bug了。我实际上是在每一行中额外添加一个元素。

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

正如您可能注意到的那样，程序正在检查列号是否为 n，而实际上它的范围是从 0 到 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};