数据结构-第5章课件

1、第 5 章数组和广义表第 5 章数组和广义表5.1 数组的定义5.1 数组定义ADT Array 数据对象：ji=0,.,bi-1,i=1,2,.,n, D=aj1j2.jn|n0, aj1j2.jnElemSet 数据关系： R=R1,R2,.,Rn Ri=| aj1. ji.jn, aj1.ji+1.jn D 基本操作： InitArray(&A,n,bound1,.boundn) DestroyArray(&A) Value(A,&e,index1,.indexn) Assign(&A,e,index1,.indexn)ADT Array数组定义ADT Array二维数组可以将二维数组看

2、成一个定长的线性表，它的每个数据元素也是一个定长线性表。A=(a0,a1,.,ap);ai=(a0j,a1j,.am-1j)typedef ElemType Array2mn;typedef ElemType Array1n;typedef Array1 Array2m;二维数组可以将二维数组看成一个定长的线性表，它的每个数据元素(0,0)(m-1,n-1)二维数组，m 行，n 列元素个数：m*n每个元素由行、列两个关系约束(0,0)(m-1,n-1)二维数组，m 行，n 列5.2 数组的顺序表示和实现5.2 数组的顺序存储结构以行为主序 例： A32 A00, A01, A10, A11,

3、A20, A21 LOCij=LOC00+(n*i+j)*L L为每个元素占用的空间单元数数组的顺序存储结构以行为主序数组的顺序存储结构以列为主序 例 A32 A00,A10,A20,A01,A11,A21 LOCij=LOC00+(m*j+i)*L L为每个元素占用的空间单元数数组的顺序存储结构以列为主序假设：b1,b2,b3,.bn为每一维的元素个数LOCj1,j2,.jn=LOC0,0,.,0 +(b2*b3.*bn*j1 + b3*.*bn*j2,+.+ bn*jn-1+jn)L=LOC0,0,.,0+( )L=LOC0,0,.,0+其中:cn=L,ci-1=bi*ci 1i=n假设：

4、b1,b2,b3,.bn为每一维的元素个数三维数组A684共6*8*4=192个元素假设：每个元素占据L=1个存储单元b1=6, b2=8, b3=4, L=1则：c3=L=1 c2=c3*b3=c3*4=1*4=4 c1=c2*b2=4*8=4*8=32A342=0+32*3+4*4+2 =114三维数组A684共6*8*4=192个元素#include /可变长参数#define MAX_ARRAY_DIM 8typedef struct ElemType *base; /数据元素基址 int dim; /数组维数 int *bounds; /每一维的元素个数 int *constants

5、; /映像函数常数#include /可变长参数Status InitArray(Array &A,int dim,.) if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=new intdim; if (!A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); /初始化参数列表 for (i=0;idim;i+) A.boundsi=va_arg(ap,int); /读取参数 if (A.boundsi=0;i-) A.constantsi= A.boundsi+1*A.co

6、nstantsi+1; return OK; A.base=new ElemTypeelemtoStauts DestroyArray(Array &A) if (!A.base) return ERROR; delete A.base; A.base=NULL; if (!A.bounds) return ERROR; delete A.bounds; A.bounds=NULL; if (!contants) return ERROR; delete A.contants; A.contants=NULL; return OK;Stauts DestroyArray(Array &A)St

