数据结构数组顺序存储详细介绍

2024-02-22 17:45:03 57

数据结构数组顺序存储

最近学习数据结构，看到数组顺序存储，很是头昏，看不懂，很多东西，这里在网上找了比较详细的资料，大家好好看注释内容：

#include
#defineMAX_ARRAY_DIM8//假设数组维数的最大值为8
typedefstruct{
ElemType*base;//数组元素基址，由InitArray分配
intdim;//数组维数
int*bounds;//数组维界基址，由InitArray分配
int*constants;//数组映象函数常量基址，由InitArray分配
}Array;

StatusInitArray(Array&A,intdim,...){//这里用的是“可变参”形参方式。它主要解决维数不定的问题。
//举例：设有4维数组，各维分别是：4,5,6,7（这些数字是随意给的），那么，调用方式：
//InitArray(ar,4,4,5,6,7);
//ar其中，ar也是假设的变量名称,4表示数组有4维,4,5,6,7这4个数是各维大小
//如果是5维的，那么就这样：
//InitArray(ar,5,第一维数，第二维数，第三维数，第四维数，第五维数);
//若维数dim和随后的各维长度合法，则构造相应的数组A，并返回OK。
if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;
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=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,0,0,0)~(0,4,5,6)和(1,0,0,0)~(1,4,5,6)这两大块，而这两大块中的每一块都有5*6*7个元素，这正好就是A.constants[0]中所存放的数据啊！
//现在应该明白了吧！
returnOK;
}

statusLocate(ArrayA,va_listap,int&off){
//若ap指示的各下标值合法，则求出该元素在A中相对地址off。
off=0;
for(i=0;i=A.bounds[i])returnOVERFLOW；
off+=A.constants[i]*ind;
}
returnOK;

补充：为什么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];这个公式的来历。当然，我只是很简单的解释了，很多细节需要你自己考虑，因为语言表示起来太复杂了，不知道怎么表述。。。
其实你仔细看A.constants[i]=A.bounds[i+1]*A.constants[i+1];，这是一个递推公式，把它展开的话，下面我就把constants[i]简写为coni，bounds[i]简写为boni那么coni=bon[i+1]*con[i+1]=bon[i+1]*bon[i+2]*con[i+2]=bon[i+1]*bon[i+2]*bon[i+3]*con[i+3]=bon[i+1]*bon[i+2]*bon[i+3]*...*bon[dim]你看这个公式是不是就是相当于上面说的高度*长度*宽度？刚才那个bon[dim]应该写成bon[dim-1]不过这个不影响理解。

然后我们看最后一维，例如上面例子的宽度，宽度+1是不是就正好内存地址+1呢？于是对应宽度这个最后的维度，每次地址只需+1就能访问下一个元素，因此bon[dim-1]也就是最后一维的，是不是就应该等于1呢。。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

数据结构 数组顺序存储详细介绍

热门推荐

随机推荐

数据结构数组顺序存储详细介绍