【数据结构】二维数组的行优先、列优先存储问题

avatar
作者
筋斗云
阅读量:0

今天同学问我一道感觉很基础的数据结构问题,虽然答案做对了,但是原理一直比较迷,仔细看了一下题,原来是自己把自己绕进去了。。。在此记录一下,大佬如果有更好的方法,可以在评论区留言,不定期更新。

先给出行优先和列优先的计算公式:

设数组为A[m][n](m 行 n 列),要求的数组为A[i][j](i 行 j 列),L为存储单元所占空间。

        行优先:

                LOC(i,j) = LOC(0,0) + [i * n + j] *L;

        列优先:

                LOC(i,j) = LOC(0,0) + [j * m + i] *L;

设二维数组A[3][5],每个数组元素占用2个存储单元,若按列优先顺序进行存储,A[0][0]的存储地址为100,则A[2][3]的存储地址是多少?

分析:

        思路一:由题意可知,该数组是一个三行五列的数组。我一开始认为这个A[2][3]指的是数组中的第二行第三列的那个元素,也就是求A[1][2](如下图所示的位置)这个元素的地址。但是按照这个算的话结果与答案不符,反复思考后还是觉得第二种更合理,更符合题意。

        思路二:按题中说的下标起始位置是A[0][0],也就是说最大下标也就到A[2][4], 如下图所示:

既然是这样,那题中要求的A[2][3]就是对应图中的A[2][3],而不是第二行第三列元素即A[1][2]。

        所以根据列优先存储的地址计算公式:LOC(i,j) = LOC(0,0) + [j * m + i] * L可得:

        A[2][3] = 100 + [ 3 * 3 + 2 ] * 2 = 122.

        注意:

                具体问题具体分析,如果数组下标位置从[1][1]开始,需要在列数/行数那里减掉1。其他位置同理。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!