数据结构_数组.ppt

《数据结构_数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构数组4.1数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单4.1数组的定义多维数组是向量的推广。例如，二维数组：a00a01………a0n-1a10a11………a1n-1……………………am-10am-11…am-1n-1Amn=可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。4.1数组的定义4.2数组的顺序表示和实现由于计算机的内存

2、结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。4.2数组的顺序表示和实现⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，按列优先顺序存储的线性

3、序列为：a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2da1,0a0,0a2,0a2,1a0,1a1,1a1,0a0,0a2,0a0,1a1,1a2,1d例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有i×n个元素，第i行上aij前面又有j个元素，故它前面一共有(i×n+j）个元素，因此，aij的地址计算函数为

4、：LOC(aij)=LOC(a00)+[i*n+j]*d(0≤i

5、道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）①开始结点的存放地址（即基地址）；②维数和每维的上、下界；③每个数组元素所占用的单元数例１：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是多少个字节。答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例２设数组a[０…60,０…70]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,

6、58]的存储地址？答：根据行优先公式LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i

7、.1特殊矩阵5.3数组的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：15137a0050800a10a1118926a20a21a2230251………………..…70613an-10an-11………an-1n-1图5.1对称矩阵若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+I=i

8、(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i(i+1)/2+j0≦k