数据结构课件(第5章)数组和广义表

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机组成原理,page,*,信阳师范学院计算机与信息技术学院,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,page,*,信阳师范学院计算机与信息技术学院,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机组成原理,page,*,信阳师范学院计算机与信息技术学院,第,五,章,数组和广义表,信阳师范学院,计算机与信息技术学院,5.1 数组的定义,5,.3,矩阵的压缩存储,5.4 广义表,5,.2,数组的顺序表示和实现,主要内容,2024/10/7,2,信阳师范学院计算机与信息技术学院,基本内容：,数组的定义和顺序存储；,矩阵的压缩存储；,广义表。,学习要点：,了解数组的逻辑结构；,掌握以行或列序为主序的方式存储时，数组元素地址的计算方法；,掌握特殊矩阵的压缩存储；,了解广义表。,2024/10/7,3,信阳师范学院计算机与信息技术学院,（2）每种数据结构中的数据元素，都是,原子数据,，不再进行分解；,本章讨论三个方面的内容：,数组、矩阵的压缩存储、广义表,本章讨论的两种数据结构：,数组和广义表,，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；,2）数据元素本身也是一个数据结构。,前4章介绍的数据结构共同特点：,（1）都属于,线性结构,；,引言,2024/10/7,4,信阳师范学院计算机与信息技术学院,数组是由一组个数固定，类型相同的数据元素组成的阵列。,A,m,n,=,a,00,a,0,2,a,1,n,-1,a,10,a,11,a,1,n,-1,a,m,-1,0,a,m,-1,1,a,m,-1,n,-1,在行关系中,a,ij,直接前趋是,a,ij-1,a,ij,直接后继是,a,ij+1,在列关系中,a,ij,直接前趋是,a,i-1j,a,ij,直接后继是,a,i+,1j,5.1,数组的定义,一维数组的特点：,1个下标，,a,i,的直接前驱是,a,i,-1,，直接后继,是,a,i,+1,。,二维数组的特点：,2,个下标，,每个元素,a,i,j,受到两个关系（行关系和列关系）的约束：,2024/10/7,5,信阳师范学院计算机与信息技术学院,N,维数组的数据类型定义,ADT,ARRAY,Ri=|,0,j,k,b,k,-1,1,k,n 且k i,0,j,i,b,i,-2,a,j1,j2,jijn,a,j1,j2,ji+1jn,D,数据关系：,R=,R1,R2,，,.Rn,D=a,j1,j2jn,|,n(0)称为数组的维数，b,i,是数组第i维的长度，,j,i,为数组元素的第i 维下标，,a,j1,j2jn,Elemset,构造数组、,销毁数组,、读数组元素、写数组元素,基本操作：,数据对象：,j,i,=0,.,b,i,-1,i=1,2,.n,2024/10/7,6,信阳师范学院计算机与信息技术学院,初始化操作,InitArray(&A,n,bound1,boundn),功能：参数合法，构造数组,A,，并返回,OK,；,销毁操作,DestroyArray(&A),功能：销毁数组,A,；,3 读元素操作,Value(A,&e,index1,indexn),功能：若指定下标不越界，读指定下标的元素，用,e,返回并返回,OK,；,4,写元素操作,Assign(A,e,index1,indexn),功能：若指定下标不越界，将,e,赋值给,A,指定的下标元素并返回,OK,。,数组的基本操作,2024/10/7,7,信阳师范学院计算机与信息技术学院,可看作是是一个定长线性表，且它的每个数据元素也是一个定长线性表。,例：,Amn,=,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,二维数组,2024/10/7,8,信阳师范学院计算机与信息技术学院,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,(1)A=(0,1,m-1)i=(ai0,ai1,ai,n-1)0=i=m-1,Amn=,0,1,m-1,=,二维数组,2024/10/7,9,信阳师范学院计算机与信息技术学院,(2)A=(0,1,n-1)j=(a0j,a1j,am-1,j)0=j=n-1,Amn=,0 1 n-1,=,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,2024/10/7,10,信阳师范学院计算机与信息技术学院,二维数组的,C,语言表示：,Typedef elemtype Array1n;,Typedef Array1 Array2m;,Typedef elemtype Arraymn;,2024/10/7,11,信阳师范学院计算机与信息技术学院,用一组,连续的,存储单元存放数组的数据元素。,二维数组的两种顺序存储方式：,（,1,）行序为主序,（,2,）列序为主序,例：,Amn,=,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,5.2,数组的顺序表示和实现,2024/10/7,12,信阳师范学院计算机与信息技术学院,行序为主序：,a00 a01,a0n-1,a10 a11a1n-1,am-1,0 am-1,1,am-1,n-1,数据元素的存储位置：,loc(i,j)=,loc(0,0),+aij,之前的元素个数,L,Amn,=,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,(i*n+j),2024/10/7,13,信阳师范学院计算机与信息技术学院,列序为主序：,a00 a10,am-10,a01 a11am-1,1,a0,n-1 a1,n-1,am-1,n-1,Amn,=,a00 a01 a02 a0,n-1,a10 a11 a12 a1,n-1,am-1,0 am-1,1 am-1,2 am-1,n-1,数据元素的存储位置：,loc(i,j)=,loc(0,0),+aij,之前的元素个数,L,j*m+i,2024/10/7,14,信阳师范学院计算机与信息技术学院,例,2,：,已知二维数组,A,m,m,按行存储的元素地址公式是：,Loc(a,ij,)=Loc(a,11,)+(i-1)*m+(j-1)*K,请问按列存储的公式相同吗？,答：,尽管是方阵，但公式仍不同。应为：,Loc(a,ij,)=Loc(a,11,)+(,j,-1)*m+(,i,-1)*K,例,1,软考题：,一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。这个数组的体积是,个字节。,288,答：,Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288,2024/10/7,15,信阳师范学院计算机与信息技术学院,例,3,：,设数组,a160,170,的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素,a32,58,的存储地址为,。,解：根据列优先公式,Loc(a,ij,)=Loc(a,11,)+(,j,-1)*m+(,i,-1)*K,得：,LOC(,a,32,58,)=2048+(,58-1,)*60+(32-1)*2,8950,想一想：若数组是,a059,069,，,结果是否仍为,8950,？,8950,维界虽未变，但此时的,a32,58,不再是原来的,a32,58,2024/10/7,16,信阳师范学院计算机与信息技术学院,基本内容,特殊矩阵的压缩存储；,稀疏矩阵的压缩存储；,稀疏矩阵在三元组顺序表存储方式下，矩阵的运算的实现。,学习要点,了解矩阵的两种压缩存储方法及适用范围；,了解在三元组顺序表存储方式下，实现矩阵运算的方法。,5.3,矩阵的压缩存储,2024/10/7,17,信阳师范学院计算机与信息技术学院,对称矩阵,是满足下面条件的,n,阶矩阵,a,ij,=,a,ji,1,i,j,n,1.特殊矩阵,值相同元素或者零元素分布有一定规律的矩阵称特殊矩阵,例 对称矩阵、上（下）三角矩阵都是特殊矩阵,2024/10/7,18,信阳师范学院计算机与信息技术学院,对称矩阵,a,11,a,12,.,.,a,1n,a,21,a,22,.,a,2n,a,n1,a,n2,.,a,nn,.,a11 a21 a22 a31 a32,an1 ann,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,k=,i(i-1)/2+j-1,当,i,j,j(j-1)/2+i-1,当,i,j,若,i,j,，则aij在下三角形中。aij之前的i,-1,行（从第,1,行到第i-1）,一共有1+2+i,-1,=i(i,-,1)/2个元素，在第i行上，ai j之前恰有j,-1,个元素（即ai,1,ai,2,aij-1），因此有：,k=i*(i,-,1)/2+j,-1,若,ij,，则,aij,是在上三角矩阵中。因为,aij=aji,，所以只要交换上述对应关系式中的,i,和,j,即可得到：,k=j*(j-1)/2+i-1,2024/10/7,19,信阳师范学院计算机与信息技术学院,a,11,0 0,.,0,a,21,a,22,0,.,0,a,n1,a,n2,a,n3,.,a,nn,.,0,Loc(a,ij,)=Loc(,a,11,)+(j-1)*L,i(i-1),2,a11 a21 a22 a31 a32,an1 ann,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,三角矩阵,2024/10/7,20,信阳师范学院计算机与信息技术学院,对角矩阵,a,11,a,12,0,.,0,a,21,a,22,a,23,0,0,0,0,a,n-1,n-2,a,n-1,n-1,a,n-1,n,0,0,a,n,n-1,a,nn.,0,a,32,a,33,a,34,0,0,Loc(a,ij,)=Loc(a,11,)+2(i-1)+(j-1),a11 a12 a21 a22 a23 ann,.,ann-1,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,2024/10/7,21,信阳师范学院计算机与信息技术学院,M,=,0 12 9 0 0 0 0,0 0 0 0 0 0 0,-3 0 0 0 0 14 0,0 0 24 0 0 0 0,0 18 0 0 0 0 0,15 0 0-7 0 0 0,M,有42（6,7）个元素,有8个非零元素,2.稀疏矩阵,例,有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。,2024/10/7,22,信阳师范学院计算机与信息技术学院,稀疏矩阵可由非零元的,三元组表,及其,行数、列数,唯一确定。,M,=,0 12 9 0 0 0 0,0 0 0 0 0 0 0,-3 0 0 0 0 14 0,0 0 24 0 0 0 0,0 18 0 0 0 0 0,15 0 0-7 0 0 0,三元组表,A=,(,(1,2,12),(1,3,9),(3,1,-3),3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),),行数为,6,列数为,7,三元组表,2024/10/7,23,信阳师范学院计算机与信息技术学院,#,define MAXSIZE 12500,/,假设非零元个数的最大值为12500,Typrdef struct,