ch5数组和广义表.ppt

《ch5数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组和广义表一、教学内容：1、数组的定义和运算2、数组的顺序存储结构3、矩阵的压缩存储4、广义表的定义5、广义表的存储结构二、教学要求：了解稀疏矩阵的三元组和十字链表存储结构和基本运算；理解稀疏矩阵和特殊矩阵进行压缩存储的方法及下标变换；理解广义表的基本概念，掌握广义表的特点及存储结构；掌握数组的两种存储表示方法，特别是以行为主的存储结构中的地址计算方法；目录5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义本章总结5.1数组的定义和特点定义:数组可以看成是一种特

2、殊的线性表，即线性表中数据元素本身也是一个线性表.数组特点数组结构固定(具有固定的上界和下界)数据元素同构(元素类型相同)数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型typedefElemTypeArray2[m][n];等价于typedefElemTypeArray1[n];typedefArray1Array2[m];如:Array2A;//数组一旦被定义，它

3、的维数和维界就不再改变。二维的数组=定长的线性表a11a12a13...a1na21a22a23...a2nAmxn=......am1am2am3...amnAm*n=((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn))数组的抽象数据类型ADTArray{数据对象：D={aj1j2...jn

4、n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn属于Elemset}数据关

5、系：R={R1,R2...Rn}Ri={＜aj1...ji...jn,aj1...ji+1...jn＞

6、0jkbk-1,1kn,aj1...ji...jn,aj1...ji+1...jn属于D}。基本操作：InitArray(&A,n,bound1,bound2,...,boundn);DestroyArray(&A);Value(A,&e,index1,index2,...,indexn);Assign(&A,e,index1,index2,...,indexn)}ADTArray5.2数

7、组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：以行序为主序以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1

8、)]*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无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素

9、便可以随机存取！）：①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数数组的应用生命细胞游戏魔术方阵5.3矩阵的压缩存储矩阵:二维数组特殊矩阵:大量重复元素或大量0元素稀疏矩阵:大量0元素压缩存储:重复元素只分配一个存储空间,0元素不分配存储空间5.3.1特殊矩阵1.对称矩阵:aij=aji(1<=i,j<=n)a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1ann…...…

10、...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。对称矩阵顺序存储实例:15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1在这个下三角矩阵中，元素总数为：n(n+1)/2因此，我们可以按从上到下、从左到右访问对称矩阵A中的元素，若i≧j，则aij在下三角形中。aij之前的i行一共有1+2+