第5章_数组和广义表07.ppt

1、第5章 数组和广义表,学习要点,了解数组在以行序为主的存储中的地址计算方法。 掌握特殊矩阵和稀疏矩阵的存储方法。 掌握广义表的结构特点及其存储表示方法。,5.1 数组的基本概念,a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1,Amn=,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组可看成由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。,5.

2、1 数组的定义和特性,二维数组可看成一个线性表A=(a0，a1，ap) (p=m-1或n-1)，其中aj是一个列向量形式的线性表： aj=（a0j，a1j，am-1,j）， 0jn-1 或ai是一个行向量形式的线性表： ai=（ai0，ai1，ai,n-1）， 0im-1,a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1,a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1,a0 a1 ap,a0 a1 ap,5.2 数组的顺序表示与实现,由于计算机的内存结构是一维的，用一维内存来表示多

3、维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。通常有两种顺序存储方式： 1. 行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，其存储线性序列为： a00,a01,a0,n-1,a10,a11,a1,n-1,am-1,0, ,am-1,n-1 2. 列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，二维数组按列优先顺序存储的线性序列为： a00,a10,am-1,0,a01,a11,am-1,1,am-1,1, ,an-1,m-1,a00 a01 a0,n-1 a10 a11 a1,n-1 am-1

4、,0 am-1,1 am-1,n-1,a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1,行 优 先 顺 序,列 优 先 顺 序,数组的顺序表示与实现,按上述两种方式顺序存储的数组，只要知道开始结点的地址，维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素存放地址表示为其下标的线性函数。 例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用L个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i+1行、第j+1列，前面i行一共有in个元素，第i+1行上a

5、ij前面又有j个元素，故它前面一共有in+j个元素，因此，aij的地址计算函数为： LOC(i,j)=LOC(0,0)+in+jL,数组的顺序表示与实现,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,

6、5.3 特殊矩阵的压缩存储,对称矩阵 若n阶矩阵A中的数据元素满足下述性质aij=aji (1i，jn)则称A为n阶对称矩阵；因aij与aji相等，二者只需分配一个存储单元。这样，可将nn个存储单元压缩到n(n+1)/2个单元。,5.3.1 对称矩阵,1 3 5 7 3 2 6 9 5 6 3 8 7 9 8 4,a11 a12 . . a1n a21 a22 . . a2n . an1 an2 . ann,为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。不失一般性，假设以行主序存储下三角（包括对角线）中的元素。 以一维数组san(n+1)/2作为n阶对称矩阵A

7、的存储结构，则sak和矩阵元aij之间存在着一一对应的关系： i(i-1)/2+j-1 当ij j(j-1)/2+i-1 当ij,对称矩阵,k=,若ij，则aij在下三角形中。 aij之前的i-1行（从第1行到第i-1行）一共有1+2+i-1=i(i-1)/2个元素，在第i行上，aij之前恰有j-1个元素，因此有： k=i (i-1)/2+j-1 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j (j-1)/2+i-1 注意：k从0开始，i、j从1开始。,对称矩阵,5.3.2 三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。

8、上三角矩阵是它的下三角（不包括主对角线）中的元素均为常数或零。下三角矩阵正好相反，它的主对角线上方均为常数或零。三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到一维数组san(n+1)/2+1中。其中c存放在向量的最后一个分量中。,i(i-1)/2+j-1 当ij n(n+1)/2 当ij,k=,三角矩阵,a11 c c . c a21 a22 c . c . c an1 an2 an3 . ann,如果矩阵中的所有的非零元素都集中在以主对角线为中心的带状区域则称为对角矩阵，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余

9、元素皆为零。如常见的三对角矩阵。,三角矩阵,5.3.3 对角矩阵,a11 a12 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann,对角矩阵,非零元素仅出现在主对角线aii （1in）上，以及紧邻主对角线上面的那条对角线上ai,i+1（1in-1)和紧邻主对角线下面的那条对角线 ai+1, i（1in-1)上。显然： 当i - j1时，元素aij=0。 主对角线元素aii所在位置分别是一维数组下标为0，3，6，9，。而主对角线上面元素ai,i+1所在位置分别是一维数组下标为1，4，

