How do you dynamically allocate a matrix?
A matrix is actually can be represented as an array of arrays.
int rows = ..., cols = ...;
int** matrix = new int*[rows];
for (int i = 0; i < rows; ++i)
matrix[i] = new int[cols];
Of course, to delete the matrix, you should do the following:
for (int i = 0; i < rows; ++i)
delete [] matrix[i];
delete [] matrix;
I have just figured out another possibility:
int rows = ..., cols = ...;
int** matrix = new int*[rows];
if (rows)
{
matrix[0] = new int[rows * cols];
for (int i = 1; i < rows; ++i)
matrix[i] = matrix[0] + i * cols;
}
Freeing this array is easier:
if (rows) delete [] matrix[0];
delete [] matrix;
This solution has the advantage of allocating a single big block of memory for all the elements, instead of several little chunks. The first solution I posted is a better example of the arrays of arrays concept, though.
How to dynamically allocate a matrix in C?
in deserialize, you should return M, not **M:
int** deserialize(int* L,int n){
int** M;
//....
return M;
}
Also, you need to declare the functions before calling them. Before main add:
int* serialize(int** M,int n);
int** deserialize(int* L,int n);
allocate matrix in C
Well, you didn't give us a complete implementation. I assume that you meant.
int **mat = (int **)malloc(rows * sizeof(int*));
for(int i = 0; i < rows; i++) mat[i] = (int *)malloc(cols * sizeof(int));
Here's another option:
int *mat = (int *)malloc(rows * cols * sizeof(int));
Then, you simulate the matrix using
int offset = i * cols + j;
// now mat[offset] corresponds to m(i, j)
for row-major ordering and
int offset = i + rows * j;
// not mat[offset] corresponds to m(i, j)
for column-major ordering.
One of these two options is actually the preferred way of handling a matrix in C. This is because now the matrix will be stored contiguously in memory and you benefit from locality of reference. Basically, the CPU cache will a lot happier with you.
How to dynamically allocate the memory for multi dimensional arrays
You have not SegFaulted only by happy accident, and due to the fact that the size of a pointer doesn't change. So where you allocate for int* where you should be allocating for int**, the size of your allocation isn't affected (by happy accident...)
You generally want to avoid becoming a 3-Star Programmer, but sometimes, as in this case, it is what is required. In allocating for any pointer, or pointer-to-pointer, or in this case a pointer-to-pointer-to-pointer, understand there is no "array" involved whatsoever.
When you declare int ***array; you declare a single pointer. The pointer then points to (holds the address of) a block of pointers (type int**) that you allocate. You allocate storage for matricies number of int** pointers as input by the user.
Each matrix is type int**, so you must allocate a block of memory containing rows number of pointer for each matrix.
Finally you allocate cols number of int (type int*) for each and every row in each and every matrix.
So your collection of matricies is an allocated block of pointers with one pointer for each matrix. Then each matrix is an allocate block of pointers with one pointer for every row in that matrix. Finally you allocate a columns worth of int for each an every row pointer for each and every matrix.
Visually your allocation and assignment would resemble the following:
array (int***)
|
+ allocate matricies number of [Pointers]
|
+----------+
| array[0] | allocate rows number of [Pointers] for each matrix
+----------+ assign to each pointer in array block
| array[1] |
+----------+ array[2] (int**)
| array[2] | <======= +-------------+
+----------+ | array[2][0] |
| .... | +-------------+ allocate cols no. of [int]
| array[2][1] | for each allocated row pointer
+-------------+
| array[2][2] | <=== array[2][2] (int*)
+-------------+ +----------------+
| ... | | array[2][2][0] |
+----------------+
| array[2][2][1] |
+----------------+
| array[2][2][2] |
+----------------+
| ... |
In order to always keep the type-size of each allocation correct, simply use the dereferenced pointer to set the type-size. For example when allocating for array (int***) you would use:
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
When allocating for each array[i], you would use:
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
Finally when allocating for each block of int for each row, every array[i][j], you would use:
array[i][row] = malloc (cols * sizeof *array[i][row]);
If you always use the dereference pointer to set type-size, you will never get it wrong.
Following the diagram above through and just taking each allocation in turn (and validating EVERY allocation), you could write your allocation and free routines similar to:
/* use dereferenced pointer for type-size */
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
if (!array) { /* validate EVERY allocation */
perror ("malloc-array");
return 1;
}
for (int i = 0; i < matrix; i++) {
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
if (!array[i]) { /* validate */
perror ("malloc-array[i]");
return 1;
}
for (int row = 0; row < rows; row++) {
/* allocate cols int per-row in each matrix */
array[i][row] = malloc (cols * sizeof *array[i][row]);
if (!array[i][row]) {
perror ("malloc-array[i][row]");
return 1;
}
}
}
The complete example that allocates for the number of matricies with the number of rows and columns entered by the user would be:
#include <stdio.h>
#include <stdlib.h>
int main (void) {
int ***array = NULL,
matrix,
rows,
cols;
fputs ("no. of matricies: ", stdout);
if (scanf ("%d", &matrix) != 1) /* validate EVERY input */
return 1;
fputs ("no. of rows : ", stdout);
if (scanf ("%d", &rows) != 1) /* ditto */
return 1;
fputs ("no. of cols : ", stdout);
if (scanf ("%d", &cols) != 1) /* ditto */
return 1;
/* use dereferenced pointer for type-size */
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
if (!array) { /* validate EVERY allocation */
perror ("malloc-array");
return 1;
}
for (int i = 0; i < matrix; i++) {
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
if (!array[i]) { /* validate */
perror ("malloc-array[i]");
return 1;
}
for (int row = 0; row < rows; row++) {
/* allocate cols int per-row in each matrix */
array[i][row] = malloc (cols * sizeof *array[i][row]);
if (!array[i][row]) {
perror ("malloc-array[i][row]");
return 1;
}
}
}
/* fill matricies with any values */
for (int i = 0; i < matrix; i++)
for (int j = 0; j < rows; j++)
for (int k = 0; k < cols; k++)
array[i][j][k] = j * cols + k + 1;
/* display each matrix and free all memory */
for (int i = 0; i < matrix; i++) {
printf ("\nmatrix[%2d]:\n\n", i);
for (int j = 0; j < rows; j++) {
for (int k = 0; k < cols; k++)
printf (" %2d", array[i][j][k]);
putchar ('\n');
free (array[i][j]); /* free row of int (int*) */
}
free (array[i]); /* free matrix[i] pointers (int**) */
}
free (array); /* free matricies pointers (int***) */
}
(note: you free the memory for each block of int before freeing the memory for the block of row pointers in each matrix before freeing the block of pointers to each matrix)
Example Use/Output
$ ./bin/allocate_p2p2p
no. of matricies: 4
no. of rows : 4
no. of cols : 5
matrix[ 0]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 1]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 2]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 3]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
Memory Use/Error Check
In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.
It is imperative that you use a memory error checking program to ensure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.
For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.
$ valgrind ./bin/allocate_p2p2p
==9367== Memcheck, a memory error detector
==9367== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9367== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9367== Command: ./bin/allocate_p2p2p
==9367==
no. of matricies: 4
no. of rows : 4
no. of cols : 5
matrix[ 0]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 1]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 2]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 3]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
==9367==
==9367== HEAP SUMMARY:
==9367== in use at exit: 0 bytes in 0 blocks
==9367== total heap usage: 23 allocs, 23 frees, 2,528 bytes allocated
==9367==
==9367== All heap blocks were freed -- no leaks are possible
==9367==
==9367== For counts of detected and suppressed errors, rerun with: -v
==9367== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Always confirm that you have freed all memory you have allocated and that there are no memory errors.
Look things over and let me know if you have further questions.
Dynamic allocation of an unknown matrix in C
My recommendation is to consider your matrix as having some abstract data type that you want to implement.
A common way might be to use an array of pointers (to arrays representing rows of your matrix). But I feel it is confusing and inefficient.
So what are the operations you want on your matrixes?
create a matrix of given dimensions
destroy a previously created matrix
access some element in a given matrix with given row and column indexes
change the value of an element in a given matrix with given row and column indexes
etc....
BTW, you might have several variants of them. For example, you could do error checking (e.g. reject a negative index) or you could have unsafe (but slightly faster) functions capable of undefined behavior (and this is very scary). Of course you could define more operations (using other ones), for example matrix multiplication etc.
You should list -on paper or board- all the operations you want on your matrixes and explain them in your documentation (or your comments). In practice you might have many dozens -or even hundreds- of operations on your abstract data type. Document also what happens in error cases.
I usually recommend keeping the dimensions with the matrix (unless you know that some of the dimension is a constant). A common way of implementing abstract data types in C is to encapsulate them in some struct and use pointers to these.
So I suggest to use a flexible array member (as the last element of your struct). Here is my matrix_st structure:
struct matrix_st {
unsigned m_h, m_w; // height and width of matrix
double m_v[]; // values inside the matrixes, there are m_h*m_w of them
};
so my abstract data type is just pointers to
typedef struct matrix_st Matrix;
Here are the declarations of the functions implementing my abstract data type:
Matrix* matrix_create(unsigned height, unsigned width);
void matrix_destroy(Matrix*mat);
double matrix_access(Matrix*mat, unsigned i, unsigned j);
void matrix_change_element(Matrix*mat, unsigned i, unsigned j,double v);
Here are some implementations (since I don't want to deal with pathologically huge matrixes, I define some maximal dimension; computer resources are always finite!):
#define MATRIX_MAXDIM 10000000 /* ten millions */
Matrix* matrix_create(unsigned height, unsigned width) {
if (height>MATRIX_MAXDIM || width>MATRIX_MAXDIM) {
fprintf(stderr, "too huge matrix height=%u width=%u\n",
height, width);
exit(EXIT_FAILURE);
};
Matrix* res =
calloc(1, sizeof(Matrix) + height*width*sizeof(double));
if (!res) {
perror("matrix calloc");
exit(EXIT_FAILURE);
};
res->m_h = height;
res->m_w = width;
return res;
} // end matrix_create
I am using calloc not malloc because I really want some zero-ed memory. So the returned matrix contains all zeros. BTW on some computers (not mine, a PC/Linux/Debian/x86-64 desktop) the height*width*sizeof(double) could overflow.
Here is the function to access some element. It does some error checking.
double matrix_access(Matrix*mat, unsigned i, unsigned j)
{
if (!mat)
{ fprintf(stderr, "no matrix to access\n"); exit(EXIT_FAILURE; };
unsigned h = mat->m_h;
unsigned w = mat->m_w;
if (i >= h || j >= w)
{ fprintf(stderr, "out-of-bound matrix access\n");
exit(EXIT_FAILURE); };
return mat->m_v [i*h + j];
}
Since I made only one calloc the destruction is simple to code:
void matrix_destroy(Matrix*mat) {
if (!mat) { fprintf(stderr, "no matrix to destroy\n"); exit(EXIT_FAILURE); };
assert (mat->m_h < MATRIX_MAXDIM);
assert (mat->m_w < MATRIX_MAXDIM);
free (mat);
}
The assert statements are in principle useless (they check something which should always be true). But I love defensive programming (this would help me catching bugs in some other places misusing my Matrix). They could be disabled (read assert(3)) at compilation time.
BTW, you could declare these functions as inline or static inline (and define them in some included header file). An optimizing compiler is likely to produce efficient code (e.g. compile with gcc -O2 -Wall -march=native when benchmarking).
Since you are reading a matrix from some file, you should define your file format (using, in your documentation, some EBNF notation to describe the syntax in that file is useful) and you could define and implement a function reading and creating a matrix from some opened file handle.
Coding the other functions is left as an exercise to the reader.
Don't forget to compile with all warnings and debug info, so gcc -Wall -Wextra -g with GCC. Use the debugger gdb (and also valgrind to hunt memory leaks). Read the documentation of every used function (for example your code don't check the return count of scanf but it really should). Run several test cases. Try to convince yourself that your code is good (by proving parts of it). Perhaps use some static source code analyzer (e.g. Frama-C, which wants extra annotations in ACSL). If you need to benchmark your program, enable optimizations at compile time (e.g. by passing -O2 -march=native to gcc ....).
In a code comment you are asking:
// I need to now dynamically allocate the input files
You don't allocate input files (the operating system is managing them), you allocate some memory zone. Read about C dynamic memory allocation. Notice that memory allocation can fail (e.g. as documented in malloc(3)), because your virtual address space cannot grow indefinitely.
BTW, the call stack is limited (typically to a megabyte or a few of them on desktop computers), so you generally want to avoid large automatic variables, so that is another good reason to avoid putting matrixes in your call frame and to prefer dynamic memory allocation for them.
How can I dynamically allocate 2D-array in one allocate C
How can i to allocate dynamically array2D in 1 allocate C
Let us start with what is a 2D array:
Example of a 2D array or "array 3 of array 4 of int"
int arr1[3][4];
arr1[0][0] = this;
OP's code declares a pointer to pointer to int, not a 2D array nor a pointer to a 2D array.
BTW, the cast in not needed.
int** arr = (int**)malloc(num * num * sizeof(int*));
Code can allocate memory for a 2D array and return a pointer to that memory. pointer to array 5 of array 6 of int
int (*arr2)[5][6] = malloc(sizeof *arr2);
if (arr2 == NULL) return EXIT_FAILURE;
(*arr2)[0][0] = this;
return EXIT_SUCCESS;
// or with Variable Length Arrays in C99 and optionally in C11
int (*arr3)[num][num] = malloc(sizeof *arr3);
(*arr3)[0][0] = that;
Alternatively code can allocate memory for a 1D array and return a pointer to that memory. pointer to array 8 of int. Sometimes this is often what one wants with with an "allocate 2D" array, really a pointer to a 1D array
int (*arr4)[8] = malloc(sizeof *arr4 * 7);
arr4[0][0] = this;
// or
int (*arr5)[num] = malloc(sizeof *arr5 * num);
arr5[0][0] = that;
Dynamically allocate a string matrix in C
char ***map; could be interpreted as an "Array of arrays of strings", so the inner array actually contains char pointers. Therefore, your loop needs to look like this:
for(i = 0; i < ROWS; i++) {
int j;
map[i] = malloc(COLS * sizeof(char*));
for(j = 0; j < COLS; j++) map[i][j] = malloc(3 * sizeof(char)); // 3 chars because a string has to be terminated by \0
}
Alternatively, you could declare map as char **map, then your initialization code would work, but then you'd need to use map[i][j] and map[i][j+1] to access the elements of the individual cells.
Related Topics
How to Check If the Input Is a Valid Integer Without Any Other Chars
How to Tell Where a Header File Is Included From
How to Use _Crt_Secure_No_Warnings
Programmatically Reading a Web Page
C++ Inheritance - Inaccessible Base
How to Use Createthread for Functions Which Are Class Members
Is Std::Vector Memory Freed Upon a Clear
Implicit Conversion from Char** to Const Char**
Error: Cannot Bind Non-Const Lvalue Reference of Type 'Int&' to an Rvalue of Type 'Int'
How to Validate Input Using Scanf
Pimpl Idiom VS Pure Virtual Class Interface
How to Convert Cstring and Std::String Std::Wstring to Each Other
Pointer-To-Pointer Dynamic Two-Dimensional Array
Cmake Unable to Determine Linker Language with C++
Openmp Set_Num_Threads() Is Not Working
Why Isn't C/C++'s "#Pragma Once" an Iso Standard
How to Read Output from Cmd.Exe Using Createprocess() and Createpipe()