资源描述:
《数组的顺序存储结构》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第五章数组引言几乎所有的计算机高级语言都把数组类型设定为基本的数据类型,但并非所有的高级语言均允许对数组进行一般性的常规操作;同时,对于特殊数组(如稀疏矩阵、对称矩阵等)一般高级语言也没有提供其压缩存储方法及其在压缩存储方法下的数组的相关操作。为此,在对数组操作有特殊要求的情况下,有必要讨论数组这种特殊的数据结构类型的存储方法及其操作的实现。5.1数组(Array)的定义本节主要讨论数组的逻辑定义(ADT定义)及数组在计算机中的顺序存储结构的实现原理。5.1.1二维数组的ADT定义ADTArray_2{D={ai,j
2、ai,j∈ElemSet,0≤i≤b1-1,0≤j≤b
3、2-1}R={R1,R2},其中R1和R2如下:R1={
4、ai,j,ai+1,j∈D,0≤i≤b1-2,0≤j≤b2-1}R2={
5、ai,j,ai,j+1∈D,0≤i≤b1-1,0≤j≤b2-2}基本操作P如下:InitArray(&A,b1,b2);即根据给定行数b1与列数b2为矩阵A做初始化DestroyArray(&A);删除矩阵AValueArray(A,&e,index1,index2);取指定位置上的值送eAssignArray(&A,e,index1,index2);将e的值送指定位置}ADTArray_2
6、R1称之为“行关系”R2称之为“列关系”5.2二维数组的顺序存储结构a0,0a0,1a0,2…………………..a0,b2-1a1,0a1,1a1,2…………………..a1,b2-1a2,0a2,1a2,2…………………..a2,b2-1ab1-1,0ab1-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)=
7、LOC(0,0)+(i*b2+j)*La0,0a0,1a0,2…………………..a0,b2-1a1,0a1,1a1,2…………………..a1,b2-1a2,0a2,1a2,2…………………..a2,b2-1ab1-1,0ab1-1,1…………………….ab1-1,b2-1二维数组的一般形式::以列顺序为主存放二维数组a0,0a1,0a2,0......ab1-1,0a0,1a1,1a2,1......ai,j......ab1-1,b2-15.2二维数组的顺序存储结构若一个ai,j占用L个存储单元,则以列序为主序的顺序存储结构下ai,j的地址计算公式:LOC(i,j)=L
8、OC(0,0)+(j*b1+i)*L由于顺序存储结构下数组的基本操作的实现方法较为简单,故在此不做深入讨论。作业:1.设一个系统中二维数组采用行序为主的顺序存储结构存储,已知二维数组A[0..9][0..7]中每个数据元素占用4个存储单元,且第一个数据元素的存储首地址为1000,求A[4][5]的存储地址。2.试分别编程实现求“两矩阵相加”和“两矩阵相乘”的函数子程序,并编写主程序对两函数进行验证。(提示:先定义数组顺序存储结构的基本数据类型,并设法分别实现InitArray(&A,b1,b2);ValueArray(A,&e,index1,index2);AssignA
9、rray(&A,e,index1,index2);然后再编程实现“矩阵相加”和“矩阵相乘”;最后在编写main{}进行验证)。END返回