资源描述：
《数据结构讲义(严蔚敏版)第五章 数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表共同特征：表中的数据元素本身也是一个数据结构介于线性结构和非线性结构之间的数据结构数组几乎所有程序设计语言中的固有数据类型广义表LISP语言，应用在人工智能等领域，以广义表为基本数据结构，把程序表示称为一系列的广义表5.1数组的定义-抽象数据类型ADTArray{数据对象:ji=0,…,bi–1,i=1,2,…,n,D={
2、∈ElemSet}数据关系:R={R1,R2,…,Rn}Ri={
3、0≤jk≤bk–1,1≤k≤n,k!=i,0≤ji≤bi–2,∈D,i=2,3,…,n}基本操作：InitArray(&A,n,bound1,…,boundn)DestroyArray(
4、&A)Value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)}ADTArray5.1数组的定义n维数组是线性表的推广n=1，n维数组退化成顺序表n>1，n维数组可看成表中数据元素是线性表的线性表a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Am*n=二维数组a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Am*n=列向量的一维数组Am*n=((a00a01…a0,n-1),(a10a11…a1,n-1),…,(am-1,0am
5、-1,1…am-1,n-1))行向量的一维数组A=(α0,α1,…αp)p=m-1或n-1在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，typedefElemtypeArray2[m][n];=>typedefElemtypeArray1[n];typedefArray1Array2[m];二维数组的二种理解方式：视作多个一维数组视作一个一维数组5.1数组的定义a00a01a02a03a10a11a12a13a20a21a22a23a[3][4]a[0]a[1]a[2]a[3]a[3][4]a[0]a[1]a[2]5.2数组的顺序表示和实现特点：用一组地址连
6、续的存储单元按照某种规则存放数组中的数据元素。两种规则（顺序存储方式）：以行序为主（低下标优先）—将数组元素按行排列，第i+1个行向量紧接在第i个行向量后。如：PASCAL、C。以列序为主（高下标优先）—将数组元素按列排列，第j+1个列向量紧接在第j个列向量后。如：FORTRAN。5.2数组的顺序表示和实现a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Am*n=二维数组am-1,n-1……a1,n-1a0,n-1……am-1,1……a11a01am-1,0……a10a00按列序为主序am-1,n-1……am-1,1am-1,0……a1
7、,n-1……a11a10a0,n-1……a01a00按行序为主序5.2数组的顺序表示和实现计算数组任一元素( )的地址需要的三要素：①数组的起始地址（即基地址）②数组维数和各维的长度；③数组中每个元素所占的存储单元已知二维数组Ab1*b2，每个元素占L个存储单元，LOC(0,0)是第一个元素的起始地址，以行序为主存储，求LOC(i,j)。行主序：LOC(i,j)=LOC(0,0)+(b2*i+j)*L列主序：LOC(i,j)=LOC(0,0)+(b1*j+i)*La00a01…a0,b2-1a10a11…a1,b2-1……aij…ab1-1,0ab1-1,1…ab1-1,b2-1Ab1*b
8、2=计算二维数组元素地址的通式设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-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)]*L5.2数组的顺序表示和实现行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k二维数
9、组三维数组5.2数组的顺序表示和实现A[5][4][6]以行序为主存储，计算A[3][2][2]的地址数组元素的存储位置是其下标的线性函数，由于计算各个元素存储位置的时间相等，所以存储数组中任一元素的时间也相等，称具有这一特点的存储结构为随机存储结构。5.2数组的顺序表示和实现n维数组元素存储地址的计算公式设各维长度分别为b1,b2,b3,…,bn,每个元素占L个存储单元，起始地址LOC(0,0,…,0)，求元素的存储位
