1. symmetric matrix

(1) symmetric matrix

In an n-order square matrix A, if the elements satisfy the following properties:

aij=aji0≤i，j≤n- 1

Then a is called a symmetric matrix.

(2) Compressed storage of symmetric matrices

The elements in the symmetric matrix are symmetric about the main diagonal, so as long as the elements in the upper triangle or the lower triangle in the matrix are stored, every two symmetry element can enjoy a storage space. This can save nearly half of the storage space.

(1) Store the elements below the main diagonal (including diagonal) according to "line priority".

That is, press A00, A 10, a1,…, an- 1, 0, an- 1 …, an- 1, n-65438+.

These include:

sa[0]=a00，

sa[ 1]=a 10，

……,

sa[n(n+ 1)/2- 1]= an- 1，n- 1

② Storage location of element aij

There are I lines (from line 0 to line i- 1) before the aij element, and a * * * has:

1+2+…+I = I× (I+1)/2 elements;

In line I, there are only j elements before aij (that is, ai0, ai 1, …, ai, j- 1), so there are:

sa[i×(i+ 1)/2+j]=aij

③ ③ The correspondence between ③③AIJ and sa[k]:

If i≥j, k = i× (i+1)/2+j0 ≤ k.

If I < j, k = j× (j+1)/2+i0 ≤ k <; n(n+ 1)/2

Let I=max(i, j) and J=min(i, j), then the corresponding relationship between k and i, j can be unified as follows:

k = I×(I+ 1)/2+j0≤k & lt； n(n+ 1)/2

(3) the address calculation formula of symmetric matrix

LOC(aij)=LOC(sa[k])

= LOC(sa[0])+k×d = LOC(sa[0])+[I×(I+ 1)/2+J]×d

Through the subscript transformation formula, the corresponding position k of matrix element aij in its compressed storage representation sa can be found immediately. Therefore, it is a random access structure.