数组的顺序存储结构.ppt

第五章 数 组 引言 几乎所有的计算机高级语言都把数组类型设 定为基本的数据类型，但并非所有的高级语言均 允许对数组进行一般性的常规操作；同时，对于 特殊数组（如稀疏矩阵、对称矩阵等）一般高级 语言也没有提供其压缩存储方法及其在压缩存储 方法下的数组的相关操作。 为此，在对数组操作有特殊要求的情况下， 有必要讨论数组这种特殊的数据结构类型的存储 方法及其操作的实现。 5.1 数组 ( Array )的定义 本节主要讨论数组的逻辑 定义（ADT定义）及数组在计 算机中的顺序存储结构的实现 原理。 5.1.1 二维数组的ADT定义 ADT Array_2 D=ai,j |ai,jElemSet,0ib1-1, 0jb2-1 R=R1, R2，其中R1和R2如下： R1=|ai,j, ai+1,j D,0ib1-2,0jb2-1 R2=|ai,j, ai,j+1 D,0ib1-1,0jb2-2 基本操作P如下: InitArray( 即根据给定行数b1与列数b2为矩阵A做初始化 DestroyArray ( 删除矩阵A ValueArray (A, 取指定位置上的值送e AssignArray ( 将e的值送指定位置 ADT Array_2 R1称之为“行关系” R2称之为“列关系” 5.2 二维数组的顺序存储结构 a0,0 a0,1 a0,2 a0,b2-1 a1,0 a1,1 a1,2 a1,b2-1 a2,0 a2,1 a2,2 a2,b2-1 ab1-1,0 ab1-1,1 .ab1-1,b2-1 二维数组的一般形式 ： ： 以行顺序为主存放二维数组 a0,0a0,1a0,2 a0,b2-1a1,0a1,1a1,2 ai,j ab1-1,b2-1 若一个ai,j占用L个存储单元，则以行序为主序 的顺序存储结构下ai,j的地址计算公式： LOC(i,j)=LOC(0,0)+ (i*b2+j) *L a0,0 a0,1 a0,2 a0,b2-1 a1,0 a1,1 a1,2 a1,b2-1 a2,0 a2,1 a2,2 a2,b2-1 ab1-1,0 ab1-1,1 .ab1-1,b2-1 二维数组的一般形式 ： ： 以列顺序为主存放二维数组 a0,0a1,0a2,0 ab1-1,0a0,1a1,1a2,1 ai,j ab1-1,b2-1 5.2 二维数组的顺序存储结构 若一个ai,j占用L个存储单元，则以列序为主序 的顺序存储结构下ai,j的地址计算公式： LOC(i,j)=LOC(0,0)+ (j*b1+i) *L 由于顺序存储结构下数组 的基本操作的实现方法较为简 单，故在此不做深入讨论。 作业： 1.设一个系统中二维数组采用行序为主的顺序存储结 构存储，已知二维数组A0907中每个数据元素 占用4个存储单元，且第一个数据元素的存储首地址 为1000，求A45的存储地址。 2.试分别编程实现求“两矩阵相加”和“两矩阵相乘”的 函数子程序，并编写主程序对两函数进行验证。 （提示：先定义数组顺序存储结构的基本数据类型 ，并设法分别实现InitArray( Val