资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第五章 数组和广义表,5.1,数组的定义,5.2,数组的顺序表示和实现,5.3,矩阵的压缩存储,5.4,广义表,5.1,数组的定义,ADT Array,数据对象：,j,i,=0,b,i,-1,i=1,2,.,n,D=a,j1j2,jn,|n,(0),为数组的维数,b,i,是数组,第,i,维的长度,j,i,是数组元素的第,i,维下标,a,j1j2,jn,ElemSet,数据关系：,R=R,1,R,2,R,n,基本操作：,详见,P,90,ADT Array,n,维数组中含有元素：,5.1,数组的定义,A,mxn,二维数组，可以看成一个线性表：,A=(,0, ,1, ,p,) (p=m-1,或,n-1),j,=(,0j, ,1j, ,2j, ,m-1j,) 0,jn-1,其中每个元素,j,是,一个列向量形式的线性表：,或行,向量：,i,=(,i0, ,i1, ,i2, ,in-1,) 0,im-1,5.2,数组的顺序表示和实现,一、数组元素的定位,列,优先存储,行优先存储,以行,优先存储：,loc(i,j)=loc(i,j-1)+L=loc(i,j-2)+L+L=,=loc(0,0)+(b,2,*i+j)*L,数据关系：,R,1,，,R,2,R,1,=|,0 j,2,b,2,-1,0, j,1,b,1,-2,R,2,=|0, j,1,b,1,-1, 0 j,2,b,2,-2,n,维数组地址公式,推广到,n,维数组，有：,loc(j,1,j,2,j,n,)=loc(0,0,0)+,(b,2,*,b,n,*j,1,+ b,3,*,b,n,*j,2,+,b,n,*b,n-1,*,j,n,)*L,c,n,=L, c,i-1,=b,i,*,c,i,二、数组的顺序存储表示和实现,数组顺序存储表示,# include,# define MAX_ARRAY_DIM 8,typedef,struct,ElemType,*base;,int,dim;,int,*bounds;,int,*constants;,Array;,数组维界基址，,boundsi,存放第,i,维大小,b,i,数组映像函数常量基址，共,dim,个,基本操作的函数原型说明,Status,InitArray(Array,&A,int,dim,);,/,若维数,dim,和,随后的各维长度合法，构造相应的数组,A,Status,DestroyArray(Array,/,销毁数组,A,Status Value(Array A,ElemType,/,若下标不超界，将指定的,A,的元素值赋予,e,，,并返回,OK,Status Assign(Array &A,ElemType,e,);,/,若下标不超界，将,e,的值赋予指定的,A,的元素并返回,OK,准备知识,typedef,void *,va_list,/,变长参数表类型,va_start(ap,parmN,) (,ap,=) /,va_list,类型数组,ap,中存放有函数的变长参数列表的每个值，将指针指向,parmN,后；,va_arg(ap,type,) (*(type*)(,ap,)+) /,返回,ap,数组当前指针所指单元的值，且指针下移一位；,va_end(ap,) (),2.,基本操作的算法描述,初始化,Status,InitArray(Array,&A,int,dim, ),if(dimMAX_ARRAY_DIM) return ERROR;,A.dim=dim; A.bounds=(,int,*),malloc(dim,*,sizeof(int,);,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.constantsi+1;,return OK;,求,相对地址,Locate(A,ap, off),Status 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;,获取某个元素,Status Value(Array A,Elemtype,&e,),va_start(ap,e,);,if(result=,Locate(A,ap,off,)=0) return result;,e=*(base+off); return OK;,给,某个元素重新赋值,Status Assign(Array &A,ElemType,e,),va_start(ap,e,);,if(result=,Locate(A,ap,off,)=0) return result;,*(base+off)=e; return OK;,5.3,矩阵的压缩存储,一、特殊矩阵,1. n,阶对称阵,特征：,a,ij,=,a,ji, 1,i , j n,存储空间个数,：,在数值分析中经常出现一些阶数很高的矩阵，同时矩阵中有许多值相同的元素或者零元素，为了节省存储空间，可以对这类矩阵进行压缩存储。,特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定的规律。,稀疏矩阵,n(n+1)/2,？如果是上三角对称矩阵呢,续前,以下三角为例，设,S,a,n(n+1)/2,作为,n,阶对称阵,A,的存储结构，则,S,a,k,和,a,ij,的关系为：,5.3,矩阵的压缩存储,2.,对角矩阵,d,d,d:,半带宽,2d+1,：,带宽,n*(2d+1)-d(d+1),个非零元,二、稀疏矩阵,什么是稀疏矩阵？简单说，设矩阵,A,中有,s,个非零元素，若,s,远远小于矩阵元素的总数（即,smn,），,则称,A,为稀疏矩阵。,设在的矩阵,A,中，有,t,个非零元素。令,=t/(m*n),称,为矩阵的稀疏因子,通常认为,0.05,时称之为稀疏矩阵。,二、稀疏矩阵,1.,抽象数据类型稀疏矩阵的定义（教材,P,9697,）,2.,稀疏矩阵的三元组表示,由于非零元素的分布一般是没有规律的，因此在存储非零元素,a,ij,的同时，还必须同时记下它所在的行和列的位置（,i,j),。,一个三元组,(,i,j,a,ij,),唯一确定了矩阵,A,的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,续,i,j,v,1,2,8,1,3,-1,2,5,4,3,1,-1,4,4,7,5,3,3,5,5,8,#define MAXSIZE 12500,typedef,struct,int,i,j;,Elemtype,v;Triple;,typedef,struct,Triple dataMAXSIZE+1;,int,mu,nu,tu;TSMatrix,;,3.,稀疏矩阵的转置算法,Status,TransposeSMatrix(TSMatrix,M,TSMatrix,&T),T.mu,=,M.mu,;,T.nu,=,M.mu,;,T.mu,=,M.nu,;,if(T.tu,),q=1;,for(col,=1;col=,M.nu,; +,col,),for(p,=1;p,ptr.hp,;,len,=0;,while(p,),p=p-,tp,;,len,+;,return,len,;,续,2.,求广义表的深度,int,GList_Depth(GList,L),if(!L,) return 0;,dep,=0;,if(L,-tag=LIST) p=L-,ptr.hp,;,dep,+;,else p=L-,tp,;,if(!p,) return,dep,;,if(p,-tag=ATOM),return(dep+GList_Depth(p,-,tp,) ;,else dep1=,dep+GList_Depth(p,-,ptr.hp,);,dep2=,dep+GList_Depth(p,-,tp,);,return(dep1dep2? dep1:dep2); ,Depth(LS,)=,1,，空表,0,，原子,1+MaxDepth(,i,),1i n,LS=,（,1, ,2, ,3, ,n,),小结,重点掌握：,1.,数组的定义和表示,2.,数组元素的定位公式,3.,稀疏矩阵的三元组表示,4.,广义表的特征和存储表示,理解：,稀疏矩阵的十字链表表示和存储结构创建,
展开阅读全文