數(shù)據(jù)結(jié)構(gòu)教程第十八課數(shù)組的順序表示與實(shí)現(xiàn)

教學(xué)目的： 掌握數(shù)組的定義,數(shù)組的順序表示方法
    教學(xué)重點(diǎn)： 數(shù)組的定義,數(shù)組的順序表示方法
    教學(xué)難點(diǎn)： 數(shù)組的順序表示方法
    授課內(nèi)容：
    一、數(shù)組的定義
    幾乎所有的程序設(shè)計(jì)語言都把數(shù)組類型設(shè)定為固有類型。
    以抽象數(shù)據(jù)類型的形式討論數(shù)組的定義和實(shí)現(xiàn)，可以讓我們加深對數(shù)組類型的理解。
    數(shù)組的定義：
    ADT Array{
    數(shù)據(jù)對象:ji=0,...,bi-1,i=1,2,...,n;
    D={aj1j2...jn|n(>0)稱為數(shù)組的維數(shù),bi是數(shù)組第i維的長度,ji是數(shù)組元素的第i維下標(biāo),aj1j2...jn (-ElemSet}
    數(shù)據(jù)關(guān)系:R={R1,R2,...Rn|
    Ri={|
    0<=jk<=bk-1,1<=k<=n且k<>i,
    0<=ji<=bi-2,aj1...ji...jn,
    aj1...ji+1 ...jn(-D,i=2,...n}
    基本操作:
    InitArray(&A,n,bound1,...,boundn)
    若維數(shù)和各維長度合法,則構(gòu)造相應(yīng)的數(shù)組A,并返回OK.
    DestroyArray(&A)
    操作結(jié)果:銷毀數(shù)組A.
    Value(A,&e,index1,...,indexn)
    初始條件:A是n維數(shù)組,e為元素變量,隨后是n個(gè)下標(biāo)值.
    操作結(jié)果:若各下標(biāo)不超界,則e賦值為所指定的A的元素值,并返回OK.
    Assign(&A,e,index1,...,indexn)
    初始條件:A是n維數(shù)組,e為元素變量,隨后是n個(gè)下標(biāo)值.
    操作結(jié)果:若下標(biāo)不超界,則將e的值賦給 所指定的A的元素,并返回OK.
    }ADT Array
    列向量的一維數(shù)組:
    a00 a01 a02 ... a0,n-1
    a10 a11 a12 ... a1,n-1
    ... ... ... ... ...
    am-1,0 am-1,1 am-1,2 ... am-1,n-1
    行向量的一維數(shù)組:
    把二維數(shù)組中的每一行看成是一個(gè)數(shù)據(jù)元素,這些數(shù)據(jù)元素組成了一個(gè)一維數(shù)組A.
    A0 a00 a01 a02 ... a0,n-1
    a10 a11 a12 ... a1,n-1
    ... ... ... ... ...
    am-1,0 am-1,1 am-1,2 ... am-1,n-1
    二、數(shù)組的順序表示和實(shí)現(xiàn)
    以行序?yàn)橹餍虻拇鎯Ψ绞?
    a00 a01 a02 ... a0,n-1 a10 a11 a12 ... a1,n-1 ... am-1,0 am-1,1 am-1,2 ... am-1,n-1
    數(shù)組的順序存儲表示和實(shí)現(xiàn):
    #include
    #define MAX_ARRAY_DIM 8
    typedef struct {
    ElemType *base;
    int dim;
    int *bounds;
    int *constants;
    }Array;
    Status InitArray(Array &A,int dim,...);
    Status DestroyArray(Array &A);
    Status Value(Array A,ElemType &e,...);
    Status Assign(Array &A,ElemType e,...);
    基本操作的算法描述:
    Status InitArray(Array &A,int dim,...){
    if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;
    A.dim=dim;
    A.bounds=(int *)malloc(dim *sizeof(int));
    if(!A.bounds) exit(OVERFLOW);
    elemtotal=1;
    va_start(ap,dim);
    for(i=1;i    A.bounds[i]=va_arg(ap,int);
    if(A.bounds[i]<0) return UNDERFLOW;
    elemtotal*=A.bounds[i];
    }
    va_end(ap);
    A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
    if(!A.base) exit(OVERFLOW);
    A.constants=(int *)malloc(dim*sizeof(int));
    if(!A.constants) exit(OVERFLOW);
    A.constants[dim-1]=1;
    for(i=dim-2;i>=0;--i)
    A.constants[i]=A.bounds[i+1]*A.constants[i+1];
    return OK;
    }
    Status DestoyArray(Array &A){
    if(!A.base) return ERROR;
    free(A.base); A.base=NULL;
    if !(A.bounds) return ERROR;
    free(A.bounds); A.bounds=NULL;
    if!(A.constatns) return ERROR;
    free(A.constants); A.constants=NULL;
    return OK;
    }
    Status Locate(Array A,va_list ap,int &off){
    off=0;
    for(i=0;i
    ind=va_arg(ap,int);
    if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
    off+=A.constants[i]*ind;
    }
    return OK;
    }
    Status Value(Array A,ElemType &e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0 return result;
    e=*(A.base+off);
    return OK;
    }
    Status Assign(Array &A,ElemType e,...){
    va_start(ap,e);
    if((result=Locate(A,ap,off))<=0) return result;
    *(A.base+off)=e;
    return OK;
    }
    三、小結(jié)
    數(shù)組的存儲方式。
    數(shù)組的基本操作種類