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

2019/7/22,1,第4章 数组,4.1 数组定义及基本操作 4.2 数组的存储结构 4.3 特殊矩阵的压缩存储 4.4 稀疏矩阵的压缩存储 4.5 数组的运算,2019/7/22,2,数组是我们最常用的一种数据结构，各种计算机语言均有此类型。例如：顺序表、顺序栈、循环队列等。 数组的定义： 数组：是（）个相同数据类型的数据元素a0,a1an-1,构成的占用一块连续的内存单元的有限序列。,数组特点： 1.有限个元素的集合； 2.所有元素具有相同的特性； 3.元素名由数组名和下标组成； 4.下标值与元素对应（代表元素的位置）。,4.1 数组的定义及操作,2019/7/22,3,数组与线性表: 相同之处:由若干个相同数据类型的数据元素组成. 不同之处: 1.存储单元连续与否 2.数据元素在逻辑意义上可分与否 3.操作不同。,2019/7/22,4,. 数组的逻辑结构,一维数组（a0,a1,a2,a3,an-1）满足线性关系； 二维或二维以上数组：（以二维为例）,Amxn=,看元素a11有两个直接前趋a10和a02两个直接后继a21和a12,三维数组:每个元素有三个直接前趋和三个直接后继. 可见:数组(除一维数组外)是一种复杂的非线性数据结构.,2019/7/22,5,但是: 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) ) 列向量为线性.,看(ai0,ai1,ain-1),除ai0,ain-1 外只有一个直接前趋和一个直接后继.,2019/7/22,6,据此 数组可看成是线性表的扩展:即线性表中的数据元素本身也是一个数据结构.,数组可表示成两类线性表: 1.以行向量做线性表的一个元素; 2.以列向量做线性表的一个元素.,2019/7/22,7,数组抽象数据类型： 数据集合： 数组的数据集合可表示为a0,a1an-1,每个数据元素的类型为抽象数据类型:DataType（限定顺序存储） 数据关系:线性关系. 操作集合： 各种高级程序设计语言的操作各不相同，必备的操作有： （1）求数组元素个数 （2）随机取 （3）随机存 （4）矩阵运算,2019/7/22,8,一般数组: (以二维数组为例) 多采用顺序存储: (1).按行优先顺序存储 假设：Amn=,即 a00,a01,a02a0n-1, a10,a11,.a1n-1,aij的存储地址:,4.2 数组的存储结构:,2019/7/22,9,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语言采用此方法.,可见:数组是一种随机存储结构.存取任意元素的时间相等,2019/7/22,10,推广:假设:Ac1-d1c2-d2,例：二维数组float a43.计算（1）数组元素数目？ （2）若数组Loc(a00)=1000,且L=4,数组元素a32的地址?(按行优先存储),4*3=12 Loc(a32)=Loc(a00)+(i*n+j)*L =1000+(3*3+2)*4 =1044,2019/7/22,11,特殊矩阵：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的规律。 采用压缩顺序存储方式:只存非零元素,节省空间. 1.下三角矩阵:,存放形式:a00,a10,a11,a20,a21,an-10,an-11, an-1n-1,4.3 特殊矩阵的压缩存储,第1行： 1个 第2行： 2个 第3行： 3个 第n行： n个,1+2+3+4+5+n=n(n+1)/2,2019/7/22,12,非零元素aij存储地址: Loc(aij)=Loc(a00)+i*(i+1)/2+j*L （0j i n-1）,2019/7/22,13,假设：以一维数组sbn(n+1)/2+1作为n阶下三角矩阵A的存储结构，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存放常数或零,2019/7/22,14,2.对称矩阵,对称矩阵：n阶方阵A中的元素满足： aij = aji 0 i, j n -1 存储：可只存储上三角矩阵或下三角矩阵 将n*n个元素压缩存储到n(n+1)/2个元素空间中（sa数组）。 以按行优先存储为例。 A矩阵与sak关系：,下三角矩阵的存储类似上三角矩阵，上三角矩阵自推,2019/7/22,15,3.对角矩阵： 形状：,Ann =,2019/7/22,16,例：三对角阵 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=n-2,n-1 或0in-1,j=i-1,i,i+1),推广：n阶对角阵有（2h-1）条非零元素带。,2019/7/22,17,以上数组存储方式与顺序存储线性表类似 数组元素的存储位置是其下标的线性函数。,总之： 特殊矩阵的压缩存储方法： 找出特殊矩阵的非零元素的分布规律，将其存储到一个存储空间，只需在算法中按公式计算即可实现矩阵元素的随机存取。,2019/7/22,18,稀疏因子：设在m*n的矩阵中，有t个非零元素，令,称为矩阵的稀疏因子。通常认为=0.05时为稀疏矩阵。 我们在存储的时候，除了存储非零元的值之外，还得存储它所在的行号和列号。由此构成一个三元组(i,j,aij)，该三元组唯一确定了该矩阵元素。,4.4 稀疏矩阵:,2019/7/22,19,含有大量零元素的矩阵,且无规律。仅存非零元素,可省空间,避免大量无意义运算,提高运算效率.,例: A=,1.顺序存储:按行优先顺序排列.,(1).三元组顺序表: 每个结点由三个域组成 a.非零元素行下标; b.非零元素列下标; c.非零元素值.,2019/7/22,20,A的三元组顺序表表示: (0,0,3) (0,4,7) (1,2,-1) (2,0,-1) (2,1,-2) (4,3,2),若有N个非零元素则需要3N个存储单元,2019/7/22,21,2. 链接存储结构:,(1)三元组(单)链表. 三元组线性表采用链接存储结构。,(0,0,3) (0,4,7) (1,2,-1) (2,0,-1) (2,1,-2) (4,3,2),缺点：算法事件复杂度高,2019/7/22,22,(2) 行指针数组结构的三元组链表. 设置一个行指针数组, 数组中每个元素为指针类型,它指向本行矩阵的第一个非零元素,若该行无非零元素,则指针为空. 以A为例:行指针数组,2019/7/22,23,(3). 三元组十字链表:,上面介绍的行指针数组结构的三元组链表形式容易实现按行找某列元素,不容易实现按列找某行元素. 改进:按照行指针数组结构的三元组链表形式构造出相同结构的列指针数组.例:,2019/7/22,24,为了方便算法中对矩阵的行方向和列方向的搜索。 采用动态存储结构:每个非零元素用一个结点由五个数据域组成:三个数值,两个指针. 三个数值：i，j，value.表示非零元素的行号、列号和元素值。 两个指针：Down：向下指针 Right：向右指针,行链表的头结点与列链表的头结点共用一个结点.,十字链表设置：行头结点、列头结点和链表头结点.,行头结点 列头结点,(4). 十字链表:,2019/7/22,25,链表头结点,例: A55=,2019/7/22,26,0,0,3,0,3,7,2,1,-2,1,2,-1,2,0,-1,head,h1,h1,h2,h2,h3,h3,h4,h4,2019/7/22,27,转置运算：设稀疏矩阵A以三元组表顺序存储结构存放。 三元组顺序表结构定义如下：,#define MAX 100 typedef struct int i; /*行*/ int j; /*列*/ DataType d;/*元素值*/ tupletype; /*三元组*/,typedef struct int md; /*总行数*/ int nd; /*总列数*/ int td; /*总非零元素数*/ tupletype dataMAX; tabletype; /*三元组表*/,4.5 数组运算：,2019/7/22,28,sa.md,#define MAX 10 typedef struct int i; /*行*/ int j; /*列*/ DataType d;/*元素值*/ tupletype; /*三元组*/,typedef struct int md; /*总行数*/ int nd; /*总列数*/ int td; /*总非零元素数*/ tupletype dataMAX; tabletype; /*三元组表*/ tabletype sa;,sa.nd,sa.td,2019/7/22,29,例：将稀疏矩阵A进行转置,2019/7/22,30,转置算法：,Void trantup (tabletype sa, tabletype *sb) int p,q,v; sb-md=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+; ,以sa.data的j域次序搜索,2019/7/22,31,算法分析： 上述算法的时间复杂度为：O(sa.ndsa.td) 关键在于非零元素个数。 当： sa.td m n 时，才适合用三元组表 当： sa.td m n 时, 不适合用三元组表,2019/7/22,32,一般数组, 按行、列存放，计算公式。 特殊矩阵：计算公式。(上下三角阵,对称阵,带状阵) 稀疏矩阵：表示方法： 顺序存储：三元组表 链接存储：三元组表的(单)链表, 行指针数组结构的三元组链表, 三元组十字链表 十字