Data structure array sequential storage is described in detail

The data structure array is stored sequentially

Recently learn data structure, see array order storage, very dizzy, do not understand, a lot of things, here on the Internet to find more detailed information, you look good annotation content:

#include<stdarg.h>  
#define MAX_ARRAY_DIM 8 // Suppose that the maximum number of dimensions of the array is 8 
typedef struct {
 ElemType *base;  // Array element base address by InitArray distribution 
 int dim;  // The array dimension 
 int *bounds;  // Array dimension bounded base address by InitArray distribution 
 int *constants;  // Array mapping function constant base address, by InitArray distribution 
}Array;

Status InitArray(Array &A,int dim,...){// The "variable parameter" method is used here. It mainly solves the problem of variable dimension. 
// Example: set 4 Dimension array, each dimension is: 4,5,6,7 (these Numbers are given at random), so, how to call: 
//InitArray(ar, 4, 4, 5, 6, 7);
//ar Among them, ar Also the name of the hypothetical variable , 4 That means the array has 4 d , 4, 5, 6, 7 this 4 The number is the size of each dimension 
// If it is 5 D 'or, so that's it: 
//InitArray(ar, 5,  The first 1 The first dimension 2 The first dimension 3 The first dimension 4 The first dimension 5 dimension );
// If the dimension dim And the subsequent dimension length is valid, then the corresponding array is constructed A And return OK . 
if (dim<1 ||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim*sizeof(int));
if (!A.bounds) exit(OVERFLOW);
// If the dimension length is legal, then deposit A.bounds And find out A The total number of elements elemtotal . 
elemtotal=1;
va_start(ap,dim); //ap for va_list Type is an array of variable - length parameter list information. 
for (i=0;i<dim;++i){
 A.bounds[i]=va_arg(ap,int);// As you can see here, A.bounds In an array, you store the dimensions 
 if (A.bounds[i]<0) return UNDERFLOW;
 elemtotal * = A.bounds[i];// The product of each dimension is, of course, the total number of elements in the array 
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal *sizeof(ElemType));// This is the storage nature of "multidimensional arrays" : 1 Dimensional array. 
// with 1 After the dimensional representation of the multi-dimensional array (in fact, from the perspective of management and use, memory is only 1 D so 1 ), there is the problem of how to position elements logically from a "multidimensional" perspective. To be clear: assume what was said earlier 4 Dimension array, whose elements are represented in subscript form, and the range is: (0,0,0,0) to (3,4,5,6) . For any subscript (within the valid range) (i1, i2, i3, i4) The corresponding element is converted to" 1 What should be the subscript after the dimension space? This is the main problem to be addressed later in the program. 
if (!A.base) exit (OVERFLOW):
// Find the constant of the image function ci ( i Is the subscript), and is stored A.constants[i-1] . i=1 . ...dim . 
A.constants=(int *)malloc(dim *sizeof(int));
if (!A.constants)exit (OVERFLOW);
// Before the 4 Dimensional array as an example, where A.bounds[0]=4 . A.bounds[1]=5 . A.bounds[2]=6 . A.bounds[3]=7 . 
// Trace the following procedures: 
A.constants[dim-1]=1;//A.constants[3] = 1
for (i=dim-2;i>=0;--i)//A.constants[2] = 7 . A.constants[1] = 6*7 . A.constants[0] = 5*6*7
 A.constants[i]=A.bounds[i+1] * A.constants[i+1];
// Here, the question becomes clear: A.constants Is used to help locate. For example: (2,0,0,0) This subscript element should go beyond the one in front (0,0,0,0)~(0,4,5,6) and (1,0,0,0)~(1,4,5,6) These two pieces, and each of these two pieces 1 Block has 5*6*7 Elements. That's exactly what it is A.constants[0] The data stored in ah! 
// Now you should understand! 
return OK;
}

status Locate(Array A,va_list ap,int &off){
// if ap If the indicated subscript values are valid, the element is found at A Medium relative address off . 
 off=0;
 for (i=0;i<A.dim;++i){
 ind=va_arg(ap,int);
 if (ind<0 || ind>=A.bounds[i]) return OVERFLOW ; 
 off + = A.constants[i] * ind;
 }
 return OK;

Additional: why A.constants[dim-1]

bounds stores the number of subscripts per dimension, and constants stores the number of subscripts per dimension. If the subscript is increased by 1, how much should the subscript corresponding to the memory space be increased? It's a little bit more abstract, but let's say it's 3 dimensions, so it's a little bit easier to explain. First of all, think of 3 dimensions as being bounds[0] high, and for every 0 up to bounds[0] minus 1, it's a plane, which is bounds[1] long and bounds[2] wide. So, if we take the height =0, the length =0, and the width =0 to the first location, the height =0, the length =0, and the width =1 to the second location, where should we put the height =0, the length =1, and the width =0? It's clearly 0 plus bounds. So where does the height =1, the length =0, and the width =0 go? Well, obviously the height is equal to 0 at the end of this plane, the height is equal to 0 and the plane has length times width, which is bounds[1] times bounds[2], so the height is equal to 1, the length is equal to 0, and the width is equal to 0 should be at 0 plus bounds[1] times bounds[2], right. Let's assume that there is a fourth dimension, let's assume that this dimension represents time, so that the elements with time =0, height =0, length =0, and width =0 are placed in the 0th place of memory, so should the elements with time =1, height =0, length =0, and width =0 be placed in the position of 0+bound[1]*bound[2]*bound[3]. This is A. constants[i]= A. bounds[i+1] * A. constants[i+1]; The origin of this formula. Of course, I just explained very simply, many details need you to consider, because the language is too complex to express, do not know how to express...
A.constants[i]= A. bounds[i+1] * A. constants[i+1]; This is a recurrence formula, and if I expand it out, I'm going to write constants[i] as coni, bounds[i] boni then con i= bon[i+1]*con[i+1]=bon[i+1]*bon[i+2]*con[i+2] = bon bon [i + 1] * * bon [i + 2] [i + 3] * con [i + 3] = bon bon [i + 1) * * [i + 2] bon [i + 3] *... *bon[dim] do you think this formula is equivalent to the height * length * width mentioned above? That bon[dim] should have been written as bon[dim-1] but that doesn't bother you.

And then let's look at the last 1 dimension, like the width of the example above, is the width plus 1 exactly the same as the memory address plus 1? So for the last dimension, the width, you only need +1 to access 1 element at a time, so bon[dim-1], which is the last dimension, should be equal to 1.

Thank you for reading, I hope to help you, thank you for your support of this site!