1、5.1 数组的类型定义数组的类型定义5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义5.5 广义表的表示方法广义表的表示方法5.1 数组的类型定义数组的类型定义ADT Array 数据对象数据对象：D|ji=0,.,bi-1,i=1,2,.,n n称为数组的维数，称为数组的维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维下标维下标 数据关系数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且且k i,0 ji bi-2,i=2,.,n ADT Arra
2、y 基本操作基本操作:njjja21二维数组的定义二维数组的定义:数据对象数据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2基本操作基本操作：InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并 返回O
3、K。DestroyArray(&A)操作结果：操作结果：销毁数组A。Value(A,&e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。Assign(&A,e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。5.2 数组的顺序表示和实现数组的顺序表示和实现 类型特点类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的
4、结构，而存储空间是 一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先):PASCAL、C;2)以列序为主序(高下标优先):FORTRAN、VB;例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存
5、储位置是其下标的线性函数。其中 cn=L，ci-1=bi ci,1=ji=j时，在下三角中，时，在下三角中，a aijij是第是第(i+1)(i+1)行第行第(j+1)(j+1)列的元素。列的元素。2)1()1(10iipipjiik2)1(2 2）当）当iji=ji=j时，在下三角中，时，在下三角中，dkaLockaLocaLocij)0()()(2 2）当）当ijij时时 ，在上三角中，在上三角中，它们共享一个空间：它们共享一个空间：0ija2)1(nnk对上三角形矩阵：对上三角形矩阵：a00 a01 a0(n-1)0 a11 a0(n-1)0 0 a(n-1)(n-1)1 1）当）当i=
6、jijij时时 ，在下三角中，在下三角中，它们共享一个空间：它们共享一个空间：0ija2)1(nnk10)(ippn)(ij 作业：求上三角形矩阵的压缩存储公式。作业：求上三角形矩阵的压缩存储公式。u对角矩阵 a00 a01 0 .0 a10 a11 a12 0 0 0 0 an-2,n-3 an-2,n-2 an-2,n-1 0 0 an-1,n-2 an-1,n-1 0 a21 a22 a23 0 0 当i=0时，0个；当ni0时,3i-1个。/每行每行3 3个元素，第个元素，第1 1行行2 2个个当i=0时，j个；当ni0时,(j-i)+1个。/)1()1(,iiiiiiaaa时当时当1
7、,20,injiijkdkaLockaLocaLocij)0()()(2)随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、十字链表十字链表#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行标和列标该非零元的行标和列标 ElemType e;/该非零元的值该非零元的值 Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE+1;/data0未用未用 int mu,nu,tu;/
8、矩阵的行数、列数及非零元个数矩阵的行数、列数及非零元个数 TSMatrix;/稀疏矩阵类型稀疏矩阵类型6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8 7600070015000001800000240001400003000000000009120M例如：如何求转置矩阵？如何求转置矩阵？028003600070500140005280000007143600用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)f
9、or(row=1;row=mu;+row)Tcolrow=Mrowcol;1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2用“三元组”表示时如何实现？快速转置算法 即按即按ma中三元组次序转置，转置结果放入中三元组次序转置，转置结果放入mb中恰当位置。中恰当位置。算法
10、关键是要预先确定算法关键是要预先确定M中每一列第一个非零元在中每一列第一个非零元在mb中位置，中位置，为确定这些位置，转置前应先求得为确定这些位置，转置前应先求得M的每一列中非零元个数的每一列中非零元个数.numcol：表示矩阵：表示矩阵M中第中第col列中非零元个数列中非零元个数cpotcol：指示：指示M中第中第col列第一个非零元在列第一个非零元在mb.data中的恰当位置中的恰当位置显然有：显然有：1357889colnumcolcpotcol122232415061707600070015000001800000240001400003000000000009120M1 2 12 1
11、 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol112232352471580681790 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 ppppppppStatus FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.
12、nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素Col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间
13、复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p)最坏情况为：最坏情况为：O(M.nu*M.mu)三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩依行顺序处理的矩阵运算阵运算。然而，若需随机存取某一行中的非零元时，则需从头开始进行查找。二、行逻辑链接的顺序表二、行逻辑链接的顺序表#define MAXSIZE 500 typedef struct Triple dataMAXSI
14、ZE+1;int rposMAXRC+1;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos,它是各行第一个非零元的位置表，其值在稀疏矩阵的初始化函数中确定。例1.给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M,int r,int c)p=M.rposr;while(M.datap.i=r&M.datap.j c)p+;if(M.datap.i=r&M.datap.j=c)return M.datap.e;else
15、return 0;/value 矩阵乘法的精典算法矩阵乘法的精典算法:for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)例2.矩阵乘法 Q Q M Mm1m1*n1n1 N Nm2m2*n2n2（n1=m2n1=m2）fedcba987654321（以行逻辑链接的顺序表存储）（以行逻辑链接的顺序表存储）fedcba987654321ctemp1=ctemp2=brow=2;brow=3;brow=1:=Q初始化初始化;if Q是非零矩阵是非零矩阵 /逐行求积逐行求
16、积 for(arow=1;arow=M.mu;+arow)/处理处理M的每一行的每一行 ctemp=0;/累加器清零累加器清零 计算计算Q中第中第arow行的积并存入行的积并存入ctemp 中；中；将将ctemp 中非零元压缩存储到中非零元压缩存储到Q.data；/for arow /if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N）的过程可大致描述如下：的过程可大致描述如下：Status MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=
17、0;if(M.tu*N.tu!=0)/Q是非零矩阵 for(arow=1;arow=M.mu;+arow)/for arow /if return OK;/MultSMatrix ctemparow=0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1;/Q中第中第arow行的第一个元素的位置行的第一个元素的位置 if(arow M.nu)tp=M.rposarow+1;else tp=M.tu+1 /tp是是M中中arow行的最后一个非零元之后的位置行的最后一个非零元之后的位置 for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元对当前行
18、中每一个非零元 brow=M.datap.j;/找到对应元在找到对应元在N中的行号中的行号 if(brow N.mu)t=N.rposbrow+1;else t=N.tu+1 /t是是N中中brow行的最后一个非零元之后的位置行的最后一个非零元之后的位置 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在乘积元素在Q中列号中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得求得Q中第中第crow(=arow)行的非零元行的非零元,下面压缩存储该行非零元下面压缩存储该行非零元 for(ccol=1;ccol MAXSI
19、ZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理 的每一行M 当矩阵的非零元当矩阵的非零元和和在操作过在操作过程中变化较大时，就不宜采用程中变化较大时，就不宜采用存储的存储的三元组表来表示矩阵了。三元组表来表示矩阵了。例如：将矩阵例如：将矩阵B 加到矩阵加到矩阵A上。上。由于非零元的插入或删除将会引起由于非零元的插入或删除将会引起A.data中元素的移动。对此采用链式存储中元素的移动。对此采用链式存储结构更为合适。结构更为合适。三、三、十字链表十字链表row col valdownright34008000450003A113418225
20、23412341 2 3 3 0 0 50-1 0 02 0 0 0练习：画出矩阵的十字链表。练习：画出矩阵的十字链表。3 0 0 50-1 0 02 0 0 0M.cheadM.rhead1 1 31 4 52 2-13 1 2 参考答案：参考答案：作业：画出矩阵作业：画出矩阵X X的三元组表和十字链表。的三元组表和十字链表。6000800000040000031002005X5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,
21、eiD,2in ADT Glist基本操作基本操作:结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);基本操作基本操作 状态函数状态函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();1.广义表是递归递归定义的线性结构线性结构，LS
22、=(1,2,n)其中：其中：i 或为原子或为原子 或为广义表或为广义表 例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,)p 递归的两层含义：递归的两层含义：1).广义表的元素是广义表的元素是另一个另一个广义表；广义表；2).广义表的某个元素可以是广义表广义表的某个元素可以是广义表本身本身；2.广义表的长度长度定义为最外层包含元素个数;例如例如:A=()F=(d,(e)D=(a,(b,c),F)0 2 23.广义表的深度深度定义为所含括号的重数;注意:“原子”的深度为 0;“空表”的深度为 1。广义表的深度广义表的深度 =Max
23、子表的深度子表的深度+1例如例如:A=()F=(d,(e)D=(a,(b,c),F)1 2 3 =(a,(b,c),(d,(e)B =(a,B)=(a,(a,(a,)递归表的深度是无穷值，长度是有限值。4.广义表是一个多层次多层次的线性结构线性结构.例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce5.广义表可以共享共享.D=(E,F,A)E=(a,(b,c)F=(d,(e),A)A=()6.任何一个非空广义表非空广义表 LS=(1,2,n)均可分解为：Head(LS)=1 和 Tail(LS)=(2,n)例如例如:D=(E,F)=(，F)Head(D
24、)=Tail(D)=Head(E)=Tail(E)=Head(b,c)=Tail(b,c)=Head(b,c)=Tail(b,c)=Head(c)=Tail(c)=1.Head();Tail()2.Head()3.Tail()4.Head(Tail()5.Tail(Head()6.Tail(Tail()练习：5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data1)表头、表尾分析法表头、表尾分析法:构造存储结构的两种分析方法构造存储结构的两种分析方法:若表头为原子，则为若表头为原子，则为空表空表 ls=N
25、ULL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依此类推。否则，依此类推。例：例：L=(a,(x,y),(x)表头表尾分析法表头表尾分析法 1 L 1 1 (x)(x,y),(x)1 (x,y)1 (x)1 (y)0 x x0 a a0 y y(x)1 0 x x 1 1 1 ls 2)元素分析法元素分析法:若元素为原子，则为若元素为原子，则为空表空表 ls=NULL非空表非空表指向元素1 的指针tag=0 data否则，依此类推。否则，依此类推。指向元素2 的指针指向元素n 的指针例：例：LS=(a,(x,y),(x)元素分析法元素分析法ls1111 x a 0 a x 0 x y 0 y x 0 x(x)(x,y)a11xy1(x)作 业 1 1 1 1 1 1 0 f 0 e 0 b 0 a 1 1 1 1 0 d 1 1 1 1.F 1 1 1 1 1 1 1 1 0 a 0 a 0 b 1 1 1 0 b 2.G
