资源描述：
《第五章-数据结构-数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第五章数组和广义表内容提要数组的定义5.1数组的顺序表示和实现5.2矩阵的压缩存储5.3广义表的定义5.4广义表的存储结构5.5基本要求（1）掌握数组的定义、运算，顺序存储结构。（2）掌握特殊矩阵的压缩、存储和处理与稀疏矩阵的三元组表示和在该存储结构下的矩阵运算。（3）掌握广义表的定义、存储结构和基本操作。重点数组在以行为主的存储结构中的地址计算方法，矩阵实现压缩存储时的下标变换，以三元组表示稀疏矩阵时进行运算采用的处理方法，广义表的定义及其存储结构，广义表的表头，表尾分析方法，编制广义表的递归算法。难点三元组表示稀疏矩阵时进行运算采用的处理方法，广义表的递归算法。基本要求
2、、重点、难点5.1数组的定义数组：由一组名字相同、下标不同的变量构成。答：对的。因为——①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。判断：“数组的处理比其它复杂的结构要简单”，对吗？二维数组的特点：一维数组的特点：1个下标，ai是ai+1的直接前驱2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一
3、个n维数组可以看成是由若干个n－1维数组组成的线性表。a11a12…a1na21a22…a2n………… am1am2…amnAmn=N维数组的数据类型定义n_ARRAY=(D,R)其中：Ri={
4、aj1,j2,…ji…jn,aj1,j2,…ji+1…jnD}数据关系：R={R1,R2，….Rn}数据对象：D={aj1,j2…jn
5、ji为数组元素的第i维下标，aj1,j2…jnElemset}构造数组、销毁数组、读数组元素、写数组元素基本操作：5.2数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是多
6、维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。补充：计算二维数组元素地址的通式设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0或1无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址：二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i
7、-c1)]*Lac1,c2…ac1,d2…aij… ad1,c2…ad1,d2Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*La(0,0)a(0,1)……a(0,3)a(1,0)a(1,1)……a(1,3)………………………………a(3,2)………………………………………………a(6,0)…………a(6,3)01230123456例1：如何
8、求出a(3,2)的存储地址？要事先确定：①是行优先方式还是列优先方式？②数组的首地址是多少？③每个元素的长度？否则无法求出结果例3：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,请问按列存储的公式相同吗？答：尽管是方阵，但公式仍不同。应为：Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例2：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。288答：Volume=m*n*L=(6-1+1)*(7-
9、0+1)*6=48*6=288例4：〖00年计算机系考研题〗：设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。根据列优先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950答：请注意审题！想一想：若数组是a[0…59,0…69]，结果是否仍为8950？8950维界虽未变，但此
