Sparse matrix (triple) creation, transpose, traversal, addition, subtraction, multiplication. C implementation

One 、 Ideas .

1. establish .

You can assign a string directly , But for 0 The elements of should also be assigned in turn , More trouble , But easy to understand can also be achieved .

Secondly, we can also conceive the assignment of triples , Only assign non-zero elements and its rows , Number of columns , When printing if Judge , Output without assignment 0, It's easy .

When creating a structure , A matrix needs to have its total number of rows and columns , And for triples , You also need the row and column of each element , And the sum of non-zero elements of this triple .

2. Traverse .

For three tuples , It includes non-zero element set and zero element set , For lines with non-zero elements , Number of columns , Carry on the double for loop , If the row of non-zero elements , Column number and for The variables in the loop are equal , Just output the value of this number , Otherwise output 0.

3. Transposition .

Transpose is to exchange row numbers and column numbers , If you order by line , Time complexity is too high , Therefore, column precedence is generally used .

• First of all to Total rows , Total number of columns , And the assignment of the total number of non-zero elements .
• Secondly, traverse the non-zero elements by column loop
• If the column number of the non-zero element == The column number of the outer cycle , Then proceed to line , Exchange of column numbers .

The detailed illustration of the rapid transposition method is a little complicated , So I didn't do , But the code has , And it's working .

4. Add , Subtraction , Multiplication .

Addition is very simple , stay A,B In two matrices , If the positions of non-zero elements are the same , Then the new matrix C The value of this position is =A,B The value of the combined , If not, the matrix C The value of is equal to A The value of or B Value .

Subtraction is adding a matrix *-1

  If multiplication is equal, multiply , Don't care if it's not equal , Because even if you manage it, you will end up with 0;

Two 、 Specific code .

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define false 0
#define true 1
#define max 100
typedef struct {
	int value;    //value Is the specific value  
	int row,col;  //row For the line ,col Column  
}Array;
typedef struct {
	Array data[max+1];    
	int rows,cols,nums;   //nums Is the number of non-zero elements  
}Arrays;
// Create sparse matrix  
int InitArray(Arrays *L,int rows,int cols,int nums){
	int i,j;
	L->nums=nums;
	L->cols=cols;
	L->rows=rows;
	assert(L->nums<max);
	printf("-------------\n");
	printf(" Please enter the number of rows of non-zero elements in sequence , Number of columns , value :\n");
	for (int i = 1; i <= L->nums; i++) {
		scanf("%d %d %d", &L->data[i].row, &L->data[i].col, &L->data[i].value);
		}
		printf(" Create success ！\n");
		return true;
	}
// Traverse the output sparse matrix    Triple form 
void bianli1(Arrays *L) {
	printf("------------- Triple form traversal output :\n");
	for (int i = 1; i <= L->rows; i++) {
		printf("%d That's ok %d Column %d \n",L->data[i].row,L->data[i].col,L->data[i].value);
	}
}

