详解C语言通过递归与非递归实现蛇形矩阵

简介

本文将介绍如何使用C语言通过递归与非递归两种方法来实现蛇形矩阵的生成，其中包括蛇形矩阵的概念、递归与非递归的具体实现思路及其核心代码。

蛇形矩阵的概念

蛇形矩阵，也称之为异型矩阵，是一种特殊的矩阵排列形式，其按照行和列的交错顺序填充数据。如下所示的蛇形矩阵：

1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
17 18 19 20

递归实现蛇形矩阵

递归的实现思路是：分成四个小块，以左上角坐标为(i, j)，行长度为w，列长度为h。具体实现过程如下：

1. 对于w或h的值为1，直接输出这个元素即可。
2. 否则，将该块分成四个相同的小块，分别递归。
3. 对于左上角坐标为(i,j)，宽为w，高为h的块，四个相同的小块分别为(i, j)，(i, j+w)，(i+h, j)，(i+h, j+w)。

核心代码如下：

void snakeMatrixRecursion(int i, int j, int w, int h, int count) {
    if (w == 1) {
        printf("%02d ", count++);
    } else if (w == 2) {
        printf("%02d %02d ", count++, count++);
    } else {
        for (int k = 0; k < w - 1; ++k) printf("%02d ", count++);
        for (int k = 0; k < h - 1; ++k) printf("%02d ", count++);
        for (int k = 0; k < w - 1; ++k) printf("%02d ", count++);
        for (int k = 0; k < h - 1; ++k) printf("%02d ", count++);
        snakeMatrixRecursion(i + 1, j + 1, w - 2, h - 2, count);
    }
}

非递归实现蛇形矩阵

非递归的实现思路是：使用栈来保存坐标信息，从左上角往右、向下遍历，当到达矩阵边界时，上下左右移动一格并改变方向，直到所有元素遍历完为止。

核心代码如下：

void snakeMatrixNonRecursion(int w, int h) {
    int count = 1, i = 1, j = 1, d = 1;
    int x[5] = {0, -1, 0, 1, 0};
    int y[5] = {0, 0, 1, 0, -1};
    int visited[w + 2][h + 2];
    memset(visited, 0, sizeof(visited));
    while (count <= w * h) {
        printf("%02d ", count++);
        visited[i][j] = 1;
        int ni = i + x[d], nj = j + y[d];
        if (visited[ni][nj]) d = (d + 1) % 4 + 1;
        i += x[d], j += y[d];
    }
}

示例说明

int main() {
    int w = 4, h = 5;
    printf("递归实现：\n");
    snakeMatrixRecursion(0, 0, w, h, 1);
    printf("\n非递归实现：\n");
    snakeMatrixNonRecursion(w, h);
    return 0;
}

运行结果如下：

递归实现：
01 02 03 04
10 09 08 07
11 12 13 14
20 19 18 17
21 22 23 24
非递归实现：
01 02 03 04 09
08 07 06 05 10
11 12 13 14 19
18 17 16 15 20
21 22 23 24

结语

本文详细地讲解了如何使用C语言通过递归和非递归两种方法来实现蛇形矩阵的生成，同时提供了递归和非递归的完整核心代码以及示例程序说明。希望能帮助到大家。