五章数组广义表章作业课件chap5-2014.pptxVIP

第五章数组和广义表;第五章数组和广义表;5.1数组的定义

数组是我们最熟悉的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。

多维数组是向量的推广。例如，二维数组：

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

既可以看成是由m个行向量组成的向量(行向量形式），也可以看成是n个列向量组成的向量（列向量形式）。

;在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，

typedefelemtypearray2[m][n];

等价于：

typedefelemtypearray1[n];

typedefarray1array2[m];

同理，一个n维数组类型可以定义为其数据元素为

n-1维数组类型的一维数组类型。

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。

抽象数据类型数组的定义参见教材p.90。

;数组的抽象类型定义;二维数组的定义:;基本操作：;InitArray(A,n,bound1,...,boundn)

操作结果：若维数n和各维长度合法，

则构造相应的数组A，并

返回OK。;操作结果：销毁数组A。;Value(A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，

随后是n个下标值。

操作结果：若各下标不超界，则e赋值为

所指定的A的元素值，并返

回OK。;Assign(A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，

随后是n个下标值。

操作结果：若下标不超界，则将e的值赋

给所指定的A的元素，并返回

OK。;第五章数组和广义表;5.2数组的顺序表示和实现;有两种顺序存储方式：

⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。

以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

在PASCAL、C语言中，数组就是按行优先顺序存储的。

⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：

a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm

在FORTRAN语言中，数组就是按列优先顺序存储的。

;15;例如：;17;推广到一般情况，可得到n维数组数据元素存储位置的映象关系;第五章数组和广义表;20;21;5.3.1特殊矩阵

所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。

1、对称矩阵

在一个n阶方阵A中，若元素满足下述性质：

aij=aji0≦i,j≦n-1

则称A为对称矩阵。;23;为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。

若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：

k=i*(i+1)/2+j0≦kn(n+1)/2

若ij，则aij是在上三角矩阵中。因为aij=aji，