数组和稀疏矩阵.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本章的基本内容是：,数组的基本概念,数组的逻辑结构,特殊矩阵的压缩存储,广义表,第五章 数组和广义表,限制插入、删除位置,线性表,具有相同类型的数据元素的有限序列。,线性表,具有相同类型的数据元素的有限序列。,限制元素类型为字符,栈,仅在表尾进行插入和删除操作的线性表。,队列,在一端进行插入操作，而另一端进行删除操作的线性表。,串,零个或多个字符组成的有限序列。,特殊线性表,广义线性表,多维数组,数组的基本概念,数组的定义,数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受,n,(,n,1),个线性关系的约束，每个元素在,n,个线性关系中的序号,i,1,、,i,2,、,、,i,n,称为该元素的下标，并称该数组为,n,维数组。,数组具有以下性质：,(1),数组中的数据元素数目固定。一旦定义了一个数组,维数与维界及其数据元素数目不再有增减变化。,(2),数组中的数据元素具有相同的数据类型。,(3),数组中的每个数据元素都和一组惟一的下标值对应。,(4),数组是一种随机存储结构。可随机存取数组中的任意数据元素。,数组的基本概念,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,A=,A=(A,1,，A,2,，A,n,),其中：,A,i,=(a,1i,，a,2i,，a,mi,),(1in),数组,线性表的推广,二维数组是数据元素为线性表的线性表。,数组的基本概念,数组的基本操作,在数组中插入（或）一个元素有意义吗？,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,A=,将元素,x,插入,到数组中第,1,行第,2,列。,x,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,A=,删除数组中,第,1,行第,2,列元素。,数组的基本概念,数组的基本操作,存取：给定一组下标，读出对应的数组元素；,修改：给定一组下标，存储或修改与其相对应的数组元素。,存取和修改操作本质上只对应一种操作,寻址,数组应该采用何种方式存储？,数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,数组的基本概念,数组的存储结构,一维数组,已知：,a0,地址为,2000H,数组每个元素所占字节数,L,为,2,计算：,a5,的地址,LOC(a5)=LOC(a0)+L*(5-0),=2000+2*5,=,总结：,若是一维数组 已知起始地址为LOC(a1)，每个元素所占K个存储单元，则 LOC(ai)=LOC(a1)+K*(i-1),总结：LOC(aij)=LOC(a00)+,0 5 -15,0 3 22,计算：a23 的地址,在数组中插入（或）一个元素有意义吗？,稀疏矩阵的压缩存储三元组,=2022,本行中aij前面的元素个数,3 cc c c,Ai=(a1i，a2i，ami),4 0 91,t-datat-nums.,0 0 15,0 0 15,已知：int a34;,设一维数组的下标的范围为闭区间,l,，,h,，,每个数组元素占用,c,个存储单元，则,其,任一元,素,a,i,的存储地址可由下式确定：,Loc(,a,i,),Loc(,a,l,),(,i,l,),c,c,a,l,a,i,-1,a,i,a,h,a,l,+1,Loc,(,a,l,),Loc,(,a,i,),数组的存储结构,一维数组,a21 a22 a2n,2 3 6,已知：a0 地址为2000H,数组每个元素所占字节数 L为2 计算：a5 的地址,am1 am2 amn,void CreatMat(TSMatrix&t,ElemType AMN),这就是稀疏矩阵，为什么要研究稀疏矩阵？,已知：int a34;,=(i-l1)(h2-l21)(j-l2),0 0 0 6 0 0,row col item,数组的存储结构二维数组,3 cc c c,0 0 0 6 0 0,空 空 空,1 1 11,dataMaxSize,计算：a23 的地址,0 0 15,常用的映射方法有两种：,按,行,优先：,先行后列,，先存储行号较小的元素，行号相同者先存储列号较小的元素。,按,列,优先：,先列后行,，先存储列号较小的元素，列号相同者先存储行号较小的元素。,二维数组,内 存,二维结构,一维结构,数组的存储结构,二维数组,l,2,h,2,l,1,h,1,(,a),二维数组,a,ij,前面的元素个数,=阴影部分的面积,=整行数每行元素个数+本行中,a,ij,前面的元素个数,=,(,i,-,l,1,),(,h,2,-,l,2,1,),(,j,-,l,2,),本行中,a,ij,前面的元素个数,每行元素个数,整行数,a,ij,按行优先存储的寻址,数组的存储结构,二维数组,数组的存储结构,二维数组,已知：,int a34;,已知：,a0 0,地址为,2000H,数组每个元素所占字节数,L,为,2,计算：,a23,的地址,LOC(a23)=LOC(a00)+(2-0)*4+(3-0)*L,=2000+(8+3)*2,=2022,总结：,LOC(aij)=LOC(a00)+,(i-0)*4+(j-0)*L,第,l,1,行,第,l,1,+1,行,a,l,1,l,2,a,l,1,h,2,a,(,l,1,+1),l,2,a,(,l,1,+1),h,2,a,ij,a,h,1,h,2,Loc,(,a,ij,),Loc,(,a,l,1,l,2,),(,i,-,l,1,),(,h,2,-,l,2,1,),(,j,-,l,2,),个元素,Loc(,a,ij,),Loc(,a,l,1,l,2,),(,i,l,1)(,h,2,l,2,1),(,j,l,2),c,按列优先存储的寻址方法与此类似。,数组的存储结构,二维数组,按行优先存储的寻址,特殊矩阵的压缩存储,特殊矩阵：,包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。,稀疏矩阵：,矩阵中有很多零元素。,3,6478,6,2,842,48,1,69,746,0,5,8295,7,A,对称矩阵特点：,a,ij,=,a,ji,如何压缩存储？,只存储下三角部分的元素。,特殊矩阵的压缩存储,对称阵,3,c,c,c,c,6 2,c,c,c,4 81,c,c,7 46 0,c,8 29 5 7,(,a),下三角矩阵,3 4 8 1 0,c,2 9 4 6,c,c,5 7,c,c,c,0 8,c,c,c,c,7,(,b),上三角矩阵,如何压缩存储？,只存储上三角（或下三角）部分的元素。,特殊矩阵的压缩存储,三角阵,15 0 0,0 0 0,0 11,0 0 0 0,0 0 0 6 0 0,0 0 0 0 0 0,9,0 0 0 0 0,A,=,如何只存储非零元素？,注意：稀疏矩阵中的非零元素的分布没有规律。,特殊矩阵的压缩存储,稀疏矩阵,稀疏矩阵是指矩阵中存在大量的,零元,，,非零元,数目较少且分布没有规律。,一个阶数较大的矩阵中的非零元素个数,s,相对于矩阵元素的总个数,t,十分小时,即,srows=M;t-cols=N;t-nums=0;,for(i=0;iM;i+),for(j=0;jdatat-nums.r=i;t-datat-nums.c=j;,t-datat-nums.d=Aij;,t-nums+;,rows,cols,nums,dataMaxSize,r,c,d,(2),输出三元组,从头到尾扫描三元组,t,依次输出元素值。算法如下：,void DispMat(TSMatrix t),int i;,printf(“t%dt%dt%dn,t-rows,t-cols,t-nums);,printf(-n);,for(i=0;inums;i+),printf(t%dt%dt%dn,t-datai.r,t-datai.c,t-datai.d);,rows,cols,nums,dataMaxSize,r,c,d,