第6章 数组及其应用数组及其应用 16.1 数组与矩阵 6.2 特殊矩阵的压缩存储6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第6章 数组及其应用数组及其应用 2 6.1.1 数组与矩阵的概念及其相互关 系 6.1.2 数组的存储结构6.1 6.1 数组与矩阵数组与矩阵第6章 数组及其应用数组及其应用 3数组的定义：数组的定义：数组是满足下列条件的同类型数据元素 的集合： 对于该集合中任一数据元素 来说，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章 数组及其应用数组及其应用 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个具有相同数据类型的数据元素，分别为： Amn = a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn)第6章 数组及其应用数组及其应用 5可以看出，二维数组每一行是一个一维数组，元素间存在序偶关系；每一列也是一个一维数组，元 素间也同样存在序偶关系。即：每个元素都受着两 个关系的约束： 、 。若把每一行看作是一个整体，则行与行之间是线性关系；若把每一列看作是一个整体，则列与列之间 也是线性关系。 第6章 数组及其应用数组及其应用 6这样，我们可以把二维数组看成是一个线性表， 它的每一个数据元素是一个一维数组，也是一个线 性表。由此可以推广到n维数组。我们说n维数组是一个线 性表，它的每一个数据元素是n-1维数组，也是一个 线性表。数组一旦被定义，其维数及每维的长度(维界)就不 再改变。因此，数组的运算除了初始化和销毁之外 ，只有查找元素和修改元素值的操作。 第6章 数组及其应用数组及其应用 7矩阵的定义：矩阵的定义：矩阵是由mn个数排列成m行(横向)、n列(纵向)所 形成的矩形数表： 称为mn矩阵，简记为A=(aij)mn，其中aij为A的第i行第j列的元素。 第6章 数组及其应用数组及其应用 8矩阵与数组的关系矩阵与数组的关系 ：对照上述数组的定义，我们不难看出，矩阵中所有数据元素组成了一个二维数组，矩阵的每一行、每一列的数据元素分别组成等长的一维数组。我们也可以说，矩阵是一个线性表，其每一个数据元素(行或列)也是一个线性表。 第6章 数组及其应用数组及其应用 96.1.1 数组与矩阵的概念及其相互关 系 6.1.2 数组的存储结构6.1 6.1 数组与矩阵数组与矩阵第6章 数组及其应用数组及其应用 10由于数组一般不作插入和删除操作，因此采用顺 序存储结构是理所当然的。问题是：以什么次序来存储各元素的值？问题是：以什么次序来存储各元素的值？下面以二维数组为例来说明：二维数组一般有两 种方法来存储：1、按行优先顺序存储将数组元素按行向量排列， i+1行向量接在 i 行 向量后面。第6章 数组及其应用数组及其应用 11a11 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 a110 1n-1m*n-1n第6章 数组及其应用数组及其应用 122、按列优先顺序存储将数组元素按列向量排列， j+1列向量接在 j 列向量后面。第6章 数组及其应用数组及其应用 13按列序为主序存放01m-1m*n-1m amn a2n a1n . am2 a22 a12 am1 . a21 a11a11 a12 a1n a21 a22 a2n am1 am2 amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 第6章 数组及其应用数组及其应用 14二维数组中任一元素的地址二维数组中任一元素的地址按上述两种方式顺序存储的数组，只要知道开开 始结点的存放地址和每维的上下界（始结点的存放地址和每维的上下界（mm、 n n的值 ），以及每个数组元素所占用的字节数每个数组元素所占用的字节数d 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】已知二维数组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)*6=48*6=288第6章 数组及其应用数组及其应用 176.1 数组与矩阵 6.2 特殊矩阵的压缩存储6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第6章 数组及其应用数组及其应用 18在用高级语言编写程序时，通常用二维数组来存储用二维数组来存储 矩阵矩阵。但对一些数据分布呈某种规律的矩阵，或是0元 素大量存在(远远多于非0元素)的矩阵，采用上述存储 方法会造成存储空间的极大浪费。若矩阵中非0元素呈某种规律分布，或存在大量0元 素，为节省存储空间，可对这类矩阵压缩存储矩阵压缩存储：即：为多个相同的非为多个相同的非0 0元素只分配一个存储空间，元素只分配一个存储空间， 对对0 0元素不分配存储空间元素不分配存储空间。若值相同的非0元素或0元素在矩阵中的分布有一 定的规律，我们称此矩阵为特殊矩阵特殊矩阵；反之，称为稀稀 疏矩阵疏矩阵。第6章 数组及其应用数组及其应用 19特殊矩阵特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。1 1、对称矩阵、对称矩阵 在一个n阶方阵A中，若元素满足下述性质：aij=aji 0=0)， 元素总数为：n(n+1)/2因此，我们可以按从上到下、从左到右将这些元素存 放在一个向量san(n+1)/2中。为了便于访问对称矩阵A 中的元素，我们必须在aij和sak之间找一个对应关系。a11 a12 a1n a21 a22 a2n an1 an2 ann 第6章 数组及其应用数组及其应用 22 若i ij 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+j 0kja00 a01 a0 n-1c a11 a1 n-1.c c an-1 n-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第6章 数组及其应用数组及其应用 26下三角矩阵的存储和对称矩阵类似，sak和aij对 应关系是：i(i+1)/2+j ijn(n+1)/2 it存放矩阵M的数组是 adatamaxsize 第一个数组元素（三元组）所在的行号、列号分别是：( adata0).i (adata0) .j 它的值为：( adata0).vam , n , t data 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 5 3 14 第6章 数组及其应用数组及其应用 382 2、十字链表十字链表若矩阵的非0元素的个数和位置在操作过程中 变化较大，则不宜采用顺序存储结构来表示三元组 的线性表。可采用链式存储结构来表示三元组的线性表 。第6章 数组及其应用数组及其应用 39在链表中，每个非0元素可用一个含有五个域 的结点表示： ijvcptrrptr其中：其中：i , j ,v 三个域分别表示该元素所在的行、列 和非0元素的值。行指针域 rptr 用以链接同一行中下一 个非0元素；列指针域 cptr 用以链接同一列中下一个非 0元素。 第6章 数组及其应用数组及其应用 40存储时，每个非0元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了 一个十字交叉的链表故称这样的存储结构为十十 字链表。字链表。可用可用两个分别存储行链表和列链表的头指针的分别存储行链表和列链表的头指针的一 维数组表示十字链表。表示十字链表。 M-chead M-rhead 第6章 数组及其应用数组及其应用 41十字链表中非0元结点的类型说明如下：typedef struct lnode int i , j ;datatype v ;struct lnode *cptr , *rptr ; OLnode； ijvcptrrptr第6章 数组及其应用数组及其应用 42十字链表的类型描述如下：#d