数据结构数组

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

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

3、a1,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行一共有in个元素，第i行上aij前面又有j个元素，故它前面一共有(in+j）个元素，因此，aij的地址计算函数为： loc(aloc(aijij)=loc(a)=loc(a0000)+i)+i* *n+jn+j* *d (0imd (0im，

4、 0jn)0jn)注：注：c c语言中数组元素采用行主序的存放方法，即语言中数组元素采用行主序的存放方法，即行优先行优先顺序。顺序。一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 amn=4.2 4.2 数组的顺序表示和实现数组的顺序表示和实现4.2 4.2 数组的顺序表示和实现数组的顺序表示和实现 同样，三维数组aijk按“行优先顺序”存储，其地址计算函数为：loc(aijk)=loc(a000)+inp+

5、jp+kd注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）任一元素可随机存取）开始结点的存放地址（即基地址）；开始结点的存放地址（即基地址）；维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数例：一个二维数组例：一个二维数组a a，行下标的范围是，行下标的范围是1 1到到6 6，列下标的范围是，列下标的范围是0 0到到7 7，每个数，每个数组元素用相邻的组元素用相邻的6 6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节存储，存储器按字节编

6、址。那么，这个数组的体积是 多少个字节。多少个字节。答：答： volume=mvolume=m* *n n* *l=(6-1+1)l=(6-1+1)* *(7- 0 +1)(7- 0 +1)* *6=486=48* *6=2886=288例例 设数组设数组aa60, 60, 7070的基地址为的基地址为20482048，每个元素占，每个元素占2 2个存储单元，个存储单元，若以行序为主序顺序存储，则元素若以行序为主序顺序存储，则元素a32,58a32,58的存储地址？的存储地址？答：根据行优先公式答：根据行优先公式 loc(aij)=loc(a00)+(iloc(aij)=loc(a00)+(i

7、* *n+j)n+j)* *k (0k (0i im，0 0j jn)n)得：得：loc(a32,58)=2048+(32loc(a32,58)=2048+(32* *70+58)70+58)* *2 2664466445.3 5.3 数组的压缩存储数组的压缩存储所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。阵，下面我们讨论几种特殊矩阵的压缩存储。 5.3.1 特殊矩阵特殊矩阵5.3.2 稀疏矩阵稀疏矩阵5.3.1 5.3.1 特殊矩阵特殊矩阵5.3 5.3 数组的压缩存储数组的压缩存储1 1、对

8、称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵a a中，若元素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji （0i,jn-10i,jn-1） 则称则称a a为对称矩阵。如图为对称矩阵。如图5.15.1便是一个便是一个5 5阶对称矩阵。阶对称矩阵。 5.3.1 5.3.1 特殊矩阵特殊矩阵5.3 5.3 数组的压缩存储数组的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空

9、间。不失一般性，我们空间，这样，能节约近一半的存储空间。不失一般性，我们按按“行优先顺序行优先顺序”存储主对角线（包括对角线）以下的元素，存储主对角线（包括对角线）以下的元素，其存储形式如图所示：其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 . 7 0 6 1 3 an-1 0 an-1 1 an-1 n-1 图 5.1 对称矩阵若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i = i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即

10、ai0, ai1, ai2, aij-1），因此有： k=i(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j(j+1)/2+i 0 kn(n+1)/2 令 i=max(i,j)， j=min(i,j)，则k和 i, j的对应关系可统一为： k=i(i+1)/2+j 0 k1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)a是满足下述条件的矩阵： 若i-j(k-1)/2 ， 则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和

11、向量下标的对应关系。 5.3 5.3 数组的压缩存储数组的压缩存储 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1k=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： 5.3 5.3 数组的压缩存储数组的压缩存储 loc(i,j) = loc(0,0)+3i-

12、1+(j-i+1)d = loc(0,0)+(2i+j)d 上例中，a34对应着 a21对应着 sa10k=2i+j=23+4=10sa5k=22+1=5由此，我们称sa0.3n-1是n阶三对角阵的压缩存储表示。5.3 5.3 数组的压缩存储数组的压缩存储5.3 5.3 数组的压缩存储数组的压缩存储5.3.2 5.3.2 稀疏矩阵稀疏矩阵5.3 5.3 数组的压缩存储数组的压缩存储5.3.2 5.3.2 稀疏矩阵稀疏矩阵三元组顺序表三元组顺序表行逻辑链接顺序表行逻辑链接顺序表十字链表十字链表5.3 5.3 数组的压缩存储数组的压缩存储1 1、三元组顺序表、三元组顺序表5.3 5.3 数组的压缩存储数组的压缩存储1 1、三元组顺序表、三元组顺序表5.3 5.3 数组的压缩存储数组的压缩存储1 1、三元组顺序表、三元组顺序表(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 6, 14)(4, 3, 24)(5, 2, 18)(