|
C/C++面试之算法系列－－打印 N*N 螺旋矩阵
VIA和EMC都曾经笔过这个试题
输入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
/*螺旋矩阵*/
#include <stdio.h>
#include <conio.h>
#define RIGHT 0
#define DOWN 1
#define LEFT 2
#define UP 3
//N*N矩阵
#define N 5
void printMatrix(int *a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("%4d", a[i][j]);
}
printf("\n");
}
}
void spiralMatrix(int *a[], int n) // int *a[]注意接口的设计
{
int i, j; //坐标
int count; //计数器
int k; //循环变量，控制每条边上的点数
int direct; //方向指示，控制行列增减
i = 0; //起点（0,0）
j = 0;
count = 1;
direct = RIGHT;
while (n > 1) //为方形才有下列代码
{
for (k = 0; k < n - 1; k++) //每条边上的点数为(2n+2(n-2))/4＝4(n-1)/4= n-1
{
a[i][j] = count++;
switch (direct)
{
case DOWN:
i++;
break;
case LEFT:
j--;
break;
case UP:
i--;
break;
case RIGHT:
j++;
break;
}
}
//如果刚走过的方向为UP, 四条边填完重新回到了起点，步长减2, 并校正位置
if (direct == UP)
{
i++;
j++;
n -= 2;
}
//换方向
direct = (direct + 1) % 4;
}
if (n == 1) //孤点
{
a[i][j] = count;
}
}
void spiralMatrix2(int *a[], int n) // int *a[]注意接口的设计
{
int k = 0, i = 0, j = 0;
int count = 1;
// / Examda提示: 要注意i、j的变化，画个图就明白了，按照螺旋矩阵的顺序赋值就行了！
for(; k < (n+1)/2; k++ )
{
while( j < n-k ) a[i][j++] = count++; i++; j--; /// 上面的一行
while( i < n-k ) a[i++][j] = count++; i--; j--; /// 右边的一列
while( j > k-1 ) a[i][j--] = count++; i--; j++; /// 下面的一行
while( i > k ) a[i--][j] = count++; i++; j++; /// 左边的一列
}
}
此法各个while中的循环条件都不一样，每走完一条边就需要重新矫正ij，比上面一个方法复杂
递归方式，将spiralMatrix稍作改动，同时注意下递归一轮的条件和最后退出的条件即可
Examda提示: 据此更改递归方式的函数接口
/*
* matrix 二维矩阵数组
*（x,y）：第一个元素的坐标
* start：第一个元素的值
* width：矩阵的大小宽度
*/
void spiralMatrix3(int *matrix[], int x, int y, int width, int start)
{
int i, j; //坐标
int k; //循环变量
int direct; //方向指示
if (width <= 0) //递归结束条件，偶数时正好遇到这种情况
return;
if (width == 1) { //矩阵大小为1时，奇数
matrix[x][y] = start;
return;
}
i = 0;
j = 0;
direct = RIGHT;
while(direct< UP+1) //走一圈即退出
{
for (k = 0; k < width - 1; k++)
{
matrix[x+i][y+j] = start++;
switch (direct)
{
case DOWN:
i++;
break;
case LEFT:
j--;
break;
case UP:
i--;
break;
case RIGHT:
j++;
break;
}
}
direct++;
}
//走完一圈, 步长减2, 并校正位置
i++;
j++;
width -= 2;
spiralMatrix(matrix, x+i, y+j, width, start); //再次跌代继续填充
}
void main(void)
{
int m[N][N] = {0};
int *a[N];
int i;
for (i = 0; i < N; i++)
{
a[i] = m[i]; //不能将二维数组直接作为参数，其与指向指针的指针本质不同
}
//spiralMatrix(a, N);
//spiralMatrix2(a, N);
spiralMatrix3(a, 0, 0, N, 1);
printMatrix(a, N);
printf("按任意键退出...");
getch();
}
|
