数据结构(严蔚敏C语言版)——数组（顺序数组）

Status InitArray(Array &A, int dim,...)  //初始化数组 
Status DestoryArray(Array &A)  //销毁数组 
Status Locate(Array A,va_list ap,int &off)  //获取元素下标对应的地址 
Status Value(Array A,ElemType &e,...)  //获取元素的值 
Status Assgin(Array &A,ElemType e,...)  //为元素赋值 
复制

#include<cstdio>
#include<cstdlib> 
#include<cstdarg>  标准头文件，提供三个宏(va_start、va_arg和va_end)
          用于存取变长参数表
#define ElemType int 
#define Status int 
#define MAX_ARRAY_DIM 8    数组维数的最大值 
typedef struct{
  ElemType *base;    数组元素基址，由InitArray分配
  int dim;  数组维数
  int *bounds;  数组维界基址，由InitArray分配
  *
  假设数组的维数是3，每个维数的值分别为（2,3,4），则这相当于是嵌套数组
  bounds[0] = 2  将数组分成两大部分 
  bounds[1] = 3  两大部分中，每一部分分为三部分（共六部分） 
  bounds[2] = 4   六部分中每一部分有4个值 
  array = (((x,x,x,x),(x,x,x,x),(x,x,x,x)),((x,x,x,x),(x,x,x,x),(x,x,x,x)))
  */
  int *constants;    数组映像函数常量基址，由InitArray分配 
  *
  就是每一个元素的在数组中的位置，如上面的三维数组元素需要24个元素位置 
  如 array[1][2][3]的地址为：3*4+2*4+3=24（就是最后一个元素的位置，数组小标从0开始） 
  */ 
}Array;


//初始化数组 
Status InitArray(Array &A, int dim,...){
  //若维数dim和各维长度合法，则构造相应的数组A，并返回OK
  if(dim < 1 || dim >MAX_ARRAY_DIM ){
    printf("维数不合法\n");
    return 0;
  } 
  A.dim = dim;
  A.bounds = (int *)malloc(dim * sizeof(int));  //分配大小为维数的命名空间，用于存储每一个维数的值，并返回基址 
  if(!A.bounds){
    printf("存储空间分配失败\n");
    return 0; 
  }
  //若各维长度合法，则存入A.bounds，并求出A的元素总数elemtotal 
  int elemtotal = 1;
  va_list ap;    //ap为va_list类型，是存放变长参数表信息的数组
  va_start(ap,dim);  // 从dim后开始读取  
  for(int i=0;i<dim;i++){    //循环，为bounds赋值 
    A.bounds[i] = va_arg(ap,int);    //从参数表中读取各个维数对应的值 
    if(A.bounds[i]<0)  //如果维数输入为0，则错误 
      return 0;
    elemtotal *= A.bounds[i];   //总数=维数对应值的乘积值 
  } 
  va_end(ap);    //结束参数的读取 
  A.base = (ElemType *)malloc(elemtotal * sizeof(ElemType));    //分配大小为元素个数的命名空间，并返回基址
  if(!A.base){
    printf("存储空间分配失败\n");
    return 0; 
  }
  //求映像函数常量Ci，并存入A.constants[i-1]，i=1~dim
  A.constants = (int *)malloc(dim * sizeof(int));    
  /*分配大小为维数的命名空间，用于存储每一个维数元素的个数，并返回基址
  例如 A.constants[0] = 12
     A.constants[1] = 4
     A.constants[2] = 1
  */
  if(!A.constants){
    printf("存储空间分配失败\n");
    return 0; 
  } 
  A.constants[dim-1] = 1;    //最后一维  L=1，指针的增减以元素的大小为单位
  for(int i=dim-2;i>=0;--i)  //循环给constants赋值 
    A.constants[i] = A.bounds[i+1] * A.constants[i+1];
  printf("初始化成功\n");
  return 0; 
}


//销毁数组 
Status DestoryArray(Array &A){
  //销毁数组A
  if(!A.base){
    printf("销毁失败，未能找到元素基址\n");
    return 0;
  }
  free(A.base);    //释放基址空间 
  A.base = NULL;     //数组元素基址置为空


  if(!A.bounds){
    printf("销毁失败，未能找到维界基址\n");
    return 0;
  }
  free(A.bounds);    //释放基址空间 
  A.bounds = NULL;     //数组维界基址置为空


  if(!A.constants){
    printf("销毁失败，未能找到映像函数常量基址\n");
    return 0;
  }
  free(A.constants);    //释放基址空间 
  A.constants = NULL;     //数组映像函数常量基址置为空
  printf("销毁数组成功\n");
  return 0; 
}


//获取元素下标对应的地址 
Status Locate(Array A,va_list ap,int &off){
  //若ap指示的各下标值合法，则求出该元素在A中相对地址off
  off = 0;
  for(int i=0;i<A.dim;i++){
    int ind = va_arg(ap,int);
    if(ind<0 || ind>=A.bounds[i]){
      printf("数组小标越界\n");
      return 0;
    }
    //公式对应P92 
    off += A.constants[i]*ind;    //每一维的小标程每一维的偏移量 
  } 
}


//获取元素的值 
Status Value(Array A,ElemType &e,...){
  //A是n维数组，e为元素变量，随后是n个下标值
  //若各下标不超界，则e赋值为所指定的A的元素值
  va_list ap;
  int off;
  Status result; 
  va_start(ap,e);
  if((result = Locate(A,ap,off))<=0){
    return result;
  } 
  e = *(A.base+off);
  printf("值为：%d\n",e); 
  return 0;
}


//为元素赋值 
Status Assgin(Array &A,ElemType e,...){
  //A是n维数组，e为元素变量，随后是n个下标值
  //若各下标不超界，则e赋值为所指定的A的元素值
  va_list ap;
  int off;
  Status result;
  va_start(ap,e);
  if((result = Locate(A,ap,off))<=0){
    return result;
  } 
  *(A.base+off) = e;
  printf("赋值为：%d成功\n",e); 
  return 0;
}


int main(){
  Array array;
  int value;
  int dim = 3;  //维数3 
  //初始化
  InitArray(array,dim,2,3,4);    //三个维数分别为2,3,4 
  printf("%d %d %d \n",array.bounds[0],array.bounds[1],array.bounds[2]);
  printf("%d %d %d \n",array.constants[0],array.constants[1],array.constants[2]);
  Assgin(array,666,1,2,3);
  Value(array,value,1,2,3);
  return 0; 
}
复制