Google Search

Saturday, January 29, 2011

Represent the given sparse matrix using Linked List MC 9217 DATA STRUCTURES LAB Anna University lab manual download

Represent the given sparse matrix using Linked List MC9217 DATA STRUCTURES LAB Anna University lab manual download


Aim: To write a program to represent Sparse Matrix using Linked list

Algorithm:

  1. start
  2. Enter the row and column matrix
  3. Read the value of m and n
  4. Set for loop i< row as i=1 and another loop i < col as j=1
  5. Read value of x
      Next j and i
  1. If we choose insert then check if (sparse == Null ) then sparse =p
      Else check while (q-> next != Null ) then q = q-> next; q-> next =p
  1. If we choose display than for i=1 to r then check p=p->next
  2. stop


Logical Description      
A matrix that has relatively few non-zero entries. It may be represented in much less than n × m space.  
An n × m matrix with k non-zero entries is sparse if k << n × m. It may be faster to represent the matrix compactly as a list of the non-zero indexes and associated entries, as a list of lists of entries (one list for each row), coordinate format (the values and their row/column positions), or by a point access method.  It is implemented with linked list
Program Code
#include<stdio.h>
struct node
{
            int row;
            int col;
            int data;
            struct node *link;
}*head=NULL,*curr=NULL,*p=NULL;

void main()
{
            int i,j,m,n,a[50][50];
            clrscr();
            printf("\nSparse Matrix using Linked List\n");
            printf("\nEnter the number of rows of the matrix:");
            scanf("%d",&m);
            printf("Enter the number of columns of the matrix:");
            scanf("%d",&n);
            printf("Enter the elements:");
            for(i=0;i<m;i++)
            {
                        for(j=0;j<n;j++)
                        {
                                    scanf("%d",&a[i][j]);
                                    if(a[i][j]!=0)
                                    {
                                                curr=(struct node*)malloc(sizeof(struct node));
                                                curr->row=i;
                                                curr->col=j;
                                                curr->data=a[i][j];
                                                curr->link=NULL;
                                                if(head==NULL)
                                                            head=curr;
                                                else
                                                {
                                                            p=head;
                                                            while(p->link!=NULL)
                                                                        p=p->link;
                                                            p->link=curr;
                                                }
                                    }
                        }
            }
            printf("\nSparse matrix using linked list:\nRow\tColumn\tElement\t\n");
            p=head;
            if(head==NULL)
                        printf("\nSparse matrix empty!\n");
           
else
            {
                        while(p->link!=NULL)
                        {
                                    printf("%d\t%d\t%d\n",p->row,p->col,p->data);
                                    p=p->link;
                        }
                        printf("%d\t%d\t%d\n",p->row,p->col,p->data);
            }
            getch();
}

1 comments:

Arjun said...

no,, didnt understand the concept :(

Post a Comment