05数组和广义表1.doc

殷忧启圣，大难兴邦第五章 数组和广义表继续增加线性表结构的内涵。数组结构每个子结构是由基本元素组成的大小均等的线性表。广义表结构每个子结构或是基本元素，或是由基本元素组成的大小不等的线性表结构。第一节 数组的逻辑结构 1_Array=(D, S, P)定长线性表 D = ai| aiElemSet, i=0,1,2, n-1 S = | ai-1,aiD, i=1,2,n-1 2_Array=(D, S, P) 定长线性表，每个元素又是定长线性表。D = ai,j| ai,jElemSet, i=0,1,n1-1; j=0,1,n2-1S = ROW,COLROW=| i=0,1,n1-1; j=1,n2-1COL=| i=1,n1-1; j=0,1,n2-13_Array=(D, S, P) 增加层的关系 二维数组：分量为一维数组的一维数组。 三维数组：分量为二维数组的一维数组。数组一旦被定义，它的维数和维界就不再改变。基本操作：取值、赋值。第二节 数组结构的顺序存储结构数组结构是多维的，内存地址是一维的。二维数组an1n2的存储方式：行主序a0,0a0,1a0,n2-1a1,0a1,n2-1an1-1,n2-2an1-1,n2-1列主序a0,0a1,0an1-1,0a0,1an1-1,1an1-2,n2-1an1-1,n2-1示例行主序列主序 多维数组的存储方式：行主序先排最右下标，从右到左；列主序先排最左下标，从左向右。以行主序为例，计算数组元素的地址： 一维： LOC(ai) =base+i 二维(MxN)： LOC(ai,j) =base+i*N +j 三维(MxNxP)： LOC(ai,j,k) =base+i*N*P +j*P +k 四维(MxNxPxQ)：LOC(ai,j,k,l)=base+i*N*P*Q+j*P*Q+k*Q+lTypedef struct ElemType *base; int dim; 维数 int *bounds; 各维的维界 int *constants; 各维成员的大小Array;例：数组A3,4,5,6的存储结构 A.dim=4 A.bounds=3,4,5,6 A.constants=120,30,6,1 Ai,j,k,l的地址: A.base+(i*120+j*30+k*6+l) 1、初始化数组结构Status Array_Init(Array &A,int dim,int bounds) A.dim=dim; A.bounds=(int *)malloc(dim*sizeof(int);A.constants=(int *)malloc(dim*sizeof(int);if(!A.bounds | !A.constants) return(OVERFLOW); for(i=0;i=0;i-)A.constantsi=A.boundsi+1*A.constantsi+1; /开辟数组空间elemtotal=A.bounds0*A.constants0; A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType); if(!A.base) return(OVERFLOW);return(OK);2、取值ElemType Array_GetValue(Array A,int dim_i) int offset; for(offset=0,i=0;i=j: k=i*(i+1)/2+j若i Sk, k=i(2d+1)+d+(j-i)改进方案：S(2d+1)n-2d，去掉数组前后2d个0。aij = Sk, k=i(2d+1)+(j-i)4、小结练习的意义：培养摸索数据规律的感觉。二、稀疏矩阵之三元组表稀疏因子=t/(m*n)稀疏矩阵：稀疏因子T (以T为中心，按需点菜) =M.data下标T.dataijeije0130001101010110301340212-521-532320245043140322053330333064250void TSMatrix_Transpose(TSMatrix M,TSMatrix &T) int k,col,i;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;for(k=0,col=0; colM.nu; col+) /找M中所有列 for(i=0; iT (以M为中心，按位就座)辅助数据结构：num：M中每列(T中每行)的三元组个数。=pos：T中每行第一个三元组的下标。pos0=0;posj=posj-1+numj-1; j1,M.nu-1 =下标01234num12121pos01346 M.data下标T.dataijeije0130001101010110301340212-521-532320245043140322053330333064250void TSMatrix_FastTranspose(TSMatrix M,TSMatrix &T) int i,j,k,numMAX,posMAX;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; /统计M中每列的三元组个数 for(i=0;iM.nu;i+) numi=0;for(i=0;iM.tu;i+) numM.datai.j+;/计算pos数组for(pos0=0,i=1;iM.nu;i+) posi=posi-1+numi-1;/快速转置for(i=0;i十字链表。三、稀疏矩阵之十字链表十字链表的存储结构：真正等价于矩阵的逻辑结构。1、十字链表typedef struct OLNode /结点类型 int i,j; ElemType e; struct OLNode *right,*down;OLNODE; typedef struct int mu,nu,tu; OLNODE *rhead,*chead; /行、列头结点表CrossList;图示：4x5矩阵的十字链表，含非0数：(1,1:1) (3,1:2) (3,4:3)用right构成行链表，用down构成列链表。2、建立、打印十字链表的算法按行主序打印矩阵Mvoid CrossList_Print(CrossList M) OLNODE *p; int i; printf(%d,%d,%dn,M.mu,M.nu,M.tu); for(i=0; iright) printf(%d,%d:%dn,p-i,p-j,p-e);根据三元组顺序表T，建立十字链表Mvoid CrossList_Create(CrossList &M, TSMatrix T) int i; CrossList_Init(M,T.mu,T.nu); for(i=0; iT.tu; i+) / 插入各个三元组结点 CrossList_Insert(M, T.datai);初始化十字链表结构Mvoid CrossList_Init(CrossList &M,int mu,int nu) int i;M.mu=mu; M.nu=nu; M.tu=0; /初始化行头结点表、列头结点表 M.rhead=(OLNODE *)malloc(M.mu*sizeof(OLNODE); for(i=0; iM.mu; i+) M.rheadi.right=NULL; M.chead=(OLNODE *)malloc(M.nu*sizeof(OLNODE) for(i=0; iright;p; pre=p,p=p-right)if(p-j = Item.j) break; / 定位 if(p=NULL | p-j Item.j) newp=(OLNODE *)malloc(sizeof(OLNODE); newp-i=Item.i; newp-j=Item.j; newp-e=Item.e; newp-right=p; pre-right=newp; M.tu+; else / 遇到同类项 p-e+=Item.e; if(p-e=0) pre-right=p-right; / 将*new结点插入列链表中 for(pre=&M.cheadItem.j,p=pre-down; p; pre=p,p=p-down)if(p-i = Item.i) break; / 定位 if(p=N