数据结构 数组顺序存储详细介绍
数据结构 数组顺序存储 最近学习数据结构,看到数组顺序存储,很是头昏,看不懂,很多东西,这里在网上找了比较详细的资料,大家好好看注释内容: #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呢。。 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持! (编辑:我爱制作网_潮州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |