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
/*螺旋矩阵*/
#
<stdio.h> #
<conio.h> #
RIGHT 0 #
DOWN 1 #
LEFT 2 #
UP 3 //N*N矩阵
#
N 5 void pr
Matrix( *a
, n) {
i, j; for (i = 0; i < n; i
) {
for (j = 0; j < n; j
) {
pr
f("%4d", a[i][j]); }
pr
f("\n"); }
}
void spiralMatrix(
*a, n) // *a注意接口
设计 {
i, j; //坐标 count; //计数器 k; //循环变量控制每条边上点数 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)
{
DOWN: i
; 
; LEFT: j--;
; UP: i--;
; RIGHT: j
; ; }
}
//如果刚走过
方向为UP, 4条边填完重新回到了起点步长减2, 并校正位置 
(direct 
UP) {
i
; j
; n -= 2;
}
//换方向
direct = (direct + 1) % 4;
}
(n 1) //孤点 {
a[i][j] = count;
}
}
void spiralMatrix2(
*a, n) // *a注意接口设计 {
k = 0, i = 0, j = 0; count = 1; // / 要注意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稍作改动同时注意下递归轮条件和最后退出条件即可 据此更改递归方式
接口 /*
* matrix 2维矩阵
*(x,y):第
个元素坐标 * start:第
个元素值 * width:矩阵
大小宽度 */
void spiralMatrix3(
*matrix, x, y, width, start) {
i, j; //坐标 k; //循环变量 direct; //方向指示 (width <= 0) //递归结束条件偶数时正好遇到这种情况 
; (width 1) { //矩阵大小为1时奇数 matrix[x][y] = start;
; }
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)
{
DOWN: i
; ; LEFT: j--;
; UP: i--;
; RIGHT: j
; ; }
}
direct
; }
//走完
圈, 步长减2, 并校正位置 i
; j
; width -= 2;
spiralMatrix(matrix, x+i, y+j, width, start); //再次跌代继续填充
}
void
(void) {
m[N][N] = {0}; *a[N]; i; for (i = 0; i < N; i
) {
a[i] = m[i]; //不能将 2维
直接作为参数其和指向指针指针本质区别 }
//spiralMatrix(a, N);
//spiralMatrix2(a, N);
spiralMatrix3(a, 0, 0, N, 1);
pr
Matrix(a, N); pr
f("按任意键退出..."); getch
; }
最新评论