数组的定义.ppt
《数组的定义.ppt》由会员分享,可在线阅读,更多相关《数组的定义.ppt(36页珍藏版)》请在三一办公上搜索。
1、5.1 数组的定义,一、数组的定义数组可看成是一种特殊的线性表,其特殊在于,线性表中的数据元素本身也是一个数据结构。数组是由下标和值组成的序对的有限集合。数组中每组有定义的下标,都存在一个与其对应的值,这个值称为数组元素。即数组中的每个数据元素都对应一组下标(j1,j2,jn),每个下标的取值范围是0jibi-1,bi称为第i维的长度(i=1,2,n)。当n=1时,n维数组就蜕化为定长的线性表;反之,n维数组可以看成是线性表的推广。,例如,对于如下形式的m*n阶矩阵,可以用二维数组表示:,二维数组A还可以看成一个线性表:A=(a0,a1,ap)(p=m-1或n-1)其中,每个数据元素aj是一个
2、列向量形式的线性表:aj=(a0,j,a1,j,am-1,j)(0 jn-1)或者每个数据元素是一个行向量形式的线性表:ai=(ai,0,ai,1,ai,n-1)(0 im-1),Amn=,二、数组的基本操作,1.初始化InitArray(A,n,bound1,boundn)如果维数n和各维长度合法,则构造相应数组A,并且返回12.销毁Destroyarray(A)销毁已存在的数组A3.取值Getarray(A,e,index1,indexn)如果各下标不超界,则e被赋值为所指定的A的元素值,并且返回1 4.赋值Assign(A,e,index1,indexn)如果各下标不超界,则e赋值给所指
3、定的A的元素值,并且返回1,5.2 数组的顺序存储结构,由于数组一般不作插入或删除操作,即一旦数组建立,结构中的数据元素个数和元素之间的关系就不再发生变动。因此数组采用顺序结构储存。对于二维数组可以有两种顺序存储方式:一种是以行序为主序的存储方式,另一种是以列序为主序的存储方式。在Basic,Pascal,C等语言中,用的是以行序为主序的存储结构,而在Fortran语言中,用的是以列序为主序的存储结构。,按行序为主序存放,0,1,n-1,m*n-1,n,Loc(aij)=Loc(a00)+(in+j)L,2n-1,按列序为主序存放,0,1,m-1,m*n-1,m,Loc(aij)=Loc(a0
4、0)+(jm+i)L,2m-1,例如,假设有二维数组AM,N,设A0,0在644处,A2,2 在676处。每个元素占一个存储空间,则A4,5的地址为多少?以行序为主序存储。,同理,可以推出n维数组的数据元素存储位置的计算公式:Loc(aj1,j2,jn)=Loc(a0,0,0)+(b2bnj1+b3bnj2+bnjn-1+jn)L=Loc(a0,0,0)+(+jn)L,矩阵是许多科学与工程计算中经常遇到的研究对象。在某些矩阵中,往往会出现许多值相同的元素或零元素,为了节省存储空间,可对这类矩阵进行压缩存储。压缩存储的原则是:对多个值相同的元素只分配一个存储空间,对零元不分配空间。我们把相同的元
5、素或零元素在矩阵中的有一定的规律分布称为特殊矩阵,如果矩阵中零元素占绝大部分的称为稀疏矩阵。,5.3 矩阵的压缩存储,5.3.1 特殊矩阵的压缩存储,一、对称矩阵在一个n阶方阵A中,若元素满足下述性质:aij=aji,0i,jn-1,则称A为对称矩阵。对称矩阵中的元素关于主对角线对称,故只要存储矩阵中上三角或下三角中的元素,让每两个对称的元素共享一个存储空间,这样,能节约近一半的存储空间。不失一般性,我们按“行优先顺序”存储主对角线(包括对角线)以下的元素。在这个下三角矩阵中,第i行恰有i+1个元素,元素总数为:n(n+1)/2.,若ij,则ai j在下三角形中。ai j之前的i行(从第0行到
6、第i-1行)一共有1+2+i=i(i+1)/2个元素,在第i+1行上,ai j之前恰有j个元素(即ai0,ai1,ai,j-1),因此有:i(i+1)/2+j 0k n(n+1)/2-1 若ij,则aij是在上三角矩阵中。因为aij=aji,所以只要交换上述对应关系式中的i和j即可得到:j(j+1)/2+i 0 k n(n+1)/2-1,二、三角阵以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵它的下三角(不包括主对角线)中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数。在大多数情况下,三角矩阵常数为零。,Loc(aij)=Loc(a00)+i(i+1)/2+j*L,三、
7、对角矩阵如果矩阵中的所有的非零元素都集中在以主对角线为中心的带状区域则称为对角矩阵。常见的三对角矩阵,可按行的顺序压缩存储。,5.3.2 稀疏矩阵的压缩存储,矩阵中非零元素的个数远远小于矩阵元素的总数,这样的矩阵称为稀疏矩阵。假设在m*n的矩阵中,有t个元素不为零,令=t/m*n,则称为矩阵的稀疏因子。通常认为0.05时,该矩阵为稀疏矩阵。,一、三元组表表示法 在存储稀疏矩阵时,为了节省存储单元,很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须同时记下它所在的行和列的位置(i,j)。所以一个三元组(i,j,v)唯一确定了矩阵A的一个非零元。其
8、中v中存放非零元素的数值。因此,稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。以行优先的顺序将稀疏矩阵中的非零元素以三元组形式存放在一个数组中形成了三元组表。也可把三元组表看成一个线性表,线性表的每个结点对应稀疏矩阵的一个非零元素,这个线性表用顺序的方式存储在连续的存储区。,0 8 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 7 0 0 0 0 2 0 0 0 0 6 0 0 0 9 0 0 0 0,A=,例如,将矩阵A转化为三元组表的形式。,转化后的三元组表形式如下:(0,1,8)(0,4,4),(2,3,5),(3,2,7),(4,0,2),(4
9、,5,6),(5,2,9)加上(6,7)这一对行、列值便可作为矩阵A的另一种描述。,#define Maxsize 255typedef structint i,j;datatype v;Triple;typedef structTriple dataMaxsize;int mu,nu,tu;TsMatrix;,稀疏矩阵的三元组表存储表示的定义:,void CreatSMatrix(int A1,TsMatrix*A)int col,row,k;k=0;for(row=0;rowdatak.i=row;A-datak.j=col;A-datak.v=A1rowcol;k+;A-mu=m;A-n
10、u=n;A-tu=k;,算法4.6 首先我们来建立一个三元组表:,/m,n为要转换矩阵的行列数,定义为全局变量,在过程中直接使用,A=,B=,求转置矩阵:转置是一种简单的矩阵运算。对于一个mn的矩阵A,它的转置B是一个nm的矩阵,且aij=bji,0im,0jn,即A的行是B的列,A的列是B的行。,/其时间复杂度为0(numu),for(col=0;coln;col+)for(row=0;rowm;row+)bcolrow=arowcol;,如何将一个三元组进行转置?将三元组A转置为B,就是将A的三元组表a.data置换为表B的三元组表b.data,如果只是简单地交换a.data中i和j的内容
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 定义
链接地址:https://www.31ppt.com/p-5361470.html