(Data structure) Storage structure of sparse matrix triplet and its basic algorithm design

Hits: 0

Experimental content

  1. Assuming that the n*n [sparse matrix] A is represented by triples, design a program ex6-1.cpp to achieve the following functions:
    (1) Generate the triples a and b of the following two sparse matrices.
    { 1 0 3 0 {3 0 0 0
    0 1 0 0 0 4 0 0
    0 0 1 0 0 0 1 0
    0 0 1 1} 0 0 0 2}
    (2) Output the triplet of a [transposed matrix] Output the triplet of a [transposed matrix]
    (3) Output the triplet of a+b
    (4) Output the triplet of axb
  2. Design an algorithm that computes the sum of the diagonal elements of a sparse matrix represented by a triple table
  3. Design an algorithm Same(g1 , g2), to determine whether the two generalized g1 and g2 are the same

Code

1、
exp6-1.cpp

# include <stdio.h>
 # define N 4 
typedef  int ElemType;
 # define MaxSize 100 /*Maximum number of non-zero elements in a matrix*/
 typedef  struct 
{ 
 int r; /*row number*/ 
 int c; /*column number* / 
 ElemType d; /*element value*/ 
}TupNode; /*triple definition*/ 
typedef  struct 
{ 
 int rows; /*row value*/ 
 int cols; /*column value*/ 
 int nums; /*non-zero elements number*/
 TupNode data[MaxSize];
}TSMatrix; /*Storage structure of triples*/ 
void  CreatMat (TSMatrix &t,ElemType A[N][N]) /*The triple representation of ungenerated sparse matrix A*/
 {
  int i,j;
 t.rows=N;t.cols=N;t.nums=0;
 for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
   if(A[i][j]!=0)
   {
    t.data[t.nums].r=i;t.data[t.nums].c=j;
    t.data[t.nums].d=A[i][j];
    t.nums++;
   }
 }
}
{
 int i;
 if(t.nums<=0)
  return;
 printf("\t%d\t%d\n",t.rows,t.cols,t.nums);
 printf("\t------------------\n");
 for(i=0;i<t.nums;i++)
  printf("\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);
}
void  TranMat (TSMatrix t,TSMatrix &tb) /*Seek the transpose tb of triple representation t*/
 {
  int p,q= 0 ,v; /*q is the subscript of tb.data*/
 tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;
 if(t.nums!=0)
 {
  for (v= 0 ;v<t.cols;v++) /*tb.data[q] records in the order of the c field*/ 
   for (p= 0 ;p<t.nums;p++) /*p is the subscript of t.data */ 
    if (t.data[p].c==v)
    {
     tb.data[q].r=t.data[p].c;
     tb.data[q].c=t.data[p].r;
     tb.data[q].d=t.data[p].d;
     q++;
    }
 }
}
int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c)
{
 int i=0,j=0,k=0;
 ElemType v;
 if (a.rows!=b.rows ||a.cols!=b.cols)
   return  0 ; /*The addition operation cannot be performed when the number of rows or columns is not equal*/
 c.rows=a.rows;c.cols=a.cols;
 while (i<a.nums && j<b.nums) /* process each element in a and b */
 {
  if (a.data[i].r==b.data[j].r) /*When the line numbers are equal*/
  {
   if (a.data[i].c<b.data[j].c) /*The column number of the a element is less than the column number of the b element*/
   {
    c.data[k].r=a.data[i].r; /*Add a element to c*/
    c.data[k].c=a.data[i].c;
    c.data[k].d=a.data[i].d;
    k++;i++;
   }
   else  if (a.data[i].c>b.data[j].c) /*The column number of the a element is greater than the column number of the b element*/
   {
    c.data[k].r=b.data[i].r; /*Add b element to c*/
    c.data[k].c=b.data[i].c;
    c.data[k].d=b.data[i].d;
    k++;j++;
   }
   else  /*The column number of the a element is equal to the ordinal number of the b element */
   {
    v=a.data[i].d+b.data[j].d;
    if (v!= 0 ) /*Add only nodes that are not 0 to c*/
    {
     c.data[k].r=a.data[i].r;
     c.data[k].c=a.data[i].c;
     c.data[k].d=v;
    }
    i++;j++;
   }
  }
  else  if (a.data[i].r<b.data[j].r) /*The row number of the a element is less than the row number of the b element*/
  {
   c.data[k].r=b.data[i].r; /*Add b element to c*/
   c.data[k].c=b.data[i].c;
   c.data[k].d=b.data[i].d;
   k++;i++;
  }
  else
  {
   c.data[k].r=b.data[j].r; /*Add b element to c*/
   c.data[k].c=b.data[j].c;
   c.data[k].d=b.data[j].d;
   k++;j++;
  }
  c.nums=k;
 }
 return  1 ;
}
int value(TSMatrix c,int i,int j)
{
 int k=0;
 while(k<c.nums && (c.data[k].r!=i || c.data[k].c!=j))
  k++;
 if ( k < c . nums )
   return ( c . data [ k ]. d ) ;
 else 
  return  0 ;
}
{
 int i,j,k,p=0;
 ElemType s;
 if (a.cols!=b.rows) /*When the number of columns of a is not equal to the number of rows of b, the multiplication operation cannot be performed*/ 
  return  0 ;
  for (i= 0 ;i<a.rows;i++)
   for ( j= 0 ;j<b.cols;j++)
  {
   s=0;
   for(k=0;k<a.cols;k++)
    s=s+value(a,i,k)*value(b,k,j);
   if (s!= 0 ) /* produce a triple element */
   {
    c.data[p].r=i;
    c.data[p].c=j;
    c.data[p].d=s;
    p++;
   }
  }
  c.rows=a.rows;
  c.cols=b.cols;
  c.nums=p;
  return  1 ;
}
int main()
{
 ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};
 ElemType b1[N][N]={{3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2}};
 TSMatrix a,b,c;
 CreatMat(a,a1);
 CreateMat(b,b1);
 printf ( "triple of a:\n" );DispMat(a);
  printf ( "triple of b:\n" );DispMat(b);
  printf ( "transpose of a to c\n" ) ;
 TranMat(a,c);
 printf ( "Triple of c:\n" );DispMat(c);
  printf ( "c=a+b\n" );
 MatAdd(a,b,c);
 printf ( "Triple of c:\n" );DispMat(c);
  printf ( "c=a*b\n" );
 MatMul(a,b,c);
 printf ( "Triple of c:\n" );DispMat(c);
}

