数组和特殊矩阵

数组和特殊矩阵第1页，共42页，2023年，2月20日，星期五数组的基本概念（P65）数组的定义数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。数组的特点元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。第2页，共42页，2023年，2月20日，星期五

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

A=(A1，A2，……，An)其中：

Ai=(a1i，a2i，……，ami)(1≤i≤n)数组——线性表的推广二维数组是数据元素为线性表的线性表。数组的基本概念第3页，共42页，2023年，2月20日，星期五设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×c

calai-1ai……ahal+1……Loc(al)Loc(ai)数组的存储结构——一维数组(P66)第4页，共42页，2023年，2月20日，星期五常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

二维数组内存二维结构一维结构数组的存储结构——二维数组第5页，共42页，2023年，2月20日，星期五特殊矩阵的压缩存储特殊矩阵：包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。

稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：为多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。第6页，共42页，2023年，2月20日，星期五3647862842481697460582957A＝对称矩阵特点：aij=aji如何压缩存储？只存储下三角部分的元素。特殊矩阵的压缩存储——对称阵第7页，共42页，2023年，2月20日，星期五对于下三角中的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i

。第1行第n-1行第0行

a00

a10

a11

a20

a21

a22

aij…

an-10

an-11…an-1n-1…第2行012345kn(n+1)/2-1特殊矩阵的压缩存储——对称阵第8页，共42页，2023年，2月20日，星期五3c

c

c

c6

2

c

c

c48

1

c

c7

4

6

0

c8

2

9

5

7(a)下三角矩阵34810c

2

9

4

6c

c１57c

c

c

0

8c

c

c

c7(b)上三角矩阵如何压缩存储？只存储上三角（或下三角）部分的元素。特殊矩阵的压缩存储——三角阵第9页，共42页，2023年，2月20日，星期五矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i×(i＋1)/2＋j

当i≥jn×(n＋1)/2当i＜jk=012345

k

n(n+1)/2第1行第0行

a00

a10

a11

a20

a21

aij…an-1n-1…第2行

c

a22存储下三角元素对角线上方的常数——只存一个特殊矩阵的压缩存储——三角阵第10页，共42页，2023年，2月20日，星期五矩阵中任一元素aij在数组中的下标k与i、j的对应关系：

i×(2n－i＋1)/2＋j－i

当i≤jn×(n＋1)/2当i＞jk=存储上三角元素对角线上方的常数——只存一个特殊矩阵的压缩存储——三角阵第11页，共42页，2023年，2月20日，星期五对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

a00a010

0

0a10a11

a120

00a21

a22

a23000

a32

a33

a340

0

0

a43

a44A=特殊矩阵的压缩存储——对角矩阵第12页，共42页，2023年，2月20日，星期五a00a010

0

0a10a11

a120

00a21

a22

a23

000

a32

a33

a340

0

0

a43

a44A=将带状区域立起来0a00

a01a10a11

a12a21

a22

a23a32a33

a34a43

a440B=s＝j-i+1t=i映射到二维数组B中，映射关系特殊矩阵的压缩存储——对角矩阵第13页，共42页，2023年，2月20日，星期五按行存储元素aij在一维数组中的序号=2+3(i－1)+(j－i+2)=2i+j+1

∵一维数组下标从0开始∴元素aij在一维数组中的下标=2i+j(b)寻址的计算方法(c)压缩到一维数组中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112(a)三对角矩阵

0

00

000

000

000

A=a00a01a10a11

a12a21a22

a23a32a33

a34a43a44特殊矩阵的压缩存储——对角矩阵第14页，共42页，2023年，2月20日，星期五1500000

0110000

000600

0000009

00000A=如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储——稀疏矩阵第15页，共42页，2023年，2月20日，星期五（1）三元组顺序表（P69）将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)——三元组（2）十字链表（P72）采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：稀疏矩阵的压缩存储rowcolitemdownright第16页，共42页，2023年，2月20日，星期五例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=三元组顺序表操作——转置操作第17页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）00150491

1111

213

3022

326

50-15

