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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,5,章 多维数组和广义表,5.1,多维,数组,5.2,特殊,矩阵,的压缩存储,5.3,稀疏,矩阵,的压缩存储,5.4,广义表的概念,1,第5章 多维数组和广义表5.1 多维数组1,5.1 数组,一、数组的定义,数组：它是n（n1)个相同数据类型的数据元素a,0,a,1,a,2,a,n-1,构成的占用一块地址连续的内存单元的有限序列。,数组的下标：数组元素的位置。,注意：,(1)C语言的数组定义下标从0开始。,(2)数组的处理相比其它复杂的结构要简单。,数组中各元素具有,统一的类型,；,数组元素的下标一般具有,固定的上界和下界,，即数组一旦被定义，它的维数和维界(上下界)就不再改变。,数组的,基本操作比较简单,，,除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。,(3)一个二维数组可以看作每个数据元素是一个一维数组的一维数组。,二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，C语言采用以行序为主序的方法存储。,2,5.1 数组 一、数组的定义2,问题：数组与线性表的区别与联系,相同之处：,它们都是若干个,相同数据类型,的数据元素a,0,a,1,a,2,，a,n-1,构成的有限序列。,不同之处：,(1)数组要求其元素占用一块,地址连续,的内存单元空间，而线性表无此要求；,(2)线性表的元素是,逻辑意义上不可再分的元素,，而数组中的每个,元素还可以是一个数组,；,(3)数组的,操作,主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作,不同,。,3,问题：数组与线性表的区别与联系相同之处：3,二、数组的实现机制,、,一维数组（n个元素）中任一元素a,i,的内存单元地址,LOC(a,i,)=LOC(a,)+i*k,(0,i,n),、一个m行n列的二维数组,LOC(a,ij,)=LOC(a,00,)+(i*n+j)*k,(0,i,m,，0,j,n),注：C语言中数组元素采用行主序的存放方法，即,行优先,顺序,。,a,的内存单元地址,每个元素所需的字节个数,每个元素所需的字节个数,a,0,的内存单元地址,一个,mn,的二维数组可以看成是,m行的一维数组，或者n列的一维数组。,a,0,0,a,0,1,a,0,n-1,a,1,0,a,1,1,a,1,n-1,a,m-1,0,a,m-1,1,a,m-1,n-1,A,mn,=,4,二、数组的实现机制、一维数组（n个元素）中任一元素ai的内,对于行优先顺序：先排最右的下标，从右往左，最后排最左下标；,对于列优先顺序：先排最左的下标，从左往右，最后排最右下标；,5,对于行优先顺序：先排最右的下标，从右往左，最后排最左下标；5,注：只要知道以下三要素便可随时求出任一元素的地址,（意义：数组中的任一元素可随机存取）,开始结点的存放首字节地址（即基地址）；维数和每维的上、下界；每个数组元素所占用的单元数。,例,软考题：,一个二维数组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(a,ij,)=LOC(a,00,)+(i*n+j)*k,(0,i,m,，0,j,n),得：LOC(a,32,58,)=2048+(,32,*71+,58,)*2,288,6,注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组,二维数组A,mn,按行优先顺序存储,元素,a,ij,的存储地址为数组的基地址加上排在aij前面的元素所占用的单元数。因为a,ij,位于第i行，第j列,前面i行一共有i*n个元素，第i行上a,ij,前面又有j个元素，故它前面一共有i*n+j个元素，因此，a,ij,的地址计算函数为：Loc(a,ij,)=Loc(a,00,)+i*n+j*d,7,二维数组Amn按行优先顺序存储元素aij的存储地址为数组的,三、,数组抽象数据类型,数据集合,：,a,0,a,1,a,2,a,n-1,每个数据类型为抽象数据元素类型,操作集合,:,(1)求,数组元素个数 ArrayLength(D),(2)存数组元素Storage(D,i,x),(3)取数组元素Get(D,i,x),8,三、数组抽象数据类型数据集合：a0,a1,a2,an-,5.2 特殊矩阵的压缩存储,特殊矩阵:,指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。,下面我们讨论几种特殊矩阵的压缩存储。,1、n阶对称矩阵,在一个n阶方阵A中，若元素满足下述性质：,a,ij,=a,ji,（1i,jn）,则称A为,n阶对称矩阵,。,1 5 1 3 7 a,11,5 0 8 0 0 a,21,a,22,1 8 9 2 6 a,31,a,32,a,33,3 0 2 5 1 .,7 0 6 1 3 a,n1,a,n2,a,n3,a,nn,图 5.1 对称矩阵,n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先,顺序”存储主对角线（包括对角线）以下的元素。,9,5.2 特殊矩阵的压缩存储 特殊矩阵:指有许多值相同的元素,i(i+1)/2+j 当ij,j(j+1)/2+i 当i,j,k=,在这个下三角矩阵中，第i行恰有i个元素，元素总数为n(n+1)/2，这样就可将,n,2,个数据元素压缩存储在,n(n+1)/2,个存储单元中。,假设以一维数组va作为n阶对称矩阵A的压缩存储单元，k为一维数组va的下标序号，a,ij,为n阶对称矩阵A中i行j列的数据元素(其中1i,jn），其数学映射关系为：,令I=max(i,j),J=min(i,j),则k和i,j的对应关系可统一为：,k=I*(I+1)/2+J 0,kn(n+1)/2,2、n阶三角矩阵,以主对角线划分，n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。,n阶上三角矩阵如图5.2(a)所示，它的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数），如图5.2(b)所示。,注：在大多数情况下，n阶三角矩阵常数为零。,10,i(i+1)/2+j 当ijk=在这,a,11,a,12,a,1n,a,11,c c,c a,22,a,2n,a,21,a,22,c,.,c c a,nn,a,n1,a,n2,a,n n,(a)上三角矩阵 (b)下三角矩阵,图5.2 三角矩阵,i(i-1)/2+j-1 当ij,n(n+1)/2,（或空）,当i,md=da.nd;/*行数值转为列数值*/,db-nd=da.md;/*列数值转为行数值*/,db-td=da.td;/*非零元个数不变*/,if(da.td=0)return;,elseq=0;/*q为b-list的下标值*/,for(v=1;v=da.nd;v+),for(p=0;p listq.,i,=a.listp.,j,;/*列号转为行号*/,b-listq.,j,=a.listp.,i,;/*行号转为列号*/,b-listq.d=a.listp.d;/*数组元素复制*/,q+;,19,三元组顺序表的转置操作的算法实现：void Transit,三、稀疏矩阵的三元组链表,1、三元组链表,用链表存储的三元组线性表。,2、行指针数组结构的三元组链表,把每行非零元素三元组组织成一个单链表，再设计一个指针类型的数组存储所有单链表的头指针。,3、三元组十字链表,把非零元素三元组按行和按列组织成单链表，这样稀疏矩阵中的每个非零元素三元组结点都将既勾链在行单链表上，又勾链在列单链表上，形成十字形状。,20,三、稀疏矩阵的三元组链表1、三元组链表20,广义表,广义表是线性表的推广。线性表的元素仅限于原子项（结构上不可分割，可以是一个数或一个结构），若而广义表容许他们具有其自身结构。,广义表是n(n0)个元素a,1,a,2,a,n,的有限序列，其中a,i,或者是原子或者是一个广义表。,记作：LS=(a,1,a,2,a,n,),若广义表LS非空(即n1),则a,1,是LS的表头，其余元素组成的表(a,1,a,2,a,n,)称为LS的表尾。,21,广义表广义表是线性表的推广。线性表的元素仅限于原子项（结构上,