title: Creating a sparse matrix using linked lists in C
body: <p>I have an assignment which is to create two sparse matrices (A and B) and then adding them up into a third sparse matrix (C). I have already done it with vectors (receiving two sparse vectors and adding them into a third) so I decided it would be easier to use a series of vectors to represent a matrix. In the future, I may need to do it without vectors but with an actual matrix (I even have a psuedo-code of a function that inserts a number into a sparse matrix), so do understand <strong>why</strong> I'm asking all of this, even though the following code <strong>somewhat</strong> works.</p>
  
  <p>Because it is a matrix, it has two arrays <strong>of pointers</strong> that are the row array and column array. each cell of the array is pointing to the respective line/column. It is as in the picture below:</p>
  
  <p><img src="https://i.stack.imgur.com/TMf3x.jpg" alt="the numbers represent {row,column,data"></p>
  
  <p>Being a sparse matrix, where there are zeroes, you see those arrows as those nodes that have zeroes with them do not exist.</p>
  
  <p>To simplfy the problem, I prefer to only address the array of rows, which, as seen in the image, are pointing to the heads of each new row. Assume each line is a vector C (like I said above, I want to represent the matrix with a series of vectors).</p>
  
  <p>This is the code of all of the linked list functions I built:</p>
  
  <pre><code>typedef struct List_node
  {
      int key;
      int i,j;
      struct List_node *next;
  }List_node;
  
  typedef struct List
  {
      List_node *head;
  }List;
  
  List *create_list()
  {
      List *list = (List*)malloc(sizeof(List));
      list-&gt;head = NULL;
      return list;
  }
  
  void insert_first(List_node *x, List *list)
  {
      x-&gt;next = list-&gt;head;
      list-&gt;head = x;
  }
  
  void insert(List_node *x, List_node *y)
  {
      x-&gt;next = y-&gt;next;
      y-&gt;next = x;
  }
  
  List_node *mk_node(int data, int row, int col)
  {
      List_node *node = (List_node *)malloc(sizeof(List_node));
      node-&gt;key = data;
      node-&gt;i = row + 1;
      node-&gt;j = col + 1;
      return node;
  }
  
  void delete_list(List *list) 
  {
      List_node *node, *temp;
      node = list-&gt;head;
      while (node != NULL) 
      {
          temp = node-&gt;next;
          free(node);
          node = temp;
      }
      free(list);
  }
  
  void print_list(List *list, char name)
  {
      List_node *p;
      p = list-&gt;head;
      printf("\nThe linked list %c consists of: ",name);
      while (p != NULL)
      {
          printf("%d(i = %d) (j = %d) ", p-&gt;key, p-&gt;i, p-&gt;j);
          p = p-&gt;next;
      }
      printf("\n");
  }
  </code></pre>
  
  <p>This is the code that creates the vectors:</p>
  
  <pre><code>List *Create_vector (List *A, List *B, int i, int m)
  {
      int l,flag = 0;
      List *C;
      List_node *node=NULL, *next, *Pointer_A, *Pointer_B;
      C = create_list();
      Pointer_A = A-&gt;head;
      Pointer_B = B-&gt;head;
  
      for (l = 0; l&lt;m; l++)
      {
          if ((Pointer_A-&gt;key + Pointer_B-&gt;key) != 0)
          {
              if (flag == 0)
              {
                  node = mk_node(Pointer_A-&gt;key + Pointer_B-&gt;key, i,l);
                  insert_first(node, C);
                  flag = 1;
              }
              else
              {
                  next = mk_node(Pointer_A-&gt;key + Pointer_B-&gt;key, i,l);
                  insert(next, node);
                  node = next;
              }
          }
          Pointer_A = Pointer_A-&gt;next;
          Pointer_B = Pointer_B-&gt;next;
      }
      return C;
  }
  </code></pre>
  
  <p>And this is the main program:</p>
  
  <pre><code>void main()
  {
      List_node *Row_A, *Row_B, *Row_C;
  
      List *A, *B, *C;
      List_node *node, *next;
      int data, m,n,l;
      printf("Enter list row\n");
      scanf("%d", &amp;m);
  
      Row_A = (List_node*)malloc(sizeof(int)*(m));
      Row_B = (List_node*)malloc(sizeof(int)*(m));
      Row_C = (List_node*)malloc(sizeof(int)*(m));
  
      printf("Enter list columns\n");
      scanf("%d", &amp;n);
  
      for (int i=0; i&lt;m; i++)
      {
  
          A = create_list();
          B = create_list();
  
          printf("\nInsert first number into A\n");
          scanf("%d", &amp;data);
          node = mk_node(data, i,0);
          insert_first(node, A);
          for (l = 1; l&lt;n; l++)
          {
              printf("Now insert the rest of the numbers\n");
              scanf("%d", &amp;data);
              next = mk_node(data, i,l);
              insert(next, node);
              node = next;
          }
          print_list(A,'A');
  
          printf("\nInsert first number into B\n");
          scanf("%d", &amp;data);
          node = mk_node(data,i,0);
          insert_first(node, B);
          for (l = 1; l&lt;n; l++)
          {
              printf("Now insert the rest of the numbers\n");
              scanf("%d", &amp;data);
              next = mk_node(data, i,l);
              insert(next, node);
              node = next;
          }
          print_list(B,'B');
  
          C = Create_vector(A,B,i,n);
      }
      getchar(); getchar();
  }
  </code></pre>
  
  <p>Hopefully you got this far. So my problems are:</p>
  
  <ol>
  <li><p>I'm not sure how to create the array of pointers that I need, which are Row_A, Row_B, Row_C. Meaning, if each cell is pointing into the head of a vector - how do I define the arrays? As list? List node? How do I make every cell of the array to point to each vector's head?</p></li>
  <li><p>List C is overriden every time the for loop is executed. The only way I see that can keep each vector C and put it in a matrix is to make each array cell point to each vector's head, which brings us back to problem #1. Is that true? How can I do this?</p></li>
  </ol>
  
  <p>Thank you very much.</p>