数据结构-第五章数组和广义表

《数据结构-第五章数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表5.1数组的定义和运算5.2数组的顺序存储和实现5.3特殊矩阵的压缩存储5.3.1三角矩阵5.3.2带状矩阵5.3.3稀疏矩阵5.4广义表5.1数组的定义和运算数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：Am×n=a12a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amnAm×n=a12a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amnA

2、=（12┅j┅n)我们可以把二维数组看成一个线性表：A=(12…j…n)，其中j（1≤j≤n）本身也是一个线性表，称为列向量。矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j,…,amj)Am×n=a12a12…a1j…a1na21a22…a2j…a2n┇┇ai1ai2…aij…ain┇┇am1am2…amj…amnB‖12┇i┇m我们还可以将数组Am×n看成另外一个线性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一个线性表，称为行向量，即：I=（ai1，ai2，…，aij，…，

3、ain）。上面二维数组的例子，介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这个性质，使得对数组的操作不象对线性表的操作那样，可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：（1）获得特定位置的元素值；（2）修改特定位置的元素值。数组的抽象数据类型定义（ADTArray）数据对象：D={aj1j2…jn

4、n>0，称为数组的维数，ji是数组的第i维下标，1≤ji≤bi，bi为数组第i维的长度，aj1j2…jn∈ElementSet}数据关系：R={R1,R2,…,Rn}Ri={

5、，aj1…ji+1…jn>

6、1≤jk≤bk，1≤k≤n且k≠i，1≤ji≤bi-1，aj1…ji…jn，aj1…ji+1…jn∈D，i=1，…，n}基本操作：（1）InitArray(A,n,bound1,…,boundn)：若维数n和各维的长度合法，则构造相应的数组A，并返回TRUE；（2）DestroyArray（A）：销毁数组A；（3）GetValue（A，e,index1,…,indexn）：若下标合法，用e返回数组A中由index1,…,indexn所指定的元素的值。（4）SetValue（A，e，index1,…,indexn）：

7、若下标合法，则将数组A中由index1,…,indexn所指定的元素的值置为e。注意：这里定义的数组下标是从1开始，与C语言的数组略有不同。5.2数组的顺序存储和实现对于数组A，一旦给定其维数n及各维长度bi（1≤i≤n），则该数组中元素的个数是固定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和PASCAL语言都是以行序为主。另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主。对于二维数组Amxn以行

8、为主的存储序列为：a11,a12,…a1n,a21,a22,…,a2n,……,am1,am2,…,amn以列为主存储序列为：a11,a21,…am1,a12,a22,…,am2,……,a1n,a2n,…,amn假设有一个3×4×2的三维数组A，其逻辑结构图为：列行纵以二维数组Amn为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc[1,1]求任意元素aij的地址，可由如下计算公式得到：Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)如果每个元素占size个存储单元，则任意元素aij

9、的地址计算公式为：Loc[i,j]=Loc[1,1]+(n×(i-1)+j-1)×size三维数组A（1..r,1..m,1..n）可以看成是r个m×n的二维数组，如下图所示：假定每个元素占一个存储单元，采用以行为主序的方法存放，首元素a111的地址为Loc[1,1,1]，ai11的地址为Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n，那么求任意元素aijk的地址计算公式为：Loc[i,j,k]=Loc[1,1,1]+(i-1)*m*n+(j-1)*n+(k-1)其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。如果将三维数组推广到一般

10、情况，即：用j1，j2，j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1，c2，c3，上限分别为d1，d2，d3，每个元素占一个存储单元。则三维数组中任