数据结构严尉敏编(共95张课件).pptxVIP

5.1数组的类型定义;5.1数组的类型定义;typedefElemtypearray2[m][n];

等价于：

typedefElemtypearray1[n];

typedefarray1array2[m];

;ADTArray{

数据对象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

数据关系：

R＝{R1,R2,...,Rn}

Ri＝{aj1,...ji,...jn,aj1,...ji+1,...jn|0?jk?bk-1,

1?k?n且k?i,0?ji?bi-2,i=2,...,n}

基本操作:

}ADTArray;InitArray(A,n,bound1,...,boundn)

操作结果：若维数n和各维长度合法，构造相应的数组A，并返回OK。;Assign(A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。;二维数组的抽象定义:;5.2数组的顺序表示和实现;;二维数组A中任一元素aij的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×L;推广到一般情况，可得到n维数组数据元素存储位置的映象关系：;容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。;下面是数组顺序存储表示和实现;StatusInitArray(ArrayA,intdim,…)

{//若维数dim和各维长度合法，构造相应的数组A，并返回OK

if(dim1||dimMAX_ARRAY_DIM)returnERROR;

A.dim=dim;

A.bounds=(int*)malloc(dim*sizeof(int));

if(!A.bounds)exit(OVERFLOW);

//若各维长度合法,则存入A.bounds,并求出元素总数elemtotal

elemtotal=1;

va_start(ap,dim);//ap为va_list类型,存放变长参数表信息的数组

for(i=0;idim;i++)

{

A.bounds[i]=va_arg(ap,int);;Tail(F)=(c,(d))

dep=GlistDepth();

新的广义表由新的表头和表尾构成。

cc…an-1n-1an-10an-11…an-1n-1

324

for(t=1;col=M.

05的矩阵为稀疏矩阵。

//va_arg和va_end的定义,其中va_list为字符指针类型

StatusTransposeSMattrix(TSMatrixM,TSMatrixT){

}TSMatrix;//稀疏矩阵类型

if(arowM.

C=(a,(b,c,d))D=(A,B,C)

base);A.;StatusDestroyArray(ArrayA)

{//销毁数组A

if(!A.base)returnERROR;

free(A.base);A.base=NULL;

if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;

if(!A.constants)returnERROR;

free(A.constants);A.constants=NULL;

returnOK;

}//DestroyArray

;StatusLocate(ArrayA,va_listap,intoff)

{//若ap所指下标合法,则求出元素在数组中的相对位置off

//最终off带回在存储该元素时已经存储的元素个数;StatusValue(ArrayA,ElemTypee,…)//如果用VC实现;5.3矩阵的压缩存储;对角线）以下的元素，其存储形式如图所示：;若i≧j，则aij在下三角形