数据基础及教程 17

第5章

数组和稀疏矩阵5.1数组CONTENTS提纲5.2特殊矩阵的压缩存储1/415.3稀疏矩阵数组是二元组（idx，value）的集合，对每个idx，都有一个value值与之对应。idx称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d（d≥1）个整数称为维数是d。5.1.1数组的概念5.1数

组2/41数组按维数分为一维、二维和多维数组。一维数组A是n（n>1）个相同特性元素a0，a1，…，an-1构成的有限序列，其逻辑表示为A=（a0，a1，…，an-1），其中，A是数组名，ai（0≤i≤n-1）是数组A中序号为i的元素。一个二维数组可以看作是每个数据元素都是相同特性的一维数组的一维数组。以此类推。3/41二维数组的逻辑关系用二元组表示B=(D，R)R={r1，r2}r1={<1，2>，<2，3>，<3，4>，<5，6>，<6，7>，<7，8>，<9，10>，<10，11>，<11，12>} //同行关系r2={<1，5>，<5，9>，<2，6>，<6，10>，<3，7>，<7，11>，<4，8>，<8，12>} //同列关系4/41数组具有以下特点

（1）数组中各元素都具有相同的特性。

（2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后继元素。

（3）数组维数确定后，数据元素个数和元素之间的关系不再发生改变，特别适合于顺序存储。

（4）每个有意义的下标都存在一个与其相对应的数组元素值。5/41d维数组抽象数据类型ADTArray{

数据对象：

D={数组中所有元素}

数据关系：

R={r1，r2，…，rd}ri={元素之间第i维的线性关系|i=1，…，d}

基本运算：Value(A，i1，i2，…，id)：A是已存在的d维数组，其运算结果是返回A[i1，i2，…，id]值。Assign(A，e，i1，i2，…，id)：A是已存在的d维数组，其运算结果是

置A[i1，i2，…，id]=e。

…}6/411.一维数组一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中。其起始地址为第一个元素a0的地址即LOC(a0)。假设每个数据元素占用k个存储单元。则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出LOC(ai)=LOC(a0)+i×k

（1≤i<n）一维数组具有随机存取特性

数组的主要操作是存、取元素值，没有插入和删除操作，所以数组通常采用顺序存储方式来实现。5.1.2数组的存储结构7/41C++中一维数组的定义方式：Ta[M];其中M为常量，T为数组元素类型。也可以使用vector<T>容器作为一维动态数组。8/412.d维数组以m行n列的二维数组Am×n=(ai，j)为例讨论（二维数组也称为矩阵）。9/41按行优先存储ai,j前面有0～i-1共i行，每行n个元素，共有i×n个元素。在第i行中前面有a[i,0..j-1]，共j个元素。合起来，ai,j前面有i×n+j个元素。LOC(ai,j)=LOC(a0,0)+(i×n+j)×k

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：10/41按列优先存储ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素。在第j列中前面有a[0..i-1,j]，共i个元素。合起来，ai,j前面有j×m+i个元素。则：LOC(ai,j)=LOC(a0,0)+(j×m+i)×k

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：二维数组也具有随机存取特性，以此类推。11/41更一般地，数组A[c1..d1，c2..d2]，则该数组按行优先存储时有：LOC(ai，j)=LOC(ac1，c2)+[(i-c1)×(d2-c2+1)+(j-c2)]×k按列优先存储时有：LOC(ai，j)=LOC(ac1，c2)+[(j-c2)×(d1-c1+1)+(i-c1)]×k12/41C++中二维数组的定义方式：Ta[M][N];其中M、N为常量，T为数组元素类型。也可以使用vector<vector<T>>容器作为二维动态数组。13/41

【例5.1】设有二维数组a[1..50，1..80]，其a[1][1]元素的地址为2000，每个元素占2个存储单元，若按行优先存储，则元素a[45][68]的存储地址为多少?若按列优先存储，则元素a[45][68]的存储地址为多少？元素a[45][68]前面有1～44行，每行80个元素，计44×80个元素。在第45行中，元素a[45][68]前面有a[45][1..67]计67个元素，这样元素a[45][68]前面存储的元素个数=44×80+67。LOC(a[45][68])=2000+(44×80+67)×2=9174。按行优先存储14/41元素a[45][68]前面有1～67列，每列50个元素，计67×50个元素。在第68列中，元素a[45][68]前面有a[1..44][68]计44个元素，这样元素a[45][68]前面存储的元素个数=67×50+44。LOC(a[45][68])=2000+(67×50+44)×2=8788。按列优先存储15/41

【例5.1】设有二维数组a[1..50，1..80]，其a[1][1]元素的地址为2000，每个元素占2个存储单元，若按行优先存储，则元素a[45][68]的存储地址为多少?若按列优先存储，则元素a[45][68]的存储地址为多少？Cache内存CPU在C++语言中二维及以上维的数组就是按行优先存储的。在程序中采用数组存放大量的数据时，这些数据存放在内存中，当CPU读数组中的元素时并不是立即访问内存，而是先访问Cache（高速缓存，其速度比访问内存快得多）。如果访问的数据在Cache中便直接取相应的数据（称为命中），如果访问的数据不在Cache中才访问内存，并将访问数据所在的一个页块调入Cache。程序局部性原理16/41//程序Ainta[1000][50][8000];intmain(){for(inti=0;i<1000;i++)for(intj=0;j<50;j++)for(intk=0;k<8000;k++)a[i][j][k]=i+j+k;return0;}//程序Binta[1000][50][8000];intmain(){for(intk=0;k<8000;k++)for(intj=0;j<50;j++)for(inti=0;i<1000;i++)a[i][j][k]=i+j+k;return0;}程序A的执行时间为1.597秒，而程序B的执行时间为17.83秒，相差10多倍。？17/415.1.3数组的应用由于数组使用简单方便，特别是具有随机存取特性，因此在编程中数组被广泛地使用。使用数组目的一方面为了储存大量的数据类型相同的数据，避免重复性操作，另一方面用于模拟现实世界，例如顺序表就是采用数组模拟线性表。18/41n阶方阵A[n][n]a0,0a0,1a0,n-1

