北邮算法与数据结构.ppt

《北邮算法与数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构---第五章数组和广义表1第五章数组和广义表5.1数组和线性表的关系以及数组的运算5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表的定义和表示方法5.5广义表的存储结构5.6广义表的递归算法本章学习要点、习题与上机作业本质上是非线性结构。扩展的线性表：表中的数据元素本身也是一个数据结构。数据结构---第五章数组和广义表25.1数组和线性表的关系以及数组的运算任何数组A都可以看作一个线性表A=(a1,a2,…,ai,…an)二维数组mn时，ai是数组中第i行所有元素，0im-1，表中每一个元素是一个

2、一维数组；三维数组时，表中每一个元素是一个二维数组；n维数组时，表中每一个元素是一个(n-1)维数组()()()()()()()()()=Amna00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1数据结构---第五章数组和广义表3数组与线性表之间的关系线性表的扩展，其数据元素本身也是线性表数组的特点数组中各元素都具有统一的类型可以认为，d维数组的非边界元素具有d个直接前趋和d个直接后继数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储每组有定义的

3、下标都存在一个与其相对应的值在数组上的基本操作给定一组下标，取得相应的数据元素值给定一组下标，修改相应的数据元素值数据结构---第五章数组和广义表4数组的基本操作定义(1)构造n维数组InitArray(&A,n,bound1,…,boundn)(2)销毁数组ADestroyArray(&A)(3)取得指定下标的数组元素值Value(A,&e,index1,…,indexn)(4)为指定下标的数组元素重新赋值Assign(&A,e,index1,…,indexn)数据结构---第五章数组和广义表55.2数组的顺序存储结

4、构一维数组b基地址L个单元a0a1aiLOC[i]=LOC[0]+iL=b+iL=c0+c1ic1=Lc0=b=LOC[0]an-1ElemTypea[n]；数据结构---第五章数组和广义表6二维数组a00a01a02...a0,n-1a10a11a12...a1,n-1::::am-1,0am-1,1am-1,2...am-1,n-1a=mna00a0,,n-1a10aijam-1,n-1ba1LOC[i,j]=LOC[0,0]+(in+j)L=c0+c1i+c2jc2=Lc1=nc2=b2c2c

5、0=b=LOC[0,0]注：Pascal、C语言以行序为主序Fortran语言以列序为主序ElemTypea[m][n];“行序为主序”即“低下标优先”“列序为主序”即“高下标优先”aij数据结构---第五章数组和广义表7n维数组LOC[j1,j2,...,jn]=c0+c1j1+c2j2+...+cnjn=c0+cijicn=L;ci-1=cibi(1

6、12]设每数组元素占用8个存储单元，起始地址为1000,求按低下标优先（类似行优先）顺序存储时，LOC[6,1,4,7]=？ElemTypea[b1][b2]...[bn];数据结构---第五章数组和广义表8参考解答维数:b1=5,b2=10,b3=6,b4=8[法1]LOC[6,1,4,7]=1000+[1068(6-3)+68(1-0)+8(4-1)+(7-5)]8=13112[法2]相当于A[0..4,0..9,0..5,0..7],求LOC[3,1,3,2]LOC[3,1,3,2]=LOC[0,0

7、,0,0]+c1j1+c2j2+c3j3+c4j4=1000+c1j1+c2j2+c3j3+82=1000+c1j1+c2j2+883+82=1000+c1j1+6461+883+82=1000+384103+6461+883+82=13112数据结构---第五章数组和广义表95.3矩阵的压缩存储目的是节省空间。5.3.1对称矩阵[特点]在nn的矩阵a中，满足如下性质：aij=aji(1i,jn)[存储方法]只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个

8、元素空间。k=i(i-1)/2+j-1当ijj(j-1)/2+i-1当i