CH5数组和广义表ppt课件.ppt

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

1、5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法15.1数组的类型定义ADTArray{数据对象：D＝{

2、ji=0,...,bi-1,i=1,2,..,nn称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标}数据关系：R＝{R1,R2,...,Rn}Ri＝{

3、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADT

4、Array基本操作:2二维数组的定义:数据对象:D={aij

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

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

7、0≤i≤b1-1,0≤j≤b2-2}3基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,inde

8、xn)45.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先):PASCAL、C;2)以列序为主序(高下标优先):FORTRAN、VB;5例如：称为基地址或基址。以“行序为主序”的存储映象二维数组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

9、6推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1

10、a22a21a1n…….a12a1101n-1m*n-1n7例5.1对二维数组floata[5][4]计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a[3][2]的内存地址。解：由于C语言中数组的行、列下界均为0,该数组行上界为5-1=4,列上界为4-l=3,所以该数组的元素数目共有(4-0+1)*(3-0+1)=5*4=20个。又由于C语言采用行序为主序的存储方式,则有：LOC(a3,2)=LOC(a0,0)+(i*n

11、+j)*k=2000+(3*4+2)*4=20568列优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元LOC(j,k)=a+(k*n+j)*l按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l9#defineMAX_ARRAY_DIM8//

12、假设最大维数为8typedefstruct{ELemType*base;//数组元素基址intdim;//数组维数int*bound;//数组各维长度信息保存区基址int*constants;//数组映像函数常量的基址}Array;即Ci信息保存区数组的基本操作函数说明（有5个）N维数组的顺序存储表示10StatusInitArray(Array&A,intdim,…);StatusDestroyArray(Array&A);StatusLocate(ArrayA,va_listap,int&o

13、ff);StatusValue(ArrayA,ElemType&e,…);StatusAssign(Array&A,ElemTypee,…);数组的基本操作函数说明（5个）11数组基址指针各维长度保存区指针映像函数保存区指针StatusDestroyArray(Array&A){//销毁数组Aif(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;i