[信息与通信]数组

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

数组前面讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。接下来讨论的数据结构——数组可以看成是特殊的线性表，其特殊性在于，表中的数据元素本身也是一种数据结构。 一、一维数组一维数组（Array）是n(n≥1)个相同类型数据元素a0,a1,…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。由此可见，一维数组可以看成是一个线性表或一个向量，一维数组的定义类似于采用顺序存储的线性表。数组的定义一维数组中任一数据元素的存储地址可直接计算得到，因此，一维数组是一种随机存储结构对于一维数组，一旦a0的存储地址Loc(a0)确定，若每个数据元素占用L个存储单元，则任一数据元素ai的存储地址Loc(ai)可由以下公式求出：Loc(ai)=Loc(a0)+i*L 二、二维数组：二维数组可以看成是一维数组的推广。设A是一个有m行、n列的二维数组，则A可以表示为： 显然，在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个直接前驱和两个直接后继（边界除外）。 二维数组可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。行向量形式：把每一行看成是一个数据元素。 二维数组可以看作“数据元素是一维数组”的一维数组。列向量形式：把每一列看成是一个数据元素 三、多维数组：同理，三维数组中的数据元素（边界除外）最多可有三个直接前驱和三个直接后继。可以把三维以上的数组称为多维数组，多维数组中的数据元素（边界除外）可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。 数组具有以下性质：1.数组中的数据元素数目固定，一旦定义了一个数组，其数据元素数目不再有增减变化；2.数组中的每个数据元素具有相同的数据类型；3.数组中的每个数据元素都和一组唯一的下标对应4.数组是一种随机存取结构，可随机存取数组中的任意数据元素。 数组的顺序表示和实现由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，适合采用顺序存储结构表示数组。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。由于存储单元是一维的结构，而二维数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。两种顺序存储方式：以行序为主序（行优先顺序）以列序为主序（列优先顺序） 一、以行序为主序：存放规则：行优先顺序也称为低下标优先或右边下标优先于左边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……例如，对二维数组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-1 2．地址计算假设二维数组Am×n每个元素占L个字节，元素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，可以按如下的形式存放到内存：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-1 2．地址计算与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素aij的地址。对二维数组有：LOC(aij)=LOC(a00)+(j×m+i)×L 例1：对C语言中的二维数组A[5][4]，计算：1)数组A中的元素数目；2)若数组A的起始地址为2000，且每个数组元素长度为32位（即4个字节），求数组元素A[3][2]的内存地址。解：1）该数组的元素数目共有5*4=20个。2）由于C语言中数组的行、列下界均为0，该数组行下标为04，列下标为03，并采用行序为主序的存储方式，有：LOC(a32)=LOC(a00)+(i*n+j)*L=2000+(3*4+2)*4=2056 例2：二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为。A.SA+141B.SA+180C.SA+222D.SA+225解：LOC(a47)=LOC(a00)+(j*m+i)*L=SA+(7*8+4)*3=SA+180 例3：一个二维数组A10*10以按行排列的顺序存放在一个大小为100的一维数组a[100]中，写算法将该二维数组转置，转置后仍占用原来的一维数组a[100]。voidconvert(inta[100]){//定义转置数组的函数for(i=0;i<10;i++)//行列互换for(j=i+1;j<10;j++){t=a[i*10+j];a[i*10+j]=a[j*10+i];a[j*10+i]=t;}} 例4：对于二维数组A[0..2][0..5]，当按行优先顺序存储时，元素A[2][3]是第几个元素？当按列优先顺序存储时，元素A[2][4]是第几个元素？解：m=3,n=6当按行优先顺序存储时，元素A[2][3]的序号为：1+i*n+j=1+2*6+3=16其中1表示元素A[0][0]当按列优先顺序存储时，元素A[2][4]的序号为：1+j*m+i=1+4*3+2=15 矩阵的压缩存储在矩阵中，常常有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。下面分别讨论它们的压缩存储。 一、特殊矩阵1.对称矩阵若一个n阶方阵A中元素满足下列条件：aij=aji其中0≤i,j≤n-1则称A为对称矩阵。 为节约存储空间，只存储对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。即为每一对对称元素分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。不失一般性，我们可以行序为主序存储其下三角(包括对角线)中的元素。saa00a10a11a20a21a22a30a31a32……an-1n-1012345678n(n+1)/2-1 若i≥j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）共有1+2+…+i=i*(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,…,ai,j-1），因此aij之前共有k个元素：k=i*(i+1)/2+ji≥j,0≤k＜n(n+1)/2-1若i