0

(I edited the programm since I was asked for a Minimum Reproducible Example) I have to build a dinamically linked list (specifically), each node having a value of the type float and it's location (row and column) in a sparce matrix. The matrix itself doesn't have a defined size, so I have to find it to print the matrix with the values in a format like:

0.0  0.0  3.0
1.0  0.0  0.0  
0.0  0.0  0.0  

The value is zero if it's not in the list, otherwise, I have to print it's value in the corresponding location from the "node->row" and "node->col" data from it's node.

Until now, I have tryed to find the size by searching the list with two functions, one for finding the biggest row value, another for finding the biggest column value:

/*
Matrix is defined as:
typedef struct node* Matrix;
in .h file
*/
struct node{
    float value;
    int row, col;
    struct node *next;
};

typedef struct node node;

Matrix* create_matrix(){
    Matrix* m = (Matrix*) malloc(sizeof(Matrix));
    *m = NULL;
    return m;
}

void free_matrix(Matrix* m){
    if(m != NULL){
        node *n;
        while((*m != NULL)){
            n = *m;
            *m = (*m)->next;
            free(n);
        }
        free(m);
    }
}

/*int size_r(Matrix* m){
    if(empty_matrix(m)) return 0;
    int r = 0;
    node *n = *m;
    while(n != NULL){
        if(n->row > r){
            r = n->row;
        }
        n = n->next;
    }
    return r;
}

int size_c(Matrix* m){
    if(empty_matrix(m)) return 0;
    int c = 0;
    node *n = *m;
    while(n != NULL){
        if(n->col >= c)
            c = n->col;
        n = n->next;
    }
    return c;
}*/

//The size functions are commented since I have been trying
//to implement their method inside the new print_matrix

int empty_matrix(Matrix *m){
    if(m == NULL) return 1;
    if(*m == NULL) return 1;
    return 0;
}

int insert_value(Matrix *m, float d, int r, int c){
    if(m == NULL) return 0;
    node *n = (node*) malloc(sizeof(node));
    if(n == NULL) return 0;
    n->value = d;
    n->row = r;
    n->col = c;
    n->next = *m;
    *m = n;
    return 1;
}

/*
//I thought this one was working, but after testing around, it returns 1
//even if only row or column matches the argument

int verify_position(Matrix *m, int r, int c){
    if(empty_matrix(m)) return 0;
    if(r < 0 || c < 0) return 1;
    node *n = *m;
    while(n != NULL && n->row != r && n->col != c){
        n = n->next;
    }
    if(n == NULL) return 0;
    else{
        return 1;
    }
}*/

/*int print_matrix(Matrix* m){
    if(empty_matrix(m)) return 0;
        int sr = size_r(m), sc = size_c(m);
        float matrix [sl][sc];
        for(int i = 0; i <= sr; i++){
            for(int j = 0; j <= sc; j++){
                node *n = *m;
                while(n != NULL && n->row != r && n->col != c){
                    n = n->next;
                }
                if(n == NULL)
                    matrix[i][j] = 0.f;
                else
                    matrix[i][j] = n->value;
                
                printf("%2.f ",matrix[i][j]);
            }
            printf("\n");
        }

    return 1;
}*/

int print_matrix(Matrix* m){
    if(empty_matrix(m)) return 0;
    int r = 0, c = 0;
    node *n = *m;
    while(n != NULL){
        if(n->row > r)
            r = n->row;
        if(n->col > c)
            c = n->col;
        n = n->next;
    }
    float matrix [r][c];
    for(int i = 0; i <= r; i++){
        for(int j = 0; j <= c; j++){
            node *aux = *m;
            while(aux != NULL && aux->row != i && aux->col != j){
                aux = aux->next;
            }
            if(aux == NULL)
                matrix[i][j] = 0.f;
            else{
                matrix[i][j] = aux->value;
            }
            printf("%2.f ",matrix[i][j]);
        }
        printf("\n");
    }
    return 1;
}

int dump_matriz(const char *tag, const Matriz *m) {
    printf("%s (%p):\n", tag, m);
    if (m == NULL) return;
    node *n = *m;
    while (n != NULL) {
        printf("\n%p: [%d][%d] = %f\n", (void*)n, n->row, n->col, n->value);
        n = n->next;
    }
    return 1;
}

When I try my printing function in the console, it just closes it. If I try using the size functions, the return value is never one of the rows or columns. After using the dump_matrix, suggested in a comment, it printed:

Result:
 (00000000006F16E0):

00000000006F19A0: [1073741824][1073741824] = 1091567616.000000

00000000006F1950: [1073741824][1065353216] = 1090519040.000000

00000000006F1900: [1073741824][0] = 1088421888.000000

00000000006F18B0: [1065353216][1073741824] = 1086324736.000000

00000000006F1860: [1065353216][1065353216] = 1084227584.000000

00000000006F1810: [1065353216][0] = 1082130432.000000

00000000006F17C0: [0][1073741824] = 1077936128.000000

00000000006F1770: [0][1065353216] = 1073741824.000000

