结构体数组结构体数组.ppt

计算机软件基础课件 第第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 a a00 a02 . a0n-1 10 11 1n-1 . a a a m-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 元素n Date5 计算机软件基础课件 据此 数组可看成是线性表的扩展:即线性表中的数据元 素本身也是一个数据结构. 数组可表示成两类线性表: 1.以行向量做线性表的一个元素; 2.以列向量做线性表的一个元素. Date6 计算机软件基础课件 数组抽象数据类型： 数据集合： 数组的数据集合可表示为a0,a1an-1,每个数据元素的类型 为抽象数据类型:DataType（限定顺序存储） 数据关系:线性关系. 操作集合： 各种高级程序设计语言的操作各不相同，必备的操作有： （1）求数组元素个数 （2）随机取 （3）随机存 （4）矩阵运算 Date7 计算机软件基础课件 一般数组: (以二维数组为例) 多采用顺序存储: (1).按行优先顺序存储 假设：Amn= a00 a01 a02 a0n-1 a10 a00 a01 a02 a03 a0n-1 a10 a11 a12 a13 a1n-1 am-10 am-11 am-12 am-13 am-1n-1 即 a00,a01,a02a0n-1, a10,a11,.a1n-1 aij的存储地址: am-1 ,0 4.2 数组的存储结构: Date8 计算机软件基础课件 L:为每个元素所占存储单元. Pascal和C语言中数组存储为此方式. 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语言采用此方法. a00 a10 a20 am-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 =1044 Loc(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 00 a10 a11 0 .0 . 0 an-10 an-11 . .an-1n-1 Ann = 可以是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-1 sbka00a10a11a20an-11an-1n-1 Date12 计算机软件基础课件 假设：以一维数组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 5650 sa : 03 19 11 25 20 11 34 37 40 17 65 50 7 6 6 sb : 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