第5章多维数组和广义表课件.ppt

1,第5章 多维数组和广义表,5.1 多维数组5.2 特殊矩阵的压缩存储5.3 稀疏矩阵的压缩存储5.4 广义表的概念,2,5.1 数组,一、数组的定义数组：它是n（n1)个相同数据类型的数据元素a0,a1,a2,an-1构成的占用一块地址连续的内存单元的有限序列。数组的下标：数组元素的位置。注意：(1)C语言的数组定义下标从0开始。(2) 数组的处理相比其它复杂的结构要简单。 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界(上下界)就不再改变。 数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。(3)一个二维数组可以看作每个数据元素是一个一维数组的一维数组。二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，C语言采用以行序为主序的方法存储。,3,问题：数组与线性表的区别与联系,相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,，an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。,4,二、数组的实现机制,、一维数组（n个元素）中任一元素ai的内存单元地址 LOC(ai)=LOC(a)+i*k (0i n)、一个m行n列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k (0im， 0jn)注：C语言中数组元素采用行主序的存放方法，即行优先顺序。,a的内存单元地址,每个元素所需的字节个数,每个元素所需的字节个数,a0的内存单元地址,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1,Amn=,5,对于行优先顺序：先排最右的下标，从右往左，最后排最左下标；对于列优先顺序：先排最左的下标，从左往右，最后排最右下标；,6,注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）开始结点的存放首字节地址（即基地址）；维数和每维的上、下界；每个数组元素所占用的单元数。,例软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288例 设数组a60, 70的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a32,58的存储地址为 。答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)得：LOC(a32,58)=2048+(32*71+58)*2,288,7,二维数组Amn按行优先顺序存储,元素aij的存储地址为数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行，第j列,前面i行一共有i*n个元素，第i行上aij前面又有j个元素，故它前面一共有i *n+j个元素，因此，aij的地址计算函数为： Loc(aij)= Loc(a00)+i *n+j*d,8,三、数组抽象数据类型,数据集合： a0,a1,a2,an-1 每个数据类型为抽象数据元素类型,操作集合:(1)求数组元素个数 ArrayLength(D) (2)存数组元素Storage(D,i,x) (3)取数组元素Get(D,i,x),9,5.2 特殊矩阵的压缩存储,特殊矩阵:指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。 下面我们讨论几种特殊矩阵的压缩存储。1、n阶对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji （1i,jn） 则称A为n阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 a nn 图 5.1 对称矩阵 n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。,10,i(i+1)/2+j 当ij j(j+1)/2+i 当ij,k=,在这个下三角矩阵中，第i行恰有i个元素，元素总数为n(n+1)/2，这样就可将n2个数据元素压缩存储在n(n+1)/2个存储单元中。 假设以一维数组va作为n阶对称矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶对称矩阵A中i行j列的数据元素(其中1i,jn ），其数学映射关系为： 令I=max(i,j), J=min(i,j),则k和i,j的对应关系可统一为： k=I*(I+1)/2+J 0kn(n+1)/2,2、n阶三角矩阵 以主对角线划分， n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。 n阶上三角矩阵如图5.2(a)所示，它的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数），如图5.2(b)所示。 注：在大多数情况下， n阶三角矩阵常数为零。,11,a11 a12 a 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵,i(i-1)/2+j-1 当ijn(n+1)/2 （或空） 当ij,k=,假设以一维数组sa作为n阶下三角矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶下三角矩阵A中i行j列的数据元素(其中1i,jn ），其数学映射关系为：,注：此时一维数组sa的数据元素个数为(n(n+1)/2)+1个，其中数组sa的最后一个位置存储A中数值不为0的那个常数。,12,5.3 稀疏矩阵的压缩存储,一 、概念1、稀疏矩阵 矩阵中非零元素的个数较少（一般小于5%）。2、稠密矩阵 一个不稀疏的矩阵。3、稀疏矩阵压缩存储方法 问题： 如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？ 实现方法： 将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组线性表来表示。,13,例1：写出下图5.3所示稀疏矩阵的压缩存储形式。 1 2 3 4 5 6 1 2 3 4 5 6 图5.3,解：用三元组线性表表示： 1,2,12,1,3,9,3,1,-3,3,5,14, 4,3,24,5,2,18,6,1,15,6,4,-7说明：稀疏矩阵的压缩存储结构主要有三元组顺序表和三元组链表两大类型。,14,二、稀疏矩阵的三元组顺序表,1、三元组顺序表 指用顺序表存储的三元组线性表。 把三元组定义成顺序表的数据元素： typedef struct int i; /*行号 */ int j; /*列号 */ elemtype d; /*元素值 */ DataType; 把稀疏矩阵的行数、列数和非零元个数定义成三元组顺序表的控制数据结构体： typedef struct int md; /*行数 */ int nd; /*列数 */ elemtype td; /*非零元素个数 */ TriType;,15,i j d 0 1 2 说明：存储一个矩阵时，通常是按照 先行后列的顺序存储。 3 4 5 md 6 nd 7 td 图5.4 稀疏矩阵的三元组顺序表,16,例2：下面的三元组表表示一个稀疏矩阵，试还原出它的稀疏矩阵。,17,2、稀疏矩阵的操作,已知三元组表a,求三元组表b,M,T,（以转置运算为例）,目的：,18,答：肯定不正确！除了： （1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还需要：（2） T的总行数md和总列数nd也要互换； （3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。,上述（1）和（2）容易实现，难点在（3）。,若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？,提问：,19,三元组顺序表的转置操作的算法实现：,void Transition2(SeqList a,TriType da,SeqList *b,TriType *db) int p, q, v;db-md = da.nd; /*行数值转为列数值*/db-nd = da.md; /*列数值转为行数值*/db-td = da.td;/*非零元个数不变*/if (da.td=0)return;elseq = 0; /*q为b-list的下标值*/ for (v=1;vlistq.i = a.listp.j; /*列号转为行号*/ b-listq.j = a.listp.i; /*行号转为列号*/ b-listq.d = a.listp.d; /*数组元素复制*/ q+; ,20,三、稀疏矩阵的三元组链表,1、三元组链表 用链表存储的三元组线性表。2、行指针数组结构的三元组链表 把每行非零元素三元组组织成一个单链表，再设计一个指针类型的数组存储所有单链表的头指针。3、三元组十字链表 把非零元素三元组按行和按列组织成单链表，这样稀疏矩阵中的每个非零元素三元组结点都将既勾链在行单链表上，又勾链在列单链表上，形成十字形状。,21,广义表,广义表是线性表的推广。线性表的元素仅限于原子项（结构上不可分割，可以是一个数或一个结构），若而广义表容许他们具有其自身结构。广义表是n(n0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表。记作： LS=(a1,a2,an) 若广义表LS非空(即n1),则a1是LS的表头，其余元素组成的表(a1,a2,an)称为LS的表尾。,