空空空闲闲闲rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）三元组顺序表操作——转置操作第18页，共42页，2023年，2月20日，星期五三元组顺序表操作——转置算法1基本思想：在A的三元组顺序表中依次找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。第19页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）三元组顺序表操作——转置算法1第20页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）在矩阵A中查找第0列非零元，顺序存储到矩阵B中00150491第21页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111在矩阵A中查找第1列非零元，顺序存储到矩阵B中第22页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111213在矩阵A中查找第2列非零元，顺序存储到矩阵B中第23页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）0015049111112133022326在矩阵A中查找第3列非零元，顺序存储到矩阵B中第24页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111213326在矩阵A中查找第4列非零元，顺序存储到矩阵B中3022第25页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111213302232650-15在矩阵A中查找第5列非零元，顺序存储到矩阵B中第26页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111213302232650-15在矩阵A中查找第6列非零元，顺序存储到矩阵B中第27页，共42页，2023年，2月20日，星期五1.设置转置后矩阵B的行数、列数和非零元个数；2.在B中设置初始存储位置q；3.for(col=最小列号;col<=最大列号;col++)3.1在A中查找列号为col的三元组；3.2交换其行号和列号，存入B中q位置；3.3q++；三元组顺序表操作——转置算法1第28页，共42页，2023年，2月20日，星期五三元组顺序表操作——转置算法1该算法的主要时间耗费是在col和p的两重循环上。对于一个m行n列且非零元素个数为t的稀疏矩阵而言，该算法的时间复杂度为O(tn)。最坏情况是，当稀疏矩阵中的非零元素个数t与mn同数量级时，上述算法的时间复杂度就为O(mn2)。显然这种情况下，该朴素算法效率较低。第29页，共42页，2023年，2月20日，星期五分析：A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数，以此类推。基本思想：顺序取，直接存。即在A中依次取三元组，交换其行号和列号放到B中适当位置。如何确定当前从A中取出的三元组在B中的位置？三元组顺序表操作——转置算法2第30页，共42页，2023年，2月20日，星期五

rowcolitem0123456MaxTerm-16（矩阵的行数）5（矩阵的列数）7（非零元个数）001504911111213302232650-15第0列第1个非零元素第0列有2个非零元素第1列第1个非零元素三元组顺序表操作——转置算法2第31页，共42页，2023年，2月20日，星期五引入两个数组作为辅助数据结构：cnum[cols]：存储矩阵A中某列的非零元素的个数；cpot[clos]：初值表示矩阵A中某列的第一个非零元素在B中的位置。数据结构设计：cpot[0]=0；cpot[col]=cpot[col-1]+cnum[col-1]；1≤col＜cols-1cnum与cpot存在如下递推关系：三元组顺序表操作——转置算法2第32页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem0123456MaxTerm-15（矩阵的行数）6（矩阵的列数）7（非零元个数）

col012345cnum[col]21

12

01cpot[col]

023466根据矩阵A计算cnum和cpot

第33页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem01234565（矩阵的行数）6（矩阵的列数）7（非零元个数）将矩阵A中col列元素存放在B中下标为cpot[col]的位置

rowcolitem01234566（矩阵的行数）5（矩阵的列数）7（非零元个数）cpot[0]cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]0015cpot[0]第34页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem01234565（矩阵的行数）6（矩阵的列数）7（非零元个数）将矩阵A中col列元素存放在B中下标为cpot[col]的位置

rowcolitem01234566（矩阵的行数）5（矩阵的列数）7（非零元个数）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]0015cpot[0]3022cpot[3]第35页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem01234565（矩阵的行数）6（矩阵的列数）7（非零元个数）将矩阵A中col列元素存放在B中下标为cpot[col]的位置

rowcolitem01234566（矩阵的行数）5（矩阵的列数）7（非零元个数）cpot[1]cpot[2]cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]cpot[5]第36页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem01234565（矩阵的行数）6（矩阵的列数）7（非零元个数）将矩阵A中col列元素存放在B中下标为cpot[col]的位置

rowcolitem01234566（矩阵的行数）5（矩阵的列数）7（非零元个数）cpot[1]cpot[2]cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]1111cpot[1]第37页，共42页，2023年，2月20日，星期五0015032205-1511111232364091

空空空闲闲闲rowcolitem01234565（矩阵的行数）6（矩阵的列数）7（非零元个数）将矩阵A中col列元素存放在B中下标为cpot[col]的位置

rowcolitem01234566（矩阵的行数）5（矩阵的列数）7（非零元个数）cpot[2]cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]1111cpot[1]213cpot[2]cpot[1]第38页，共42页，2023年，2月20日，星期五0015032205-15