10、7，10，。 主对角线下面的那条对角线 ai+1,i所在位置分别是一维数组下标为2，5，8，11，。,设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即smn)，则称A为稀疏矩阵。 稀疏矩阵的三元组表表示 在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置(i，j)。一个三元组(i，j，aij)唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。,5.4 稀疏矩阵的压缩存储,例如： M由(1,2,12), (1,3,9), (3,1,

11、-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数(6,7)唯一确定。,稀疏矩阵,三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 # define MAXSIZE 12500 /非零元个数最大值 typedef struct int i, j; /行下标和列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元组表 int mu,nu,tu; /行数、列数、非零元个数 TSMatrix;,5.4.1 三

12、元组表,下面以矩阵的转置为例，说明稀疏矩阵的存储。 一个mn的矩阵M，它的转置T是一个nm的矩阵，且T（i，j）=M（j，i），1in，1jm，即M的行是T的列，T的列是M的行。 将M转置为T，就是将M的三元组表M.data置换为表T的三元组表T.data，如果只是简单地交换M.data中i和j的内容，那么得到的T.data将是一个按列优先顺序存储的稀疏矩阵T，要得到按行优先顺序存储的T.data，就必须重新排列三元组的顺序。,矩阵的转置,三 元 组 表 M.data,(6, 4, -7),(6, 1, 15),(5, 2, 18),(4, 3, 24),(3, 5, 14),(3, 1, -

13、3),(1, 3, 9 ),(1, 2, 12),三 元 组 表 T.data,(4, 6, -7),(1, 6, 15),(2, 5, 18),(3, 4, 24),(5, 3, 14),(1, 3, -3),(3, 1, 9 ),(2, 1, 12),由于M的列是T的行，按M.data的列序转置，所得到的转置矩阵T的三元组表T.data必定是按行优先存放。 思路：反复扫描M.data中的列序，从小到大依次进行转置。,矩阵转置方法一,(6, 4, -7),(6, 1, 15),(5, 2, 18),(4, 3, 24),(3, 5, 14),(3, 1, -3),(1, 3, 9 ),(1,

14、 2, 12),三 元 组 表 a.data,三 元 组 表 b.data,Status TransPoseSMatrix(TSMatrix M, TSMatrix ,矩阵转置算法,col=1,col=2,矩阵的转置方法一的演示,依次把M.data中的元素直接送入T.data的恰当位置上（即M三元组的p指针不回溯）。,矩阵转置方法二,(6, 4, -7),(6, 1, 15),(5, 2, 18),(4, 3, 24),(3, 5, 14),(3, 1, -3),(1, 3, 9 ),(1, 2, 12),设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第

15、col列第一个非零元在T.data中位置 显然有：cpot1=1; cpotcol=cpotcol-1+numcol-1; (1col M.nu),矩阵转置具体实现,1,3,5,7,8,8,9,col,numcol,cpotcol,1,2,2,2,3,2,4,1,5,0,6,1,7,0,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,M =,Status FastTransposeSMatrix（TSMatirx M, TSMatirx ,矩阵转置算法,实现过程

16、演示,4,6,2,9,7,5,3,广义表是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。 广义表是n(n0)个元素a1，a2，ai，an的有限序列。 其中： ai或者是原子(单个元素)或者是一个广义表。 广义表记作LS=(a1，a2，ai，an )，LS是广义 表的名字，n为它的长度。 若ai是广义表，则称它为LS的子表。 注意： 广义表通常用圆括号括起来，用逗号分隔其中的元素。 若广义表LS非空(n1)，则a1是LS的表头，其余元素 组成的表(a2，a3，an)称为LS的表尾。 广义表是递归定义的。,5.5 广义表,1. A=( )A是一个空表，其长度为零。 2.

17、B=(e)表B只有一个原子e，B的长度为1。 3. C=(a,(b,c,d)表C的长度为2，两个元素分别为原子a和子表(b,c,d)。 4. D=(A,B,C)表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有 D=( ),(e),(a,(b,c,d)。 5. E=(a,E)这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,)。,5.5.1 广义表的定义,由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是广义表，而其表尾必定是广义表。 A=(e) 则：gethead(A)=e gettail(A)=( ) B=(a,b),c,d

18、,e,f) 则：gethead(B)=(a,b) gettail(B)=(c,d,e,f) C = (a,(b,c,d) 则： gethead(C)= a gettail(C)= (b,c,d) 注意：广义表( )和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表(只不过该表中唯一的一个元素是空表)。对其可进行分解，得到表头和表尾均为空表( )。,广义表表示,由于广义表(a1,a2,a3, ,an)中的数据元素可以具有不同的结构(或是原子，或是广义表)，因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。 由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。 下面介绍两种广义表的链式存储结构。,5.5.2 广义表的存储结构,方法一： 表结