《数据结构 数组和广义表》由会员分享，可在线阅读，更多相关《数据结构 数组和广义表（60页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表华侨大学计算机学院 谢晓东 XiaodongX内容简介l5.1 数组的定义和运算l5.2 数组的顺序存储和实现l5.3 特殊矩阵的压缩存储 l5.4 广义表 5.1数组n数组是一种人们非常熟悉的数据结构， 几乎所有的程序设计语言都支持这种数 据结构或将这种数据结构设定为语言的 固有类型。n数组这种数据结构可以看成是线性表的 推广。 5.1数组的定义n数组是一组偶对(下标值，数据元素值)的集合。在数组 中，对于一组有意义的下标，都存在一个与其对应的值 。一维数组对应着一个下标值，二维数组对应着两个下 标值，如此类推。n数组是由n(n1)个具有相同数据类型的数据元素a1，a2 ，an
2、组成的有序序列，且该序列必须存储在一块地址 连续的存储单元中。n数组中的数据元素具有相同数据类型。n数组是一种随机存取结构，给定一组下标，就可以 访问与其对应的数据元素。n数组中的数据元素个数是固定的。5.1.1二维数组示意图图5.1 Amn的二维数组 5.1.1数组的抽象数据类型定义 ADT Array 数据对象：D = aj1j2jn | n0称为数组的维数，ji= 0,1,bi-1 ；i=1,2, ,n ; bi是数组第i维的长度，ji是数 组元素第i维的下标，aj1j2jnElemSet 数据关系：R = R1, R2, , RnRi=|0jkbk-1 ， 1kn且ki，0jibi-2
3、， aj1j2 ji+1jnD 基本操作： ADT Array5.1.1数组在维上的约束n由数组定义知，n维数组中有b1b2 bn个数据元 素，每个数据元素都受到n维关系的约束。n 以二维数组为例，将二维数组看成是一个定长的线性 表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则A=(1，2，p) (p=m或n)其中每个数据元素j是一个列向量(线性表) ：j =(a1j ，a2j ，amj) 1jn或是一个行向量：i =(ai1 ，ai2 ，ain) 1im图5.2 矩阵Amn看成n个列向量的线性表 图5.3 矩阵Amn看成m个行向量的线性表 5.1.1数组的操作n数组是一组
4、有固定个数的元素的集合。即，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。 由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类： n(1) 获得特定位置的元素值； n(2) 修改特定位置的元素值。 5.1.1数组的基本操作n（1） InitArray(A, n, bound1, , boundn)： 若维数n 和各维的长度合法，则构造相应的数组A，并返回 TRUE。n（2） DestroyArray（A）： 销毁数组A。n（3） GetValue（A，e, index1, , indexn）： 若下标
5、 合法，则用e返回数组A中由index1, , indexn所指定的 元素的值。 n（4） SetValue（A，e，index1, , indexn）： 若下标 合法，则将数组A中由index1, , indexn所指定的元素 的值置为e。 5.2 数组的顺序表示和实现n数组一般不做插入和删除操作，也就是说，数 组一旦建立，结构中的元素个数和元素间的关系 就不再发生变化。因此，一般都是采用顺序存储 的方法来表示数组。n问题：计算机的内存结构是一维(线性)地址结 构，对于多维数组，将其存放(映射)到内存一维 结构时，有个次序约定问题。即必须按某种次序 将数组元素排成一列序列，然后将这个线性序列
6、 存放到内存中。5.2.1两种存储顺序n数组的顺序存储结构有两种：一种是按行序存储，如 高级语言BASIC、 COBOL和PASCAL语言都是以行序为 主；另一种是按列序存储，如高级语言中的FORTRAN 语言就是以列序为主显然，二维数组Amn以行为主的 存储序列为： na11, a12, ，a1n, a21, a22, , a2n, , am1, am2, , amnn而以列为主的存储序列为： na11, a21, ，am1，a12, a22, , am2, , a1n, a2n, , amn图5-4 二维数组及其顺序存储图例形式a11 a12 a1na21 a22 a2n am1 am2
7、amnA=(a) 二维数组的表示形式(b) 行优先顺序存储(c) 列优先顺序存储a11a12 a1n第1 行a21a22 a2n第2 行am1am2 Amn 第m 行 a11a21 am1第1 列a12a22 am2第2 列a1ma2m amn第n 列5.2.1行优先的内存地址映射设有二维数组A=(aij)mn，若每个元素占用的存储单元数为L(个 )，LOCa11表示元素a11的首地址，即数组的首地址。(1)第1行中的每个元素对应的(首)地址是：LOCa1j=LOCa11+(j-1)L j=1,2, ,n(2)第2行中的每个元素对应的(首)地址是：LOCa2j=LOCa11+nl +(j-1)
8、L j=1,2, ,n (3) 第m行中的每个元素对应的(首)地址是：LOCamj=LOCa11+(m-1)nL+(j-1)L j=1,2, ,n 由此可知，二维数组中任一元素aij的(首)地址是：LOCaij=LOCa11+(i-1)n +(j-1)L (5-1)i=1,2, ,m j=1,2, ,n5.2.1行优先映射的推广根据(5-1)式，对于三维数组A=(aijk)mnp，三维数组中 任一元素aijk的(首)地址是：LOC(aijk)=LOCa111+(i-1)np+(j-1)p+(k- 1)L推而广之，对n维数组A=(aj1j2jn) ，n维数组中任 一元素aj1j2jn的(首)地址
9、是：LOCaj1j2jn=LOCa11 1+(b2bn)(j1-1)+ (b3bn)(j2-1)+ + bn(jn-1-1)+ (jn-1) L 5.2.1列优先的内存地址映射(1)第1列中的每个元素对应的(首)地址是：LOCaj1=LOCa11+(j-1)L j=1,2, ,m(2)第2列中的每个元素对应的(首)地址是：LOCaj2=LOCa11+mk+(j-1)L j=1,2, ,m (3)第n列中的每个元素对应的(首)地址是：LOCajn=LOCa11+ (n-1)mL+(j-1)Lj=1,2, ,m 由此可知，二维数组中任一元素aij的(首)地址是：LOCaij=LOCa11+(i-1
10、)m+(j-1)L i=1,2, ,n j=1,2, ,m 5.3 矩阵的压缩存储 n通常将一个矩阵描述为一个二维数组。n对于高阶矩阵，若其中非零元素呈某种规律分 布(特殊矩阵)或者矩阵中有大量的零元素(稀疏 矩阵)，若仍然用常规方法存储，可能存储重复 的非零元素或零元素，将造成存储空间的大量浪 费。对这类矩阵进行压缩存储：(1)多个相同的非零元素只分配一个存储空间 ；(2)零元素不分配空间。5.3.1特殊矩阵对称矩阵若一个n阶方阵A=(aij)nn中的元素满足性质： aij=aji 1i,jn且ij 则称A为对称矩阵，如图5-5所示。图5-5 对称矩阵示例1 5 1 3 73 0 2 5 1
11、 7 0 6 1 35 0 8 0 0 1 8 9 2 6A=a11a21 a22a31 a32 a33 an1 an2 annA=5.3.1对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，因此，让每 一对对称元素aij和aji(ij)分配一个存储空间，则n2个元素 压缩存储到n(n+1)/2个存储空间。 设用一维数组(向量)sa0n(n+1)/2存储n阶对 称矩阵，不失一般性，假设按“行优先顺序”存储下三角形( 包括对角线)中的元素。 问题：矩阵A中的元素的下标值（i,j）和向量sak 的下标值k之间的对应关系。sa a11 a21 a22 a31 a32 a33 an1 an2 ann
12、K 1 2 3 4 n(n-1)/2 n(n+1)/2图5-6 对称矩阵的压缩存储示例5.3.1对称矩阵的压缩存储（1）若ij：ai j在下三角形中，直接保存在sa中。ai j之前的i-1 行共有元素个数： 1+2+(i-1)=i(i-1)/2 。而在第i行上，ai j之前恰有j-1个元素，因此，元素ai j保存在向量sa中时的下标 值k之间的对应关系是： k=i(i-1)/2+j-1 ij（2）若ij时K=1i,jn (5-6)5.3.3对角矩阵矩阵中，除了主对角线和主对角线上或下方若干条对角 线上的元素之外，其余元素皆为零。即所有的非零元素集 中在以主对角线为了中心的带状区域中，如图5-8
13、所示。 a11 a12 0 . 0a21 a22 a23 0 . 0 0 a32 a33 a34 0 . 0 . 0 . 0 0 an n-1 an n0 . 0 an-1 n-2 an-1 n-1 an-1 nA=图5-8 三对角矩阵示例5.3.3对角矩阵如图5.8的三对角矩阵，非零元素仅出现在主对角(ai i,1in)上、主对角线上的那条对角线(ai i+1,1in-1) 、主对角线下的那条对角线上(ai+1 i,1in-1)。显然，当| i -j |1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件： 当| i-j |(k-1)/2时， ai j=0 。对角矩阵可
14、按行优先顺序或对角线顺序，将其压缩存储 到一个向量中，并且也能找到每个非零元素和向量下标的对应 关系。5.3.3对角矩阵的压缩存储以三对角矩阵为例。当i=1，j=1、2，或 i=n， j=n-1、n或1m= A.n ; B-n= A.m ; B-len= A.len ; if(B-len0) j=1; for(k=1; kdataj.row=A.datai.col B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; 算法的时间耗费主要是在双重循环中，其时间复杂度为O（A.nA.len）, 最坏情况下，当A.len=A.mA.n时，时间复杂度为O（A.mA.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.mA.n）。 5.3.4三元顺序表的转置算法依次按三元组表A的次序进行转置，转置后直接放到三元 组表B的正确位置上。这种