Screenshot of the result:
2.

# include <iostream>
 using  namespace  std ;
 # define N 4 
# define MaxSize 100 
typedef  int ElemType;
 typedef  struct 
{ 
    int r; //line number 
    int c; //column number 
    ElemType d; //element value 
}TupNode; // Triple definition 
typedef  struct 
{ 
    int rows; //Number of rows 
    int cols; //Number of columns 
    int nums; //Number of non-zero elements
    TupNode data[MaxSize];
}TSMatrix; //Definition of triplet order table 
          //Generate triplet representation of sparse matrix A t 
void  CreatMat (TSMatrix &t, ElemType A[N][N])
 {
     int i, j;
    t.rows = N;
    t.cols = N;
    t.nums = 0;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (A[i][j] != 0)
            {
                t.data[t.nums].r = i;
                t.data[t.nums].c = j;
                t.data[t.nums].d = A[i][j];
                t.nums++;
            }
        }
    }
}
//output triple representation t 
void  DispMat (TSMatrix t)
 {
     int i;
     if (t.nums <= 0 )
         return ;
     else 
        printf ( "\t%d\t%d\t%d\n" , t .rows, t.cols, t.nums);
     printf ( "\t----------------------------\n" );

    for (i = 0; i < t.nums; i++)
    {
        printf("\t%d\t%d\t%d\n", t.data[i].r, t.data[i].c, t.data[i].d);
    }

}
bool diagonal(TSMatrix a, ElemType &sum)
{
    sum = 0;
    if (a.rows != a.cols)
    {
        printf ( "Not a diagonal matrix\n" );
         return  false ;
    }
    for (int i = 0; i < a.nums; i++)
    {
        if (a.data[i].r == a.data[i].c)
            sum += a.data[i].d;
    }
    return true;
}
int main()
{
    ElemType sum,A[N][N] = { {1,0,0,0},{0,3,0,5},{0,0,5,0},{0,0,0,7} };
    TSMatrix a;
    CreatMat(a, A);
    printf ( "A triplet\n" );
    DispMat(a);
    diagonal(a, sum);
    printf ( "The sum of the diagonal elements is %d\n" , sum);
     return  0 ;
}

Screenshot of the result:
3.