00000000006F1720: [0][0] = 1065353216.000000

for values 1 through 9 in a 3x3 matrix.

  • 1
    Q: How do I find the size of a matrix from a linked list? A: You need to tell it. If this were C++, you'd design a "Matrix" class. Since you're programming in C, you'd instead design a "Matrix" struct. In any case, your struct would have a) #/rows, b) #/columns, c) a pointer to your list head, d) any other "essential" data needed for your implementation. – paulsm4 Nov 13 '21 at 23:27
  • If lists are required, then I personally I would use nested lists: One list for the rows, and each row then have one list for its columns. And as mentioned by @paulsm4 have a top-level structure for the matrix itself, containing the number of rows and columns. Using nested lists like this also allows for non-uniform rows, where each row could have different number of columns. – Some programmer dude Nov 13 '21 at 23:36
  • 1
    Style guide: do not put a semicolon after the close brace of a function definition. It corresponds to an empty declaration and compilers might well warn about that. – Jonathan Leffler Nov 13 '21 at 23:38
  • You seem to be working with sparse matrices. You can deduce the minimum size of the array by determining the maximum recorded row and column value. You cannot tell if there are any rows with all zeros after the last row with a non-zero value, not if there are any columns with all zeros after the last column with a non-zero value. – Jonathan Leffler Nov 13 '21 at 23:43
  • Yes, @JonathanLeffler, I'm working with a sparse matrix and I need to save it's values specifically in a dinamically linked list. As for "You can deduce the minimum size of the array by determining the maximum recorded row and column value", I believe that's what I'm trying to do with the "size_r" and "size_c" from the post, so I guess we both thought of the same thing. My problem is that both "size" functions don't work properly, neither does the "print_matrix" function that needs them. – Pietro Giacomitti Nov 14 '21 at 14:57
  • If your `size_r()` and `size_c()` functions are not working correctly, I want to see the data that is in the linked list of entries — `static inline void dump_matrix(const char *tag, const Matrix *matrix) { printf("%s (%p):\n", tag, matrix); if (matrix == NULL) return; struct node *n = *m; while (node != NULL) { printf("%p: [%d][%d] = %g\n", (void *)n, n->row, n->col, n->value); n = n->next; }`. I observe that there is no visible `typedef struct node node;` definitio, nor a `struct Matrix` definition, so I used `struct node` rather than just `node` for the type. Be wary of compiling as C++. – Jonathan Leffler Nov 14 '21 at 15:27
  • You say that the `create_matrix` and `insert_node` functions are known to work. As soon as I see that, I begin to suspect those functions. The `free_matrix` function is not immediately relevant; I don't know whether the `position_validation` function is relevant. If you have a `struct Matrix` containing some data, you could perhaps store the matrix size too, determining it as you go. This could help if there are rows or columns of trailing zeros. – Jonathan Leffler Nov 14 '21 at 15:31
  • @JonathanLeffler. I tryed your "dump_matrix()", passing "Result:\n" and the matrix m as arguments after inserting value 21 at row 1, column 2. It printed Result: (00000000000A16E0): 00000000000A1720: [1065353216][1073741824] = 1101529088.000000 – Pietro Giacomitti Nov 14 '21 at 15:56
  • We need to see a [mcve]. – Jonathan Leffler Nov 14 '21 at 15:57
  • Values 1 - 9 in a 3x3 matrix `Result: (00000000009D16E0): 00000000009D19A0: [1073741824][1073741824] = 1091567616.000000 00000000009D1950: [1073741824][1065353216] = 1090519040.000000 00000000009D1900: [1073741824][0] = 1088421888.000000 00000000009D18B0: [1065353216][1073741824] = 1086324736.000000 00000000009D1860: [1065353216][1065353216] = 1084227584.000000 00000000009D1810: [1065353216][0] = 1082130432.000000 00000000009D17C0: [0][1073741824] = 1077936128.000000 00000000009D1770: [0][1065353216] = 1073741824.000000 00000000009D1720: [0][0] = 1065353216.000000` – Pietro Giacomitti Nov 14 '21 at 16:08
  • 1
    The updated code is a bit helpful, but you don't show how you're using the code — it is not an MCVE ([Minimal, Complete, Verifiable Example](https://stackoverflow.com/help/mcve) — or MRE or whatever name SO now uses) or an SSCCE ([Short, Self-Contained, Correct Example](http://sscce.org/)) — the same idea by a different name. We are also missing the data that you're using to create the matrix. That means we have to write extra code to debug your code, and we probably won't make the same mistakes you're making. Please read what it means to create an MCVE. – Jonathan Leffler Nov 15 '21 at 14:16
  • [Is it a good idea to typedef pointers?](https://stackoverflow.com/q/750178/15168). TL;DR — the answer is "No", with the possible exception of pointers to functions. – Jonathan Leffler Nov 15 '21 at 14:20
  • I note that your sample matrix has a row of zeros at the bottom; if none of those zeros is represented in the list, you're never going to know how big the matrix is — unless it is known to be a square matrix, in which case you don't need two functions to determine its size. – Jonathan Leffler Nov 15 '21 at 14:22

1 Answers1

0

After a few hours, I've managed to fix the code. I'm gonna leave the updated code here, just in case someone else run into this same problem (kinda unlikely, since it's an assignment from university and I'm from another country, so even if someone else from my university has the same assignment, it's unlikely they'll search for help in English). Also, keep in mind that English isn't my first language and that I'm translating the code so it's easier to understand.

/*
matrix from .h file
typedef struct node* Matrix;
*/

struct node{
    float value;
    int row, col;
    struct node *next;
};

typedef struct node node;

Matrix* new_matrix(){
    Matrix* m = (Matrix*) malloc(sizeof(Matrix));
    if(m != NULL) *m = NULL;
    return m;
}

void free_matrix(Matrix* m){
    if(m != NULL){
        struct node* n;
        while((*m != NULL)){
            n = *m;
            *m = (*m)->next;
            free(n);
        }
        free(m);
    }
}

int size_c(Matrix* m){
    if(empty_matrix(m)) return 0;
    int c = 0;
    struct node *n = *m;
    while(n != NULL){
        if(n->col >= c)
            c = n->col;
        n = n->next;
    }
    return c;
}

int size_r(Matrix* m){
    if(empty_matrix(m)) return 0;
    int r = 0;
    struct node *n = *m;
    while(n != NULL){
        if(n->row >= r)
            r = n->row;
        n = n->next;
    }
    return r;
}

int empty_matrix(Matrix *m){
    if(m == NULL) return 1;
    if(*m == NULL) return 1;
    return 0;
}

int insert_value(Matrix *m){
    if(m == NULL) return 0;
    struct node *n = (node*) malloc(sizeof(node));
    do{
        printf("\n\tValue to be inserted: ");
        scanf("%f", &n->value);
        if(n->value == 0.0f)    //My assignment specified that I couldn't allow 0 as a valid entry for the sparse matrix, sice most of its values are already 0.
            printf("\n\tInvalid entry: %.1f\n", n->value);
    }while(n->value == 0.0f);
    printf("\n\tRow coordenate: ");
    scanf("%d", &n->row);
    printf("\n\tColumn coordenate: ");
    scanf("%d", &n->col);
    if(verify_position(m, n->row, n->col) != 0){
        printf("\n\tCoordenate already in use!\n");
        return 0;
    }else{
        if(*m == NULL) n->next = NULL;
        else n->next = *m;
        *m = n;
        printf("\n\tValue %.2f inserted in [%d][%d].\n", n->value, n->row, n->col);
        return 1;
    }
}

int verify_position(Matrix *m, int r, int c){
    if(empty_matrix(m)) return 0;
    struct node *n = *m;
    while(n != NULL && (n->row != r || n->col != c)){
        n = n->next;
    };
    if(n == NULL) return 0;
    else{
        return 1;
    }
}

int print_matrix(Matrix* m){
    if(empty_matrix(m)) return 0;
        int sr = size_r(m), sc = size_c(m);
        float mat[sr][sc];
        for(int i = 0; i <= sr; i++){
            for(int j = 0; j <= sc; j++){
                struct node *n = *m;
                while(n != NULL && (n->row != i || n->col != j)){
                    n = n->next;
                }
                if(n == NULL)
                    mat[i][j] = 0.f;
                else{
                    mat[i][j] = n->value;
                }
                printf("\t%.2f",mat[i][j]);
            }
            printf("\n\n");
        }

    return 1;
}

Since someone asked for the main() so they could have a Minimal, Complete, Verifiable Exemple:

int main(){
    Matrix *m;
    m = new_matrix();
    int opt = 0;

    printf("1 - Insert value into the sparce matrix\n2 - Delete sparse matrix");
    printf("\n3 - Print sparce matrix\n4 - Exit");

    do{
        printf("\nOption: ");
        scanf("%d", &opt);
        switch(opt){
            case 1:
                insert_value(m);
                break;
            case 2:
                free_matrix(m);
                break;
            case 3:
                printf("\n");
                print_matrix(m);
                break;
            case 4:
                break;
            default: printf("\n\tInvalid option!\n");
        }
    }while(opt != 4);
    free_matrix(m);
    return 0;
}
  • When I create a 2-row, 3-column matrix like the sample data, printing works correct. I freed the matrix; I then printed again and it produced nothing — OK. I then exited the loop and got a memory error `malloc: *** error for object 0x7fe8bbc05850: pointer being freed was not allocated`. That's not great. Although the exit works OK if I add `m = NULL;` after the `free_matrix(m);` in the loop, I can't add any more entries. It seems that using `m = new_matrix();` after the call to `free_matrix()` in the loop does allow things to work correctly. I've not run [Valgrind](http://valgrind.org). – Jonathan Leffler Nov 16 '21 at 19:49
  • Thanks for the heads-up. I will updated the new_matrix() function in the code so that *m is only NULL if m isn't. If that doesn't fix the allocation error, then I don't know what else could be wrong. – Pietro Giacomitti Nov 19 '21 at 18:12