资源描述：
《数据结构 数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、课前导学5.1数组的定义5.2数组顺序存储的表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构第五章数组和广义表【学习目标】理解数组类型的特点,掌握数组在“以行为主”的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；掌握广义表的结构特点及其存储表示方法。【重点和难点】数组类型的定义及存储位置计算【知识点】数组、特殊矩阵、压缩存储、广义表【课前思考】为什么顺序表以及其它线性结构的顺序存储结构都可以用"一维数组"来描述？因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。5.1数组的定义1.基本概念数组：按一定格式排列起来的一列同一属性的项目,是相同类
2、型的数据元素的集合。有一维数组A[5]、二维数组A[5][5]、三维数组A[5][5][5]、多维数组等。二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。数组的逻辑结构：一维数组是线性结构。多维数组属于非线性结构。但数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。2.数组的抽象数据类型ADTArray{数据对象：D＝{aj1j2…jn
3、ji=0,...,bi-1,i=1,2,..,n, n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2…jn∈ElemSet}数据关系：R＝{R1,R2,...,Rn
4、}Ri＝{
5、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。Ass
6、ign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。}ADTArray5.2数组顺序存储的表示和实现数组的存储结构：由于数组一旦建立，其维数和维界就确定了，则结构中的数据元素个数和元素之间的关系就不再发生变动，故一般采用顺序存储结构。数组是一种随机存储结构。由于计算机中的存储单元是一维结构，数组是多维结构，用一维的连续单元存放数组时，按存放次序的不同有下列不同的存放形式。按行优先存放按列优先存放按列序为主序存放01m-1m*n-1mamn……..a2na1n……….a
7、m2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*la11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n数组元素存储位置的计算公式◆按行优先顺序存放（以二维数组、下标从0开始为例）元素aij的存储地址为：Lo
8、c（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//标准头文件，提供宏va_start、va_arg和va_end，用于存取变长参数表#defineMAX_ARRAY_DIM8//假设数组维
9、数的最大值为8typedefstruct{ElemType*base;//数组元素的基址，由InitArray分配intdim;//数组维数int*bounds;//数组维界基址，由InitArray分配int*constants;//数组映象函数常量基址，由InitArray分配}Array;数组的顺序存储结构图示basedimboundsconstantsElemTypeintintArray3a231.
