打印螺旋矩阵

 求职过程遇到的一道面试题，当时没有做出来，回来想出几种方法，其中大多是“蛮力”解法，不得不陷入一堆的 i、j 循环之中。最后想出一种递归解法，现记录如下。
题目如下：
输入N, 打印 N*N 螺旋矩阵
比如 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
 
递归解法如下：
 
+--------------------------> X 轴
| 1   2   3   4
|  12 13 14 5
|  11 16 15 6
|  10 9   8   7
|
Y轴
 
设元素1的坐标为(0,0)，元素13的坐标为（1，1），……，任一元素的坐标为（x,y）
以下为完整代码：
//功能：打印螺旋矩阵
//参数说明：matrix ：螺旋矩阵         (x，y) ：第一个元素的坐标
//          start ：第一个元素的值     n ：矩阵的大小
void SetMatrix(int **matrix, int x, int y, int start, int n) {
       int i, j;
       if (n <= 0)
              return;
       if (n == 1) {
              matrix[x][y] = start;
              return;
       }
       for (i = x; i < x + n-1; i++)          /* 上部 */
              matrix[y][i] = start++;
       for (j = y; j < y + n-1; j++)          /* 右边 */
              matrix[j][x+n-1] = start++;
       for (i = x+n-1; i > x; i--)              /* 底部 */
              matrix[y+n-1][i] = start++;
       for (j = y+n-1; j > y; j--)              /* 左边 */
              matrix[j][x] = start++;
       SetMatrix(matrix, x+1, y+1, start, n-2);     /* 递归 */
}
 
void main() {
       int i, j;
       int n;
    int **matrix; //螺旋矩阵（二维数组）
      
       scanf("%d", &n);
       matrix = (int **)malloc(n * sizeof(int *)); //为矩阵分配空间
       for (i = 0; i<n; i++)
              matrix[i] = (int *)malloc(n * sizeof(int));
      
SetMatrix(matrix, 0, 0, 1, n);
 
       //打印螺旋矩阵
       for(i = 0; i < n; i++) {
              for (j = 0; j < n; j++)
                     printf("%4d", matrix[i][j]);
       printf("\n");
       }
}
 

 

//我修改的Java代码：
public class TestSpiralMatrix {

	
	//功能：打印螺旋矩阵
	//参数说明：matrix ：螺旋矩阵         
          //(x，y) ：第一个元素的坐标
          //start ：第一个元素的值     n ：矩阵的大小
	private static void SetMatrix(int[][] matrix, int x, int y, int start, int n) {
	       int i, j;
	       if (n <= 0)
	              return;
	       if (n == 1) {
	              matrix[x][y] = start;
	              return;
	       }
//感觉原来的代码有点问题，我把x和y顺序调整了过来
	       for (i = y; i < y + n-1; i++)          /* 上部 */
	              matrix[x][i] = start++;
	       for (j = x; j < x + n-1; j++)          /* 右边 */
	              matrix[j][y+n-1] = start++;
	       for (i = y+n-1; i > y; i--)              /* 底部 */
	              matrix[x+n-1][i] = start++;
	       for (j = x+n-1; j > x; j--)              /* 左边 */
	              matrix[j][y] = start++;
	       SetMatrix(matrix, x+1, y+1, start, n-2);     /* 递归 */
	}
	 


	public static void main(String[] args) {
		int i, j;
//	       int n=15;
	       int n=4;
	       int[][] matrix = new int[n][n]; //螺旋矩阵（二维数组）
	       
	       SetMatrix(matrix, 0, 0, 1, n);
	 
	       //打印螺旋矩阵
	       for(i = 0; i < n; i++) {
	              for (j = 0; j < n; j++)
	                     System.out.printf("%4d", matrix[i][j]);
	              System.out.printf("\n");
	       }
	}

}

 
 

 

运行结果， n = 15 时
 
1      2        3       4        5       6        7        8       9        10     11      12     13     14   15
56   57      58     59     60     61      62     63      64     65     66      67     68     69   16
55   104   105   106   107   108   109   110   111   112   113   114   115   70   17
54   103   144   145   146   147   148   149   150   151   152   153   116   71   18
53   102   143   176   177   178   179   180   181   182   183   154   117   72   19
52   101   142   175   200   201   202   203   204   205   184   155   118   73   20
51   100   141   174   199   216   217   218   219   206   185   156   119   74   21
50   99     140   173   198   215   224   225   220   207   186   157   120   75    22
49   98     139   172   197   214   223   222   221   208   187   158   121   76    23
48   97     138   171   196   213   212   211   210   209   188   159   122   77    24
47   96     137   170   195   194   193   192   191   190   189   160   123   78    25
46   95     136   169   168   167   166   165   164   163   162   161   124   79    26
45   94     135   134   133   132   131   130   129   128   127   126   125    80   27
44   93     92     91     90      89     88      87     86      85     84     83      82      81   28
43   42     41     40     39      38     37      36     35      34     33     32      31      30   29

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/blackeagle_/archive/2006/02/22/606341.aspx

评论

1 楼 rootxue 2011-09-10  

大哥不用释放内存吗