特殊矩阵广义表及其应用课件

1、特殊矩阵广义表及其应用特殊矩阵广义表及其应用数组的定义：数组是满足下列条件的同类型数据元素 的集合： 对于该集合中任一数据元素 来说，ji = 0，bi-1， i =1，2，n，n0称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标； 数据元素之间的关系表示为Ri = |，0jkbk-1 ，1kn且ki，0jibi-2 ，i =1，2，n，且R = R1，R2，. Rn； 数组的定义： 下面以二维数组为例解释上述关于数组的定义。【例6.1】设有二维数组A，其第1维的长度b1= 3，第2维的长度b2 = 4；数据元素描述为，其中j1 = 0，b1-1= 0，1，2，j2 = 0，

2、b2-1= 0，1，2，3；则该二维数组共有12个具有相同数据类型的数据元素，分别为： Amn = a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn) 下面以二维数组为例解释上述关于数组的定义。【例 可以看出，二维数组每一行是一个一维数组，元素间存在序偶关系；每一列也是一个一维数组，元素间也同样存在序偶关系。即：每个元素都受着两个关系的约束： 、 。 若把每一行看作是一个整体，则行与行之间是线性关系；若把每一列看作是一个整体，则列与列之间也是线性关系。 可以看出，二维数组每一行是一个一维数组，元素间 这样，我们可以把二维数组看成是一个线性表，它的每一个

3、数据元素是一个一维数组，也是一个线性表。 由此可以推广到n维数组。我们说n维数组是一个线性表，它的每一个数据元素是n-1维数组，也是一个线性表。 数组一旦被定义，其维数及每维的长度(维界)就不再改变。因此，数组的运算除了初始化和销毁之外，只有查找元素和修改元素值的操作。 这样，我们可以把二维数组看成是一个线性表，它的矩阵的定义： 矩阵是由mn个数排列成m行(横向)、n列(纵向)所形成的矩形数表： 称为mn矩阵，简记为A=(aij)mn，其中aij为A的第i行第j列的元素。 矩阵的定义：称为mn矩阵，简记为A=(aij)mn，其中矩阵与数组的关系 ： 对照上述数组的定义，我们不难看出，矩阵中所有

4、数据元素组成了一个二维数组，矩阵的每一行、每一列的数据元素分别组成等长的一维数组。 我们也可以说，矩阵是一个线性表，其每一个数据元素(行或列)也是一个线性表。 矩阵与数组的关系 ： 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构6.1 数组与矩阵 6.1.1 数组与矩阵的概念及其相互关系 6.1 由于数组一般不作插入和删除操作，因此采用顺序存储结构是理所当然的。问题是：以什么次序来存储各元素的值？ 下面以二维数组为例来说明：二维数组一般有两种方法来存储：1、按行优先顺序存储 将数组元素按行向量排列， i+1行向量接在 i 行向量后面。 由于数组一般不作插入和删除操作，因此

5、采用顺序存储结 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n a11 a12 .2、按列优先顺序存储 将数组元素按列向量排列， j+1列向量接在 j 列向量后面。2、按列优先顺序存储按列序为主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n

6、 am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 按列序为主序存放01m-1m*n-1m amn二维数组中任一元素的地址 按上述两种方式顺序存储的数组，只要知道开始结点的存放地址和每维的上下界（m、 n的值），以及每个数组元素所占用的字节数d，就可求出各个数组元素的存储地址。 二维数组中任一元素的地址设 数组的首地址 即： a11 的地址 记为： LOC (a11)则：二维数组按“行优先顺序”存储，数组元素的存储地址为： LOC (a11) + 前面 i 1行元素所占字节数 + 第j 行中前j 1个元素所占字节数即：LOC( aij ) = LO

7、C(a11) + ( i-1)*n*d +(j -1)*d 前面 i 1行元素的个数（每行n个）每个元素所占的字节数设 数组的首地址 即： a11 的地址 前面【例2】已知二维数组Amm按行存储的元素地址公式是： 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

8、)*6=48*6=288【例2】已知二维数组Amm按行存储的元素地址公式是： 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用 6.1 数组与矩阵 第6章 特殊矩阵、广义表及其应用 在用高级语言编写程序时，通常用二维数组来存储矩阵。但对一些数据分布呈某种规律的矩阵，或是0元素大量存在(远远多于非0元素)的矩阵，采用上述存储方法会造成存储空间的极大浪费。 在用高级语言编写程序时，通常用二维数组来存储矩阵 若矩阵中非0元素呈某种规律分布，或存在大量0元素，为节省存储空间，可对这类矩阵压缩存储： 即：为多个相同的非0元素只分配一个

