资源描述：
《数据结构(清华)第五章 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章数组和广义表5.1数组的类型定义5.3矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的存储结构学习提要：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn
2、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{3、...ji,...jn,aj1,...ji+1,...jn>
4、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁
5、数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返OK。二维数组的定义:数据对象:D={aij
6、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={
7、0≤i≤b1-1,0≤j≤b2-2}COL={
8、0
9、≤i≤b1-2,0≤j≤b2-1}二维数组的定义:5.2数组的顺序表示和实现类型特点:（1）只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:（1）以行序为主序（2）以列序为主序a00a01……a0n-1a10a11……a1n-1am-10am-11…am-1n-1………………….按行序为主序存放am-1n-1……..am-11am-10……….a1n-1……..a11a10a0n-1…….a01a0001n-1m*n-1n按列序为主序存放01m-1m*n-1mam-1n-1……..a1n-1a0n-1……….am-11……..a1
10、1a01am-10…….a10a00a00a01……..a0n-1a10a11……..a1n-1am-10am-11…am-1n-1………………….称为基地址或基址以“行序为主序”的存储映象:二维数组A中任一元素aij的存储位置LOC(i,j)=LOC(0,0)+(n×i＋j)×L以“列序为主序”的存储映象:二维数组A中任一元素aij的存储位置LOC(i,j)=LOC(0,0)+(m×j＋i)×L推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,111、jn)=LOC(0,0,...,0)+∑cijii=1n5.3.1特殊矩阵5.3矩阵的压缩存储5.3.2稀疏矩阵以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:(1)零值元素占了很大空间;(2)计算中进行了很多和零值的运算。(1)尽可能少存或不存零值元素；解决问题的原则:(2)尽可能减少没有实际意义的运算；(3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。5.3.1特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。对称矩阵元素满足条件aij=aji1=12、.a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1三角矩阵按行序为主序：Loc(aij)=Loc(a11)+[i*(i-1)/2+(j-1)]*La1100……..0a21a220……..0an1an2an3……..ann………………….0a11a21a22a31a32an1ann…...…..
