1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sparse Matrix using linked list of a linked list

  1. Feb 16, 2013 #1
    1. The problem statement, all variables and given/known data

    The idea is to create following type of structure:
    first_row_with_a_nonzero_cell->next_row_with_a_nonzerocell->...->NULL
    rowN_with_a_nonzerocell->firstnonzerocolinrowN->nextnonzerocolinrowN...->NULL

    Input file is a 20x50 sparse matrix.

    The only problem I have is while switching to next row, when a '\0' is encountered.
    The new rownode I create using link2 function, should point to the header of the cell node of same row. But I created head1 as a pointer to the first non zero element of the first row. And I can't use the same head1 to point to the first non zero element of the second row.

    How do I make sure that everytime a new row is created, the rownode of that row points to the first non zero cell of the same row?

    2. Relevant equations



    3. The attempt at a solution

    Code (Text):

    #include <stdio.h>

    struct cellnode {

        int val;
        int col;
        struct cellnode *nextcell;

    };

    struct rownode {

        int row;
        struct rownode *firstcell;
        struct rownode *nextrow;

    };

    struct rownode * create_rownode(){

        struct rownode *new;
        new = (struct rownode *)malloc(sizeof(struct cellnode));
        return new;

        };struct rownode *head2=NULL;

    struct cellnode * create_cellnode(){
       
        struct cellnode *new;
        new = (struct cellnode *)malloc(sizeof(struct cellnode));
        return new;

        };struct cellnode *head1=NULL;

    void link1(int v,int c){

        struct cellnode *temp,*new;
       
        new=create_cellnode();
        new->val=v;
        new->col=c;
        if(head1==NULL)
            head1=new;
        else{
            temp=head1;
            while(temp->nextcell!=NULL){
                temp=temp->nextcell;
            }
            temp->nextcell=new;
        }
        if(c=19)
        new->nextcell=NULL;
    }

    void link2(int r){

        struct rownode *temp,*new;

        new=create_rownode();
        new->row=r;
        new->firstcell=head1;
        new->nextrow=NULL;
        if(head2==NULL)
            head2=new;
        else{
            temp=head2;
       
            while(temp->nextrow!=NULL){

                temp=temp->nextrow;

            }

            temp->nextrow=new;
        }
    }

    main() {

        FILE *fp;
        char i,c;
        int n,col=0,row=0;
        fp=fopen("1.txt","r");
        if(fp==NULL){
            printf("cannot open");
            return;
        }
        else printf("File Opened\n");

           
        while(((i=getc(fp))!=EOF)){
        printf("%c",i);
        }
       
        rewind(fp);
       

        while(((i=getc(fp))!=EOF)){

            while(i!='\0'){
            fscanf(fp,"%d%c",&n,&c);
               
                if(n!=0){

                    link1(n,col);
                }
                i=getc(fp);
                col++;
            }

            if(i='\0'){
               
                link2(row);
                head1=NULL;
                col=0;
                row++;
            }
        }
                               
    }


     
     
  2. jcsd
  3. Feb 18, 2013 #2
    bump.
     
  4. Feb 18, 2013 #3

    rcgldr

    User Avatar
    Homework Helper

    This should be:
    Code (Text):

        new = (struct rownode *)malloc(sizeof(struct rownode));
     
    If you need a head pointer for each row, couldn't you add a head pointer to the rownode structure?
     
  5. Feb 18, 2013 #4
    Isn't the firstcell of row node structure itself a head pointer to the first non-zero valued node of cell node?
     
  6. Feb 18, 2013 #5
    I hope you understood my problem.

    In the following code snippet:

    Code (Text):
    void link2(int r){

        struct rownode *temp,*new;

        new=create_rownode();
        new->row=r;
        new->firstcell=head1;
        new->nextrow=NULL;...
    the firstcell of the newly created node should point to the first non zero valued node of the cellnode. In other words, it should point to the head pointer of the cellnode structure of that row.

    My code will work for the first row. But when it goes to second, head1 has the address of the first non zero element of the second row but then the previous rownode will lose the address of the first non zero element of the first row.

    I also need to print the values of the linked list at the end.
     
    Last edited: Feb 18, 2013
  7. Feb 18, 2013 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Abdul, there are quite a few problems in your code.

    rcglr was correct about new = (struct rownode *)malloc(sizeof(struct cellnode));. You will get lucky on a 32 bit machine because both rownode and cellnode are the same size, 12 bytes, on such a machine. You will get burned, badly, on a 64 bit machine. Now sizeof(cellnode) is 16 bytes but sizeof(rownode) is 24.

    Some other problems:

    1. The element firstcell in struct rownode is typed as a pointer to a rownode structure. This should be a pointer to a cellnode structure.

    2. The global variable head1. This, I think is the heart of your problem. Every row in a matrix should have its own linked list of cells. Do it right and there won't be global list of cells.

    3. The global variable head2. What if someone wants to represent two sparse matrices? Global variables are not the way to go here. (They aren't the way to go in general.)

    4. The lack of a structure to represent the matrix as a whole. Where are you capturing the fact that the matrix in question is a 20x50 sparse matrix? What if the next matrix to be dealt with is 50x10?
     
  8. Feb 18, 2013 #7
    I modified my program as per your suggestion.
    It works pretty good before the display() function is called, where it gives a segmentation fault. I spent hours debugging it but came up with no error.

    Code (Text):
    #include <stdio.h>
    #define MAX 20

    static struct cellnode *a[MAX];
    static int k=0;


    struct cellnode {

        int val;
        int col;
        struct cellnode *nextcell;

    };


    struct rownode {

        int row;
        struct rownode *firstcell;
        struct rownode *nextrow;
       
        };

    struct rownode * create_rownode(){

        struct rownode *new;
        new = (struct rownode *)malloc(sizeof(struct rownode));
        return new;

        };struct rownode *head2=NULL;

    struct cellnode * create_cellnode(){
       
        struct cellnode *new;
        new = (struct cellnode *)malloc(sizeof(struct cellnode));
        return new;

        };

    struct cellnode * create_header(){

        struct cellnode *head;
        head=NULL;
        return head;
       
        }
    void link1(int v,int c){

        struct cellnode *temp,*new;
        new=create_cellnode();
        new->val=v;
        new->col=c;
        new->nextcell=NULL;
        if(a[k]==NULL)
            a[k]=new;
        else{
            temp=a[k];
            while(temp->nextcell!=NULL){
                temp=temp->nextcell;
            }
            temp->nextcell=new;
        }
       
    }

    void link2(int r){

        struct rownode *temp,*new;
       
        new=create_rownode();
        new->row=r;
        new->firstcell=(struct rownode *)a[k];
        new->nextrow=NULL;
        if(head2==NULL)
            head2=new;
        else{
            temp=head2;
       
            while(temp->nextrow!=NULL){

                temp=temp->nextrow;

            }

            temp->nextrow=new;
        }
    }

    void display() {

        struct cellnode *temp1;
        int i;
           
        for(i=0;i<MAX;i++){
            line1: temp1=a[i];
            if(a[i]==NULL){
            i++;
            goto line1;
            }
            else{
            while(temp1->nextcell!=NULL)
            {
                printf("%d %d\t",temp1->col,temp1->val);
                temp1=temp1->nextcell;
            }
            }
        }
    }
    main(){

        FILE *fp1,*fp2;
        char i,c;
        a[k]=create_header();
        int n,col=0,row=0;
            fp1=fopen("1.txt","r");
            fp2=fopen("1.txt","r");
        if(fp1==NULL){
            printf("cannot open");
            return;
        }
        else printf("File Opened\n");

           
        while(((i=getc(fp1))!=EOF)){
        printf("%c",i);
        }
       
        rewind(fp1);
       
    //printf("row %d\n",row);
        while(((i=getc(fp1))!=EOF)){
            //printf("%c",i);
            if(i==' ')
            i=getc(fp1);
            if(i=='\n'){
            //  printf("In IF loop");      
                            link2(row);
                    col=0;
                            row++;
            //  printf("row %d\n",row);      
                a[k++]=create_header();
            }

            else {

                fscanf(fp2,"%d%c",&n,&c);
                    if(n!=0){
                        link1(n,col);
                        printf("%d %d\t",n,col);
                    }
                col++;
           
            }
        }
        printf("\n");  
        display();             
    }

     
     
  9. Feb 18, 2013 #8

    rcgldr

    User Avatar
    Homework Helper

    If you have windows, try microsoft visual C++ express (it's free). It includes a source level debugger, that will show you what line caused the segmenation fault.
     
  10. Feb 18, 2013 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Abdul, if you have a tutoring center, a teaching assistant, or a professor that you can talk to, do so. Your coding needs a lot of help, more than we can give in forum.

    You did not follow my advice. You still have global variables. You do not need any globals.

    Some questions:
    - What is the format of the data in the input file?
    - How is it organized? (e.g., row major, column major, random?)
    - What do you think should happen when you read a row/column/datum triple (or the equivalent) from the input file?
    - Why made you think you need two FILE pointers?
     
  11. Feb 19, 2013 #10
    This is an assignment, and my professors won't help.
    I just used one global variable head2. That's how we did in class for a single linked list. Here we have a single linked list of rownodes.

    Attached is the .txt file containing input matrix.
    Every time the end of a row is reached, i.e. a \n character in encountered,
    link2 is called which adds a new node to the rownode linked list.

    fp1 gets one character at a time and it keeps a track till EOF is reached. If I use fscanf with the same file pointer then I think some values will be skipped while traversing the matrix. Suppose getc(fp1) returns 1, then fscanf(fp1,"%d",n) will return the character/number after 1. This can be modified of course but I thought creating 2 file pointers will be convinient.
     

    Attached Files:

    • 1.txt
      1.txt
      File size:
      2 KB
      Views:
      84
  12. Feb 19, 2013 #11
    I got my code working.
    Below if the final version.
    If I need to improve on something please let me know.

    Code (Text):
    #include <stdio.h>
    #define MAX 20

    static struct cellnode *a[MAX];
    static int k=0;

    struct cellnode {

        int val;
        int col;
        struct cellnode *nextcell;

    };


    struct rownode {

        int row;
        struct rownode *firstcell;
        struct rownode *nextrow;
       
        };struct rownode *head2=NULL;

    struct rownode * create_rownode(){

        struct rownode *new;
        new = (struct rownode *)malloc(sizeof(struct rownode));
        return new;

        }

    struct cellnode * create_cellnode(){
       
        struct cellnode *new;
        new = (struct cellnode *)malloc(sizeof(struct cellnode));
        return new;

        }

    struct cellnode * create_header(){

        struct cellnode *head;
        head=NULL;
        return head;
       
        }

    void link1(int v,int c){

        struct cellnode *temp,*new;
        new=create_cellnode();
        new->val=v;
        new->col=c;
        new->nextcell=NULL;
        if(a[k]==NULL)
            a[k]=new;
        else{
            temp=a[k];
            while(temp->nextcell!=NULL){
                temp=temp->nextcell;
            }
            temp->nextcell=new;
        }
    }

    void link2(int r){

        struct rownode *temp,*new;
       
        new=create_rownode();
        new->row=r;
        new->firstcell=(struct rownode *)a[k];
        new->nextrow=NULL; 
        if(head2==NULL)
            head2=new;
        else{
            temp=head2;
       
            while(temp->nextrow!=NULL){

                temp=temp->nextrow;

            }

            temp->nextrow=new;
        }
    }

    void display() {

        struct cellnode *temp1;
        struct rownode *temp2;
        int i=0;
        temp2=head2;
       
        while(i!=MAX){

            temp1=a[i];
            if(a[i]==NULL){
                i++;
                temp2=temp2->nextrow;
            }
            else{
                while(temp1->nextcell!=NULL)
                {
                    printf("Row %d Col %d Val %d\n",temp2->row,temp1->col,temp1->val);
                    temp1=temp1->nextcell;
                }
                printf("Row %d Col %d Val %d\n",temp2->row,temp1->col,temp1->val);
                i++;
                temp2=temp2->nextrow;
            }
        }
    }

    main(){

        FILE *fp1,*fp2;
        char i,c;
        a[k]=create_header();
        int n,col=0,row=0;
            fp1=fopen("1.txt","r");
            fp2=fopen("1.txt","r");
        if(fp1==NULL){
            printf("cannot open");
            return;
        }
        else printf("File Opened\n");

           
        while(((i=getc(fp1))!=EOF)){
            printf("%c",i);
        }
       
        rewind(fp1);
        while(((i=getc(fp1))!=EOF)){
                   
            if(i==' ')
                i=getc(fp1);
            if(i=='\n'){       
                            link2(row);
                    col=0;
                            row++;
                k++;      
                a[k]=create_header();
            }
            else{
                fscanf(fp2,"%d%c",&n,&c);
                if(n!=0)
                link1(n,col);
                col++;
           
            }
        }
        printf("\n");  
        display();             
    }

     
     
  13. Feb 19, 2013 #12

    rcgldr

    User Avatar
    Homework Helper

    Is firstcell a pointer to a rownode or a cellnode? You should fix this or change the name to firstrow.

    Also you could use typedef's to avoid having to use "struct" so often:

    Code (Text):

    typedef struct _cellnode {  /* underscore on struct name */
        int val;
        int col;
        struct _cellnode *nextcell;
    }cellnode;                  /* no underscore on typedef name */

    typedef struct _rownode {   /* underscore on struct name */
        int row;
        cellnode *firstcell;
        struct _rownode *nextrow;
    }rownode;                   /* no underscore on typedef name */

    rownode *head2 = NULL;

    rownode * create_rownode()
    {
    rownode *new;
        new = (rownode *)malloc(sizeof(rownode));
        return new;
    }
    ...
     
     
    Last edited: Feb 19, 2013
  14. Feb 19, 2013 #13
    firstcell is a pointer to the first non zero valued cellnode.

    Thank you! I did not know that.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sparse Matrix using linked list of a linked list
Loading...