a1,0a1,1a1,n-1

an-1,0an-1,1an-1,n-1

ai,j（i<j）上三角ai,j（i>j）下三角ai,i（0≤i≤n-1）主对角线5.2特殊矩阵的压缩存储19/41若一个n阶方阵A的元素满足ai,j=aj,i（0≤i，j≤n-1），则称其为n阶对称矩阵。a0,0，a1,0，a1,1，，an-1,0，an-1,1，，an-1,n-1B=（b0，b1，b2，，，bs）下三角+主对角线n(n+1)/2个元素a0,0a0,1a0,n-1

a1,0a1,1a1,n-1

an-1,0an-1,1an-1,n-1

i≥jai,jbkk=?5.2.1对称矩阵的压缩存储20/41k=当i≥j时（下三角+主对角线的元素）当i<j时（ai,j=aj,i）i(i+1)2+jj(j+1)2+iB=(a0,0,a1,0,a1,1,

,ai-1,0,

,ai-1,i-1，ai,0,

,ai,j-1,ai,j,

,an-1,n-1)1个元素2个元素i个元素j个元素共计i(i+1)/2+j个元素bk21/41n2个元素

n(n+1)/2个元素A[0..n-1,0..n-1]

B[0..n(n+1)/2-1]

a[i][j]

b[k]对于对称矩阵A，采用一维数组B存储，并提供A的所有运算。k=当i≥j时（下三角+主对角线的元素）当i<j时（ai,j=aj,i）i(i+1)2+jj(j+1)2+i22/41a0,0a0,1a0,n-1

a1,1a1,n-1

an-1,n-1c

i≤j上三角矩阵5.2.2三角矩阵的压缩存储23/41a0,0a0,1a0,n-1

a1,1a1,n-1

an-1,n-1c

对于上三角部分的元素ai,j第0行：n个元素第1行：n-1个元素…第i-1行：n-i+1个元素i(2n-i+1)/2个元素第i行有a[i,i..j-1]：j-i个元素k=当i≤j时当i>j时存放常量ci(2n-i+1)2+j-in(n+1)224/41存放一个常量ck=当i≥j时当i<j时i(i+1)2+jn(n+1)2a0,0a0,1a0,n-1

a1,0a1,1a1,n-1an-1,0an-1,1an-1,n-1

ci≥j下三角矩阵25/41

若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（i≤j）的下标i、j与k的对应关系是（）。A.i(i+1)/2+j B.i(i-1)/2+jC.j(j+1)/2+i

D.j(j-1)/2+i

a1,1a1,2a1,n

a2,2a2,n

an-1,0an-1,1an,n

a1,0i≤jc按行还是按列初始下标从0还是从1开始1～j-1列的元素个数：j(j-1)/2第j列aij之前的元素个数：i-1k=j(j-1)/2+i-1+1=j(j-1)/2+i示例26/41

半带宽为b的对角矩阵

b条00……b条5.2.3对角矩阵的压缩存储27/41

A

B

a[i][j]b[k]当b=1时称为三对角矩阵其压缩地址计算公式如下：

k=2i+j

00对角矩阵压缩存储28/41一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t时，称该矩阵为稀疏矩阵。

例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。定性的描述5.3稀疏矩阵29/41稀疏矩阵和特殊矩阵的不同点：特殊矩阵的特殊元素（值相同元素、常量元素）分布有规律。稀疏矩阵的特殊元素（非0元素）分布没有规律。30/41通常按行优先顺序排列5.3.1稀疏矩阵的三元组表示31/41structTupElem { //单个三元组元素的类型intr;

//行号intc;

//列号

intd;

//元素值TupElem(){} //构造函数TupElem(intr1,intc1,intd1){ //重载构造函数r=r1;c=c1;d=d1;}};三元组表示中每个元素的类定义如下：32/41classTupClass { //三元组存储结构类

introws;

//行数

intcols;

//列数

intnums;

//非零元素个数

TupElem*data;

//稀疏矩阵对应的三元组顺序表

//基本运算算法};设计稀疏矩阵三元组存储结构类TupClass如下：33/41CreateTup(A,m,n)：由m行n列的稀疏矩阵A创建其三元组表示。Setvalue(i,j,x)：利用三元组给稀疏矩阵的元素赋值即执行A[i][j]=x。GetValue(i,j)：利用三元组取稀疏矩阵的元素值即执行x=A[i][j]。DispTup()：输出稀疏矩阵的三元组表示。TupClass类中包含如下基本运算方法：

其中，data列表用于存放稀疏矩阵中所有非零元素，通常按行优先顺序排列。这种有序