数据结构 数组课件.ppt

课前导学 5.1 数组的定义 5.2 数组顺序存储的表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 【学习目标】 理解数组类型的特点, 掌握数组在“以行为主”的存储表示中的地址计算方法； 掌握特殊矩阵的存储压缩表示方法； 掌握广义表的结构特点及其存储表示方法。 【重点和难点】 数组类型的定义及存储位置计算 【知识点】 　　数组、特殊矩阵、压缩存储、广义表 【课前思考】 为什么顺序表以及其它线性结构的顺序存储结构都可以用一维数组来描述？ 　 5.1 数组的定义 1. 基本概念 数组：按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。有一维数组A[5]、二维数组A[5][5]、三维数组A[5][5][5]、多维数组等。 二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。 数组的逻辑结构： 一维数组是线性结构。多维数组属于非线性结构。但数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。 2.数组的抽象数据类型 ADT Array {数据对象：D＝{aj1j2…jn | ji =0,...,bi-1, i=1,2,..,n, n(0)称为数组的维数，bi是数组第i维的长度， ji是数组元素的第i维下标，aj1j2…jn∈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…ji+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 数组顺序存储的表示和实现 数组的存储结构：由于数组一旦建立，其维数和维界就确定了，则结构中的数据元素个数和元素之间的关系就不再发生变动，故一般采用顺序存储结构。 数组是一种随机存储结构。 由于计算机中的存储单元是一维结构，数组是多维结构，用一维的连续单元存放数组时，按存放次序的不同有下列不同的存放形式。 按行优先存放 按列优先存放 数组元素存储位置的计算公式 ◆ 按行优先顺序存放（以二维数组、下标从0开始为例）元素aij的存储地址为：Loc（aij）= Loc（a00）+（i* n +j）L （0≤i≤m， 0≤j≤n）(式中：Loc（a00）为元素a00的存储位置，即二维数组的起始存储位置，也称基地址，m为二维数组的总行数，n为总列数，aij代表其中第i行、第j列的那个元素,每个数据元素占L个存储单元)◆ 按列优先顺序存放元素aij的存储地址为：Loc（aij）= Loc（a00）+（j* m +i）L （0≤i≤m， 0≤j≤n） 三维数组的计算 数组顺序存储的表示和实现 #include stdarg.h // 标准头文件，提供宏va_start、va_arg 和va_end，用于存取变长参数表#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为8typedef struct{ ElemType *base; //数组元素的基址，由InitArray分配 int dim; //数组维数 int *bounds; //数组维界基址，由InitArray分配 int *constants; //数组映象函数常量基址，由InitArray分配}Array; 数组的顺序存储结构图示 例: 计算多维数组的地址 已知4维数组: A[3][4][5][6], 求A1241的地址 A1241=A0000+1*5*6*7+2*6*7+4*7+1 A.Constants[3]=1 A.