《数据结构》-数据结构作业 第五章.docx

按行存储:
设n维数组第k维的下标范围是[lk,hk],记
Dk=hk-lk+1,jk=ik-lk,k=1,2,….n
显然,dk为第k维的体积(元素个数),设每个元素占c个单元,则下标为i1,i2,…in的元素的相对地址的计算公式由数学归纳法可计算为
LOC(i1,i2,…,in)=c*(j1d2d3…dn+j2d3…dn+…+jn-1dn+jn)
按列存储
由按行存储的证明可推知
LOC(i1,i2,…,in)=c*(j1+d1j2+d1d2j3+…+d1d2…dn-1jn)

用秦九韶法变换按列存储公式中的主要部分:
j1+d1j2+d1d2j3+…+d1d2…dn-1jn
=d1d2…dn-1jn+…+d1d2j3+d1j2+j1
=(dn-1jn+jn-1)d1d2…dn-2+d1d2…dn-3jn-2+…+d1d2j3+d1j2+j1
=((dn-1jn+jn-1)dn-2+jn-2)d1d2…dn-3+d1d2…dn-4jn-3+…+d1d2j3+d1j2+j1
=…
=(…(((dn-1jn+jn-1)dn-2+jn-2)dn-3+jn-3)…)d1+j1
=(…((((0*dn+jn)dn-1+jn-2)dn-2+jn-2)dn-3+jn-3)…)d1+j1
此式的值乘以元素占用的单元数c即为元素(i1,i2,…,in)的相对地址(jk=ik-lk).
此式可按下法计算:
s=0;
k=n;
while(k<=n)
{
s=s*dk+jk
k=k-1
}
用三个一维数组l[] h[] i[]分别表示n个下标的下界、上街及代求地址的元素的n个下标值。
Long GetArrayElemAddress(long l[],long h[],long i[],long n,long c)
{