Number structure (C language) -- Chapter 4, compressed storage of matrices (Part 2)

Individuality signature ： The most important part of the whole building is the foundation , The foundation is unstable , The earth trembled and the mountains swayed . And to learn technology, we should lay a solid foundation , Pay attention to me , Take you to firm the foundation of the neighborhood of each plate .
Blog home page ： Qigui's blog
special column ： data structure （C Language version ）
From the south to the North , Don't miss it , Miss this article ,“ wonderful ” May miss you la
Triple attack( Three strikes in a row ):Attention,Like and Collect.

One 、 Compressed storage of matrix

（ One ）、 Storage structure of array

1、 One dimensional array

（1）、 Definition ：

ElemType a[MaxSize]; //ElemType Type one-dimensional array
Each array element has the same size , And physically continuous storage

int main()
{
    
	int a[10]={
    0};
	int i=0;
	for(i=0;i<10;i++)
		a[i]=i;
	return 0;
}

Array elements a[i] Storage address = Initial address +i*sizeof(ElemType)

2、 Two dimensional array

（1）、 Definition ：

ElemType b[M][N]; //M That's ok N Two dimensional array of columns

（2）、 storage ：

Row first storage or column first storage .M That's ok N Two dimensional array of columns b[M][N] in ,
If pressed Line first Storage , be b[i][j] Storage address = Initial address +(iN+j)sizeof(ElemType)
If pressed Column priority Storage , be b[i][j] Storage address = Initial address +(jM+i)sizeof(ElemType)

（ Two ）、 Special matrix

Some matrices with high order often appear in numerical analysis , At the same time, there are many elements with the same value in the matrix , Or zero element . Sometimes To save storage space , This kind of matrix can be compressed and stored .
Compressed storage ： It means that only one storage space is allocated for multiple elements with the same value , Do not allocate storage space to zero elements . The purpose is to save storage space .
If the elements with the same value or zero elements are distributed regularly in the matrix , Then we call this kind of matrix Special matrix

1、 Symmetric matrix

if n Any element of a square matrix of order $a_{i,j}$ There are $a_{i,j}$=$a_{j,i}$ Then the matrix is Symmetric matrix

The symmetric matrix A[1…n][1…n] Stored in one-dimensional array B[n(n+1)/2] in ,B The numerical subscript is from 0 Start

Ordinary storage ：n*n Two dimensional array
Compressed storage policy ：

（1）、 Lower triangular matrix ：

Store only the main diagonal （i=j）+ Lower triangle （i>j）

if i>=j, Lower triangle elements A[i][j] The storage position in the array is （i-1）*i/2+j-1

（2）、 Upper triangular matrix ：

Store only the main diagonal （i=j）+ Upper triangle （i<j）

if i<j, Upper triangle element A[i][j] The storage position in the array is （j-1）*j/2+i-1

2、 Trigonometric matrix

Similar to symmetric matrices , The difference is that after storage （ Next ） Elements on the triangle and the main diagonal , Also store the elements on the other side of the diagonal once .
Put this on （ Next ） Trigonometric matrix A[1…n][1…n] Compressed storage in B[n(n+1)/2+1] in .

Compressed storage policy ： Line by line priority / The principle of column priority will be （ On ） The triangle elements are stored in a one-dimensional array , And store the constant in the last position c

（1）、 Lower triangular matrix ： Except for the main diagonal and the lower triangle , The rest of the elements are the same

The subscript of any element in the lower triangular matrix in an array k And i、j The corresponding relation of is ：
1、i>=j：（i-1）i/2+j-1;
2、i<j：n(n+1)/2

（2）、 Upper triangular matrix ： Except for the main diagonal and the upper triangle , The rest of the elements are the same

The subscript of any element in the upper triangular matrix in an array k And i、j The corresponding relation of is ：
1、i>=j：（i-1）（2n-i+2）/2+（j-i）;
2、i<j：n(n+1)/2

3、 Tridiagonal matrix （ Also known as banded matrix ）

In a tridiagonal matrix, except for the elements on the main diagonal and the two diagonals most adjacent above and below the main diagonal , All elements are 0.

All in all 3n-2 A non-zero element . When |i-j|>1 when , Yes $a_{i,j}$=0
Compressed storage ： Line by line priority （ Or column priority ） principle , Store only the banded portion

4、 sparse matrix

The number of non-zero elements is far less than the number of matrix elements and the distribution is irregular .

Compressed storage policy ： Only non-zero elements are stored

（1）、 Sequential storage :

A triple < That's ok , Column , value >
Non zero elements and their rows and columns form a triple （ Line mark 、 Column mark 、 value ）. Sparse matrix compressed storage will lose the characteristics of random access

// Definition of triples 
struct element
{
    
	int row,col;
	ElemType item;
}

（2）、 Chain store :

Cross linked list method
Rightward field right： Point to the next element of the peer
Down field down： Point to the next element in the same column