<> Sparse matrix compression and transpose

1, Random number generating matrix algorithm : use time() Function seeding random numbers , Get the total number of rows of the matrix , Total number of columns , Number of nonzero elements . The values of total row number and total column number can be directly stored in triples . After each generation of a non-zero row and column , Input the size of non-zero element by keyboard e; And store it into two-dimensional array first a[][].

2, Algorithm thought of compressing matrix to triples : After obtaining the matrix , Compress it into a triple table , The initial number of non-zero elements of a triple is 0, Because the same row may appear in the process of generating random matrix , column , Causes the nonzero elements of the matrix to be covered , Therefore, the number of non-zero elements in the matrix shall prevail . ergodic matrix , If there are nonzero elements , The line label of the element is i And column label j, Save triple , The number of simultaneous nonzero elements +1.

3, The algorithm of printing matrix : Print the elements of each line first , If i,j And in the triple table i,j Match , Then print the element , Otherwise, print 0.

4, Algorithm thought of fast transpose of triples : Find the transposed matrix M The number of nonzero elements in each column of , Then, the first non-zero element of each column is obtained T.data Should be in the right place , So we need two auxiliary vectors :num And copt. First make T.mu=M.nu,T.nu=M.mu,T.tu=M.tu. If T.tu Not equal to 0, The number of non-zero elements in each column is calculated first num[col],col from 1 reach M.nu; Seek the position again copt[col],copt[col]=copt[col-1]+num[col-1]
,col from 2 reach M.nu,copt[1]=1; Finally, transpose operation , order M Of i,j exchange , One element at a time ++copt[col].

5, The specific implementation code is as follows :
#include<stdio.h> #include<stdlib.h> #include<time.h> #define MAXSIZE 200 #
define OK 1 #define FALSE 0 #define OVERFLOW -2 #define ERROR 0 typedef int
Status; typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple;
typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }TSMatrix; Status
CreateMatrix(TSMatrix *M) { int i,j,n,k; // That's ok , column , Number of nonzero elements int a[50][50]={0};
// Storage matrix , The initial value is 0 ElemType e; printf(" The number of rows and columns of this sparse matrix are generated by random numbers !\n"); srand((unsigned)time(
NULL) + (unsigned)rand()); // with time() Generating random numbers for seeds (*M).mu=rand()%10+6;
// Random row size , The remainder is to determine the scope ,mu stay (6~15) between (*M).nu=rand()%10+7; // Random column size k=rand()%10+6;
// Number of random nonzero elements printf(" The number of rows of the sparse matrix is %d, The number of columns is %d, The number of nonzero elements is %d.",(*M).mu,(*M).nu,k); (*M).data[0].
i=0; for(n = 1; n <= k; n++) // Generating random number matrix { i=rand()%(*M).mu+1; j=rand()%(*M).nu+1;
printf(" Please enter the second line in line order %d Non zero elements , That's ok %d, column %d, Element value :\n",n,i,j); scanf("%d",&e); a[i][j]=e; } (*
M).tu=1; for(i=1;i<=(*M).mu;i++) // Storing triples in behavior order { for(j=1;j<=(*M).nu;j++) { if(a[i
][j]!=0) { (*M).data[M->tu].i = i; // Line subscript (*M).data[M->tu].j = j; // Column subscript (*M).data
[M->tu].e = a[i][j]; // The value of the subscript M->tu++; } } } M->tu--; return OK; } Status
PrintMatrix(TSMatrix M) { int i,j,n=1; printf("\n\n"); for(i=1;i<=M.mu;i++) {
for(j=1;j<=M.nu;j++) { if(M.data[n].i==i&&M.data[n].j==j) { printf("%4d",M.data[
n].e); n++; } else printf("%4d",0); } printf("\n"); } return OK; } Status
FastTransposeSMatrix(TSMatrix M,TSMatrix *T) { int col,t,p,q; int *num,*copt;
num=(int*)malloc((M.nu+1)*sizeof(int)); // to num Allocate memory space ; Size is M Number of columns +1,num[1] start copt=(
int*)malloc((M.nu+1)*sizeof(int)); //copt Represents the first nonzero element of the column in the T.data Position in ,copt Size and num equal T->
mu=M.nu; T->nu=M.mu; T->tu=M.tu; //T The number of rows of is equal to M Number of columns , The number of columns equals the number of rows , The number of nonzero elements is equal if(T->tu) // Not empty {
for(col=1;col<=M.nu;++col) num[col]=0; // Clearing operation for(t=1;t<=M.tu;++t) ++num[M.data[
t].j]; // seek M The number of nonzero elements in each column copt[1]=1; //M The first nonzero element of the first column of the T The first position of for(col=2;col<=M.nu;++
col) copt[col]=copt[col-1]+num[col-1]; // Accumulation operation , It's complicated , Find the first non-zero element in each column T.data Position in for(p=
1;p<=M.tu;++p) { col=M.data[p].j; q=copt[col]; T->data[q].i=M.data[p].j; // Transpose operation
T->data[q].j=M.data[p].i; T->data[q].e=M.data[p].e; ++copt[col]; // Location used , Count plus one } }
return OK; } void main() { TSMatrix M,T; CreateMatrix(&M); printf(" The original matrix is as follows :\n");
PrintMatrix(M); // Printing M FastTransposeSMatrix(M,&T); printf(" The transpose matrix is as follows :\n");
PrintMatrix(T); // Printing T }
6, On the number of fans 50, Add a flowchart next time , It's not easy to create , Thank you for your support .

Technology
©2019-2020 Toolsou All rights reserved,
python3 Of tkinter Design of login interface +mysql Import data of database CRC Partial understanding of modular division use MySQL Processing 100 million level data The greatest common divisor and the least common multiple C Language Edition 【 Data structure and algorithm 8】 The maze problem of recursion 2020 year ,Java Is there any future ?【2020 The best little program : You can find all kinds of resources you want ?】element Form validation number type and range An interview of Alibaba outsourcing vue:word Local upload Preview