Compressed storage of arrays and special matrices

Catalog

One 、 Array related concepts

Two 、 Abstract data type definition of array

3、 ... and 、 The sequential storage structure of an array

Four 、 Compressed storage of special matrices

5、 ... and 、 The sequential storage method of sparse matrix —— Triple storage

6、 ... and 、 The chain storage method of sparse matrix —— Cross linked list

---

One 、 Array related concepts

1、 Declaration format ： data type Variable name [ Row number ] [ Number of columns ]

example :int num[5] [8]

stay C In language , A two-dimensional array type can also be defined as a one-dimensional array type ( Its component type is one-dimensional array type ).

2、 Three dimensional array : If the elements in a two-dimensional array are a one-dimensional array , Is called a three-dimensional array .

n Dimension group : if n-1 The element in the dimension group is a one-dimensional array structure , It's called n Dimension group .

3、 Conclusion ： Linear table structure is a special case of array structure , The array structure is an extension of the linear table structure .

4、 Array characteristics : Fixed structure —— After the definition , The dimension and dimension boundary no longer change .

Two 、 Abstract data type definition of array

1、 Basic operations of arrays : In addition to the initialization and destruction of the structure , Only the operations of fetching elements and modifying element values .

2、 Basic operation ：

(1) InitArray (&A,n, bound1, ...boundn)                                       // Construct an array A

(2) DestroyArray (&A)                                                                // Destroy array A

(3) Value(A, &e,index1,...,indexn)                                             // Take the value of the array element

(4) Assign (A, &e,index1,...,indexn)                                        // Assign values to array elements

3、 ... and 、 The sequential storage structure of an array

1、 because ： Array characteristics : The structure has fixed dimension and constant dimension bound . An array of basic operations : initialization 、 The destruction 、 Take the element 、 Modify element values , Insert and delete operations are generally not performed .

therefore ： Generally, the array is represented by sequential storage structure .

Be careful : Arrays can be multidimensional , But the address of the memory unit where the data element is stored is one-dimensional , therefore , Before storing the array structure , We need to solve the problem of mapping multidimensional relationships to one-dimensional relationships .

2、 Two sequential storage methods ：① The main order is line order （ Subscript first ）② The main order is column order （ Subscript first ）

for example ： The main order is line order ： Set the starting storage position of the array LOC( 0, 0 ), Storing each element requires L Storage units are array elements a[i][j] The storage location of is : LOC( i, j)= LOC(0,0)+(n*i+j)*L.(n Is the number of elements contained in each row ,n*i+j It means that a[i][j] The number of all the previous elements ）.

Four 、 Compressed storage of special matrices

1. Definition of compressed storage ： If the values of multiple data elements are the same , Only one element value is allocated , And zero elements don't take up storage space .

2. Compressible matrix ： Some special matrices , Such as : Symmetric matrix , Diagonal matrix , Trigonometric matrix , Sparse matrix, etc .

3. sparse matrix ： The number of nonzero elements in a matrix is small ( Generally less than 5%).

4、 The principle of compressed storage ： Store the value of each nonzero element 、 Row and column position and the number of rows and columns of the matrix .

5、 ... and 、 The sequential storage method of sparse matrix —— Triple storage

1、 A triple （i,j,Aij） A non-zero element of a matrix can be uniquely determined .

2、 Advantages of triple sequence table : Non zero elements in the table by Line order Orderly storage , So it is convenient for Perform matrix operations that are processed in row order .

3、 Disadvantages of triple sequence table : No random access , If you access non-zero elements in a line by line number , You need to find it from scratch .

6、 ... and 、 The chain storage method of sparse matrix —— Cross linked list

1、 advantage : It can flexibly insert new non-zero elements generated by operation , Delete the new zero element generated by the operation , Realize various operations of matrix .

2、 In the cross linked list , Each non-zero element of the matrix is represented by a node , This node except (row, col, value) outside , There are also two domains :

①right: Used to link the next non-zero element in the same row ;

②down: Used to link the next non-zero element in the same column .

3、 Structure diagram of nodes in cross linked list