最近拜读了DK大神的程序设计艺术，感觉DK不愧为大神，思路有一种让人眼前一亮的感觉。另外一个感觉就是，这部书的难度真的不是一般的大。。。由于本人数学知识有限，部分习题看了答案也要思考半天才能明白。为了勉励自己能坚持下去，从今天开始不定期的把感悟较深的地方贴出来。本人浅见，欢迎大家拍砖。。。

2013.3.15-变长数组的分配策略

原问题大概是这样的：
    设计一个可扩充矩阵(m*n)，开始时为1*1(m=n=1)，然后通过加上新的行和列变成(m+1)*n或m*(n+1)的大小。给出一种分配策略，使得矩阵中的所有元素A[I,J]占据大小为m*n的连续的内存单元，当矩阵增长时，没有元素改变地址。

没看过的人建议先思考10分钟。。。。

==============================================================

这个其实就是在连续的内存地址中存储一个2维数组，并且所有元素的内存地址已经分配就不再变动。

我们先做如下定义：

矩阵中的第I行，J列的元素：A[I,J]

地址函数Loc(x)：x的地址。

第I行元素的首地址：R[I]

第J列元素的首地址：C[J]

下面来看分配函数：

1.行分配函数：

假设当前一共有n列，当增加一行后(m=m+1)，新增加的行I的地址为：

R[I]=Loc(A[I,0])=Loc(A[0,0])+n*I

2.列分配函数：

假设当前一共有m列，当增加一列后(n=n+1)，新增加的列J的地址为：

C[J]=Loc(A[0,J])=Loc(A[0,0])+m*J

3.A[I,J]的分配函数：

1）当第J列的地址值大于等于第I行的地址值时：

Loc(A[I,J])=I+C[J]   (C[J]>=R[I])

2）其余情况

Loc(A[I,J])=J+R[I]（其余情况）

是不是有点晕？我们举一个实例来说明：

假设有一个m行n列的矩阵，初始为

m=1，n=1。

C[0]=Loc(0,0)=0

R[0]=Loc(0,0)=0

按如下步骤进行扩充：

A：先来看行列首元素的地址分配

1.增加一列：

m=1，n=n+1=2；

C[1]=Loc(A[0,1])=Loc(A[0,0])+1*1=1

2.增加一行：

m=m+1=2，n=2；

R[1]=Loc(A[1,0])=Loc(A[0,0])+2*1=2

3.再增加一行：

m=m+1=3，n=2；

R[2]=Loc(A[2,0])=Loc(A[0,0])+2*2=4

4.增加一列：

m=3，n=n+1=3；

C[2]=Loc(A[0,2])=Loc(A[0,0])+3*2=6

5.再增加一列：

m=3，n=n+1=4；

C[3]=Loc(A[0,3])=Loc(A[0,0])+3*3=9

内存分配表（初始值m=1，n=1）：

B：再来看元素的地址分配

1. I=1,J=1

∵C[1]<R[1] (C[1]=1,R[1]=2)，

∴取第二种分配函数:Loc(A[I,J])=J+R[I]，

    Loc(A[1,1])=1+R[1]=1+2=3；

2.I=1,J=2

∵C[2]>=R[1] (C[2]=6,R[1]=2)，

∴取第一种分配函数:Loc(A[I,J])=I+C[J]，

    Loc(A[1,2])=1+C[2]=1+6=7；