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) 增加层的关系
二维数组:分量为一维数组的一维数组。
三维数组:分量为二维数组的一维数组。
数组一旦被定义,它的维数和维界就不再改变。
基本操作:取值、赋值。
第二节数组结构的顺序存储结构
数组结构是多维的,内存地址是一维的。
二维数组a[n1][n2]的存储方式:
行主序
a0,0
a0,1
…
a0,n2-1
a1,0
…
a1,n2-1
…
an1-1,n2-2
an1-1,n2-1
列主序
a0,0
a1,0
…
an1-1,0
a0,1
…
an1-1,1
…
an1-2,n2-1
an1-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+l
Typedef struct
{ ElemType *base;
int dim; 维数
int *bounds; 各维的维界
int *constants; 各维成员的大小
}Array;
例:数组A[3,4,5,6]的存储结构
=4
[]={3,4,5,6}
[]={120,30,6,1}
A[i,j,k,l]的地址: +(i*120+j*30+k*6+l)
1、初始化数组结构
Status Array_Init(Array &A,int dim,int bounds[])
{ =dim;
=(int *)malloc(dim*sizeof(int));
=(int *)malloc(dim*sizeof(int));
if(! || !) return(OVERFLOW);
for(i=0;i<dim;i++) [i]=bounds[i];
for([dim-1]=1,i=dim-2;i>=0;i--)
[i]=[i+1]*[i+1];
//开辟数组空间
elemtotal=[0]*[0];
=(ElemType *)malloc(elemtotal*sizeof(ElemType));
if(!) return(OVERFLOW);
return(OK);
}
2、取值
ElemType Array_GetValue(Array A,int dim_i[])
{ int offset;
for(offset=0,i=0;i<;i++)
offset+=[i]* dim_i[i];
return(*(+offset));
}
第三节矩阵的压缩存储
矩阵的用途:
大型方程组求解、高次方程求解
真正有用的计算是矩阵的计算。
从空间/时间复杂度出发,讨论矩阵的存储结构。
一、特殊矩阵
利用矩阵的特征,尽量减少数据的存储量。
1、对称矩阵 ai