数据结构-数组

数组的定义:

    数组可以看成是线性表的推广。其特点是结构中的元素本身可以是具有某种结构的数据,但都属于同一数据类型。

    例如二维数组A(m*n),可以看成是由m个行向量组成的向量,也可以看成是n个列向量组成的向量。

    数组一旦被定义,它的维数和维界就不再改变。因此,除了结构的初始化和销毁从左之外,数组只有存取元素和修改元素值的操作。

数组的顺序表示:

    数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化,因此,一般采用顺序存储的方法来表示数组。

1.行优先顺序或以行为主序存储方式:将数组元素按行排列,第i+1个行向量紧接在第i个行向量后面,以二维数组为例,按行优先顺序存储的线性序列为:

a11,a12,…….,a1n,a21,a22,……,a2n,……,am1,am2,……,amn

第i行第j列元素的地址为:

LOC(aij) = LOC(a11)+[(i – 1)  *  n + j – 1] * d

其中:LOC(aij)为aij的存储位置;d为该数组的类型所占内存大小。(例如是int型的数组,这里d就是sizeof(int);

2.列优先顺序或以列为主序存储方式:将数组元素按列向量排列,第j+1个列向量紧接在第j个列向量之后,按列优先存储的线性序列为:

a11,a21,……,am1,a12,a22,……,am2,……,an1,an2,……,anm

同理第i行第j列的元素地址为:

LOC(aij) = LOC(a11) + [(j – 1) * m + i – 1] * d

行优先顺序–先排最右的下标,从右到左,最后排最左下标

列优先顺序–先排最左的下标,从左到右,最后排最右下标

数组存储的特点:

    只要知道开始节点的存放地址(即基地址)、维数和每维的上、下界,以及每个数组元素所占用的单元数,就可以将数组元素的存放地址表示为其下标的线性函数。因此,数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。

矩阵的压缩存储

压缩存储:为多个值相同的非零元素只分配一个存储单元;对零元素不分配空间

稀疏矩阵

设矩阵A中有s个非零元素,若s远远小于矩阵元素的总数(即s<<m*n),则称A为稀疏矩阵

设在矩阵A中,有s个非零元素。令e = s / (m * n),称e为矩阵的稀疏因子。通常认为e<=0.05时称之为稀疏矩阵。

由于稀疏矩阵中的非零元素一般没有分布规律,因此对稀疏矩阵进行压缩存储时,对于非零元素,必须同时记下它的值及其所在的位置(行号i,列号j)。反之,一个三元组(i,j,aij)可唯一确定矩阵A的一个非零元。

一个稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

对矩阵M中的非零元素构成一个三元组表:

( (1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7) )

#define MAXSIZE 10000
typedef int ElemType;
typedef struct{
    int I,j;
    ElemType v;
}TRIPLE;   //三元组
typedef struct{
    TRIPLE data[MAXSIZE];
    int m,n,t;
}TSMatrix;    //三元组顺序表类型

以上面矩阵M为例:

矩阵转置:

二维数组(矩阵)的转置:

int A[m+1][n+1], AT[n+1][m+1];
int i, j;

for (i = 1;i <= m; ++i)
    for (j = 1;j <= n; ++j)
        AT[j][i] = A[i][j];

对三元组进行转置的步骤:

(1)将矩阵的行列值相互交换

(2)将每个三元组中的i和j相互调换

(3)重排三元组之间的次序

typedef struct{
    TRIPLE data[MAXSIZE + 1];
    int m,n,t;
}TSMatrix;

void TransMatrix(TSMatrix A, TSMatrix &AT){
    AT.m = A.n;
    AT.n = A.m;
    AT.t = A.t;
    if (AT.t <= 0)
    return;
    for (int p = 1;p <= A.t;++p){
        AT.data[p].i = A.data[p].j;
        AT.data[p].j = A.data[p]/i;
        AT.data[p].v = A.data[p].v;
    }
}

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注