第5章 数组与广义表-稀疏矩阵

《第5章 数组与广义表-稀疏矩阵》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构讲义第5章数组与广义表黄可坤嘉应学院—稀疏矩阵1数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：()()()()()()()()()可以看成是由一个行向量组成的向量，也可以看成是由一个列向量组成的向量。2数组的两种顺序存储方式(1)以行序为主序(2)以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序

2、存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l3矩阵的压缩存储在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储

3、空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素。其存储形式如图所示：15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-

4、12…an-1n-1图5.1对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2因此，我们可以按从上到下、从左到右将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若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≦k

5、上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i0≦k

6、阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s<

7、0024000000000–70180000000140001500–7000000000000000图5.4稀疏矩阵M和TM=T=假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法—三元顺序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triplet;typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;稀疏矩阵的转置的实现一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i]

8、[j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，