[信息与通信]数组

《[信息与通信]数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组前面讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。接下来讨论的数据结构——数组可以看成是特殊的线性表，其特殊性在于，表中的数据元素本身也是一种数据结构。一、一维数组一维数组（Array）是n(n≥1)个相同类型数据元素a0,a1,…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。由此可见，一维数组可以看成是一个线性表或一个向量，一维数组的定义类似于采用顺序存储的线性表。数组的定义一维数组中任一数据元素的存储地址可直接计算得到，因此，一维数组是一种随机存储结构对于一维数组，一旦a0的存

2、储地址Loc(a0)确定，若每个数据元素占用L个存储单元，则任一数据元素ai的存储地址Loc(ai)可由以下公式求出：Loc(ai)=Loc(a0)+i*L二、二维数组：二维数组可以看成是一维数组的推广。设A是一个有m行、n列的二维数组，则A可以表示为：显然，在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个直接前驱和两个直接后继（边界除外）。二维数组可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。行向量形式：把每一行看成是一个数据元素。二维数组可以看作“数据元素是一维

3、数组”的一维数组。列向量形式：把每一列看成是一个数据元素三、多维数组：同理，三维数组中的数据元素（边界除外）最多可有三个直接前驱和三个直接后继。可以把三维以上的数组称为多维数组，多维数组中的数据元素（边界除外）可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。数组具有以下性质：1.数组中的数据元素数目固定，一旦定义了一个数组，其数据元素数目不再有增减变化；2.数组中的每个数据元素具有相同的数据类型；

4、3.数组中的每个数据元素都和一组唯一的下标对应4.数组是一种随机存取结构，可随机存取数组中的任意数据元素。数组的顺序表示和实现由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，适合采用顺序存储结构表示数组。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。由于存储单元是一维的结构，而二维数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。两种顺序存储方式：以行序为主序（行优先顺序）以列序为主序（列优先顺序）一、以行序为主序：存放规

5、则：行优先顺序也称为低下标优先或右边下标优先于左边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……例如，对二维数组Am×n，可用如下形式存放到内存：a00，a01,…a0n-1，a10，a11，...，a1n-1，…，am-10，am-11，…，am-1n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。a00a01…a0,n-1a10a11…a1,n-1…am-1,0am-1,1…am-1,n-12．地址计算假设二维数组Am×n每个元素占L个字节，元素

6、aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij的前面有i行(0i-1)共i×n个元素，而第i行上aij前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的地址为LOC(a00)，则aij的地址为：LOC(aij)=LOC(a00)+（i×n+j）×L二、以列序为主序：存放规则：列优先顺序也称为高下标优先或左边下标优先于右边下标。具体实现时，按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元素，第三列元素，依次类推……例如，二维数组Am×n，可以按如下的形式存放到内存

7、：a00，a10…，am-10，a01，a11，…，am-11，…，a0m-1，a1m-1，...，am-1n-1。即二维数组按列优先存放到内存后，也变成了一个线性序列（线性表）。a00a10…am-1,0a01a11…am-1,1…a0,n-1a1,n-1…am-1,n-12．地址计算与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素aij的地址。对二维数组有：LOC(aij)=LOC(a00)+(j×m+i)×L例1：对C语言中的二维数组A[5][4]，计算：1)数组A中的元素数目；2)若数组A的起

8、始地址为2000，且每个数组元素长度为32位（即4个字节），求数组元素A[3][2]的内存地址。解：1）该数组的元素数目共有5*4=20个。2）由于C语言中数组的行、列下界均为0，该数组行下标为04，列下标为03，并采用行序为主序