数据结构（Java语言版）课件 第五章 数组

数据结构（Java语言版）05数组【知识目标】

掌握数组的基本概念；

掌握一维数组和二维数组的应用；

掌握特殊矩阵及其压缩存储结构；

掌握稀疏矩阵及其压缩存储结构。【能力目标】

能熟练应用数组解决简单的实际问题；

能根据顺序存储结构特点进行数组元素地址的计算；

会对特殊矩阵进行压缩存储；

会对稀疏矩阵进行三元组存储并实现相关算法。1.数组的定义 数组（Array）是一组具有相同数据类型的数据集合。数组中的每个数据称为数据元素。数据元素按次序存储于一段地址连续的内存空间中。数组的基本概念0123data.length-1

一维数组可以通过下标访问数组中的任何元素。数组元素的访问格式如下：

<数组名>[<下标表达式>]，a[0]

Java还提供了length返回数组的长度，即数组中元素个数，其格式如下：

<数组名>.length数组维数数组下标的个数就是数组的维数，有一个下标就是一维数组；有两个下标就是二维数组；有三个以上的下标，就统称为多维数组。数组的基本概念根据系统为数组分配内存空间的方式：

静态数组：声明时

指定元素个数

动态数组：声明时不指定数组长度

数组的基本概念例：intarr[3][4]表示二维数组元素的方法：intarr[3][4]={{1,2,3,4}{5,6,7,8}{9,10,11,12}}intarr[3][4]={1,2,3,4,5,6,7,8,9,10,11,12}数组的基本概念表示某个特定元素时：arr[2][1]=1;Intarr[2][1]=｛0,0,0,0,0,0,0,0,0,1｝数组的基本概念如果a[0]存储的位置表示为LOC(a[0]),那一维数组中任一元素a[i]的存储位置为：LOC（a[i]）=LOC（a[0]）+(i)×La[i]前有（0~i-1）共i个元素，其中L是每个数据元素所占存储空间的大小。一维数组元素存储位置二维数组元素的存储位置a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij………am-1,0am-1,1…am-1,n-1A=

m行n列的二维数组二维数组的一般有两种存储方式：行为主序,列为主序a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij………am-1,0am-1,1…am-1,n-1A=

m行n列的二维数组以行为主序a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij………am-1,0am-1,1…am-1,n-1A=

m行n列的二维数组以列为主序如，一个2×3的二维数组Aa00a01a02a10a11a12A2×3=

a00a01a02a10a11a12a00a10a01a11a02a12以行为主序以列为主序

二维数组元素的存储位置二维数组a[m][n]，以行为主序存储，元素a[i][j]的存储位置：LOC(a[i][j])=LOC(a[0][0])+(i×n+j)×L首地址：LOC(a[0][0])a[i][j]前有i行，每行元素个数为n，在第i+1行中a[i][j]的前面还有j个数组元素。L：数组元素所占空间。a00a01…a0,n-1a10a11…a1,n-1…

…

…

aij

………am-1,0am-1,1…am-1,n-1A=

二维数组元素的存储位置特殊矩阵的压缩存储矩阵是很多科学与工程计算问题中研究的数学对象，通常用二维数组来存储矩阵元素。

5x1+2x2+x3=12-x1+4x2+2x3=202x1-3x2+10x3=3521-1422-310线性方程组构成的矩阵有时矩阵元素零元素或相同元素分布呈现一定规律，我们称之为特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。为了节省存储空间，可以对这类特殊矩阵进行压缩存储，所谓压缩存储就是对多个值相同的元素只分配一个存储空间，对零元素不分配空间。1600068008000003000022060000000019-1500000

N=对称矩阵

在一个n阶方阵中，若数据元素满足A[i][j]=A[j][i]（0≤i,j≤n-1）

则称之为对称矩阵。3６896２5885169860A=对称矩阵可以为每一对对称元素分配一个存储空间，把n2个元素压缩到n(n+1)/2个存储空间中。将矩阵A以行为主序压缩存储到一维数组SA中，则矩阵元素A[i][j]和数组元素SA[k]之间对应关系:

a00a10a11a20a21a22…a00

a01

a02

a03

a10

a11

a12

a13

a20

a21

a22

a23

a30

a31

a32

a33

A=SA01230123对称矩阵对称矩阵若i≥j：A[i][j]之前有i行元素，共有1+2+…+i=i×(i+1)/2个，A[i][j]之前有j个元素，因此A[i][j]前面共有i×(i+1)/2+j个元素分别存储在SA[0]到SA[i×(i+1)/2+j-1]，所以A[i][j]存储在

SA[i×(i+1)/2+j]中，所以k=i×(i+1)/2+j

若i<j：则A[i][j]与居于下三角矩阵中的元素A[j][i]值相当,所以j、i带入上式：k=j×(j+1)/2+i

对称矩阵对称矩阵A[i][j]压缩存储到一维数组

SA[k]中

i≥j：k=i×(i+1)/2+j

i<j：

k=j×(j+1)/2+i

SA思考：对称矩阵压缩存储到SA[k]中，编写算法获取对称矩阵元素A[i][j]的值a00a10a11a20a21a22…三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。上三角矩阵下三角矩阵三角矩阵a00c……ca10a11

c…c……………an-1,0an-1,1…an-1,n-1下三角矩阵n*n的三角矩阵的压缩存储：重复元素c、n×(n+1)/2个元素，可存储到数组元素SA[0]…SA[n(n+1)/2]中，其中c存放在最后一个数组元素中。分析下三角矩阵元素存储于数组SA中的位置，即i、j、k的关系。例：

10ccc89cc567c1234A=a21对应的k=i*(i+1)/2+j=4a00c……ca10a11

c…c……………an-1,0an-1,1…an-1,n-1k=i*(i+1)/2+j当i≥jn*(n+1)/2当i<j(常数c的存储位置)三角矩阵稀疏矩阵设m×n矩阵中有s个非零元素，若且s<<m×n(s/(m×n)≤0.05)，且这些非零元素在矩阵中分布又没有什么规律，则称这种矩阵为稀疏矩阵。1600220-1508300000060000000068000000000190稀疏矩阵M

M=思考：这样的矩阵如何压缩存储到计算机中？1600220-1508300000060000000068000000000190稀疏矩阵M

M=

稀疏矩阵的压缩存储由于非零元素在矩阵中分布没有规律，所以除了存储矩阵元素值外还要存储该元素所在的行号和列号，所以用一个三元组（i,j,aij）便可唯一的确定了矩阵中一个非零元素。为了计算方便,这里i和j都从“1”开始.1600220-1508300000060000000068000000000190稀疏矩阵M

M=稀疏矩阵的压缩存储8个三元组表示出了矩阵M中的8个非零元素。1600220-1508300000060000000068000000000190稀疏矩阵M

M=（1116）（1422）（1