7、atus Locate(Array A,va_list ap,int &off) off=0; for (i=0;iA.dim;i+) ind=va_arg(ap,int); if (ind=A.boundsi) return OVERFLOW; off +=A.constantsi*ind; return OK;三维数组A684Status Locate(Array A,va_list Stauts Value(Array A,ElemType &e,.) va_start(ap,e); if (result=Locate(A,ap,off)=0) return result; e=*(A.

8、base+off); return OK;Stauts Value(Array A,ElemType Status Assign(Array &A,ElemType e,.) va_start(ap,e); if (result=Locate(A,ap,off)=j-1 ij2 0 0 0 02 4 7 9 5 7 52. 稀疏矩阵0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 06*7判定稀疏矩阵的标准：t/(m*n)T按照 T 中的顺序在 M 中选择相应的元素并放入T中

9、。 时间复杂度 O(M.nu*M.tu)依次把 M 中的元素转置到T中，再对T进行排序。 时间复杂度 O(M.tu*log(M.tu)转置方法 M-T按照 T 中的顺序在 M 中选择相应的元素Stauts TransposeSMatrix(TSMatrix M,TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for (col=1;col=M.nu;+col) /按列扫描 for (p=1;p=M.tu;+p) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.data

10、p.i; T.dataq.e=M.datap.e; +q; return OK;时间复杂度：O(M.nu*M.tu)Stauts TransposeSMatrix(TSMatr三元组快速转置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14M T三元组快速转置1 2 121 3快速转置法元素一次定位时间复杂度O(M.nu+M.tu)快速转置法元素一次定位for (col=1;col=M.nu;+=col) numcol=0;for (t=1;t=M.tu;+

11、t) +numM.datat.j;/累计每列的元素数目计算各列第一个非零元素在T中的位置cpot1=1;for (col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1统计M中各列的非零元素个数for (col=1;col=M.nu;+=col)统计M1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14M T22210101 2 3 4 5 6 7num1357889cpot1 2 121 3 -3M Status Fa

12、stTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; 计算num,cpot的值； for (p=1;p=M.tu;+p) 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+; return OK; Status FastTransposeSMatrix(TS(2) 行逻辑链接表示法为了便于随机存取任意一行的非零元素，需知道每一行的第一个非零元素在三元组表

13、中的位置。为此，将此信息保留在结构体类型中。typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; int mu,nu,tu;RLSMatrix;(2) 行逻辑链接表示法为了便于随机存取任意一行的非零元素，1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 2 3 4 5 6133567M.rposM.mu=6M.nu=7M.tu=8M.data1 2 121 2 3 行逻辑链接矩阵相乘Q m1*n2=Mm1*n1*N m2*n2 (n1=m2)for (i=1;i=m1;i+) for (j=1

14、;j=n2+j) Qij=0; for (k=1;k=n1;k+) Qij=Qij+Mik*Nkj 时间复杂度O(m1*n1*n2)行逻辑链接矩阵相乘Q m1*n2=Mm1*n1*N m2*相乘操作的特点两个稀疏矩阵相乘，结果不一定是稀疏矩阵Qij= Mik*Nkj每个M.datap要与N中所有满足条件 M.datap.j = N.dataq.i 的元素进行相乘操作 相乘操作的特点两个稀疏矩阵相乘，结果不一定是稀疏矩阵M=1 2 3 4 1235rpos1 1 31 4 52 2 -13 1 21 2 22 1 13 1 -23 2 4N=0 0 50 -1 0 02 0 0 00 20-2

15、40 03*44*21 2 3 134rposM=1 2 3 4 1235Q 初始化；if （M与N都不是零矩阵） for (arow=1;arow=M.mu; arow +) ctemp =0; 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元素压缩存储到Q.data； i,kk,.Q 初始化；i,kk,.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=0; if (M.tu*N.tu) fo

16、r (arow=1;arow=M.mu;arow+) Ctemp=0; Q.rposarow=Q.tu+1; /Q的rpos值 if (arowM.mu) tp=M.rposarow+1; else tp=M.tu+1;Status MultSMatrix(RLSMatrix M for (p=M.rposarow;ptp;p+) brow=M.datap.j; /N中的位置 if (browN.mu) t=N.rposbrow+1; else t=N.tu+1; for (q=N.rposbrow;qt;q+) ccol=N.dataq.j; ctempccol+=M.datap.e*N.d

17、ataq.e; for (ccol=1;ccolMAXSIZE) return ERROR; Q.dataQ.tu=(arow,ccol,ctempccol); return OK; for (p=M.rposarow;pmnt; if (!(M.rhead=new OLinkm+1) exit(OVERFLOW); if (!(N.chead=new OLinkn+1) exit(OVERFLOW); M.rhead =M.chead =NULL; for (i=1;iije; if (!(p=new OLNode) exit(OVERFLOW): p-i=i;p-j=j;p-e=e; if

18、 (M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p; else for (q=M.rheadi;(q-right)&q-right-jright); p-right=q-right;q-right=p; if (M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p; else for (q=M.cheadj;(q-down)&q-down-idown); p-down=q-down;q-down=p; return OK; Status CreateSMatrix_OL(CrossL

19、十字链表相加 A+B-A分析相加后结点由三类组成原A中结点 (Aij0,Bij=0)B 中结点 (Aij=0,Bij0)A,B之和 (Aij0,Bij0)十字链表相加 A+B-A分析思路逐行一列一列比较(pa-jpb-j)或 pa行已处理完在A中插入Bij;(pa-jj)A移动指针;(pa-j=pb-j)if 之和不为零 then 修改pa-e else 删除pa；思路逐行一列一列比较注意由于每个结点处在两个链表中,因而插入、删除要同时对两个方向的链表进行。没有破坏B十字链表。注意由于每个结点处在两个链表中,因而插入、删除要同时对两个方5.4 广义表的定义5.4 广义表的定义广义表的定义长度为

20、n的广义表是一种数据结构 Lists=(D,R)D=di|i=1,2,.,n,n=0, 且diD0或di ListsR=LR LR=|d i-1, di属于D，2=i=1 1=itag=ATOM) return 0; for (max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr.hp); if (depmax) max=dep; return max+1;int GListDepth(GList L)复制广义表非空广义表由表头和表尾唯一确定基本项: 空表归纳项: 分别复制表头和表尾复制广义表非空广义表由表头和表尾唯一确定Status CopyGList(GList &T,GList L) if (!L) T=NULL; /空表 else if (!(T=new GLNode) exit(OVERFLOW); T-tag=L-tag; if (L-tag=ATOM) T-data=L-data; else CopyGList(T-ptr.hp,L-ptr.hp); CopyGList(T-ptr.tp,L-ptr.tp); return OK;Status CopyGList(GList &T,GLisStatus CreateGList(GLisst