数据结构课件数组 和广 义表.ppt

《数据结构课件数组 和广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构第五章数组和广义表7/22/2021第五章数组5.1数组的类型定义数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。例如，二维数组：a11a12…a1na21a22…a2n…………am1am2…amnAmn=5.1数组的类型定义可以看成是由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。在C语言中，一个二维数组类型可以定义为：typedefelemtypearray2[m][n];等价于：typedefelemtypearray1[n];ty

2、pedefarray1array2[m];数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,ji,...jn

3、ji=0,...,bi-1,i=1,2,..,n,n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1...,jn∈ElemSet}数据关系：R＝{R1,R2,...,Rn}Ri＝{

4、j1,...,ji+1,...,jn>

5、0jkbk-1,1kn且ki,0jibi-2,aj1,...,ji,...,jn,aj1,...ji+1,...,jn∈D,i=2,...,n}5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为

6、元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。}ADTArray5.2数组的顺序表示和实现通常有两种顺序存储方式：类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的结构,而存储空间是一个一维的结构。⑴行优先顺序——将数组元素按行排列，第i+1个行向量

7、紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C语言中,数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。5.2数组的顺序表示和实现

8、通常有两种顺序存储方式：以上规则可以推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。5.2数组的顺序表示和实现例如，二维数组Amn按“行优先顺序”存储

9、在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1)×n+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p

10、+(k-1)]*d5.2数组的顺序表示和实现上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组