9、存储空间，对0元素不分配存储空间。 若值相同的非0元素或0元素在矩阵中的分布有一定的规律，我们称此矩阵为特殊矩阵；反之，称为稀疏矩阵。 若矩阵中非0元素呈某种规律分布，或存在大量0元素，为节特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0=i, j=0)，元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在一个向量san(n+1)/2中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。a11 a12 a1n a2

10、1 a22 a2n an1 an2 ann 在这个下三角矩阵中，第i行恰有i+1个元素(i=0)， 若ij，则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+j 0k n(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij= aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 若ij，则aij在下三角形中。 aij之前的i行（从2、三角矩阵 以主对角线划分，

11、三角矩阵有上三角和下三角两种。上三角矩阵如图(a)所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图(b)所示。在大多数情况下，三角矩阵常数为零。 a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c . . c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 2、三角矩阵 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量san(n+1)/2 +1中，其中c存放在向量的最后一个分量中。 a0

12、0 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c . . c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 三角矩阵中的重复元素c可共享一个存储空间，其余的元 上三角矩阵中，主对角线之上的第i行(0ij 上三角矩阵中，主对角线之上的第i行(0in)恰 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij k = 下三角矩阵的存储和对称矩阵类似，sak和aij对应关3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除

13、了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 3、对角矩阵三对角矩阵有如下特点： 当时，aij非0； 其它情况时，aij的值为0。 三对角矩阵有如下特点： 当时，aij非0； 我们以行序为主序进行存储三对角矩阵，并且只存储矩阵中的非0元素。 在n阶三对角矩阵中，除了第一行和最后一行只有2个非0元素外，其余各行均有3个非0元素， 共2+2+3*(n-2) = 3n-2个非0元素。

14、 这样，可以将该三对角矩阵存储在一维数组sa3n-2中。现在，对给定的非0元素aij，与其对应的数组元素的下标是什么呢？ 我们以行序为主序进行存储三对角矩阵，并且只存储矩 由三对角矩阵的特点知，矩阵中的非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 由三对角矩阵的特点知，矩阵中的非0元素aij的前 上述的各种特

15、殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因稀疏矩阵 什么是稀疏矩阵？ 简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即st 存放矩阵M的数组是 adatamaxsize am , n , t data 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 93 4 244 6 -75 3 14 若定义指针变量a存放矩阵M三元组表的首地址： 第一个数组元素（三元组）所在的行号、列号分

16、别是： ( adata0).i (adata0) .j 它的值为： ( adata0).v 第一个数组元素（三元组）所在的行号、列号分别是：2、十字链表 若矩阵的非0元素的个数和位置在操作过程中变化较大，则不宜采用顺序存储结构来表示三元组的线性表。 可采用链式存储结构来表示三元组的线性表。2、十字链表 在链表中，每个非0元素可用一个含有五个域的结点表示：ijvcptrrptr 其中：i , j ,v 三个域分别表示该元素所在的行、列和非0元素的值。行指针域 rptr 用以链接同一行中下一个非0元素；列指针域 cptr 用以链接同一列中下一个非0元素。 在链表中，每个非0元素可用一个含有五个域的

17、结点表示 存储时，每个非0元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了一个十字交叉的链表故称这样的存储结构为十字链表。 可用两个分别存储行链表和列链表的头指针的一维数组表示十字链表。 M-chead M-rhead 存储时，每个非0元既是某个行链表中的一个结点，又是某个十字链表中非0元结点的类型说明如下： typedef struct lnode int i , j ; datatype v ; struct lnode *cptr , *rptr ; OLnode； ijvcptrrptr十字链表中非0元结点的类型说明如下：ijvcptrrptr十字链表的类型描述

18、如下： #define N 10 /预设稀疏矩阵的行数 #define K 10 /预设稀疏矩阵的列数 typedef struct OLnode *cheadN , *rheadK ; int m , n , t ; /*行数、列数、非0元个数*/ Crosslist ; Crosslist *M ; 十字链表的类型描述如下： 讨论：如何建立一个十字链表 算法步骤： 1、建立两个一维数组 Mchead 、 Mrhead 分别存储列链表及行链表的头指针。 初始时， Mcheadj = NULL , Mrheadj = NULL. 2、读入非0元结点的三元组（ i , j , v ），生成一个结

19、点*p ,将其插入第 i 个行链表和第j个列链表的正确位置上。 讨论：如何建立一个十字链表 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用 6.1 数组与矩阵 第6章 特殊矩阵、广义表及其应用【例】求稀疏矩阵A的转置矩阵B 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0

20、 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 -7 0 0 0B = 【例】求稀疏矩阵A的转置矩阵B 0 0 -3 将A转置为B，就是将A的三元组表a-data置换为表B的三元组表b-data。 有： at = bt ; am = bn ; an = bm ; 但:(adatax).i (bdatax).j 为什么？ 将A转置为B，就是将A的三元组表a-data置换为表 也不能将 (adatax).i 与(adatax).j 简单互换！为什么？ 答：如果只是简单地交换a-data中i和j的内容，那么得

21、到的b-data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b-data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。 也不能将 (adatax).i 与(0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0

22、0 -7 0 0 0B = 行号i 列号j 值v行号i 列号j 值v1 3 -31 6 152 1 122 5 18 3 1 93 4 244 6 -75 3 141 2 12 1 3 93 1 -33 5 144 3 245 2 186 1 156 4 -70 0 -3 0 0 15A = 0 算法步骤如下：(1) 产生顺序表b，存放转置后的矩阵B Spmatrix *b; b = malloc( sizeof (Spmatrix); 并确定其结点个数、行数、列数。即：bt = at ;bm = an ; bn = am ;算法步骤如下：bt = at ;(2) 一维数组 bdata结点个数

23、 中各数组元素赋值，且bdata 按行优先。 具体做法如下： 对三元组表adata 扫描(从第一行开始) 令：x为数组adata 中数组元素的下标 y为数组bdata 中数组元素的下标(2) 一维数组 bdata结点个数 中各数组元素赋扫描过程：首先，令 y = 0; for (x = 0; x datax).j = = 1 (1是列号) 若为1 则 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+ 该轮for循环结束后，矩阵N中第一行（即矩阵M中第一列）的元素的三元组已存放在三元组表（数组）b

24、data 中了。扫描过程：首先，令 y = 0; 该轮for循环结 下面再次扫描三元组表（数组）adata ，查寻矩阵M中第二列的元素：此时，y值为上轮for 循环后的结果； for (x = 0; x datax).j = = 2 (2是列号) 若为2 则 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+ 下面再次扫描三元组表（数组）adata 这样，整个扫描的过程可描述为： y = 0 ; for ( z = 1; z =矩阵M的列数；z+) for (x = 0; x datax).j =

25、 = z ) (bdatay).v = (adatax).v ; (bdatay).i = (adatax).j ; (bdatay).j = (adatax).i ; y+ ; 这样，整个扫描的过程可描述为：算法分析： 该算法的时间主要耗费在 z 和 x 的二重循环上，若矩阵M的列数为 n ，非0元素个数为 t ，则 算法的时间复杂度数量级为: O( n*t )算法分析： 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用 6.1 数组与矩阵 第6章 特殊矩阵、广义表及其应用6.4.1 广义表的概念 6.4.2 广义表的存储

26、结构 6.4.3 广义表的应用6.4 广义表6.4.1 广义表的概念6.4 广义表广义表的概念 广义表是n(n0)个元素的有限序列, 记作 A=(a1, a2, , an) 其中, A是广义表的名称, n是它的长度, ai(1in)或者是数据元素, 或者是广义表。 习惯上： 用英文大写字母表示广义表的名称, 小写字母表示数据元素。广义表的概念 对于广义表A中的某个元素ai ：若它是一个数据元素时, 称其为A的一个原子; 当其不是一个数据元素时, 则称它为广义表A的子表。 当广义表A非空时, 称第一个元素a1为A的表头(head), 称其余元素组成的表(a2, , an)为A的表尾(tail)。

27、广义表举例如下: A=( ) A是一个空表, 其长度为零。 B=(e) 广义表B只有一个原子e, B的长度为1。 对于广义表A中的某个元素ai ：若它是一个数 C=(a, (b, c, d), 广义表C的长度为2, 两个元素分别为原子a和子表(b, c, d) D=(A, B, C), 广义表D的长度为3, 3 个元素都是广义表。 E=(a, E), 这是一个递归的表, 其长度为2, E表相当于一个无穷表。从以上例子可以看出： 广义表可以共享子表, 且允许递归。 广义表的元素之间除了存在次序关系外, 还存在层次关系。 C=(a, (b, c, d), 广义表C的长度为2 广义表中元素的最大层次

28、为表的深度。元素的层次就是包含该元素的括号对的数目。 例如: F=(a, b, (c, (d) 其中, 数据元素a, b在第一层, 数据元素c在第二层, 数据元素d在第三层。广义表F的深度为3。 任何一个非空广义表，其表头可能是原子, 也可能是广义表, 而其表尾必定为广义表。 广义表中元素的最大层次为表的深度。元素的层次例如: 若 C=(a, (b, c, d) D=(A, B, C) 则：Head(D)=A Tail(D)=(B, C) Head(C)=a Tail(C)=(b, c, d)以上是广义表的两个操作： 取表头 Head 、取表尾Tail 这些操作还可以嵌套调用： Head（ T

29、ail(D) ） Head(B,C) = B取广义表D的第二个元素例如: 若 C=(a, (b, c, d) D=(注意： 广义表（）和广义表( )不同。 （）为空表，长度 n0 ，不能分解成表头和表尾。 ( ) 不是空表，其长度 n = 1 ，可以分解得到表头是空表( ) , 表尾是空表( ) .注意： 6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表 6.4.1 广义表的概念6.4 广义表 由于广义表（a1, a2, , an)中的数据元素可以具有不同的结构(或是原子, 或是列表）, 因此难以用顺序存储结构表示, 通常采用链式存储结构, 每个数

30、据元素可用一个结点表示。 如何设定结点的结构？由于列表中的数据元素可能为原子或列表, 由此需要两种结构的结点: 一种是表结点, 用以表示列表; 一种是原子结点, 用以表示原子。 由于广义表（a1, a2, , an)中的数据元 按前述分析：若列表不空, 则可分解成表头和表尾; 反之, 一对确定的表头和表尾可唯一确定列表。 由此, 一个表结点可由 3 个域组成: 标志域、指示表头的指针域和指示表尾的指针域; 而原子结点只需两个域: 标志域和值域：原子结点atomtag = 0 tag = 1hptp表结点 按前述分析：若列表不空, 则可分解成表头和表尾; 反之原子结点atomtag = 0 类型

31、说明如下： typedef enum ATOM, LIST ElemTag ; /*ATOM=0：原子, LIST=1:子表*/tag = 1hptp表结点枚举类型原子结点atomtag = 0 类型说明如下：tag = typedef struct GLNode ElemTag tag ; union AtomType atom ; struct struct GLNode *hp, *tp ; ptr ; ; Glist ;公共部分, 用于区分原子结点和表结点原子结点和表结点的联合部分ptr.hp和ptr.pt分别指向表头和表尾广义表类型typedef struct GLNode公共部分,

32、 用 A=( ) B=(e) C=(a, (b, c, d) D=(A, B, C) E=(a, E)Glist *A; A = NULL10eBCDE110a1110b0c0d111110a A=( ) B=(e) 在这种存储结构中有几种情况： 除空表的表头指针为空外，对任何非空广义表，其表头指针均指向一个表结点，且该结点中的hp域指示广义表表头（或为原子结点，或为表结点），tp域指向广义表表尾（除非表尾为空，则指针为空，否则必为表结点）；在这种存储结构中有几种情况： 容易分清广义表中原子和子表所在层次。如在广义表D中，原子a和e在同一层次上，而b、c和d在同一层次且比a和e低一层，B和C是

33、同一层的子表； 最高层的表结点个数即为广义表的长度。 容易分清广义表中原子和子表所在层次。如在广义表D中，原 6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表 6.4.1 广义表的概念6.4 广义表m元多项式的表示 一个m元多项式的每一项最多有m个变元，如果用单链表表示，则每个节点应该包括m个指数项和一个数据项；如果多项式各项的变元数不相同，将势必造成存储空间的浪费。为此，我们考虑采用其它的方式来存储一个m元多项式。 我们以三元多项式：P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 为例，讨论其存储表示。 m元多项式的表示 P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 该多项式中各项的变元数目不尽相同，某些因子多次出现，我们可以将其改写为：P(x,y,z) = (x10 + 2x6)y3+3x5y2)z2+(x4 + 6x3)y4+2y)z+15 此时，该多项式就变成了变元z的多项式，即A z2 + B z1 +15 z0，对这个一元多项式我们用单链表表示为： P(x,y,z) =