This is the 14th day of my participation in Gwen Challenge

Stack and queue applications

The stack

  • Parentheses matching
  • Expression evaluation
  • recursive

The queue

  • Hierarchical traversal (BFS)

Compressed storage of special matrices

Storage computing

  • A one-dimensional array LOC (ai) = LOC (a0) + (I) * L (0 or less I < n) LOC (a_i) = LOC (a_0) + (I), times the L (0, le I < n) LOC (ai) = LOC (a0) + (I) * L (0 or less I < n)
  • A two-dimensional array [l1, h1], [l2, h2] [l_1, h_1], [l_2, h_2] [l1, h1], [l2, h2]

1. Line is preferred L O C ( a i . j ) = L O C ( a l 1 . L 2 ) + [ ( i – l 1 ) x ( h 2 – l 2 + 1 ) + ( j – l 2 ) ] x L 2. The column is preferred L O C ( a i . j ) = L O C ( a l 1 . L 2 ) + [ ( j – l 2 ) x ( h 1 – l 1 + 1 ) + ( i – l 1 ) ] x L 1. Line priority \ \ LOC (a_ {I, j}) = LOC (a_ {l_1 and L_2}) + [(I – l_1) \ times (h_2 L_2 + 1) + (j – L_2)] \ \ \ 2 times L. Column priority \ \ LOC (a_ {I, j}) = LOC (a_ {l_1 and L_2}) + [(j – L_2) \ times (h_1 – l_1 + 1) + (I – l_1)] \ times L \ \

Matrix compression

Symmetric matrices

Triangular matrix

Tridiagonal matrix

Diagonal matrix aka banded matrix [three like diagonals]

  • k=2i+j-3
  • i = |(k+1)/3 +1|
  • j = k-2i+3

Sparse matrix

For the large sparse matrix that appears in practical problems, if it is stored in the computer by conventional allocation method, it will waste a lot of memory, and will also waste a lot of time in accessing and operating. In order to solve this problem, a variety of solutions have been produced.

Due to its sparse characteristics, the memory cost of sparse matrix can be greatly reduced by compression. The specific operation is to form a triplet (I,j, V) of the row, column and value of the non-zero element, and then store these triples according to some rules. This method can save storage space.

#define SMAX 1000
typedef struct
{
    int i,j;     // Store row and column information for non-zero elements
    ElementType e; // The value of a non-zero element
} Triple;       // Define the triple type
typedef struct
{
    int mu,nu,tu; // The number of rows, columns, and non-zero elements of the matrix
    Triple data[SMAX]; // Table of triples} TSMatrix;Copy the code

Take a chestnut

So for a simple matrix transpose, how do you do it using triples?

Swap the val values that represent the rows and columns, and then reorder them.