《结构体数组结构体数组.ppt》由会员分享，可在线阅读，更多相关《结构体数组结构体数组.ppt（34页珍藏版）》请在金锄头文库上搜索。
1、计算机软件基础课件计算机软件基础课件 4.1 4.1 数组定义及基本操作数组定义及基本操作 4.2 4.2 数组的存储结构数组的存储结构 4.3 4.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 4.4 4.4 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 4.5 4.5 数组的运算数组的运算 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241 1计算机软件基础课件计算机软件基础课件 数组是我
2、们最常用的一种数据结构，各种计算机语言数组是我们最常用的一种数据结构，各种计算机语言均有此类型均有此类型。例如：顺序表、顺序栈、循环队列等。例如：顺序表、顺序栈、循环队列等。数组的定义：数组的定义： 数组：数组：是（）个相同数据类型的数据元素是（）个相同数据类型的数据元素a0,a1an-1,构成的占用一块连续的内存单元的有限序列。构成的占用一块连续的内存单元的有限序列。数组特点：数组特点： 1. 1.有限个元素的集合；有限个元素的集合； 2. 2.所有元素具有相同的特性；所有元素具有相同的特性； 3. 3.元素名由数组名和下标组成；元素名由数组名和下标组成； 4. 4.下标值与元素对应（代表元
3、素的位置）。下标值与元素对应（代表元素的位置）。4.1 4.1 数组的定义及操作数组的定义及操作Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20242 2计算机软件基础课件计算机软件基础课件 数组数组与与线性表线性表:相同之处相同之处:由若干个相同数据类型的数据元素组由若干个相同数据类型的数据元素组成成.不同之处不同之处: 1.存储单元连续与否存储单元连续与否 2.数据元素在逻辑意义上
4、可分与否数据元素在逻辑意义上可分与否 3.操作不同操作不同。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20243 3计算机软件基础课件计算机软件基础课件. . 数组的逻辑结构数组的逻辑结构 一维数组一维数组（a a0 0,a,a1 1,a,a2 2,a,a3 3,a,an-1n-1）满足）满足线性关系；线性关系； 二维或二维以上数组：（以二维为例）二维或二维以上数组：（以二维为例）A
5、mxn= a a . aa00 a02 . a0n-1 10 11 1n-1.a a a m-10 m-12 m-1n-1看元素看元素a a1111有两个直接前趋有两个直接前趋a a1010和和a a0202两个直接后继两个直接后继a a2121和和a a1212三维数组三维数组: :每个元素有三个直接前趋和三个直接后继每个元素有三个直接前趋和三个直接后继. .可见可见: :数组数组( (除一维数组外除一维数组外) )是一种是一种复杂的非线性数据结构复杂的非线性数据结构. .Evaluation only.Created with Aspose.Slides for .NET 3.5 Clie
6、nt Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20244 4计算机软件基础课件计算机软件基础课件但是但是: :1)1)可将可将Amxn看成由看成由m m个行向量组成的向量个行向量组成的向量, ,即即 Amn= (a00,a01,a0n-1),(a10,a11,a1n-1),(am-10, am-11,am-1n-1) 2)将将Amxn看成由看成由n n个列向量组成的向量个列向量组成的向量, ,即即 Amn=( (a00,a10,am-10),(a01,a11,am-11) (a0n-1,a1n-1,am-
7、1n-1) ) 列向量为线性列向量为线性. .元素元素1 1元素元素2 2元素元素m m看看(ai0,ai1,.ain-1),除除ai0,ain-1 外只有一个直接前趋和一个直接后继外只有一个直接前趋和一个直接后继. .元素元素1 1元素元素2 2元素元素n nEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20245 5计算机软件基础课件计算机软件基础课件 据此据此 数组可看成是线性表的
8、扩展数组可看成是线性表的扩展: :即线性表中的数据元即线性表中的数据元素本身也是一个数据结构素本身也是一个数据结构. . 数组可表示成两类线性表数组可表示成两类线性表: : 1. 1.以行向量做线性表的一个元素以行向量做线性表的一个元素; ; 2. 2.以列向量做线性表的一个元素以列向量做线性表的一个元素.Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20246 6计算机软件基础课件计算
9、机软件基础课件数组抽象数据类型：数组抽象数据类型：数据集合：数据集合：数组的数据集合可表示为数组的数据集合可表示为a a0 0,a,a1 1aan-1n-1, ,每个数据元素的类型每个数据元素的类型为抽象数据类型为抽象数据类型:DataType:DataType（限定顺序存储）（限定顺序存储）数据关系数据关系: :线性关系线性关系. .操作集合：操作集合： 各种高级程序设计语言的操作各不相同，必备的操作有：各种高级程序设计语言的操作各不相同，必备的操作有：（1 1）求数组元素个数）求数组元素个数（2 2）随机取）随机取（3 3）随机存）随机存（4 4）矩阵运算）矩阵运算Evaluation o
10、nly.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20247 7计算机软件基础课件计算机软件基础课件 一般数组一般数组: : ( (以二维数组为例以二维数组为例) ) 多采用顺序存储多采用顺序存储: : (1). (1).按行优先顺序存储按行优先顺序存储 假设：假设：Amn= a00a01a02a0n-1a10a00 a01 a02 a03 a0n-1 a10 a11 a12 a13 a1n-1 am-10 am-
11、11 am-12 am-13 am-1n-1即即 a00,a01,a02a0n-1, a10,a11,.a1n-1 aij的存储地址的存储地址: :am-1 ,04.2 4.2 数组的存储结构数组的存储结构: :Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20248 8计算机软件基础课件计算机软件基础课件 L:为每个元素所占存储单元为每个元素所占存储单元. .Pascal和和C语言中数
12、组存储为此方式语言中数组存储为此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列优先顺序存储列优先顺序存储, ,即即 a00,a10,a20am-10, a01,a11,.am-11 aij存储地址存储地址: : Loc(aij)=Loc(a00)+(j*m+i)*L Fortran语言采用此方法语言采用此方法.a00a10a20am-10a01可见可见: :数组是一种数组是一种随机存储结构随机存储结构. .存取任意元素的时间相等存取任意元素的时间相等Evaluation only.Created with Aspose.Slides for .NET 3.5 Clien
13、t Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20249 9计算机软件基础课件计算机软件基础课件推广推广: :假设假设: :AcAc1 1-d-d1 1cc2 2-d-d2 2 例：二维数组例：二维数组float a43.float a43.计算计算（1 1）数组元素数目？数组元素数目？ （2 2）若数组）若数组Loc(aLoc(a0000)=1000,)=1000,且且L=4,L=4,数组元素数组元素a32a32的的地址地址?(?(按行优先存储按行优先存储) )(1)4*3=12(2)Loc(a32)=L
14、oc(a00)+(i*n+j)*L =1000+(3*3+2)*4 =1044Loc(aij)=Loc(ac1c2)+(i-c1 1)*(d2 2-c2 2+1)+(j-c2 2)*L按行优先顺序存储：按行优先顺序存储：Loc(aij)=Loc(ac1c2)+(j-c2 2)*(d1 1-c1 1+1)+(i-c1 1)*L按列优先顺序存储：按列优先顺序存储：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/
15、20247/24/20241010计算机软件基础课件计算机软件基础课件特殊矩阵：特殊矩阵：指有一定量的零元素（或相同元素），并且指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的规律。其分布（非零元素的位置）有一定的规律。采用压缩顺序存储方式采用压缩顺序存储方式: :只存非零元素只存非零元素, ,节省空间节省空间. . 1.1.下三角矩阵下三角矩阵: : 存放形式存放形式: :a00,a10,a11,a20,a21,an-10,an-11, an-1n-1 4.3 4.3 特殊矩阵的压缩存储特殊矩阵的压缩存储a00 0 0.0a10 a11 0 .0 . 0an-10 an
16、-11 . .an-1n-1Ann =可以是可以是0 0和常数和常数C C第第1 1行：行： 1 1个个第第2 2行：行： 2 2个个第第3 3行：行： 3 3个个 第第n n行：行： n n个个 1+2+3+4+5+n=n(n+1)/2 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241111计算机软件基础课件计算机软件基础课件非零元素非零元素aijaij存储地址存储地址: :L
17、oc(aij)=Loc(a00)+i*(i+1)/2+j*L （0j i n-1）K0123n(n-1)/2n(n+1)/2-1sbk a00a10a11a20an-11an-1n-1Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241212计算机软件基础课件计算机软件基础课件假设：以一维数组假设：以一维数组sbn(n+1)/2+1作为作为n阶下三角矩阵阶下三角矩阵A的的存储结构，存
18、储结构，A中任意元素中任意元素aij与与sbk对应关系如下：对应关系如下： i(i+1)/2+j 当当ij时时 (非零元素非零元素) k= n(n+1)/2 当当ij时时 (零或常数零或常数)其中：其中：sbk:sb0sbn(n+1)/2 -1 sbn(n+1)/2存放常数或零存放常数或零Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241313计算机软件基础课件计算机软件基础课件2
19、.2.对称矩阵对称矩阵对称矩阵：对称矩阵：n n阶方阵阶方阵A A中的元素满足：中的元素满足： a aij ij = a= aji ji 0 i, j n -1 0 i, j n -1 存储：可只存储上三角矩阵或下三角矩阵存储：可只存储上三角矩阵或下三角矩阵将将n*nn*n个元素压缩存储到个元素压缩存储到n(n+1)/n(n+1)/2 2个元素空间中个元素空间中（sasa数组）。数组）。以按行优先存储为例。以按行优先存储为例。A A矩阵与矩阵与saksak关系：关系：下三角矩阵的存储类似上三角矩阵，下三角矩阵的存储类似上三角矩阵，上三角矩阵上三角矩阵自推自推i(i+1)/2+j ijj(j+1
20、)/2+i ijk=Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241414计算机软件基础课件计算机软件基础课件K0123n(n-1)/2n(n+1)/2-1sak a00a10a11a20an-11an-1n-1隐含隐含a01a02a1n-13.3.对角矩阵：对角矩阵： 形状：形状：Ann =非零元素带非零元素带Evaluation only.Created with Aspos
21、e.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241515计算机软件基础课件计算机软件基础课件例：三对角阵例：三对角阵 Ann =其中非零元素按行优先顺序存放：其中非零元素按行优先顺序存放：a00 ,a01 ,a10 , a11, a12, a21, a22, a23, , an-1,n-2 , an-1,n-1 非零元素非零元素aij的地址关系式：的地址关系式：Loc(aij)= Loc(a00)+2*i+j(i=0,j=0,1 或或i=n-1,j
22、=n-2,n-1 或或0in-1,j=i-1,i,i+1)推广：推广：n阶对角阵有阶对角阵有（2h-1）条非零元素带。条非零元素带。hEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241616计算机软件基础课件计算机软件基础课件以上数组存储方式与顺序存储线性表类似以上数组存储方式与顺序存储线性表类似数组元素的存储位置是其下标的线性函数。数组元素的存储位置是其下标的线性函数。总之：总之
23、：特殊矩阵的压缩存储方法：特殊矩阵的压缩存储方法： 找出特殊矩阵的非零元素的分布规律，将其存储到一个存找出特殊矩阵的非零元素的分布规律，将其存储到一个存储空间，只需在算法中按公式计算即可实现矩阵元素的随机存储空间，只需在算法中按公式计算即可实现矩阵元素的随机存取。取。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20241717计算机软件基础课件计算机软件基础课件稀疏因子：设在稀疏因子：
24、设在m*nm*n的矩阵中，有的矩阵中，有t t个非零元素，令个非零元素，令称称 为矩阵的稀疏因子。通常认为为矩阵的稀疏因子。通常认为 =0.05md=sa.nd; sb-nd=sa.md; sb-td=sa.td; if(sb-td!=0) q=0; for(v=0; vsa.nd; v+) for(p=0; pdataq.i=sa.datap.j; sb-dataq.j=sa.datap.i; sb-dataq.d=sa.datap.d; q+; q q为为sb.datasb.data的下标的下标以以sa.datasa.data的的j j域次序搜索域次序搜索p p为为sa.datasa.da
25、ta的下标的下标676021104171125301943375650sa:03 1911 2520 1134 3740 1765 50766sb:Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20243030计算机软件基础课件计算机软件基础课件算法分析：算法分析：上述算法的时间复杂度为：上述算法的时间复杂度为：O(sa.ndsa.td)O(sa.ndsa.td)关键在于非零元素个数。关
26、键在于非零元素个数。当：当： sa.td m n sa.td m n 时，才适合用三元组表时，才适合用三元组表当：当： sa.td m n sa.td m n 时时, , 不适合用三元组表不适合用三元组表Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20243131计算机软件基础课件计算机软件基础课件 一般数组一般数组, , 按行、列存放，计算公式。按行、列存放，计算公式。特殊矩阵：计算
27、公式。特殊矩阵：计算公式。( (上下三角阵上下三角阵, ,对称阵对称阵, ,带状阵带状阵) )稀疏矩阵：表示方法：稀疏矩阵：表示方法： 顺序存储：三元组表顺序存储：三元组表 链接存储：三元组表的链接存储：三元组表的( (单单) )链表链表, , 行指针数组结构的三元组链表行指针数组结构的三元组链表, 三元组三元组十字链表十字链表 十字链表十字链表总结总结: :Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/
28、20247/24/20243232计算机软件基础课件计算机软件基础课件作业补充题：作业补充题：1. 二维数组二维数组A A的元素由的元素由6 6个字符组成，行下标以个字符组成，行下标以0 8；列下列下标标从从1 10；问：问： （1 1）A A至少需占多少字节？至少需占多少字节？ （2 2）A A的第的第8 8 列和第列和第5 5行共占多少字节？行共占多少字节？ （3 3）若）若A A按行存放，元素按行存放，元素A8,5A8,5的起始行地址与的起始行地址与当当A A按列存放时的哪一个元素的起始地址一致按列存放时的哪一个元素的起始地址一致? ? Evaluation only.Created w
29、ith Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20243333计算机软件基础课件计算机软件基础课件2 2、已知一稀疏矩阵如图所示，（、已知一稀疏矩阵如图所示，（1 1）试写出该稀疏）试写出该稀疏矩阵的三元组顺序表矩阵的三元组顺序表和三元组单链表和三元组单链表 ；（；（2 2）试）试写出该稀疏矩阵的十字链表。写出该稀疏矩阵的十字链表。 A= A=作业作业P145:P145: 1, 3 1, 3Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.7/24/20247/24/20243434
