A, arrays,

1. Array definition

An array is an ordered collection of data elements of the same type. Each element is called an array element. Each element is constrained by n(n>=1) linear relationships, and the ordinal number of each element in n linear relationships is i1, I2… In is called the subscript of the element, and the data element can be accessed through the subscript.

Arrays are divided into one-dimensional arrays and multidimensional arrays.

Once an array is defined, its dimensions and bounds do not change. Therefore, in addition to structure initialization and destruction, arrays only have operations to access elements and modify their values.

1.1. One-dimensional Arrays

A one-dimensional array is an array with only one index, sometimes called a vector. It is the most basic data type, and must be declared in Java so that programs can reserve memory space during compilation.

The general format of the declaration is:

< data type >< variable name >[]=new< data type >[< array size >];

Copy the code

Such as:

float numbera=new int[5];

Copy the code

Declares a one-dimensional array of floating-point data type of length 5 named numbera.

1.2. Multidimensional Arrays

Multi-dimensional array refers to the number of subscripts of two or more, we are more commonly used is two-dimensional array.

A two-dimensional array is declared the same as a one-dimensional array. Format for:

< data type > < array name >[][]=new< data type >[sizel][size2];

Copy the code

Such as:

int data[][]=newim [5] [4];

Copy the code

Indicates that an integer two-dimensional array named data is declared.

2. Array storage

2.1 Storage of one-dimensional arrays

The one-dimensional array A[n] = {a0, a1… An-1} data stores are stored sequentially, with both logical and physical addresses contiguous.

Storage unit address of any data element AI in one-dimensional array: Loc(ai) = Loc(A0) + I * k (0 ≤ I < n), where K is the space occupied by a single element.

2.2 Storage of multidimensional arrays

Since memory is one-dimensional and arrays are multidimensional, a two-dimensional array can be thought of as a one-dimensional array in which each data element is a one-dimensional array; A three-dimensional array is a one-dimensional array where each data element is a two-dimensional array; A four-dimensional array is a one-dimensional array in which each data element is a three-dimensional array, and so on.

Taking the sequential storage of a two-dimensional array as an example, an M × N two-dimensional array can be regarded as a matrix:

You can also view it as a one-dimensional array of row vectors:

There are generally two kinds of two-dimensional arrays stored sequentially.

• Row priority: Stores the data in ascending order. Stores the data in ascending order based on the column number.

• Column priority: Stores columns in ascending order and rows in ascending order.

In the above two storage sequences, the first element to be stored is always the data element in the first row and column, so the address of the element is our known condition.

Loc(a[I,j]) = Loc(a[0, 0]) + (I * n + j) * K (0 ≤ I < m, 0 ≤ j < n), where K is the space occupied by a single element.

Loc(a[I,j]) = Loc(a[0,0]) + (j * m + I)* K (0 ≤ I < m,0 ≤ j < n), where K is the space occupied by a single element.

Second, the storage of matrix

1, matrix compression storage

So-called matrix compression storage, that is, when the storage arrays, as far as possible to reduce the storage space, so in the matrix storage, if there are rules, as long as the part of storage, and the other part of the memory address can through the corresponding algorithm calculated it, which occupies less storage space to achieve the purpose of storing the entire matrix.

The compressed storage of matrix is only for special matrix, and can not be used for two-dimensional array with no rules.

There are generally three kinds of compressed storage of two-dimensional array (matrix), which are symmetric matrix, sparse matrix and triangular matrix respectively.

1.1. Symmetric matrix

If the elements in the n-order matrix A satisfy the following conditions:

It becomes a symmetric matrix. The following cases:

Combining with the idea of data structure compression storage, we can use one-dimensional array to store symmetric matrices. Since the data in the matrix is equal along both sides of the diagonal, only one side of the diagonal (including the diagonal) is stored in the array.

The realization process of symmetric matrix is that if the elements in the lower triangle are stored, the row index I and column index J of each element are substituted into the following formula:

To store the elements of the upper triangle, substitute the row index I and column index J of each element into another formula:

The final k value is the location of the element stored in the array (the row and column labels of elements in the matrix start at 1).

For example, if the symmetric matrix mentioned above is stored in array SKR [6], the compressed storage state of the matrix is shown in the figure (the results of storing upper triangle and lower triangle are the same) :

