数据结构 第5章

1、第 5 章,数组和广义表,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( ai=(a0j,a1j,.am-1j) typedef ElemType Array2mn; typedef ElemType Array1n; typedef Array1 Array2m;,(0,0),(m-1,n-1),二维数组，m 行，n 列 元素个数：m*n 每

2、个元素由行、列两个关系约束,5.2 数组的顺序 表示和实现,数组的顺序存储结构,以行为主序 例： A32 A00, A01, A10, A11, 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 =LO

3、C0,0,.,0+( )L =LOC0,0,.,0+ 其中:cn=L,ci-1=bi*ci 1i=n,三维数组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=32 A342=0+32*3+4*4+2 =114,#include /可变长参数 #define MAX_ARRAY_DIM 8 typedef struct ElemType *base; /数据元素基址 int dim; /数组维数 int *bounds; /每一维的元素

4、个数 int *constants; /映像函数常数 ,Status InitArray(Array /复位,A.base=new ElemTypeelemtotal; if (!A.base) exit(OVERFLOW); A.constants=new intdim; if (!A.constants) exit(OVERFLOW); A.constantsdim-1=1; /计算Ci for (i=dim-2;i=0;i-) A.constantsi= A.boundsi+1*A.constantsi+1; return OK; ,Stauts DestroyArray(Array ,

5、Status Locate(Array A,va_list ap,int ,三维数组A684,Stauts Value(Array A,ElemType ,Status Assign(Array ,5.3 矩阵的压缩存储,1. 特殊矩阵的压缩存储,若矩阵元素有规律地排列，则称为特殊矩阵。例如：对称矩阵，三角矩阵，主对角矩阵，.,2 4 7 9 5 7 5 6 3 6 1 3 5 3 7,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,压缩,位置转换公式,2. 稀疏矩阵,判定稀疏矩阵的标准：t/(m*n)=0.05,基本操作,CreateSMatrix( /行、列 Elem

6、Type e; /非零元素值 Triple; typedef struct Triple dataMAXSIZE+1; /从1开始 int mu,nu,tu; /矩阵的行数、 列数及非零元素个数 TSMatrix;,三元组表示要求,每个非零元素用三元表示 元素之间按行主序排列,三元组求转置矩阵,M T,转置方法 M-T,按照 T 中的顺序在 M 中选择相应的元素并放入T中。 时间复杂度 O(M.nu*M.tu) 依次把 M 中的元素转置到T中，再对T进行排序。 时间复杂度 O(M.tu*log(M.tu),Stauts TransposeSMatrix(TSMatrix M,TSMatrix

7、,时间复杂度：O(M.nu*M.tu),三元组快速转置,M T,快速转置法,元素一次定位 时间复杂度O(M.nu+M.tu),for (col=1;col=M.nu;+=col) numcol=0; for (t=1;t=M.tu;+t) +numM.datat.j;/累计每列的元素数目 计算各列第一个非零元素在T中的位置 cpot1=1; for (col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1,统计M中各列的非零元素个数,M T,Status FastTransposeSMatrix(TSMatrix M, TSMatrix ,(2) 行逻辑

8、链接表示法,为了便于随机存取任意一行的非零元素，需知道每一行的第一个非零元素在三元组表中的位置。为此，将此信息保留在结构体类型中。 typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; int mu,nu,tu; RLSMatrix;,1 2 3 4 5 6,1,3,3,5,6,7,M.rpos,M.mu=6 M.nu=7 M.tu=8,M.data,行逻辑链接矩阵相乘,Q m1*n2=Mm1*n1*N m2*n2 (n1=m2) for (i=1;i=m1;i+) for (j=1;j=n2+j) Qij=0; for (k=1;k=n1

9、;k+) Qij=Qij+Mik*Nkj ,时间复杂度O(m1*n1*n2),相乘操作的特点,两个稀疏矩阵相乘，结果不一定是稀疏矩阵 Qij= Mik*Nkj 每个M.datap要与N中所有满足条件 M.datap.j = N.dataq.i 的元素进行相乘操作,M=,1 1 3,1 4 5,2 2 -1,3 1 2,1 2 2,2 1 1,3 1 -2,3 2 4,N=,0 0 5 0 -1 0 0 2 0 0 0,0 2 0 -2 4 0 0,3*4,4*2,Q 初始化； if （M与N都不是零矩阵） for (arow=1;arow=M.mu; arow +) ctemp =0; 计算Q

10、中第arow行的积并存入ctemp 中； 将ctemp 中非零元素压缩存储到Q.data； ,Status MultSMatrix(RLSMatrix M, RLSMatrix N,RLSMatrix ,for (p=M.rposarow;pMAXSIZE) return ERROR; Q.dataQ.tu=(arow,ccol,ctempccol); return OK; ,(3) 十字链表,十字链表定义,typedef struct OLNode int i,j; ElemType e; struct OLNode *right,*down; OLNode;*OLink; typedef

11、struct OLNode *rhead,*chead; int mu,nu,tu; CrossList;,建立十字链表算法伪语言,输入总行数,列数 m,n及非零元素个数t; 建立行、列头指针； 重复下列过程： 输入非零元素； 生成新结点p; 把p结点插入到行链表中(以列有序); 把p结点插入到列链表中(以行有序);,Status CreateSMatrix_OL(CrossList ,十字链表相加 A+B-A,分析 相加后结点由三类组成 原A中结点 (Aij0,Bij=0) B 中结点 (Aij=0,Bij0) A,B之和 (Aij0,Bij0),思路,逐行一列一列比较 (pa-jpb-j)

12、或 pa行已处理完 在A中插入Bij; (pa-jj) A移动指针; (pa-j=pb-j) if 之和不为零 then 修改pa-e else 删除pa；,注意,由于每个结点处在两个链表中,因而插入、删除要同时对两个方向的链表进行。 没有破坏B十字链表。,5.4 广义表的定义,广义表的定义,长度为n的广义表是一种数据结构 Lists=(D,R) D=di|i=1,2,.,n,n=0, 且diD0或di Lists R=LR LR=|d i-1, di属于D，2=i=n,广义表记作,LS=(d1,d2,.,dn) di:单原子或子表 习惯:大写表示表 小写表示原子 若广义表非空,d1为LS的表

13、头 （d2,.,dn）将组成LS的表尾,A=( ) 长度为0 B=(e) 长度为1 C=(a,(b,c,d) 长度为2 D=(A,B,C) 长度为3 E=(a,E) 长度为2,A=( ) B=(e) 表头e 表尾 ( ) C=(a,(b,c,d) 表头a 表尾 (b,c,d) D=(A,B,C) 表头A 表尾 (B,C) E=(a,E) 表头a 表尾 (E),表,原子,结论,广义表具有层次结构 广义表可以共享 广义表可以递归,基本操作,InitGList( typedef struct GLNode ElemTag tag; union AtomType atom; struct struct

14、 GLNode *hp,*tp;ptr; ; *GList,对于非空表，头指针 指向一个表结点，表 结点的hp指向表头元 素，tp指向表尾。,存储特点,表头指针: 广义表为空其值为空 否则指向一个表结点 容易获得某个元素所在的层次 容易获得广义表的长度,广义表存储结构（2）,表结点,原子结点,一层括号一个表结点,5.5 广义表的递归算法,递归算法,递归算法由两部分组成 基本项 描述递归的终结状态 归纳项 描述从当前状态到终结状态的转化,递归算法,递归过程的实质是将一个复杂的问题分解成若干个子问题，而其中某些子问题与原问题具有相同的特征属性，可利用与原问题相同的方法进行处理。,求广义表的深度,LS=(a1,a2,.,an),depth(LS)=,1 LS=nil 0 LS指原子 1+maxdepth(ai) n=1 1=i=n,算法伪语言,if 空表 then 深度为1； if 原子 then 深度为0； 计算每个元素的深度， 并将最大深度存入max； return max+1;,int GListDepth(GList L) if (!L) return 1; if (L-tag=ATOM) return 0; for (max=0,pp=L;pp;pp=pp-ptr.tp) dep