Dynamically allocating array explain

问题:

This is sample code my teacher showed us about "How to dynamically allocate an array in C?". But I don't fully understand this. Here is the code:

int k;
int** test;
printf("Enter a value for k: ");
scanf("%d", &k);
test = (int **)malloc(k * sizeof(int*));
for (i = 0; i < k; i++) {
    test[i] = (int*)malloc(k * sizeof(int)); //Initialize all the values
}

I thought in C, to define an array you had to put the [] after the name, so what exactly is int** test; isn't it just a pointer to a pointer? And the malloc() line is also really confusing me.....

回答1:

According to declaration int** test; , test is pointer to pointer, and the code pice allocating memory for a matrix of int values dynamically using malloc function.

Statement:

test = (int **)malloc(k * sizeof(int*));
    //                ^^------^^-------
    //  allocate for  k  int*  values    

Allocate continue memory for k pointers to int (int*). So suppose if k = 4 then you gets something like:

 temp      343  347  351  355
+----+    +----+----+----+----+
|343 |---►| ?  | ?  | ?  |  ? |
+----+    +----+----+----+----+

I am assuming addresses are of four bytes and ? means garbage values.

temp variable assigned returned address by malloc, malloc allocates continues memory blocks of size = k * sizeof(int**) that is in my example = 16 bytes.

In the for loop you allocate memory for k int and assign returned address to temp[i] (location of previously allocated array).

test[i] = (int*)malloc(k * sizeof(int)); //Initialize all the values
//                     ^^-----^^----------
//       allocate for  k   int  values    

Note: the expression temp[i] == *(temp + i). So in for loop in each iterations you allocate memory for an array of k int values that looks something like below:

   First malloc                     For loop   
  ---------------                  ------------------
       temp
      +-----+
      | 343 |--+
      +-----+  |
               ▼                    201   205   209    213  
        +--------+                +-----+-----+-----+-----+
 343    |        |= *(temp + 0)   |  ?  |  ?  |  ?  | ?   |  //for i = 0
        |temp[0] |-------|        +-----+-----+-----+-----+
        | 201    |       +-----------▲
        +--------+                  502   506  510    514
        |        |                +-----+-----+-----+-----+
 347    |temp[1] |= *(temp + 1)   |  ?  |  ?  |  ?  | ?   |  //for i = 1
        | 502    |-------|        +-----+-----+-----+-----+
        +--------+       +-----------▲
        |        |                  43    48    52    56
 351    | 43     |                +-----+-----+-----+-----+
        |temp[2] |= *(temp + 2)   |  ?  |  ?  |  ?  | ?   |  //for i = 2
        |        |-------|        +-----+-----+-----+-----+
        +--------+       +-----------▲
 355    |        |
        | 9002   |                 9002  9006   9010 9014
        |temp[3] |                +-----+-----+-----+-----+
        |        |= *(temp + 3)   |  ?  |  ?  |  ?  | ?   |  //for i = 3
        +--------+       |        +-----+-----+-----+-----+
                         +-----------▲

Again ? means garbage values.

Additional points:

1) You are casting returned address by malloc but in C you should avoid it. Read Do I cast the result of malloc? just do as follows:

test = malloc(k* sizeof(int*));
for (i = 0; i < k; i++){
    test[i] = malloc(k * sizeof(int));
}

2) If you are allocating memory dynamically, you need to free memory explicitly when your work done with that (after freeing dynamically allocated memory you can't access that memory). Steps to free memory for test will be as follows:

for (i = 0; i < k; i++){
    free(test[i]);
}
free(test);

3) This is one way to allocate memory for 2D matrix as array of arrays if you wants to allocate completely continues memory for all arrays check this answer: Allocate memory 2d array in function C

4) If the description helps and you want to learn for 3D allocation Check this answer: Matrix of String or/ 3D char array

回答2:

Remember that arrays decays to pointers, and can be used as pointers. And that pointers can be used as arrays. In fact, indexing an array can be seen as a form or pointer arithmetics. For example

int a[3] = { 1, 2, 3 };  /* Define and initialize an array */
printf("a[1] = %d\n", a[1]);  /* Use array indexing */
printf("*(a + 1) = %d\n", *(a + 1));  /* Use pointer arithmetic */

Both outputs above will print the second (index 1) item in the array.

The same way is true about pointers, they can be used with pointer arithmetic, or used with array indexing.

From the above, you can think of a pointer-to-pointer-to.type as an array-of-arrays-of-type. But that's not the whole truth, as they are stored differently in memory. So you can not pass an array-of-arrays as argument to a function which expects a pointer-to-pointer. You can however, after you initialized it, use a pointer-to-pointer with array indexing like normal pointers.

回答3:

malloc is used to dynamically allocate memory to the test variable think of the * as an array and ** as an array of arrays but rather than passing by value the pointers are used to reference the memory address of the variable. When malloc is called you are allocating memory to the test variable by getting the size of an integer and multiplying by the number of ints the user supplies, because this is not known before the user enters this.

回答4:

Yes it is perfectly Ok. test is pointer to pointer and so test[i] which is equivalent to writing test + i will be a pointer. For better understanding please have a look on this c - FAQ.

回答5:

Yes indeed, int** is a pointer to a pointer. We can also say it is an array of pointers.

test = (int **) malloc(k * sizeof(int*));

This will allocate an array of k pointers first. malloc dynamically allocates memory.

test[i] = (int*) malloc(k * sizeof(int));

This is not necessary as it is enough to

test[i] = (int*) malloc(sizeof(int*));

Here we allocate each of the array places to point to a valid memory. However for base types like int this kind of allocation makes no sense. It is usefull for larger types (structs).

Each pointer can be accessed like an array and vice versa for example following is equivalent.

int a;
test[i] = &a;
(test + i) = &a;

This could be array test in memory that is allocated beginning at offset 0x10000000:

+------------+------------+
|   OFFSET   |  POINTER   |
+------------+------------+
| 0x10000000 | 0x20000000 | test[0]
+------------+------------+
| 0x10000004 | 0x30000000 | test[1]
+------------+------------+
| ...        | ...

Each element (in this example 0x2000000 and 0x30000000) are pointers to another allocated memory.

+------------+------------+
|   OFFSET   |    VALUE   |
+------------+------------+
| 0x20000000 | 0x00000001 | *(test[0]) = 1
+------------+------------+
| ...
+------------+------------+
| 0x30000000 | 0x00000002 | *(test[1]) = 2
+------------+------------+
| ...

Each of the values contains space for sizeof(int) only.

In this example, test[0][0] would be equivalent to *(test[0]), however test[0][1] would not be valid since it would access memory that was not allocted.

回答6:

For every type T there exists a type “pointer to T”.

Variables can be declared as being pointers to values of various types, by means of the * type declarator. To declare a variable as a pointer, precede its name with an asterisk.

Hence "for every type T" also applies to pointer types there exists multi-indirect pointers like char** or int*** and so on. There exists also "pointer to array" types, but they are less common than "array of pointer" (http://en.wikipedia.org/wiki/C_data_types)

so int** test declares an array of pointers which points to "int arrays"

in the line test = (int **)malloc(k*sizeof(int*)); puts enough memory aside for k amount of (int*)'s

so there are k amount of pointers to, each pointing to...

test[i] = (int*)malloc(k * sizeof(int)); (each pointer points to an array with the size of k amounts of ints)

Summary...

int** test; is made up of k amount of pointers each pointing to k amount of ints.

回答7:

int** is a pointer to a pointer of int. take a look at "right-left" rule