Note that both formulas are used to store the elements of the matrix and to extract the elements of the matrix from the array. For example, if you want to extract the element at (3,1) in the matrix from the array in the figure above, since the element is located in the lower triangle, you need to use the lower trigonometric formula to obtain the position of the element in the array, namely:

1.2. Sparse matrix

Sparse matrix is a special case of matrix in which the number of non-zero elements is much smaller than the number of zero elements.

Sparse matrix compression storage is mainly realized by ternary representation. The storage rule is that each non-zero element occupies a row, and each row contains the row number, column number and value of the non-zero element.

For example, sparse matrix:

In ternary notation:

1.3. Triangular matrix

Diagonally divided, triangle matrix has two kinds of upper triangle and lower triangle.

The matrix with all the same data elements under the main diagonal is the upper triangular matrix, and the matrix with all the same elements on the main diagonal is the lower triangular matrix.

For this kind of special matrix, the compressed storage method is: the repeated element C can share a storage space, and the rest elements can be stored in the compressed storage method of symmetric matrix.

In this way, the symmetric matrix can be regarded as a special kind of triangular matrix.

Three, generalized table

1. Definition of generalized tables

Generalized table is a generalization of linear table, specifically defined as a finite sequence of N (n>=0) elements.

LS=(a1,a2,a3… Ai,… , an)

The data elements of a generalized table can be divided into two types, one is non-divisible (atoms) and the other is divisible (subtables).

Here are some common definitions of generalized tables:

• A = () : A represents A generalized table, except that the table is empty.
• B = (e) : There is only one atom E in the generalized table B.
• C = (a,(b, C,d)) : There are two elements in generalized table C, atom A and subtable (b, C,d).
• D = (A,B,C) : there are three subtables in the generalized table D, which are A,B and C respectively. This representation is equivalent to D = ((),(e),(b,c, D)).
• E = (a,E) : The generalized table E has two elements, atom A and itself. This is a recursive generalized table equivalent to: E = (a,(a,(a,…) )).

Some conclusions can be drawn from the above examples:

• The elements of a generalized table can be child tables, and the elements of a child table can also be child tables… Therefore, the generalized table is a multi-level structure.
• Generalized tables can be shared by other generalized tables.
• A generalized table can be a recursive table, that is, a generalized table can also be a subtable of itself.

When the generalized table is not empty, the first data (atomic or subtable) is called “table head”, and the new generalized table formed by the remaining data is called “table tail”.

2. Storage of generalized tables

Since the data elements in the generalized table have different structures, usually a recursive data structure, it is difficult to allocate a fixed size of storage space for each generalized table. Generally, it is represented by a chain storage structure, and there are two storage modes, head and tail representation and child sibling representation.

2.1. Head and tail representation

Any nonempty generalized table can be decomposed into header and tail, conversely, a pair of determinate header and tail can uniquely determine a generalized table.

There are two kinds of nodes in the head and tail representation: one is the table node, which can represent the word table; One is atomic nodes, which represent atoms.

There are three fields in the table node: marker field, pointer field to the table head and pointer field to the table tail; Atomic nodes require two domains: the flag domain and the range domain. The flag field is used to distinguish between these two types of nodes.

2.3. Child brother representation

In child sibling notation, atomic nodes and table nodes are represented by two similar types of nodes.

Where, the table node has the child node, cp and bp respectively point to the pointer field of the first child to change a brother.

Atomic nodes are childless nodes, and data and BP are domains and pointer fields to siblings, respectively.

Tag is a flag field, which is used to distinguish the two types of nodes. If tag is 1, it indicates that the node is a table node, that is, the node with children. If tag is 0, it means that the node is atomic node, i.e., childless node.

Relearn data Structure (3, Queue)

---

Reference:

[1] : Deng Junhui. Data Structure and Algorithm [2] : Wang Shimin et al. Data Structure and Algorithm Analysis [3] : “Data-structures -and Algorithm-In-Java -6th-Edition” [4] : Yan Weimin, Wu Weimin. “Data Structures” [5] : [7] : Matrix (sparse matrix) compressed storage (3 ways) [8] : What is generalized table, generalized table and definition details