《数据结构域算法设计-数据结构-清华大学严蔚敏PPT-串》由会员分享，可在线阅读，更多相关《数据结构域算法设计-数据结构-清华大学严蔚敏PPT-串（56页珍藏版）》请在金锄头文库上搜索。
1、第5章 数组和广义表,数组是一种人们非常熟悉的数据结构，几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型。数组这种数据结构可以看成是线性表的推广。 科学计算中涉及到大量的矩阵问题，在程序设计语言中一般都采用数组来存储，被描述成一个二维数组。但当矩阵规模很大且具有特殊结构(对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等)，为减少程序的时间和空间需求，采用自定义的描述方式。 广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。,5.1 数组的定义,数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维
2、数组对应着一个下标值，二维数组对应着两个下标值，如此类推。数组是由n(n1)个具有相同数据类型的数据元素a1，a2，an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。 数组中的数据元素具有相同数据类型。 数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。 数组中的数据元素个数是固定的。,5.1.1 数组的抽象数据类型定义,1 抽象数据类型定义 ADT Array 数据对象：ji= 0,1,bi-1 , 1,2, ,n ; D = aj1j2jn | n0称为数组的维数，bi是数组第i维的长度，ji是数组元素第i维的下标，aj1j2jnElemSet 数据关系：R
3、 = R1, R2, , Rn Ri=|0jkbk-1 ， 1kn且ki，0jibi-2， aj1j2 ji+1jnD 基本操作： ADT Array,由上述定义知，n维数组中有b1b2 bn个数据元素，每个数据元素都受到n维关系的约束。 2 直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则A=(1，2，p) (p=m或n) 其中每个数据元素j是一个列向量(线性表) ：j =(a1j ，a2j ，amj) 1jn 或是一个行向量： i =(ai1 ，ai2 ，ain) 1im 如图5-1所示。,5.2 数组的顺
4、序表示和实现,数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。问题：计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。,通常有两种顺序存储方式 行优先顺序(Row Major Order) ：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。对二维数组，按行优先顺序存储的线性
5、序列为：a11,a12,a1n, a21,a22,a2n , am1,am2,amn PASCAL、C是按行优先顺序存储的，如图5-2(b)示。 列优先顺序(Column Major Order) ：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列为：a11,a21,am1, a12,a22,am2, , an1,an2,anmFORTRAN是按列优先顺序存储的，如图5-2(c)。,设有二维数组A=(aij)mn，若每个元素占用的存储单元数为l(个)，LOCa11表示元素a11的首地址，即数组的首地址。 1 以“行优先顺序”存储 第1行中的
6、每个元素对应的(首)地址是：LOCa1j=LOCa11+(j-1)l j=1,2, ,n (2) 第2行中的每个元素对应的(首)地址是：LOCa2j=LOCa11+nl +(j-1)l j=1,2, ,n 第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, ,n根据(5-1)式，对于三维数组A=(aijk)mnp，若每个元素占用的存储单元数为l(个)，LOCa111表示元素
7、a111的首地址，即数组的首地址。以“行优先顺序”存储在内存中。三维数组中任一元素aijk的(首)地址是：LOC(aijk)=LOCa111+(i-1)np+(j-1)p+(k-1)l (5-2)推而广之，对n维数组A=(aj1j2jn) ，若每个元素占用的存储单元数为l(个)，LOCa11 1表示元素a11 1的首地址。则 以“行优先顺序”存储在内存中。,n维数组中任一元素aj1j2jn的(首)地址是：LOCaj1j2jn=LOCa11 1+(b2bn)(j1-1)+ (b3bn)(j2-1)+ + bn(jn-1-1)+ (jn-1) l (5-3),2 以“列优先顺序”存储 第1列中的每
8、个元素对应的(首)地址是：LOCaj1=LOCa11+(j-1)l j=1,2, ,m (2) 第2列中的每个元素对应的(首)地址是：LOCaj2=LOCa11+ml +(j-1)l j=1,2, ,m 第n列中的每个元素对应的(首)地址是： LOCajn=LOCa11+ (n-1)ml +(j-1)l j=1,2, ,m 由此可知，二维数组中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1)m+(j-1)l (5-1) i=1,2, ,n j=1,2, ,m,5.3 矩阵的压缩存储,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一
9、个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储： 多个相同的非零元素只分配一个存储空间； 零元素不分配空间。,5.3.1 特殊矩阵,特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵。 1 对称矩阵 若一个n阶方阵A=(aij)nn中的元素满足性质： aij=aji 1i,jn且ij 则称A为对称矩阵，如图5-3所示。,对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素aij和aji(ij)分配一
10、个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。不失一般性，假设按“行优先顺序”存储下三角形(包括对角线)中的元素。设用一维数组(向量)sa0n(n+1)/2存储n阶对称矩阵，如图5-4所示。为了便于访问，必须找出矩阵A中的元素的下标值（i,j）和向量sak的下标值k之间的对应关系。,若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若ij：则
11、aij是在上三角矩阵中。因为aij=aji，在向量sa中保存的是aji 。依上述分析可得：k=j(j-1)/2+i-1 i1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件： 当| i-j |(k-1)/2时， ai j=0,对角矩阵可按行优先顺序或对角线顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。仍然以三对角矩阵为例讨论。 当i=1，j=1、2，或i=n， j=n-1、n或 1in-1,j=i-1、i、i+1的元素aij外，其余元素都是0。对这种矩阵，当以按“行优先顺序”存储时， 第1行和第n行是2个非零元素，其余每行的非零元素都要是
12、3个，则需存储的元素个数为3n-2。,如图5-7所示三对角矩阵的压缩存储形式。数组sa中的元素sak与三对角矩阵中的元素aij存在一一对应关系，在aij之前有i-1行,共有3i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：LOCai j =LOCa11 +3i-1+(j-i+1)l =LOCa11+(2i+j)l 上例中，a34对应着sa10 , k=2i+j=23+4=10 称sa03n-2是n阶三对角矩阵A的压缩存储。上述各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关
13、系，通过这个关系，仍能对矩阵的元素进行随机存取。,5.3.2 稀疏矩阵,稀疏矩阵(Sparse Matrix)：对于稀疏矩阵，目前还没有一个确切的定义。设矩阵A是一个nm的矩阵中有s个非零元素，设 =s/(nm)，称为稀疏因子，如果某一矩阵的稀疏因子满足0.05时称为稀疏矩阵，如图5-8所示。,5.3.2.1 稀疏矩阵的压缩存储,对于稀疏矩阵，采用压缩存储方法时，只存储非0元素。必须存储非0元素的行下标值、列下标值、元素值。因此，一个三元组(i, j, aij)唯一确定稀疏矩阵的一个非零元素。如图5-8的稀疏矩阵A的三元组线性表为： ( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) ) 1 三元组顺序表若以行序为主序，稀疏矩阵中所有非0元素的三元组，就可以得构成该稀疏矩阵的一个三元组顺序表。,