# include <iostream>
 using  namespace  std ;
 typedef  struct  lnode 
{ 
    int tag; //node type identifier 
    union
    {
        char data;
        struct  lnode * sublist ;
    }val;
    struct  lnode * link ; //point to the next element 
}GLNode; //declare the generalized table node type 
//return the generalized table-linked storage structure of s represented by bracket notation 
GLNode * CreateGL ( const  char * &s)
 {
    GLNode *g;
    char ch = * s++; // take a character 
    if (ch != '
# include <iostream>
using  namespace  std ;
typedef  struct  lnode 
{ 
int tag; //node type identifier 
union
{
char data;
struct  lnode * sublist ;
}val;
struct  lnode * link ; //point to the next element 
}GLNode; //declare the generalized table node type 
//return the generalized table-linked storage structure of s represented by bracket notation 
GLNode * CreateGL ( const  char * &s)
{
GLNode *g;
char ch = * s++; // take a character 
if (ch != '\0' ) // judge that the string is not over
{
g = (GLNode *)malloc(sizeof(GLNode));
if (ch == '(')
{
g->tag = 1;
g->val.sublist = CreateGL(s);
}
else if (ch == ')')
g = NULL;
else if (ch == '#')
g->val.sublist = NULL;
else
{
g->tag = 0;
g->val.data = ch;
}
}
else
g = NULL;
ch = * s++;
if (g != NULL)
{
if (ch == ',')
g->link = CreateGL(s);
else
g->link = NULL;
}
return g;
}
//Output generalized table g 
void  DispGL (GLNode *g)
{
if (g != NULL )
{
if (g->tag == 0)
cout << g->val.data;
else
{
cout << "(";
if (g->val.sublist == NULL)
cout << "#";
else
DispGL(g->val.sublist);
cout << ")";
}
if (g->link != NULL)
{
cout << ",";
DispGL(g->link);
}
}
}
//Destroy the generalized table g 
void  DestroyGL (GLNode * &g)
{
GLNode *g1, *g2;
g1 = g->val.sublist;
while (g1 != NULL)
{
if (g1->tag == 0)
{
g2 = g1->link;
free(g1);
g1 = g2;
}
else
{
g2 = g1->link;
DestroyGL(g1);
g1 = g2;
}
}
free(g);
}
bool Same(GLNode *g1, GLNode *g2)
{
if (g1 == NULL && g2 == NULL)
return true;
else if (g1 == NULL || g2 == NULL)
return false;
else
{
if (g1->tag == 0 && g2->tag == 0)
{
if (g1->val.data != g2->val.data)
return false;
return(Same(g1->link, g2->link));
}
else if (g1->tag == 1 && g2->tag == 1)
return(Same(g1->val.sublist, g2->val.sublist))
&Same(g1->link, g2->link);
else 
return  false ;
}
}
int main()
{
GLNode  *g1, *g2;
const char * str1 ="(b,(b,a,(#),d),((a,b),c,((,))))";
const char * str2= "(b,(b,a,(#),d),((a,b),c,((#))))";
g1 = CreateGL(str1);
g2 = CreateGL(str2);
cout << "Generalized table g1:" ;
DispGL(g1);
cout << endl ;
cout << "Generalized table g2:" ;
DispGL(g2);
cout << endl;
if (Same(g1, g2))
{
cout << "Generalized table g1, g2 are the same" << endl ;
}
else 
cout << "Generalized table g1, g2 are not the same" << endl ;
DestroyGL(g1);
DestroyGL(g2);
return 0;
}
' ) // judge that the string is not over { g = (GLNode *)malloc(sizeof(GLNode)); if (ch == '(') { g->tag = 1; g->val.sublist = CreateGL(s); } else if (ch == ')') g = NULL; else if (ch == '#') g->val.sublist = NULL; else { g->tag = 0; g->val.data = ch; } } else g = NULL; ch = * s++; if (g != NULL) { if (ch == ',') g->link = CreateGL(s); else g->link = NULL; } return g; } //Output generalized table g void DispGL (GLNode *g) { if (g != NULL ) { if (g->tag == 0) cout << g->val.data; else { cout << "("; if (g->val.sublist == NULL) cout << "#"; else DispGL(g->val.sublist); cout << ")"; } if (g->link != NULL) { cout << ","; DispGL(g->link); } } } //Destroy the generalized table g void DestroyGL (GLNode * &g) { GLNode *g1, *g2; g1 = g->val.sublist; while (g1 != NULL) { if (g1->tag == 0) { g2 = g1->link; free(g1); g1 = g2; } else { g2 = g1->link; DestroyGL(g1); g1 = g2; } } free(g); } bool Same(GLNode *g1, GLNode *g2) { if (g1 == NULL && g2 == NULL) return true; else if (g1 == NULL || g2 == NULL) return false; else { if (g1->tag == 0 && g2->tag == 0) { if (g1->val.data != g2->val.data) return false; return(Same(g1->link, g2->link)); } else if (g1->tag == 1 && g2->tag == 1) return(Same(g1->val.sublist, g2->val.sublist)) &Same(g1->link, g2->link); else return false ; } } int main() { GLNode *g1, *g2; const char * str1 ="(b,(b,a,(#),d),((a,b),c,((,))))"; const char * str2= "(b,(b,a,(#),d),((a,b),c,((#))))"; g1 = CreateGL(str1); g2 = CreateGL(str2); cout << "Generalized table g1:" ; DispGL(g1); cout << endl ; cout << "Generalized table g2:" ; DispGL(g2); cout << endl; if (Same(g1, g2)) { cout << "Generalized table g1, g2 are the same" << endl ; } else cout << "Generalized table g1, g2 are not the same" << endl ; DestroyGL(g1); DestroyGL(g2); return 0; }

Result screenshot:

You may also like...

Leave a Reply

Your email address will not be published.