特殊矩阵广义表及其应用教学文案.ppt
《特殊矩阵广义表及其应用教学文案.ppt》由会员分享,可在线阅读,更多相关《特殊矩阵广义表及其应用教学文案.ppt(84页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 1特殊矩阵广义表及其应用第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 2下面以二维数组为例解释上述关于数组的定义。下面以二维数组为例解释上述关于数组的定义。【例例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个具有相同数个具有相同数据类型的数据元素,分别为:据类型的数据元素,分别为:Amn=a11 a1
2、2a1na21a22a2n am1am2amn(1im,1jn)第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 3可以看出,二维数组每一行是一个一维数组,元素可以看出,二维数组每一行是一个一维数组,元素间存在序偶关系;每一列也是一个一维数组,元素间也间存在序偶关系;每一列也是一个一维数组,元素间也同样存在序偶关系。即:每个元素都受着两个关系的约同样存在序偶关系。即:每个元素都受着两个关系的约束:束:、。若把每一行看作是一个整体,则行与行之间是线性若把每一行看作是一个整体,则行与行之间是线性关系;若把每一列看作是一个整体,则列与列之间也是关系;若把每一列看作是一个整体,则列与列
3、之间也是线性关系。线性关系。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 4这样,我们可以把二维数组看成是一个线性表,它这样,我们可以把二维数组看成是一个线性表,它的每一个数据元素是一个一维数组,也是一个线性表。的每一个数据元素是一个一维数组,也是一个线性表。由此可以推广到由此可以推广到n维数组。我们说维数组。我们说n维数组是一个线性维数组是一个线性表,它的每一个数据元素是表,它的每一个数据元素是n-1维数组,也是一个线性维数组,也是一个线性表。表。数组一旦被定义,其维数及每维的长度数组一旦被定义,其维数及每维的长度(维界维界)就不再就不再改变。因此,数组的运算除了初始化和
4、销毁之外,只有改变。因此,数组的运算除了初始化和销毁之外,只有查找元素和修改元素值的操作。查找元素和修改元素值的操作。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 5矩阵的定义:矩阵的定义:矩阵的定义:矩阵的定义:矩阵是由矩阵是由mn个数排列成个数排列成m行行(横向横向)、n列列(纵向纵向)所所形成的矩形数表:形成的矩形数表:称为称为mn矩阵,简记为矩阵,简记为A=(aij)mn,其中,其中aij为为A的第的第i行行第第j列的元素。列的元素。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 6矩阵与数组的关系矩阵与数组的关系矩阵与数组的关系矩阵与数组的关系:
5、对照上述数组的定义,我们不难看出,矩阵中所有对照上述数组的定义,我们不难看出,矩阵中所有数据元素组成了一个二维数组,矩阵的每一行、每一数据元素组成了一个二维数组,矩阵的每一行、每一列的数据元素分别组成等长的一维数组。列的数据元素分别组成等长的一维数组。我们也可以说,矩阵是一个线性表,其每一个数据我们也可以说,矩阵是一个线性表,其每一个数据元素元素(行或列行或列)也是一个线性表。也是一个线性表。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 7 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构6.1 数组与矩阵第第6 6章章 数组及其应用数组及其应用数组及其
6、应用数组及其应用 8 由于数组一般不作插入和删除操作,因此采用顺序存储结构是理所当然的。问题是:以什么次序来存储各元素的值?问题是:以什么次序来存储各元素的值?下面以二维数组为例来说明:二维数组一般有两种方法来存储:1、按行优先顺序存储、按行优先顺序存储将数组元素按行向量排列,i+1行向量接在 i 行向量后面。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 9a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放amn.am2am1.a2n.a22a21a1n.a12a11
7、01n-1m*n-1n第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 102、按列优先顺序存储、按列优先顺序存储 将数组元素按列向量排列,j+1列向量接在 j 列向量后面。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 11按列序为主序存放按列序为主序存放01m-1m*n-1mamn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 12二维数组中任一元素的地址二维
8、数组中任一元素的地址二维数组中任一元素的地址二维数组中任一元素的地址按上述两种方式顺序存储的数组,只要知道按上述两种方式顺序存储的数组,只要知道开始开始开始开始结点的存放地址和每维的上下界(结点的存放地址和每维的上下界(结点的存放地址和每维的上下界(结点的存放地址和每维的上下界(mm、n n的值),以的值),以及及每个数组元素所占用的字节数每个数组元素所占用的字节数每个数组元素所占用的字节数每个数组元素所占用的字节数d d,就可求出各个数,就可求出各个数组元素的存储地址。组元素的存储地址。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 13设设数组的首地址数组的首地址即:即:
9、a11的地址的地址记为:记为:LOC(a11)则:二维数组按则:二维数组按“行优先顺序行优先顺序”存储,数组元素的存储存储,数组元素的存储地址为:地址为:LOC(a11)+前面前面i1行元素所占字节数行元素所占字节数+第第j行中前行中前j1个元素所占字节数个元素所占字节数即:即:LOC(aij)=LOC(a11)+(i-1)*n*d+(j-1)*d前面前面i1行元素的行元素的个数(每行个数(每行n个)个)每个元素所占每个元素所占的字节数的字节数第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 14【例例2 2】已知二维数组已知二维数组AmmAmm按行存储的元素地址公按行存储的元
10、素地址公式是:式是:Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K 按列存储的公式是?按列存储的公式是?Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K (尽管是方阵,但公式仍不同)(尽管是方阵,但公式仍不同)【例例1 1】一个二维数组一个二维数组A A,行下标的范围是,行下标的范围是1 1到到6 6,列下标,列下标的范围是的范围是0 0到到7 7,每个数组元素用相邻的,每个数组元素用相邻的6 6个字节存储,存个字节存储,存储器按字节编址。那么,这个数组占用储器按字节编址。那么,这个数组占用 个字节。个字节。答:答:m*n*L=(6-1+1)*(7-0+1
11、)*6=48*6=288第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 15 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 16在用高级语言编写程序时,通常在用高级语言编写程序时,通常用二维数组来存储用二维数组来存储用二维数组来存储用二维数组来存储矩阵矩阵矩阵矩阵。但对一些数据分布呈某种规律的矩阵,或是。但对一些数据分布呈某种规律的矩阵,或是0元元素大量存在素大量存在(远远多于非远远多于非0元素元素)的矩阵,采用上述存储的矩阵,采用上述存储
12、方法会造成存储空间的极大浪费。方法会造成存储空间的极大浪费。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 17 若矩阵中非若矩阵中非0 0元素呈某种规律分布,或存在大量元素呈某种规律分布,或存在大量0 0元元素,为节省存储空间,可对这类素,为节省存储空间,可对这类矩阵压缩存储矩阵压缩存储矩阵压缩存储矩阵压缩存储:即:即:为多个相同的非为多个相同的非为多个相同的非为多个相同的非0 0 0 0元素只分配一个存储空间,元素只分配一个存储空间,元素只分配一个存储空间,元素只分配一个存储空间,对对对对0 0 0 0元素不分配存储空间元素不分配存储空间元素不分配存储空间元素不分配存储空
13、间。若值相同的非若值相同的非0 0元素或元素或0 0元素在矩阵中的分布有一元素在矩阵中的分布有一定的规律,我们称此矩阵为定的规律,我们称此矩阵为特殊矩阵特殊矩阵特殊矩阵特殊矩阵;反之,称为;反之,称为稀稀稀稀疏矩阵疏矩阵疏矩阵疏矩阵。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 18特殊矩阵特殊矩阵特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,下面我们讨论几种特殊矩阵的压缩存规律的矩阵,下面我们讨论几种特殊矩阵的压缩存储。储。1 1 1 1、对称矩阵、对称矩阵、对称矩阵、对称矩阵 在一个在一个n n阶方
14、阵阶方阵A A中,若元素满足下述性质:中,若元素满足下述性质:aij=aji0=i,j=0)(i=0),元素总数为:元素总数为:n(n+1)/2 因此,我们可以按从上到下、从左到右将这些元素存因此,我们可以按从上到下、从左到右将这些元素存放在一个向量放在一个向量san(n+1)/2中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中的元素,我们必须在中的元素,我们必须在aij和和sak之间找一个对应关系。之间找一个对应关系。a11 a12a1na21a22a2n an1 an2 ann第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 21若若i ij j,则,则aij在下三
15、角形中。在下三角形中。aij之前的之前的i i行(从第行(从第0 0行行到第到第i-1行)一共有行)一共有1+2+i=i(i+1)/2个元素,在第个元素,在第i i行上,行上,aij之前恰有之前恰有j个元素(即个元素(即ai0,ai1,ai2,aij-1),因此有:),因此有:k=i*(i+1)/2+j0kn(n+1)/2 若若ijij,则,则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji,所以只,所以只要交换上述对应关系式中的要交换上述对应关系式中的i和和j即可得到:即可得到:k=j*(j+1)/2+i0kn(n+1)/2 第第6 6章章 数组及其应用数组及其应用数组及其应
16、用数组及其应用 222 2 2 2、三角矩阵、三角矩阵、三角矩阵、三角矩阵 以主对角线划分,三角矩阵有上三角和下三角两种。以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵如图上三角矩阵如图(a)所示,它的下三角(不包括主对角线)所示,它的下三角(不包括主对角线)中的元素均为常数。下三角矩阵正好相反,它的主对角中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数,如图线上方均为常数,如图(b)所示。在大多数情况下,三角所示。在大多数情况下,三角矩阵常数为零。矩阵常数为零。a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c .c c an-
17、1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 23 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间,其余可共享一个存储空间,其余的元素正好有的元素正好有n(n+1)/2n(n+1)/2个,因此,三角矩阵可压缩存个,因此,三角矩阵可压缩存储到向量储到向量san(n+1)/2+1san(n+1)/2+1中,其中中,其中c c存放在向量的最存放在向量的最后一个分量中。后一个分量中。a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c
18、 .c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 24 上三角矩阵上三角矩阵上三角矩阵上三角矩阵中,主对角线之上的中,主对角线之上的第第第第i i行行行行(0 0 inij第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 25 下三角矩阵的存储和对称矩阵类似,下三角矩阵的存储和对称矩阵类似,sak和和aij对应对应关系是:关系是:i(i+1)/2+jijn(n+1)/2ij k=第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 263
19、3 3 3、对角矩阵、对角矩阵、对角矩阵、对角矩阵 对角矩阵中,所有的非零元素集中在以主对角线为对角矩阵中,所有的非零元素集中在以主对角线为中心的带状区域中,即除了主对角线和主对角线相邻中心的带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零。两侧的若干条对角线上的元素之外,其余元素皆为零。下图给出了一个三对角矩阵,下图给出了一个三对角矩阵,a00a01a10a11a12a21a22a23.an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1 第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 27三对角矩阵有如下特点:三对角
20、矩阵有如下特点:当当时,时,aij非非0;其它情况时,其它情况时,aij的值为的值为0。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 28我们以行序为主序进行存储三对角矩阵,并且只存储我们以行序为主序进行存储三对角矩阵,并且只存储矩阵中的非矩阵中的非0元素。元素。在在n阶三对角矩阵中,除了第一行和最后一行只有阶三对角矩阵中,除了第一行和最后一行只有2个个非非0元素外,其余各行均有元素外,其余各行均有3个非个非0元素,元素,共共2+2+3*(n-2)=3n-2个非个非0元素。元素。这样,可以将该三对角矩阵存储在一维数组这样,可以将该三对角矩阵存储在一维数组sa3n-2中。现在
21、,对给定的非中。现在,对给定的非0元素元素aij,与其对应的数组元素的,与其对应的数组元素的下标是什么呢?下标是什么呢?第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 29由三对角矩阵的特点知,矩阵中的非由三对角矩阵的特点知,矩阵中的非0元素元素aij的前的前面有面有i行,共有行,共有3i-1个非个非0元素;在元素元素;在元素aij所在的第所在的第i行,行,aij之前有之前有j-i+1个非个非0元素。因此可得与非元素。因此可得与非0元素元素aij对应对应的数组元素的下标为:的数组元素的下标为:k=3i-1+j-i+1=2i+j 这样,非零元素这样,非零元素aij的地址为:的地
22、址为:LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 30 上述的各种特殊矩阵,其非零元素的分布都是有上述的各种特殊矩阵,其非零元素的分布都是有规律的,因此总能找到一种方法将它们压缩存储到一规律的,因此总能找到一种方法将它们压缩存储到一个向量中,并且一般都能找到矩阵中的元素与该向量个向量中,并且一般都能找到矩阵中的元素与该向量的对应关系,通过这个关系,仍能对矩阵的元素进行的对应关系,通过这个关系,仍能对矩阵的元素进行随机存取。随机存取。第第6 6章章 数组及其应用数组及其应
23、用数组及其应用数组及其应用 31稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵 什么是稀疏矩阵?什么是稀疏矩阵?简单说,设矩阵简单说,设矩阵A A中有中有s s个非零元素,若个非零元素,若s s远远小于矩远远小于矩阵元素的总数(即阵元素的总数(即smnst 存放矩阵M的数组是 adatamaxsize am,n,tdata13-3161521122518 3 19342446-75314 第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 38 第一个数组元素(三元组)所在的行号、列号分别第一个数组元素(三元组)所在的行号、列号分别是:是:(adata0).i(adata0).j 它的值为:它
24、的值为:(adata0).v 第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 392 2、十字链表、十字链表、十字链表、十字链表若矩阵的非若矩阵的非0元素的个数和位置在操作过程中变化元素的个数和位置在操作过程中变化较大,则不宜采用顺序存储结构来表示三元组的线较大,则不宜采用顺序存储结构来表示三元组的线性表。性表。可采用链式存储结构来表示三元组的线性表。可采用链式存储结构来表示三元组的线性表。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 40 在链表中,每个非在链表中,每个非0 0元素可用一个含有五个域的结元素可用一个含有五个域的结点表示:点表示:ijvcp
25、trrptr其中:其中:其中:其中:i,j,v三个域分别表示该元素所在的行、列三个域分别表示该元素所在的行、列和非和非0元素的值。行指针域元素的值。行指针域rptr用以链接同一行中下一用以链接同一行中下一个非个非0元素;列指针域元素;列指针域cptr用以链接同一列中下一个非用以链接同一列中下一个非0元素。元素。第第6 6章章 数组及其应用数组及其应用数组及其应用数组及其应用 41 存储时,每个非存储时,每个非0 0元既是某个行链表中的一个结点,元既是某个行链表中的一个结点,又是某个列链表中的一个结点;整个矩阵构成了一个十又是某个列链表中的一个结点;整个矩阵构成了一个十字交叉的链表字交叉的链表故
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 特殊 矩阵 广义 及其 应用 教学 文案
限制150内