《数组和广义表 》ppt课件

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

1、第五章数组和广义表数组和广义表可看成是一种特殊的线性表，其特殊在于:表中的数据元素本身也是一种线性表5.1数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a11a12…a1na21a22…a2n…………am1am2…amnAmn=可以看成是m由个行向量组成的向量，也可以看成是n个列向量组成的向量。数组一旦被定义，它的维数和

2、维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5.2数组的顺序表示和实现由于计算机的内存储结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法5.6广

3、义表操作的递归函数5.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn

4、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{

5、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:二维数组的定义:数据对象:D={aij

6、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={

7、i+1,j>

8、0≤i≤b1-2,0≤j≤b2-1}COL={

9、0≤i≤b1-1,0≤j≤b2-2}基本操作：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)操作结

10、果：销毁数组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。5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的

11、方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1

12、(0,0,...,0)+∑cijii=1n假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。5.3稀疏矩阵的压缩存储何谓稀疏矩阵？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。1)特殊矩阵非零元在

13、矩阵中的分布有一定规则例如:三角矩阵对角矩阵2)随机稀疏矩阵非零元在矩阵中随机出现有两类稀疏矩阵：5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关