05数组和广义表1

《05数组和广义表1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、殷忧启圣，大难兴邦第五章数组和广义表继续增加线性表结构的内涵。数组结构每个子结构是由基本元素组成的大小均等的线性表。广义表结构每个子结构或是基本元素，或是由基本元素组成的大小不等的线性表结构。第一节数组的逻辑结构1_Array=(D,S,P)　定长线性表D={ai

2、ai∈ElemSet,i=0,1,2,…,n-1}S={

3、ai-1,ai∈D,i=1,2,…,n-1}2_Array=(D,S,P)定长线性表，每个元素又是定长线性表。D={ai,j

4、ai,j∈ElemSet,i=0,1,…,n1-1;j=0,1,…,n2

5、-1}S={ROW,COL}ROW={

6、i=0,1,…,n1-1;j=1,…,n2-1}COL={

7、i=1,…,n1-1;j=0,1,…,n2-1}3_Array=(D,S,P)增加层的关系二维数组：分量为一维数组的一维数组。三维数组：分量为二维数组的一维数组。数组一旦被定义，它的维数和维界就不再改变。基本操作：取值、赋值。第二节数组结构的顺序存储结构5-12数组结构是多维的，内存地址是一维的。二维数组a[n1][n2]的存储方式：行主序a0,0a0,1…a0,n2-1a1,0…a1

8、,n2-1…an1-1,n2-2an1-1,n2-1列主序a0,0a1,0…an1-1,0a0,1…an1-1,1…an1-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

9、+k*Q+lTypedefstruct{ElemType*base;intdim;　　　　维数int*bounds;　各维的维界int*constants;各维成员的大小}Array;例：数组A[3,4,5,6]的存储结构A.dim=4A.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)5-121、初始化数组结构StatusArray_Init(Array&A,intdim,intbounds[]){A.dim=dim

10、;A.bounds=(int*)malloc(dim*sizeof(int));A.constants=(int*)malloc(dim*sizeof(int));if(!A.bounds

11、

12、!A.constants)return(OVERFLOW);for(i=0;i=0;i--)A.constants[i]=A.bounds[i+1]*A.constants[i+1];//开辟数组空间elemtota

13、l=A.bounds[0]*A.constants[0];A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)return(OVERFLOW);return(OK);}2、取值ElemTypeArray_GetValue(ArrayA,intdim_i[]){intoffset;for(offset=0,i=0;i

14、的压缩存储矩阵的用途：大型方程组求解、高次方程求解真正有用的计算是矩阵的计算。从空间/时间复杂度出发，讨论矩阵的存储结构。一、特殊矩阵利用矩阵的特征，尽量减少数据的存储量。5-121、对称矩阵aij=ajiNxN矩阵的存储结构：S[N(N+1)/2]。以行主序的方式存储下三角元素：a0,0a1,0a1,1a2,0……an-1,0……an-1,n-1若i>=j:k=i*(i+1)/2+j若i

15、N(N+1)/2]，以行主序的方式存储A的下三角，则元素A[3][5]的存储位置是？3、对角矩阵非0元素的分布：以主对角线为中心的带状区域。半带宽为d，带宽为2d+1。存储方案：S[(2d+1)n]，扩展了上下二个三角区