Unable to create a linked list matrix

Question

I am trying to convert an array to a linked list matrix. If my input is:

1 2 3
4 5 6
7 8 9

then the linked list matrix will be something of this kind:

1 -> 2 -> 3 -> NULL
|    |    |
v    v    v
4 -> 5 -> 6 -> NULL
|    |    |
v    v    v
7 -> 8 -> 9 -> NULL
|    |    |
v    v    v
NULL NULL NULL

I've tried to debug the code. I get segmentation fault error in col = col->down. But I'm unable to understand the reason behind this error. Here's the code for your reference.

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
  int data;
  struct node *next;
  struct node *down;
}matrix;
matrix *start = NULL;
void insert();
void arrToMatrix();
void arrDisplay();
void matrixDisplay();
int a[10][10];
int r,c;
int main()
{
  int n;
  printf("1:Insert elements 2:Convert Array to Linked Matrix 3:Display Array 4:Display Linked Matrix\n");
 for(;;)
 {
   printf("Enter choice: ");
   scanf("%d",&n);
   switch(n)
   {
      case 1: insert();
      break;
      case 2: arrToMatrix();
      break;
      case 3: arrDisplay();
      break;
      case 4: matrixDisplay();
      break;
      default: printf("Wrong Input\n");
      exit(0);
   }
 }
 return 0;
}

