第5章(数组和广义表)概要ppt课件.ppt

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

1、第5章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的所有或部分元素本身也是一种线性表。由于数组中各元素具有统一的类型，并且数组元素的下标具有固定的上界和下界，因此，数组的处理比其它复杂的数据结构较为简单。多维数组是向量的推广。例如，二维数组：5.1数组的定义二维数组可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。同样，可把三维数组看成是一个线性表，表中每一个数据元

2、素为一个二维数组。依次类推，可把n维数组看成是一个线性表，表中每一个数据元素是一个n-1维数组。数组的运算：数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作，即给定一组下标，存取或修改相应的数组元素。5.1数组的定义1、顺序存储结构5.2数组的顺序表示和实现用一组地址连续的存储单元依次存放数组的数据元素，称为数组的顺序存储结构。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。由于对数组一般

3、不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储结构来表示数组。通常有两种顺序存储方式：2、顺序存储方式⑴行优先顺序——将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量之后。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2,…,amn在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。以二维数组为例，按列

4、优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……,a1n,a2n,…,amn在FORTRAN语言中，数组就是按列优先顺序存储的。a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l以行序为主序存放amn……am2am1………a2n……a22a21a1n……a12a1101n-1m*n-1n以列序为主序存放01m-1m*n-1mamn……a2na1n………am2……a22a12am1……a2

5、1a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l以上规则推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左的下标；3、n维数组按上述两种方式顺序存储的数组，只要知道开始元素的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。列优先顺序

6、与此相反，先排最左的下标，从左到右，最后排最右的下标。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。4、地址公式元素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同样，三维数组Amnp按“行优先顺序”存储，其地址计算函数为：LOC(

7、aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d上述讨论均是假设数组各维的下界是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语言中，二维

8、数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d4、地址公式在高级语言编制程序时，将一个矩阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现大量的零元素的情况