двумерный массив через указатель

Question

Я хотел бы создать динамический массив, в котором будет храниться последовательность перестановок, такая, что

order[0][]={1,2,3}
order[1][]={2,1,3}
order[2][]={2,3,1}

допустим, скажем, порядок [m] [n], m = количество перестановок, n = количество членов, m и n идентифицируются в реальном времени.

Я сделал следующее и обнаружил, что адрес указателя перекрывается, что приводит к неправильному хранению значений. Как это сделать правильно, используя динамический массив через двойной указатель?

void permute(int num_permute, int num_term, int** order) {
    int x, y;
    int term[5];

    /* debug only */
    for(y=num_term, x=0; y>0; y--, x++){
        term[x] = y;
    }
    fprintf(stderr, "\n");

    printf("order%12c", ' ');
    for (x=0; x<num_permute; ++x) {
        printf("  %-11d", x);
    }
    printf("\n");
    for(y=0; y<num_permute; y++){
        printf("%-5d%12p", y, (order+y));
        memcpy(&(order[y]), term, sizeof(term));

        for (x=0; x<num_term; x++)
            printf(" %12p", order+y+x);

        printf("\n");

    }
}

int main(){
    int y, z;
    int** x;

    x = (int*) malloc(5*5*sizeof(int*));

    permute(5, 5, x);
    printf("\n");

    printf("x   ");
    for(z=0; z<5; z++){
        printf(" %2d ", z);
    }
    printf("\n");
    for(y=0; y<5; y++){
        printf("%-4d", y);
        for(z=0; z<5; z++){
            printf(" %2d ", *(x+y+z));
        }
        printf("\n");
    }

    free(x);

    return 0;
}

Результат: order [0] [1] и order [1] [0] указывают на один и тот же адрес ... и другие тоже. Со строками в качестве главной оси и столбцами второстепенных:

order             0            1            2            3            4           
0     0x100100080 0x100100080  0x100100084  0x100100088  0x10010008c  0x100100090
1     0x100100084 0x100100084  0x100100088  0x10010008c  0x100100090  0x100100094
2     0x100100088 0x100100088  0x10010008c  0x100100090  0x100100094  0x100100098
3     0x10010008c 0x10010008c  0x100100090  0x100100094  0x100100098  0x10010009c
4     0x100100090 0x100100090  0x100100094  0x100100098  0x10010009c  0x1001000a0

x     0   1   2   3   4 
0     5   5   5   5   5 
1     5   5   5   5   4 
2     5   5   5   4   3 
3     5   5   4   3   2 
4     5   4   3   2   1 

Answer 1

Исходный код:
Код будет что-то вроде:

#include <stdlib.h>

int **array;
array = malloc(nrows * sizeof(int *));
if(array == NULL)
{
     fprintf(stderr, "out of memory\n");
     /*exit or return*/
}
for(i = 0; i < nrows; i++)
{
    array[i] = malloc(ncolumns * sizeof(int));
    if(array[i] == NULL)
    {
          fprintf(stderr, "out of memory\n");
         /*exit or return*/
    }
}

Концепция:

array - указатель на указатель на int: на первом уровне он указывает на блок указателей, по одному на каждую строку. Этот указатель первого уровня является первым, который будет выделен; он имеет nrows элементов, причем каждый элемент достаточно большой, чтобы вместить pointer-to-int или int *. Если выделение выполнено успешно, заполните указатели (все nrows из них) указателем (также полученным из malloc) на число ncolumns, которое является хранилищем для этой строки массива.

Изображение:

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

Принимая это во внимание, пример кода можно переписать как:

void permute(int num_permute, int num_term, int** order) {
    int x, y;
    int term[5];
    int* ptr = NULL;

    for (y=num_term, x=0; y>0; y--, x++) {
        term[x] = y;
    }
    printf("\n");

    printf("order%12c", ' ');
    for (x=0; x<num_permute; ++x) {
        printf(" %2d ", x);
    }
    printf("\n");
    for (y=0; y<num_permute; y++) {
        ptr = order[y];
        memcpy(ptr, term, sizeof(term));

        printf("%-5d%12p", y, ptr);
        for (x=0; x<num_term; x++) {
            printf(" %2d ", ptr[x]);
        }
        printf("\n");
    }
}

int main() {
    int y, z;
    int** x = NULL;
    int num_term = 5;
    int num_permutation = 5;
    int* pchk = NULL;

    x = (int**) malloc(num_permutation * sizeof(int*));

    for (y=0; y<num_permutation; y++){
        x[y] = (int*) malloc(num_term * sizeof(int));
        printf("x[%d]: %p\n", y, x[y]);
    }

    permute(num_permutation, num_term, x);

    printf("\nx:  ");
    for(z=0; z<5; z++){
        printf(" %2d ", z);
    }
    printf("\n");

    for(y=0; y<num_permutation; y++){
        pchk = x[y];
        printf("%-4d", y);
        for(z=0; z<num_term; z++){
            printf(" %2d ", pchk[z]);
        }
        printf("\n");
    }

    for (y=0; y<num_permutation; y++) {
        free(x[y]);
    }
    free(x);

    return 0;
}

