计算机软件基础课件第第4 4章章 数组数组4.1 4.1 数组定义及基本操作数组定义及基本操作4.2 4.2 数组的存储结构数组的存储结构4.3 4.3 特殊矩阵的压缩存储特殊矩阵的压缩存储4.4 4.4 稀疏矩阵的压缩存储稀疏矩阵的压缩存储4.5 4.5 数组的运算数组的运算 Date1计算机软件基础课件数组是我们最常用的一种数据结构，各种计算机语言 均有此类型。例如：顺序表、顺序栈、循环队列等。数组的定义：数组：是（）个相同数据类型的数据元素 a0,a1an-1,构成的占用一块连续的内存单元的有限序列。数组特点：1.有限个元素的集合；2.所有元素具有相同的特性；3.元素名由数组名和下标组成；4.下标值与元素对应（代表元素的位置）。4.1 数组的定义及操作Date2计算机软件基础课件数组与线性表:相同之处:由若干个相同数据类型的数据元素组 成.不同之处:1.存储单元连续与否2.数据元素在逻辑意义上可分与否3.操作不同。Date3计算机软件基础课件. 数组的逻辑结构一维数组（a0,a1,a2,a3,an-1）满足线性关系；二维或二维以上数组：（以二维为例）Amxn= a a aa00 a02 . a0n-110 11 1n-1.a a am-10 m-12 m-1n-1看元素a11有两个直接前趋a10和a02两个直接后继a21和a12三维数组:每个元素有三个直接前趋和三个直接后继.可见:数组(除一维数组外)是一种复杂的非线性数据结构.Date4计算机软件基础课件但是:1)可将Amxn看成由m个行向量组成的向量,即Amn= (a00,a01,a0n-1),(a10,a11,a1n-1),(am-10,am-11,am-1n-1) 2)将Amxn看成由n个列向量组成的向量,即Amn=( (a00,a10,am-10),(a01,a11,am-11)(a0n-1,a1n-1,am-1n-1) )列向量为线性.元素1元素2元素m 看(ai0,ai1,ain-1),除ai0,ain-1 外只有一个直接前趋和一个直接后继.元素1元素2元素nDate5计算机软件基础课件据此 数组可看成是线性表的扩展:即线性表中的数据元 素本身也是一个数据结构.数组可表示成两类线性表:1.以行向量做线性表的一个元素;2.以列向量做线性表的一个元素.Date6计算机软件基础课件数组抽象数据类型：数据集合：数组的数据集合可表示为a0,a1an-1,每个数据元素的类型 为抽象数据类型:DataType（限定顺序存储）数据关系:线性关系.操作集合：各种高级程序设计语言的操作各不相同，必备的操作有：（1）求数组元素个数（2）随机取（3）随机存（4）矩阵运算Date7计算机软件基础课件一般数组: (以二维数组为例) 多采用顺序存储:(1).按行优先顺序存储假设：Amn= a00 a01 a02a0n-1 a10a00 a01 a02 a03 a0n-1a10 a11 a12 a13 a1n-1am-10 am-11 am-12 am-13 am-1n-1即 a00,a01,a02a0n-1, a10,a11,.a1n-1 aij的存储地址:am-1 ,04.2 数组的存储结构:Date8计算机软件基础课件L:为每个元素所占存储单元.Pascal和C语言中数组存储为此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列优先顺序存储,即a00,a10,a20am-10, a01,a11,.am-11aij存储地址:Loc(aij)=Loc(a00)+(j*m+i)*LFortran语言采用此方法.a00 a10 a20am-10 a01可见:数组是一种随机存储结构.存取任意元素的时间相等Date9计算机软件基础课件推广:假设:Ac1-d1c2-d2例：二维数组float a43.计算（1）数组元素数目？（2）若数组Loc(a00)=1000,且L=4,数组元素a32 的地址?(按行优先存储)(1) 4*3=12(2) Loc(a32)=Loc(a00)+(i*n+j)*L=1000+(3*3+2)*4=1044Loc(aij)=Loc(ac1c2)+(i-c1)*(d2-c2+1)+(j-c2)*L按行优先顺序存储：Loc(aij)=Loc(ac1c2)+(j-c2)*(d1-c1+1)+(i-c1)*L按列优先顺序存储：Date10计算机软件基础课件特殊矩阵：指有一定量的零元素（或相同元素），并且 其分布（非零元素的位置）有一定的规律。采用压缩顺序存储方式:只存非零元素,节省空间.1.下三角矩阵:存放形式:a00,a10,a11,a20,a21,an-10,an-11, an-1n-1 4.3 特殊矩阵的压缩存储a00 0 00a10 a11 0 .0. 0an-10 an-11 . .an-1n-1Ann =可以是0和常数C第1行： 1个第2行： 2个第3行： 3个 第n行： n个 1+2+3+4+5+n=n(n+1)/2 Date11计算机软件基础课件非零元素aij存储地址:Loc(aij)=Loc(a00)+i*(i+1)/2+j*L （0j i n-1）K0123n(n-1)/2n(n+1)/2-1sbka00a10a11a20an-11an-1n-1Date12计算机软件基础课件假设：以一维数组sbn(n+1)/2+1作为n阶下三角矩阵A的 存储结构，A中任意元素aij与sbk对应关系如下：i(i+1)/2+j 当ij时 (非零元素)k=n(n+1)/2 当imd=sa.nd;sb-nd=sa.md;sb-td=sa.td;if(sb-td!=0) q=0;for(v=0; vdataq.i=sa.datap.j;sb-dataq.j=sa.datap.i;sb-dataq.d=sa.datap.d;q+; q为sb.data的下标以sa.data的j域次序搜索p为sa.data的下标6 7 6 0211 0417 1125 3019 4337 5650sa :03 19 11 25 20 11 34 37 40 17 65 507 6 6sb :Date30计算机软件基础课件算法分析：上述算法的时间复杂度为：O(sa.ndsa.td)关键在于非零元素个数。当： sa.td m n 时，才适合用三元组表当： sa.td m n 时, 不适合用三元组表Date31计算机软件基础课件一般数组, 按行、列存放，计算公式。特殊矩阵：计算公式。(上下三角阵,对称阵,带状阵)稀疏矩阵：表示方法：顺序存储：三元组表链接存储：三元组表的(单)链表,行指针数组结构的三元组链表,三元组十字链表十字链表总结:Date32计算机软件基础课件作业补充题：1. 二维数组A的元素由6个字符组成，行下标以0 8 ；列下标从1 10；问：（1）A至少需占多少字节？（2）A的第8 列和第5行共占多少字节？（3）若A按行存放，元素A8,5的起始行地址与 当A按列存放时的哪一个元素的起始地址一致?Date33计算机软件基础课件2、已知一稀疏矩阵如图所示，（1）试写出该稀疏 矩阵的三元组顺序表和三元组单链表 ；（2）试 写出该稀疏矩阵的十字链表。A=作业P145:1, 3Date34