华东理工大学数据结构第5章课件.ppt

数 据 结 构; 第五章 数组和广义表; 5.1 数组的定义 数组可以看作线性表的推广。 表中的数所元素本身也是一种线性表。一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，例如， m行n列二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn ; 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型: typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。; 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。因此，在数组上不能做插入、删除数据元素的操作。在数组中通常做下面两种操作： (1)??? 取值操作：给定一组下标，读其对应的数据元素。 (2)??? 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 ;数组的抽象数据类型的定义： ADT Array { 数据对象：D＝{aj1 ,j2 ,..., ,...jn | ji =0,...,bi -1, i=1,2,..,n, n(0)称为数组的维数， bi 是数组第i维的长度， ji是数组元素的第i维下标， aj1 ,...,j n∈ElemSet } 数据关系：R＝{R1, R2, ..., Rn} Ri＝{aj1 ,...ji ,...jn aj1 ,...,ji +1,...,jn | 0 = jk= bk -1, 1 = k = n 且k != i, 0 = ji = bi -2, aj1 ,...,ji ,...,jn , aj1 ,...j i+1,...,jn∈D, i=2,...,n } ;基本操作： InitArray(A, n, bound1, ..., boundn) 操作结果：若维数n和各维长度合法，则构造相应的 数组A，并返回OK。 DestroyArray(A) 操作结果：销毁数组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。 } ADT Array; 5.2 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式: 以行序为主序：将数组元素按行排列，第i+1个行紧接在第i个行后面。(先行后列、低下标优先);如BASIC、PASCAL、COBOL、C等程序设计语言 以列序为主序：将数组元素按列排列，第j+1个列紧接在第j个列之后，(高下标优先);如FORTRAN语言 ;例如一个2×3二维数组，逻辑结构和内存映象;可知三维数组中：3x2x2 1.以行序为主序(低下标优先); A(0, 0, 0), A(0, 0, 1), A(0, 1, 0), A(0, 1, 1), A(1, 0, 0), A(1, 0,1) , …, A(2, 1, 1) 2. 以列序为主序(高下标优先); A(0, 0, 0), A(1, 0, 0), A(2, 0, 0) A(0, 1, 0), A(1, 1, 0), A(2, 1, 0) A(0, 0, 1), …, A(2, 1, 1);推广到多维数组： 以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。 以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。 ;