数据结构(严蔚敏)C语言版课件第5章(精品·公开课件).ppt

第五章 数组和广义表 ;【课前思考】;【学习目标】;【重点和难点】;【学习指南】;5.1 数组的类型定义;一、数组的概念 ;例如，设A是一个有m行n列的二维数组，则A可以表示为：;图5.2 矩阵Am×n看成n个列向量的线性表 ;图5.3 矩阵Am×n看成m个行向量的线性表 ; 以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。 例如二维数组A3×4，它有3行、4列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：  (1） 获得特定位置的元素值；  (2） 修改特定位置的元素值。 ;数组的抽象类型定义;二维数组的定义:;基本操作：; 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。;5.2 数组的顺序表示和实现;一、 行优先顺序;因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。 ;二、 列优先顺序 ; 因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。; 三、3维数组存储实例 假设有一个3×4×2的三维数组A ，共有24个元素，其逻辑结构如图5.4所示。 ; 三维数组元素的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A3×4×2（下标从1开始）采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为： a111，a112，a121，a122， …，a331，a332，a341，a342 采用以列为主序的方法存放， 即纵下标变化最慢， 行下标变化最快， 则顺序为：  a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342 ; 以上的存放规则可推广到多维数组的情况。总之，知道了多维数组的维数，以及每维的上下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标， 可以计算出其在存储器中的位置。因此，数组的顺序存储是一种随机存取的结构。  四、多维数组地址计算 以二维数组Am×n为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc［1, 1］，求任意元素aij的地址。aij是排在第i行，第j列，并且前面的第i-1行有n×（i-1）个元素，第ｉ行第j个元素前面还有ｊ-１个元素。由此得到如下地址计算公式：  Loc［i, j］=Loc［1, 1］+n×(i-1)+(j-1) ; 根据计算公式，可以方便地求得aij的地址是Loc［i, j］。如果每个元素占size个存储单元，则任意元素aij的地址计算公式为： Loc［i, j］=Loc［1, 1］ + (n×(i-1)+j-1)×size 三维数组A（1..r ,