Array

2022-10-16

简介 Overview

定义 Definition

. 由类型相同的数据元素组成的有序集合；

特点 Features

. 线性表的特例

. 数量固定、类型相同、连续存储的数据序列

. 是随机存取的数据结构

. 存取元素时，依据的是每个元素在关系中的序号/索引/下标；从0开始

. 根据每个元素处于的相对关系，可以分为一维数组和多维数组；如一维数组可以看做数据元素是一维数组的一维数组[以一维数组为例]

. 数组一旦被定义，整个结构[维数、维界]就不再变化

. 更多信息，请访问数组 Array

抽象数据类型 ADT

. 数据对象

D={a1 ,a2, a3 , … , an}

. 数据关系

R1={<a0, a1>, <a1, a2>, … , <an-1, an>}

. 数据运算

Init( )	初始化
Destroy( )	销毁
Value( )	取值
Assign( )	赋值
Create( )	生成

一维数组的存储 Storage

. 利用数组首地址/基地址和数据的索引index，实现数据的随机存取；

//使用数组名代表的地址配合索引
loc( arr[i] )=loc( arr )+i*sizeof( elType )

//使用首元素地址配合索引
loc( arr[i] )=loc( arr[0] )+i*sizeof( elType )

[]遍历数组元素

#include <stdio.h>

int main() {
    int arr[5];
    printf("arr=%p\n", arr);
    printf("arr[0]=%p\n", &arr[0]);
    for (int i = 0; i < 5; i++)
    {
        printf("item[%d]=%p\n", i, &arr[i]);
    }
    return 0;
}
//参考结果为：
arr=0x7ffd5f830d80
arr[0]=0x7ffd5f830d80
item[0]=0x7ffd5f830d80
item[1]=0x7ffd5f830d84
item[2]=0x7ffd5f830d88
item[3]=0x7ffd5f830d8c
item[4]=0x7ffd5f830d90

多维数组的存储 Storage

设m行n列的多维数组A_mxn：

行优先存储

. 一行一行的存储

. 任一元素arr[i][j]位置为

loc(arr[i][j])=loc(arr[0][0])+(i*n+j)*sizeof(elType)

[示例]多维数组为A_4x3

a00	a01	a02
a10	a11	a12
a20	a21	a22
a30	a31	a33

行优先存储结果为：

[a00 a01 a02]

[a10 a11 a12]

[a20 a21 a22]

[a30 a31 a32]

列优先存储

. 一列一列的存储

. 任一arr[i][j]元素位置为

loc(arr[i][j])=loc(arr[0][0])+(j*m+i)*sizeof(elType)

[示例]多维数组为A_4x3

a00	a01	a02
a10	a11	a12
a20	a21	a22
a30	a31	a33

列优先存储结果为：

[a00 a10 a20]

[a01 a11 a21]

[a02 a12 a22]

[a03 a13 a23]

矩阵 Matrix

二维数组特别适合描述矩阵；实际应用中，矩阵的规模很大；为了加快运算速度，必须压缩。基本原则：

. 值重复的元素，只分配一个元素的存储空间

. 值为0的元素，不分配存储空间

. 可无损解压：没有分配存储空间的元素可以恢复

一、对称矩阵 Symmetric Matrix

满足以下条件的n阶矩阵

aij=aji (0≤I,j≤n)

. 存储时只需要存储上三角或下三角数据，包括对角线元素

. 需要的存储空间为：n(n+1)/2

a00	a01	a02	a03
a10	a11	a12	a13
a20	a21	a22	a23
a30	a31	a33	a33

1. 上三角存储

a00

a01

a02

a03

a11

a12

a13

a22

a23

a33

2. 下三角存储

a00

a10

a11

a20

a21

a22

a30

a31

a32

a33

二、三角矩阵 Triangular Matrix

1. 下三角矩阵：满足下面条件的n阶矩阵

. 存储时，除了存储下三角区域的元素外，还要增加一个存储空间，存放常数C

. 存储空间为：n(n+1)/2

aij=C，(0≤i < j≤n，C为常数，通常C=0)

a00	C	C	C
a10	a11	C	C
a20	a21	a22	C
a30	a31	a33	a33

a00

a10

a11

a20

a21

a22

a30

a31

a32

a33

2. 上三角矩阵：满足下面条件的n阶矩阵

. 存储时，除了存储上三角区域的元素外，还要增加一个存储空间，存放常数C

. 存储空间为：n(n+1)/2

aij=C，(0≤j < i≤n，C为常数，通常C=0)

a00	a01	a02	a03
C	a11	a12	a13
C	C	a22	a23
C	C	C	a33

a00

a01

a02

a03

a11

a12

a13

a22

a23

a33

三、稀疏矩阵 Sparse Matrix

稠密度

. 非零元素占矩阵所有元素的比值

. 矩阵稠密度<5%的矩阵，即：矩阵含有大量0元素，且分布没有规律；仅仅是0元素比较多

. 主要应用于大规模集成电路、计算机图形、图像处理

存储

. 只存储非0元素的信息

. 为了不丢失信息，实现无损解压，不仅要存储元素本身，还要存储元素的位置

. 数据结构参考定义

    typedef struct Arr
    {
        int row, col;
        int data;
    } Array;

四、转置矩阵

. 将矩阵A的行列互换得到的新矩阵称为转置矩阵A^T

[示例]

a00	a01	a02	a03
a10	a11	a12	a13
a20	a21	a22	a23
a30	a31	a33	a33

原矩阵A

a00	a10	a20	a30
a01	a11	a21	a31
a02	a12	a22	a32
a03	a13	a33	a33

转置矩阵A^T

应用 Application

串：模式匹配；

数组：存储；