6wz第6章特殊矩阵广义表及其应用

第6章数组及其应用1☞6.1数组与矩阵6.2特殊矩阵的压缩存储6.3矩阵的应用实例6.4广义表第6章特殊矩阵、广义表及其应用第6章数组及其应用2☞6.1.1数组与矩阵的概念及其相互关系6.1.2数组的存储结构6.1数组与矩阵第6章数组及其应用3数组的定义：数组是满足下列条件的同类型数据元素的集合：⑴对于该集合中任一数据元素来说，ji=0，…，bi-1，i=1，2，…，n，n0称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标；⑵数据元素之间的关系表示为Ri={，|，0≤jk≤bk-1，1≤k≤n且k≠i，0≤ji≤bi-2，i=1，2，…，n}，且R={R1，R2，...Rn}；nijjja......1nijjja......11nijjja......1nijjja......1第6章数组及其应用4下面以二维数组为例解释上述关于数组的定义。【例6.1】设有二维数组A，其第1维的长度b1=3，第2维的长度b2=4；数据元素描述为，其中j1=0，…，b1-1=0，1，2，j2=0，…，b2-1=0，1，2，3；则该二维数组共有12个具有相同数据类型的数据元素，分别为：a00a01a02a03a10a11a12a13a20a21a22a23第6章数组及其应用5可以看出，二维数组每一行是一个一维数组，元素间存在序偶关系；每一列也是一个一维数组，元素间也同样存在序偶关系。即：每个元素都受着两个关系的约束：，、，。若把每一行看作是一个整体，则行与行之间是线性关系；若把每一列看作是一个整体，则列与列之间也是线性关系。21jja121jja21jjia2jjia第6章数组及其应用6这样，我们可以把二维数组看成是一个线性表，它的每一个数据元素是一个一维数组，也是一个线性表。由此可以推广到n维数组。我们说n维数组是一个线性表，它的每一个数据元素是n-1维数组，也是一个线性表。数组一旦被定义，其维数及每维的长度(维界)就不再改变。因此，数组的运算除了初始化和销毁之外，只有查找元素和修改元素值的操作。第6章数组及其应用7矩阵的定义：矩阵是由m×n个数排列成m行(横向)、n列(纵向)所形成的矩形数表：)1,1(,..................212222111211njmiaaaaaaaaaamnmmijnnnmA称为m×n矩阵，简记为A=(aij)m×n，其中aij为A的第i行第j列的元素。第6章数组及其应用8矩阵与数组的关系：对照上述数组的定义，我们不难看出，矩阵中所有数据元素组成了一个二维数组，矩阵的每一行、每一列的数据元素分别组成等长的一维数组。我们也可以说，矩阵是一个线性表，其每一个数据元素(行或列)也是一个线性表。第6章数组及其应用96.1.1数组与矩阵的概念及其相互关系☞6.1.2数组的存储结构6.1数组与矩阵第6章数组及其应用10由于数组一般不作插入和删除操作，因此采用顺序存储结构是理所当然的。问题是：以什么次序来存储各元素的值？下面以二维数组为例来说明：二维数组一般有两种方法来存储：1、按行优先顺序存储将数组元素按行向量排列，i+1行向量接在i行向量后面。第6章数组及其应用11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n每个元素aij的长度第6章数组及其应用122、按列优先顺序存储将数组元素按列向量排列，j+1列向量接在j列向量后面。第6章数组及其应用13按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l每个元素aij的长度第6章数组及其应用14二维数组中任一元素的地址按上述两种方式顺序存储的数组，只要知道开始结点的存放地址和每维的上下界（m、n的值），以及每个数组元素所占用的字节数d，就可求出各个数组元素的存储地址。第6章数组及其应用15设数组的首地址即：a11的地址记为：LOC(a11)则：二维数组按“行优先顺序”存储，数组元素的存储地址为：LOC(a11)+前面i–1行元素所占字节数+第j行中前j–1个元素所占字节数即：LOC(aij)=LOC(a11)+(i-1)*n*d+(j-1)*d前面i–1行元素的个数（每行n个）每个元素所占的字节数第6章数组及其应用16【例2】已知二维数组A[m][m]按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K按列存储的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（尽管是方阵，但公式仍不同）【例1】一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组占用个字节。答：m*n*L=(6-1+1)*(7-0+1)*6=48*6=288第6章数组及其应用176.1数组与矩阵☞6.2特殊矩阵的压缩存储6.3矩阵的应用实例6.4广义表第6章特殊矩阵、广义表及其应用第6章数组及其应用18在用高级语言编写程序时，通常用二维数组来存储矩阵。但对一些数据分布呈某种规律的矩阵，或是0元素大量存在(远远多于非0元素)的矩阵，采用上述存储方法会造成存储空间的极大浪费。若矩阵中非0元素呈某种规律分布，或存在大量0元素，为节省存储空间，可对这类矩阵压缩存储：即：为多个相同的非0元素只分配一个存储空间，对0元素不分配存储空间。若值相同的非0元素或0元素在矩阵中的分布有一定的规律，我们称此矩阵为特殊矩阵；反之，称为稀疏矩阵。第6章数组及其应用19特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0=i,j=n-1则称A为对称矩阵。第6章数组及其应用20对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。a11a21a22……an1an2…anna11a12…a1na21a22…a2n…………an1an2…ann第6章数组及其应用21在这个下三角矩阵中，第i行恰有i+1个元素(i=0)，元素总数为：n(n+1)/2因此，我们可以按从上到下、从左到右将这些元素存放在一个向量sa[n(n+1)/2]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。a11a12…a1na21a22…a2n…………an1an2…ann第6章数组及其应用22☞若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≤kn(n+1)/2☞若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i0≤kn(n+1)/2a11a12…a1na21a22…a2n…………an1an2…ann等差数列第6章数组及其应用232、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图(a)所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图(b)所示。在大多数情况下，三角矩阵常数为零。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…………………..……………..cc…an-1n-1an-10an-11…an-1n-1(a)上三角矩阵(b)下三角矩阵第6章数组及其应用24三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[n(n+1)/2+1]中，其中c存放在向量的最后一个分量中。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…………………..……………..cc…an-1n-1an-10an-11…an-1n-1(a)上三角矩阵(b)下三角矩阵第6章数组及其应用25上三角矩阵中，主对角线之上的第i行(0≤in)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i*(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。因此，sa[k]和aij的对应关系是：k=i*(2n-i+1)/2+j-i当i≤jn(n+1)/2当ija00a01…a0n-1ca11…a1n-1……………….cc…an-1n-1(a)上三角矩阵(n-i)+(n-(i-1))+(n-(i-2))+…+(n-1)=(n-1)+(n-2)+…+(n-i)=i*n-(1+2+3+…+i)=i*n-(i*(i-1))/2=i*(2n-i+1)/2是矩阵中的C，存放在最后一个元素的后面第6章数组及其应用26下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是：i(i+1)/2+ji≥jn(n+1)/2ijk=a00c…ca10a11…c……………..an-10an-11…an-1n-1(b)下三角矩阵第6章数组及其应用273、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00a01a10a11a12a21a22a23….…..….an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1在n阶三对角矩阵中，除第一行和最后一行只有2个非0元素外，其余行均有3个非0元素。第6章数组及其应用28三对角矩阵有如下特点：时，1,2,11,,1,101,0,0nnjniiiijniji当aij非0；其它情况时，aij为0；第6章数组及其应用29我们以行序为主序进行存储三对角矩阵，并且只存储矩阵中的非0元素。在n阶三对角矩阵中，除了第一行和最后一行只有2个非0元素外，其余各行均有3个非0元素，共2+2+3*(n-2)=3n-2个非0元素。这样，可以将该三对角矩阵存储在一维数组sa[3n-2]中。现在，对给定的非0元素aij，与其对应的数组元素的下标是什么呢？第6章数组及其应用30由三对角矩阵的特点知，矩阵中的非0元素aij的前面有i行，共有3i-1个非0元素；在元素aij所在的第i行，aij之前有j-i+1个非0元素。因此可得与非0元素aij对应的数组元素的下标为：k=3i-1+j-i+1=2i+j这样，非零元素aij的地址为：LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d第6章数组及其应用31上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。第6章数组及其应用32稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即sm×n），则称A为稀疏矩阵。00-3001512000180900240000000–70014000000000000000M=第6章数组及其应用33在存储稀疏矩阵时，