// Traverse the output sparse matrix    Matrix form 
void bianli2(Arrays *L) {
	int flag = 1;         //flag representative  
	for (int i = 1; i <= L->rows; i++) {
		for (int j = 1; j <=L->cols; j++) {
			if (L->data[flag].value!=0&&L->data[flag].row==i&&L->data[flag].col==j) {
				printf(" %d", L->data[flag].value);
				flag++;
			}
			else {
				printf(" 0");
			}
		}
		printf("\n");
	}
}
// Matrix general transpose ( By column )
int Transform(Arrays a,Arrays *b){   // //a Is the original matrix ,b Is the transposed matrix 
	b->cols=a.cols;
	b->nums=a.nums;
	b->rows=a.rows;
	if(b->nums>0){
		int j=1;
		for(int k=1;k<=a.cols;k++){
			for(int i=1;i<=a.nums;i++){    // Enter the non-zero element cycle  
				if(a.data[i].col==k){      // If there are non-zero elements in each column , Then perform transpose operation  
					b->data[j].row=a.data[i].col;    //j Representative table B Non-zero element number of , It is from 1 Start . 
					b->data[j].col=a.data[i].row;
					b->data[j].value=a.data[i].value;
					j++;
					if(j>a.nums) return false;
				}
			} 
		}
	}
} 
// Matrix fast transpose 
void FastTransform(Arrays *a,Arrays *b){   //a Is the original matrix ,b Is the transposed matrix  
	int num[max],position[max];
	int col,i,k,m;
	b->cols=a->cols;
	b->nums=a->nums;
	b->rows=a->rows;
	if(b->nums>0){
		for(col=1;col<=a->cols;col++){   // First of all, will num The values of the array are assigned 0 
			num[col]=0;
		}
		for(i=1;i<=a->nums;i++){   // Then traverse non-zero elements , Put the column of non-zero elements in num Array ++ operation  
			num[a->data[i].col]++;
		} 
		position[1]=1;     // The first non-zero element position Value is defined as 1 
	 	for(col=2;col<=a->cols;col++){
		position[col]=position[col-1]+num[col-1];   // The starting position of non-zero elements in the previous column plus the number of non-zero elements is equal to the starting position of the next column  
		}
		for(k=1;k<=a->nums;k++){   // Traverse the non-zero elements and transpose them in turn  
			col=a->data[k].col; 
			m=position[col];
			b->data[m].row=a->data[k].col;
			b->data[m].col=a->data[k].row;
			b->data[m].value=a->data[k].value;
			position[col]++;
		} 
	}
} 
// Matrix addition 
int ADD(Arrays a,Arrays b,Arrays *c){
	int k=1,i,j;      //i by a The number of elements ,j by b The number of elements ,k by c The number of elements  
	
	// Only those in the same row and column can be added  
	if(a.cols!=b.cols||a.rows!=b.rows){
		return false;
	}
	
	c->cols=a.cols;   // Total number of assigned rows , The total number of columns  
	c->rows=a.rows;
	// Perform traversal assignment  
	for(i=1,j=1;i<=a.nums&&j<=b.nums;){
	   
	   //B The line number of is greater than A Direct will A Add elements in C matrix  
		if(a.data[i].row<b.data[j].row){
			c->data[k].col=a.data[i].col;
			c->data[k].row=a.data[i].row;
			c->data[k].value=a.data[i].value;
			k++;       //C The element is incremented by one digit  
			i++;       //a Assignment rule a The element is incremented by one digit , If the time is b be b The element is incremented by one digit  
		}
		//B The line number of is less than A Direct will B Add elements in C matrix 
		else if(a.data[i].row>b.data[j].row){
			c->data[k].col=b.data[j].col;
			c->data[k].row=b.data[j].row;
			c->data[k].value=b.data[j].value;
			k++;
			j++; 
		}else{  // Same line number  
			
			//B The column number of is less than A Direct will B Add elements in C matrix 
			if(a.data[i].col>b.data[j].col) {
			c->data[k].col=b.data[j].col;
			c->data[k].row=b.data[j].row;
			c->data[k].value=b.data[j].value;
			k++;
			j++;
			}
			
			//B The column number of is greater than A Direct will A Add elements in C Moment 
			else if(a.data[i].col<b.data[j].col){
			c->data[k].col=a.data[i].col;
			c->data[k].row=a.data[i].row;
			c->data[k].value=a.data[i].value;
			k++;
			i++;
			}
			// equal  
			else {
				 
				c->data[k].col=a.data[i].col;
				c->data[k].row=a.data[i].row;
				c->data[k].value=a.data[i].value+b.data[j].value;
				k++;
				i++;
				j++;
			}
		}
	}
	while(i<=a.nums){ //B Take it out A Not finished 
	
			// take A The remaining elements in are added to C in 
		c->data[k].col=a.data[i].col;
		c->data[k].row=a.data[i].row;
		c->data[k].value=a.data[i].value;
		k++;
		i++;
	}   
	while(j<=b.nums){  //A Take it out B Not finished 
			
			// take A The remaining elements in are added to C in 
		c->data[k].col=b.data[j].col;
		c->data[k].row=b.data[j].row;
		c->data[k].value=b.data[j].value;
		k++;
		j++;
	}
}
    
			


// Matrix subtraction 
int reduce(Arrays a,Arrays b,Arrays *c){   // Call the addition operation , stay b Multiply on the basis of matrix  -1  In Canada  a matrix  
	for(int i=1;i<=b.nums;i++){
		b.data[i].value=b.data[i].value*-1;
	}
	ADD(a,b,c);
} 
// Matrix multiplication 
int multipe(Arrays a,Arrays b,Arrays *c){
	int m=1,n=1,k=1;      //m by a The number of elements ,n by b The number of elements ,k by c The number of elements  
	if(a.cols!=b.cols||a.rows!=b.rows){
		return false;
	}
	c->cols=a.cols;
	c->rows=a.rows;
	while(m<=a.nums&&n<=b.nums){
		if(a.data[m].col==b.data[n].col&&a.data[m].row==b.data[n].row){
			c->data[k].col=a.data[m].col;
			c->data[k].row=a.data[m].row;
			c->data[k].value=a.data[m].value*b.data[n].value;
		}
		m++;n++;k++;
	}
} 
int main(){
	Arrays s;
	Arrays s1;
	Arrays s2;
	Arrays s3;
	int row, col, num;
	// establish 
	printf(" Please input the sparse matrix in sequence A The number of rows , Number of columns , The number of nonzero elements ( Space off ):\n");
	scanf("%d %d %d", &row, &col, &num);
	InitArray(&s,row,col,num);
	bianli2(&s);
	printf(" Please input the sparse matrix in sequence B The number of rows , Number of columns , The number of nonzero elements ( Space off ):\n");
	scanf("%d %d %d", &row, &col, &num);
	InitArray(&s1,row,col,num);
	bianli2(&s1);
	printf("--------- matrix B The transpose of is ：\n");
	Transform(s1,&s3);
	bianli2(&s3);
	printf("--------- Matrix multiplication is ：\n"); 
	multipe(s,s1,&s2);
	bianli2(&s2);
	printf("--------- The matrix is added to ：\n"); 
	ADD(s,s1,&s2);
	bianli2(&s2);
	printf("--------- The matrix is subtracted to ：\n");
	reduce(s,s1,&s2); 
	bianli2(&s2);
}

3、 ... and 、 Achieve results .