Переместить 0 на вершину каждого столбца в массиве MxN

Question

У меня есть матрица NxM (размеры задаются пользователем), и я хочу, чтобы функция перемещала 0 в верхнюю часть каждого столбца и оставляла остальные целые числа такими, как они есть.Посмотрите на пример:

Переместить 0 на верх каждого столбца в массиве MxN

После перемещения на 0 с Iхотите иметь:

Кто-то, пожалуйста, исправьте мою zerototopMatrix функцию ниже:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>

void printMatrix(int (*arr), int rows, int cols,int level)
{
    int i, j;

    printf("\n");
    printf("\n");

    printf("The matrix elements are:\n   ");
    for (i = 0; i < cols+level; i++) {
        printf("%d ", i+1);
    } 
    printf("\n");
    for (i = 0; i < (cols*2+1+level); i++) {
        printf("-");
    } 
    printf("-\n");
    for (i = 0; i < rows+level; i++) {
        printf("%d| ", i+1);
        for (j = 0; j < cols+level; j++) {
            printf("%d ", *(arr + i*cols + j)); 
        }     
        printf("\n");
    }
}

void zerototopMatrix(int (*arr), int rows, int cols,int level)
{
    int i, j;

    printf("\n");
    printf("\n");

    int count = 0,temp = 0;

    for (j = 0; j < cols+level; j++) {
        for (i = 0; i < rows+level; i++) {
            if (*(arr + i*cols + j)==0)
            {
                (*(arr + i*cols + j)= (*(arr + count*cols + j)));
                (*(arr + count*cols + j))=0;
                count++;
            }
        }     
    }
}

int main() { 

    int number;

    srand ( time(NULL) );
    int level = 0;

    int row,col,colors;
    int points = 0;


    printf("How many rows:\n");
    scanf("%d", &row);

    printf("How many columns:\n");
    scanf("%d", &col);

    printf("How many colors:\n");
    scanf("%d", &colors);

    int *arr = (int *)malloc(row * col * sizeof(int)); 
    int i, j; 

    for (i = 0; i < row+level; i++) 
        for (j = 0; j < col+level; j++) {
            number = rand() % colors ;
            *(arr + i*col + j) = number;   
        }

    printMatrix(arr, row, col,level);

    printf("\n\nMove 0s to top:\n");
    zerototopMatrix(arr, row, col,level);

    printMatrix(arr, row, col,level);

    free(arr); 
    return 0; 
}

Answer 1

Это можно сделать, просто переместив ненулевые элементы в конец массива, работая снизу вверх для каждого столбца:

• Установите исходный индекс S и целевой индекс D нанижняя часть массива.
• Итерация и уменьшение S до тех пор, пока S не пройдет верхнюю часть массива:
  • Если элемент S не равен нулю, скопируйте элемент S в элемент D и уменьшите D.
• Итерируйте и уменьшайте D, пока D не пройдет вершину массива:
  • Установите элемент D в ноль.

Код:

void zeroToTopMatrix(int *arr, int rows, int cols, int level)
{
    //  Iterate through columns.
    for (int c = 0; c < cols + level; ++c)
    {
        //  Start destination index at bottom of column.
        int D = rows + level;

        //  Iterate source index backwards through column, skipping zeros.
        for (int S = rows + level - 1; 0 <= S; --S)
            if (arr[S*cols + c] != 0)
                arr[--D*cols + c] = arr[S*cols + c];

        //  Fill in top elements with skipped zeros.
        while (0 < D)
            arr[--D*cols + c] = 0;
    }
}

Я сохранил переменную level, как в исходном коде, но она выглядит неуместно и, скорее всего, сломает код, если он не равен нулю.

Answer 2

Первоначально я хотел создать временный буфер для хранения всех ненулевых элементов:

void zeroToTopMatrix(int *arr, int rows, int cols, int level) {
    int i, j;

    for (j = 0; j < cols + level; j++) {
        int tmp[rows];
        int tmpLen = 0;

        for (i = 0; i < rows + level; i++) {
            if (arr[i*cols+j]) {
                tmp[tmpLen++] = arr[i*cols+j];
            }
        }

        for (i = 0; i < rows - tmpLen; i++) {
            arr[i*cols+j] = 0;
        }

        for (int k = 0; i < rows; i++) {
            arr[i*cols+j] = tmp[k++];
        }
    }
}

Но предложение Эрика Постпишила гораздо умнее - двигайтесь снизу вверх в каждом столбце, выполняя перестановки по мере необходимости и дополняя вершину нулями. Вот код:

void zeroToTopMatrix(int *arr, int rows, int cols, int level) {
    int i, j;

    for (j = 0; j < cols + level; j++) {
        int k = rows + level - 1;

        for (i = k; i >= 0; i--) {
            if (arr[i*cols+j]) {
                arr[k--*cols+j] = arr[i*cols+j];
            }
        }

        while (k >= 0) {
            arr[k--*cols+j] = 0;
        }
    }
}

Вот полный тест:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>

void zeroToTopMatrix(int *arr, int rows, int cols, int level) {
    int i, j;

    for (j = 0; j < cols + level; j++) {
        int k = rows + level - 1;

        for (i = k; i >= 0; i--) {
            if (arr[i*cols+j]) {
                arr[k--*cols+j] = arr[i*cols+j];
            }
        }

        while (k >= 0) {
            arr[k--*cols+j] = 0;
        }
    }
}


void printMatrix(int *arr, int rows, int cols, int level) {
    int i, j;

    printf("\n");
    printf("\n");
    printf("The matrix elements are:\n   ");

    for (i = 0; i < cols + level; i++) {
        printf("%d ", i + 1);
    } 

    printf("\n");

    for (i = 0; i < (cols * 2 + 1 + level); i++) {
        printf("-");
    } 

    printf("-\n");

    for (i = 0; i < rows + level; i++) {
        printf("%d| ", i + 1);

        for (j = 0; j < cols + level; j++) {
            printf("%d ", *(arr + i * cols + j)); 
        }     

        printf("\n");
    }
}

int main() { 
    int i, j; 
    int number;
    int level = 0;
    int row, col, colors;
    int points = 0;

    srand(15/*time(NULL)*/);
    row = 5;
    col = 9;
    colors = 5;

    int *arr = malloc(row * col * sizeof(int)); 

    for (i = 0; i < row + level; i++) {
        for (j = 0; j < col + level; j++) {
            number = rand() % colors;
            *(arr + i * col + j) = number;   
        }
    }

    printMatrix(arr, row, col, level);
    zeroToTopMatrix(arr, row, col, level);
    printMatrix(arr, row, col, level);

    free(arr); 
    return 0; 
}

Выход:

The matrix elements are:
   1 2 3 4 5 6 7 8 9
--------------------
1| 3 0 2 0 1 0 4 2 3
2| 3 3 2 4 4 0 0 4 2
3| 4 3 0 0 3 1 0 1 3
4| 1 0 3 0 0 0 4 0 3
5| 0 0 1 3 0 4 3 1 0


The matrix elements are:
   1 2 3 4 5 6 7 8 9
--------------------
1| 0 0 0 0 0 0 0 0 0
2| 3 0 2 0 0 0 0 2 3
3| 3 0 2 0 1 0 4 4 2
4| 4 3 3 4 4 1 4 1 3
5| 1 3 1 3 3 4 3 1 3

Пара дополнительных советов:

• Иногда арифметика указателей элегантна, но в данном случае кажется более понятным просто использовать индексы массива с массивом 2d, упакованным в 1d.
• Нет необходимости разыгрывать результат malloc в C.