数据结构 数组顺序存储详细介绍
|
数据布局 数组次序存储 最近进修数据布局，看到数组次序存储，极端头昏，看不懂，许多对象，这里在网上找了较量具体的资料，各人好悦目注释内容：
#include<stdarg.h>
#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8
typedef struct {
ElemType *base; //数组元素基址，由InitArray分派
int dim; //数组维数
int *bounds; //数组维界基址，由InitArray分派
int *constants; //数组映象函数常量基址，由InitArray分派
}Array;
Status InitArray(Array &A,int dim,...){//这里用的是“可变参”形参方法。它首要办理维数不定的题目。
//举例：设有4维数组，各维别离是：4,5,6,7（这些数字是随意给的），那么，挪用方法：
//InitArray(ar,4,7);
//ar个中，ar也是假设的变量名称,4暗示数组有4维,7这4个数是各维巨细
//假如是5维的，那么就这样：
//InitArray(ar,第一维数，第二维数，第三维数，第四维数，第五维数);
//若维数dim和随后的各维长度正当，则结构响应的数组A，并返回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);
//若各维长度正当，则存入A.bounds，并求出A的元素总数elemtotal。
elemtotal=1;
va_start(ap,dim); //ap为va_list范例，是存放变长参数表信息的数组。
for (i=0;i<dim;++i){
A.bounds[i]=va_arg(ap,int);//从这里可以看出，A.bounds数组中，存放的是各维的巨细
if (A.bounds[i]<0) return UNDERFLOW;
elemtotal * = A.bounds[i];//各维数之积，天然是数组中元素的总个数
}
va_end(ap);
A.base=(ElemType *)malloc(elemtotal *sizeof(ElemType));//这个就是“多维数组”的存储本质：一维数组！
//用一维方法暗示多维数组后（着实，从打点和行使的角度看，内存就只有一维这么一种情势），存在怎样按“多维”的逻辑角度定位元素的题目。再说清晰些：假设前面所讲的4维数组，其元素用下标情势暗示，范畴为：(0,0)到(3,6)。对付恣意下标（在有用范畴内）(i1,i2,i3,i4)所对应的元素，转换到“一维”空间后，其下标应该是什么？这就是这个措施后头要处理赏罚的首要题目。
if (!A.base) exit (OVERFLOW):
//求映象函数的常数ci（i为下标），并存入A.constants[i-1]，i=1，...dim。
A.constants=(int *)malloc(dim *sizeof(int));
if (!A.constants)exit (OVERFLOW);
//早年面的4维数组为例子，个中A.bounds[0]=4，A.bounds[1]=5，A.bounds[2]=6，A.bounds[3]=7。
//跟踪下面的措施：
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];
//说到这里，这个题目就清楚了：A.constants中的元素，是辅佐定位用的。好比说：对付(2,0)这个下标的元素，应该越过前面的(0,0)~(0,6)和(1,0)~(1,6)这两大块，而这两大块中的每一块都有5*6*7个元素，这正好就是A.constants[0]中所存放的数据啊！
//此刻应该大白了吧！
return OK;
}
status Locate(Array A,va_list ap,int &off){
//若ap指示的各下标置魅正当，则求出该元素在A中相对地点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;
增补：为什么A.constants[dim-1] bounds存的就是每一维内里的个数，constants生涯的是每一个维度假如下标增进1，谁人对应到内存空间的下标应该增进几多。提及来较量抽象，我们假设是3维，就较量轻易说清晰了，起首把3维看作有bounds[0]那么高，对付每一个0到bounds[0]-1的范畴内，就是一个平面，这个平面有bounds[1]那么长，bounds[2]那么宽。那么，我们把高=0，长=0，宽=0对应到内存的第一个位置，高=0，长=0，宽=1的对应到第二个位置，那么高=0，长=1，宽=0应该放在什么位置呢？显然就是0+bounds[2]这个位置。那么高=1，长=0，宽=0的谁人元素应该在哪个位置呢？显然是高=0这一个平面放完了之后的谁人位置，高=0这个平面有长度*宽度那么多个元素，也就是bounds[1]*bounds[2]这么多个元素，以是高=1，长=0，宽=0这个元素就应该在0+bounds[1]*bounds[2]这个位置，对吧。假设尚有第四维度，我们假设这个维度代表时刻吧，当时刻=0，高=0，长=0，宽=0的元素放在内存第0个位置，那么时刻=1，高=0，长=0，宽=0的元素是不是应该放在0+bound[1]*bound[2]*bound[3]这个位置呢。这就是A.constants[i]=A.bounds[i+1] * A.constants[i+1];这个公式的泉源。虽然，我只是很简朴的表明白，许多细节必要你本身思量，由于说话暗示起来太伟大了，不知道怎么表述。。。 然后我们看最后一维，譬喻上面例子的宽度，宽度+1是不是就正好内存地点+1呢？于是对应宽度这个最后的维度，每次地点只需+1就能会见下一个元素，因此bon[dim-1]也就是最后一维的，是不是就应该便是1呢。。 感激阅读，但愿能辅佐到各人，感谢各人对本站的支持！ （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
