[2018年最新整理]05数组和广义表1.doc

第五章 数组和广义表 继续增加线性表结构的内涵。 数组结构 每个子结构是由基本元素组成的大小均等的线性表。 广义表结构 每个子结构或是基本元素，或是由基本元素组成的大小不等的线性表结构。 本章学习要点： 掌握数组的相关概念 掌握特殊矩阵的压缩存储方式 掌握稀疏矩阵的存储方法 掌握广义表的相关运算 掌握广义表的存储结构 掌握广义表的基本运算的实现 第一节 数组的逻辑结构 1_Array=(D, S, P)　定长线性表 D = {ai| ai∈ElemSet, i=0,1,2,…, n-1} S = {ai-1,ai| ai-1,ai∈D, i=1,2,…,n-1} 2_Array=(D, S, P) 定长线性表，每个元素又是定长线性表。 D = {ai,j| ai,j∈ElemSet, i=0,1,…,n1-1; j=0,1,…,n2-1} S = {ROW,COL} ROW={ai,j-1,ai,j| i=0,1,…,n1-1; j=1,…,n2-1} COL={ai-1,j,ai,j| i=1,…,n1-1; j=0,1,…,n2-1} 3_Array=(D, S, P) 增加层的关系 基本操作：取值、赋值。 第二节 数组结构的顺序存储结构 数组结构是多维的，内存地址是一维的。 存储方式：行主序，列主序 以行主序为例： 一维： 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+l Typedef struct { ElemType *base; int dim;　　　　 维数 int *bounds; 　 各维元素个数 int *constants; 各维包含的基本元素个数 }Array; 例：数组A[3,4,5,6]的存储结构 A.dim=4 A.bounds[]={3,4,5,6} A.constants[]={120,30,6,1} A[i,j,k,l]的地址: A.base+(i*120+j*30+k*6+l) 1、初始化数组结构 void 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) { printf(“overflow!”); return; } for(i=0;idim;i++) A.bounds[i]=bounds[i]; for(A.constants[dim-1]=1,i=dim-2;i=0;i--) A.constants[i]=A.bounds[i+1]*A.constants[i+1]; //开辟数组空间 elemtotal=A.bounds[0]*A.constants[0]; A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType)); if(!A.base) { printf(“overflow!”); return; } printf(“OK!”); } 2、取值 ElemType Array_GetValue(Array A,int dim_i[])//dim[]存放要求元素的下表 { int offset; for(offset=0,i=0;iA.dim;i++) offset+=A.constants[i]* dim_i[i]; return(*(A.base+offset)); } 补充：计算二维数组元素地址的通式设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0 一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 第三节 矩阵的压缩存储 矩阵的用途： 大型方程组求解、高次方程求解 真正有用的计算是矩阵的计算。 从空间/时间复杂度出发： 一、特殊矩阵 利用矩阵的特征，尽量减少数据的存储量。 对称矩阵 aij=aji NxN矩阵的存