Answer 2

Пример кода имитирует только многомерный массив и делает это неправильно.Чтобы увидеть, что происходит не так, начните с рассмотрения того, что происходит, когда вы объявляете многомерный массив:

int foo[3][5];

Это выделяет непрерывную область памяти размером 3 * 5 * sizeof (int).В выражении, таком как foo[i], foo преобразуется в указатель int [5], затем применяется оператор индекса.Другими словами, foo[i] эквивалентно *( (int (*)[5])foo) + i).Каждый foo[i] считается размером 5 * sizeof (int).

   x,y:  0,0 0,1 0,2 0,3 0,4 1,0 
foo --> | 1 | 2 | 3 | 4 | 5 | 1 |...
        <- 5 * sizeof(int) ->

Когда вы создаете x в примере кода, вы реплицируете этот тип многомерного массива.Индексное выражение, которое вы используете (*(order + y + x)), таким образом, неверно, поскольку оно неправильно обрабатывает размер order[y]: order + 1 + 0 == order + 0 + 1, что является проблемой, которую вы видите в примере вывода.

Правильные выражения: (order + num_term * y) для перестановки y ^th и *(order + num_term * y + x) для элемента order[y][x].

Это говорит о другом классе ошибок в образце.Для этого типа моделируемого многомерного массива типы массивов фактически являются указателями на одномерные массивы.Заявленные типы x и order должны быть int*, а не int**.Это должно быть подкреплено предупреждениями типа, которые должен генерировать пример кода:

• при выделении пространства для x, тип указателя (int*) не соответствует типу x
• при печати элементов x, тип *(x+y+z) не соответствует формату "% d".

Однако при моделировании многомерного массива сохраняетсяпространство, это более подвержено ошибкам при использовании (если вы не пишете функцию для обработки индексации).Такое решение, как Als, может быть более безопасным, поскольку вы можете использовать стандартный оператор индексации.

Answer 3

Эмуляция 2D-массива с массивами указателей является полным излишним, если у вас есть C99 (или C11).Просто используйте

void permute(size_t num_permute, size_t num_term, unsigned order[][num_term]);

в качестве сигнатуры функции и выделите вашу матрицу в main с чем-то вроде

unsigned (*order)[m] = malloc(sizeof(unsigned[n][m]));

Также, как вы можете видеть в примерах выше, я бы предложилчто вы используете семантически правильные типы.Размеры всегда лучше всего подаются с size_t, и ваши значения перестановок выглядят так, как будто они никогда не будут отрицательными.Может быть, для этого вы также должны начать считать с 0.

Answer 4

Следующий фрагмент кода создает 2-мерную матрицу для данной строки и столбца.Пожалуйста, используйте это как ссылку для отладки вашей программы.

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

int main()
{
        int row, column;
        int **matrix;
        int i, j, val;

        printf("Enter rows: ");
        scanf("%d", &row);
        printf("Enter columns: ");
        scanf("%d", &column);

        matrix = (int **) malloc (sizeof(int *) * row);
        if (matrix == NULL) {
                printf("ERROR: unable to allocate memory \n");
                return -1;
        }  
        for (i=0 ; i<row ; i++) 
                matrix[i] = (int *) malloc (sizeof(int) * column);

        val=1;
        for (i=0 ; i<row ; i++) {
                for (j=0 ; j<column; j++) {
                        matrix[i][j] = val++;
                }
        }

        for (i=0 ; i<row ; i++) {
                for (j=0 ; j<column; j++) {
                        printf("%3d  ", matrix[i][j]);
                }
                printf("\n");
        }

        return 0;
}

/*
Allocation of 2d matrix with only one call to malloc and 
still get to access the matrix with a[i][j] format

the matrix is divided into headers and data.

headers = metadata to store the rows
data = actual data storage - buffer

allocate one contigious memory for header and data
and then make the elements in the header to point to the data are

        <- headers -----><----------- data -----------

        -----------------------------------------------------------------
        | | | | | |     ..      |
        | | | | | |     ..      |
        -----------------------------------------------------------------
         |                                 ^
         |                                 |
         |-----------------|
        header points to data area

*/

/*
Output:

$ gcc 2darray.c 
$ ./a.out 
Enter rows: 10
Enter columns: 20
  1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20  
 21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40  
 41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60  
 61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80  
 81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99  100  
101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  
121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  
141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  
161  162  163  164  165  166  167  168  169  170  171  172  173  174  175  176  177  178  179  180  
181  182  183  184  185  186  187  188  189  190  191  192  193  194  195  196  197  198  199  200  
$ 

*/