void insert()
{
  int i,j;
  printf("Enter row: ");
  scanf("%d",&r);
  printf("\nEnter column: ");
  scanf("%d",&c);
  printf("Enter elements: \n");
  for(i=0;i<r;i++)
      for(j=0;j<c;j++)
        scanf("%d",&a[i][j]);
}
void arrDisplay()
{
  int i,j;
  printf("Array elements: \n");
  for(i=0;i<r;i++)
  {
    for(j=0;j<c;j++)
    {
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
}
void arrToMatrix()
{
  int i,j;
  matrix *ptr, *col, *row;
  ptr = malloc(sizeof(matrix));
  ptr->data = a[0][0];
  ptr->next = NULL;
  ptr->down = NULL;
  start = ptr;
  col = start;
  for(i=0;i<r;i++)
  {
    row = col;
    for(j=0;j<c;j++)
    {
      ptr = malloc(sizeof(matrix));
      ptr->data = a[i][j];
      ptr->next = NULL;
      ptr->down = NULL;
      if(row == col)
        row = ptr;
      else
      {
        while(row->next!=NULL)
          row = row->next;
        row->next = ptr;
      }
    }
    col = col->down;
  }
}

void matrixDisplay()
{
  matrix *row, *col, *ptr;
  col = start;
  while(col!=NULL)
  {
    row = col;
    while(row!=NULL)
    {
      printf("%d ",row->data);
      row = row->next;
    }
    printf("\n");
    col = col->down;
  }
}

Answer 1

The assignment is not easy for a beginner.

For starters it is a bad idea when global variables like start are used and function definitions depend on global variables.

For example you can not define in your program more than one matrices.

Within the function arrToMatrix you have to deal with pointers to pointers. Otherwise the function will be more complicated or the pointer start will not be changed because changing local variables col and row in your program does not influence i=on the pointer start. And moreover for example in this code snippet

  ptr = malloc(sizeof(matrix));
  ptr->data = a[i][j];
  ptr->next = NULL;
  ptr->down = NULL;
  if(row == col)
    row = ptr;

there is a redundant allocation of a node when i is equal to 0 and j is equal to 0.

In the beginning of the function the current matrix pointed by the head pointer shall be freed. Otherwise there can be memory leaks and the user will not be able to reassign the matrix with a different array.

So you need to write one more function that free all allocated memory for the current matrix.

Here is a demonstrative program that shows how the functions can be implemented. In the program there is commented function matrixDisplay used for testing. You can run it instead of the non-commented function matrixDisplay to see how the list and its links are defined.

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

typedef struct node
{
    int data;
    struct node *next;
    struct node *down;
} matrix;

void deleteMatrix( matrix **head )
{
    if ( *head != NULL )
    {
        for ( matrix *row = ( *head )->next; row != NULL; )
        {
            while ( row != NULL )
            {
                matrix *tmp = row;
                row = row->next;
                free( tmp );
            }

            row = ( *head )->down;

            if ( ( *head )->down != NULL )
            {
                ( *head )->down = row->down;
            }
        }

        free( *head );
        *head = NULL;
    }
}

void arrToMatrix( matrix **head, size_t m, size_t n, int a[m][n] )
{
    deleteMatrix( head );

    matrix **row = head;

    for ( size_t i = 0; i < m; i++ )
    {
        matrix **column = row;

        for ( size_t j = 0; j < n; j++ )
        {
            *column = malloc( sizeof( matrix ) );
            ( *column )->data = a[i][j];
            ( *column )->down = NULL;
            ( *column )->next = NULL;

            column = &( *column )->next;    
        }

        row = &( *row )->down;
    }

    row = head;

    for ( size_t i = 0; i + 1 < m; i++ )
    {
        matrix *column   = *row;
        matrix *next_row_column = ( *row )->down;

        for ( size_t j = 0; j < n; j++ )
        {
            column->down = next_row_column;
            column = column->next;
            next_row_column = next_row_column->next;
        }           

        row = &( *row )->down;
    }
}

void matrixDisplay( const matrix *head )
{
    for ( ; head != NULL; head = head->down )
    {
        for ( const matrix *column = head; column != NULL; column = column->next )
        {
            printf( "%2d ", column->data );
        }
        putchar( '\n' );
    }
}
/*
void matrixDisplay( const matrix *head )
{
    for ( ; head != NULL; head = head->down )
    {
        for ( const matrix *column = head; column != NULL; column = column->next )
        {
            printf( "%2d ( %p ): next( %p ), down( %p )  ", 
                     column->data, ( void * )column, ( void * )column->next, ( void * )column->down );
        }
        putchar( '\n' );
    }
}
*/
int main(void) 
{
    enum { N = 3 };
    int a[][N] = 
    {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };

    matrix *head = NULL;

    arrToMatrix( &head, N, N, a );

    matrixDisplay( head );
    putchar( '\n' );

    deleteMatrix( &head );

    return 0;
}

The program output is

 1  2  3 
 4  5  6 
 7  8  9 

The output of the commented function matrixDisplay might look for example the following way.

 1 ( 0x558b577e7260 ): next( 0x558b577e7280 ), down( 0x558b577e72c0 )   2 ( 0x558b577e7280 ): next( 0x558b577e72a0 ), down( 0x558b577e72e0 )   3 ( 0x558b577e72a0 ): next( (nil) ), down( 0x558b577e7300 )  
 4 ( 0x558b577e72c0 ): next( 0x558b577e72e0 ), down( 0x558b577e7320 )   5 ( 0x558b577e72e0 ): next( 0x558b577e7300 ), down( 0x558b577e7340 )   6 ( 0x558b577e7300 ): next( (nil) ), down( 0x558b577e7360 )  
 7 ( 0x558b577e7320 ): next( 0x558b577e7340 ), down( (nil) )   8 ( 0x558b577e7340 ): next( 0x558b577e7360 ), down( (nil) )   9 ( 0x558b577e7360 ): next( (nil) ), down( (nil) )  

Answer 2

Nice exercise. I have a solution using the approach of a static matrix of pointers. You can allocate it dynamically the same way, but just to get an idea.

So, here we go:

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
  int data;
  struct node *next;
  struct node *down;
} matrix;

matrix *start = NULL;

#define MAX_DIM 10

matrix ptrMatrix[MAX_DIM][MAX_DIM];

void insert();
void arrToMatrix();
void arrDisplay();
void matrixDisplay();

int a[MAX_DIM][MAX_DIM];
int r,c;

int main()
{
  int n;
 for(;;)
 {
   printf("1:Insert elements 2:Convert Array to Linked Matrix 3:Display Array 4:Display Linked Matrix\n");
   printf("Enter choice: ");
   scanf("%d",&n);
   switch(n)
   {
      case 1: insert();
      break;
      case 2: arrToMatrix();
      break;
      case 3: arrDisplay();
      break;
      case 4: matrixDisplay();
      break;
      default: printf("Wrong Input\n");
      exit(0);
   }
 }
 return 0;
}

void insert()
{
  int i,j;
  printf("Enter number of rows: ");
  scanf("%d",&r);
  printf("\nEnter number of columns: ");
  scanf("%d",&c);

  if(r >= MAX_DIM)
  {
      printf("\nNo more than %d rows please!\n");
      return;
  }

  if(c >= MAX_DIM)
  {
      printf("\nNo more than %d columns please!\n");
      return;
  }

  printf("\n Now enter the elements (%d number in total): \n", r*c);
  for(i=0;i<r;i++)
  {
      for(j=0;j<c;j++)
      {
        scanf("%d",&a[i][j]);
      }
  }
}
void arrDisplay()
{
  int i,j;
  printf("Array elements: \n");
  for(i=0;i<r;i++)
  {
    for(j=0;j<c;j++)
    {
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }
}
void arrToMatrix()
{
  if(r<=0 || c <=0)
  {
      printf("Matrix is empty. Try again!\n");
      return;
  }

  int i,j;

  for(i=0;i<r-1;i++)
  {
      for(j=0;j<c-1;j++)
      {
        ptrMatrix[i][j].data = a[i][j];
        ptrMatrix[i][j].next = &ptrMatrix[i][j+1];
        ptrMatrix[i][j].down = &ptrMatrix[i+1][j];
      }

      ptrMatrix[i][c-1].data = a[i][c-1];
      ptrMatrix[i][c-1].next = NULL;
      ptrMatrix[i][c-1].down = &ptrMatrix[i+1][c-1];
  }

  for(j=0;j<c-1;j++)
  {
    ptrMatrix[r-1][j].data = a[r-1][j];
    ptrMatrix[r-1][j].next = &ptrMatrix[r-1][j+1];
    ptrMatrix[r-1][j].down = NULL;
  }

  ptrMatrix[r-1][c-1].data = a[r-1][c-1];
  ptrMatrix[r-1][c-1].next = NULL;
  ptrMatrix[r-1][c-1].down = NULL;

  start = &(ptrMatrix[0][0]);
}

void matrixDisplay()
{
  matrix *row, *col;
  col = start;
  while(col!=NULL)
  {
    row = col;
    while(row!=NULL)
    {
      printf("%d ",row->data);
      row = row->next;
    }
    printf("\n");
    col = col->down;
  }
}

Answer 3

ptr->down is always NULL in your case. it is never initialised. so col=col->down is assigning the value NULL to col