螺旋矩阵、螺旋队列算法

### 问题描述 螺旋矩阵是一个nxn的方阵，其中元素为自然数，但像螺旋方向一样递增。举例如下： 若n = 3，螺旋矩阵为： ~~~ 1 2 3 8 9 4 7 6 5 ~~~ 若n = 4，螺旋矩阵为： ~~~ 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 ~~~ ~~~ 若n = 5，螺旋矩阵是： ~~~ ~~~ 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 ~~~ 那么如何打印这样的矩阵呢？ ### 解析 当然它的规律很简单，直接的方法就是先申请一个矩阵，然后按螺旋方向填入相应的元素，填充完毕后再打印出来。它的时间按复杂为O(n2)，已经是最优的（为什么？）。空间复杂度也为O(n2）。似乎已经很好了。 但是还不够好。 按照矩阵规律填充元素时，我们是随机访问矩阵元素的（如果可以按顺序访问，根本不用先存起来再打印）。随机访问内存，效率当然不高。所以即使时间复杂度已为最优，但那只是理论上的最优，在实践中表现并不一定就好。 假如能根据行列号直接计算出对应的矩阵元素就好了。当n给定后，这个矩阵就已经唯一确定了，那么每一个元素也是确定的。也就是说，每一个位置放什么元素仅仅取决于n。因此我们可以找到一个函数*element*(*i, j*)，将行号i和列号j映射成对应这个行列号的元素。当然这个函数肯定不是一个简单的函数，不是一眼就可以看出来的，但也并不是不可能。 现在我们就来考查一下这个矩阵有什么特点。注意观察一下螺旋矩阵的最外层，它的左上角的元素是最小的，然后沿顺时针方向递增，就如同一个环一样（比如n为4时，1, 2, ..., 12就是最外面一层环）。再注意一下里面一层，也是一样，顺时针方向递增的一个环（比如n为4时，13, 14, 15, 16就是里面一层环）。以此类推，环里面还有一层环（n为4时有2层环，n为5时有3层环，最里面一层只有一个元素25），实际上是一个圆环套圆环结构。每一圆环最关键的元素就是左上角的那一个元素。只要知道了这个元素，再加上这个正方形环的边长就可以计算出剩下的元素。设左上角元素为a，边长为l（ell），也就是边上有几个元素，并假设左上角的行号和列号均为0，其它元素的行号和列号都以它作参考，计算方法如下所示： 1. 若i == 0，*element*(*i, j*) = a + j; 2. 否则若j == 0，*element*(*i, j*) = a + 4(l-4) - (i-1) - 1; 3. 否则若i == l-1，*element*(*i, j*) = a + 4(l-4) - (l-2) - 1 - j; 4. 否则*element*(*i, j*) = a + l - 1 + i; ### 螺旋矩阵代码： ~~~ //螺旋矩阵 #include using namespace std; int a[10][10]; void Fun(int n) { int m=1; int i,j; for(i =0;ii;j--){ if(a[n-i-1][j] ==0) a[n-i-1][j] = m++; } for(j=n-i-1;j>i;j--){ if(a[j][i] ==0) a[j][i] = m++; } } if(n%2==1) a[n/2][n/2]=m; } int main(void) { int n,i; cout<<"请输入螺旋矩阵维数： "<< endl; cin>>n; cout<<"显示螺旋矩阵数值： "<< endl; for(int i=0;i #define max(a,b) ((a)<(b)?(b):(a)) #define abs(a) ((a)>0?(a):-(a)) using namespace std; int foo(int x,int y) { int t = max(abs(x),abs(y)); int u = t+t; int v = u-1; v= v*v+u; if(x == -t) v+=u+t-y; else if(y==-t) v+=3*u+x-t; else if(y ==t) v+= t-x; else v+=y-t; return v; } int _tmain(int argc, _TCHAR* argv[]) { int x ,y; int N; cout<<"请输入螺旋队列数字： "<>N; cout<<"显示螺旋队列数值： "< ';