最新数组和广义表概要教学讲义PPT.ppt

《最新数组和广义表概要教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组和广义表概要数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的所有或部分元素本身也是一种线性表。由于数组中各元素具有统一的类型，并且数组元素的下标具有固定的上界和下界，因此，数组的处理比其它复杂的数据结构较为简单。多维数组是向量的推广。例如，二维数组：5.1数组的定义二维数组可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。同样，可把三维数组看成是一个线性表，表中每一个数据元素为一个二维数组。依次类推，可把n维数组看成是一个线性表，表中每一个数据元素是一个n-1维数组。数组的运算：数组一旦被定义，它的维数和维界就不再改变

2、。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作，即给定一组下标，存取或修改相应的数组元素。5.1数组的定义以上规则推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左的下标；3、n维数组按上述两种方式顺序存储的数组，只要知道开始元素的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。列优先顺序与此相反，先排最左的下标，从左到右，最后排最右的

3、下标。例如，二维数组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(aijk)=LOC(a111)+[(i-1)*n*p+(

4、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语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*

5、(d2+1)+j)*d4、地址公式在高级语言编制程序时，将一个矩阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现大量的零元素的情况下，实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵的存储会造成极大的浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。5.3矩阵的压缩存储压缩存储：为多个值相同的非零元素只分配一个存储空间；对零元素不分配空间。假若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。1、对称矩阵5.3.1特殊矩阵在一个n阶方阵A中，若元素满足下述性质

6、：aij=aji0≦i,j≦n-1则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：a00a01……….a0n-1a10a11……….a1n-1an-10an-11……..an-1n-1………………….a00a10a11a20a21a22………………..an-10an-11an-12…an-1n-1a00a01….……..a0n-1a10a11…….

7、.…….a1n-1an-10an-11……..an-1n-1………………….对称矩阵的下三角在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2。这样可将n2个压缩到n(n+1)/2个元的空间中。因此，可以按将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，必须在aij和sa[k]之间找一个对应关系。1、对称矩阵若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1

8、,ai2,…,aij-1），因此有：1、对称矩阵k=i*(i+1)/2+j0≦k