严蔚敏数据结构(数组和广义表)ppt课件.ppt

《严蔚敏数据结构(数组和广义表)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。5.1数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组(是以类型相同的一维数组为元素的线性表）A：可以看成是由一个行向量组成的向量，也可以看成是一个列向量组成的向量。()()()()()()()()()在C语言中，一个二维数组类型

2、可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedefelemtypearray2[m][n];等价于：typedefelemtypearray1[n];typedefarray1array2[m];数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5.2数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。通常有两种顺序存储方式：以行序为主序以列序为主序a11a12……..a1na21a22……..

3、a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l多维数组元素地址的计算(以行序为主序)：三维数组：a[b1][b

4、2][b3]Loc(a[i][j][k])=Loc(a[0][0][0])+(i*b2*b3+j*b3+k)*l多维数组：a[b1][b2]…[bn]Loc[(a[j1][j2]…[jn])=Loc[a[0][0]…[0])+(j1*b2*b3*…*bn+j2*b3*…*bn+j3*b4*…*bn+…+jn-1*bn+jn)*l缩写为：Loc[(a[j1][j2]…[jn])＝Loc[a[0][0]…[0])＋Loc[(a[j1][j2]…[jn])＝Loc[a[0][0]…[0])＋其中cn=l,ci-1=bi*ci此式称为n维数组的映象函数。一旦确定了数组的各维长度ci就是常

5、数。数组的顺序存储表示：#include#defineMAX_ARRAY_DIM8typedefstruct{elemtype*base;//数组元素基址intdim;//数组维数int*bounds;//数组维界基址int*constants;//数组映象函数常量基址}Array;数组的顺序存储的实现：InitArray(A,dim){if(dim<1

6、

7、dim>MAX_ARRAY_DIM)exit(‘cuowu’);A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(‘失败’

8、);elemtotal=1;va_start(ap,dim);for(i=0;i=0;--i)A.constant

9、s[i]=A.bounds[i+1]*A.constants[i+1];}5.3矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