如何使用指针在 C 中以螺旋方式遍历矩阵？

Question

这是以螺旋方式遍历矩阵并将遍历打印为数组的算法 Python:

def spiralTraverse(array):
    result = []
    startRow, endRow = 0, len(array) - 1
    startCol, endCol = 0, len(array[0]) - 1
    
    while startRow <= endRow and startCol <= endCol:
        for col in range(startCol, endCol + 1):
            result.append(array[startRow][col])
            
        for row in range(startRow + 1, endRow + 1):
            result.append(array[row][endCol])
            
        for col in reversed(range(startCol, endCol)):
            if startRow == endRow:
                break
            result.append(array[endRow][col])
            
        for row in reversed(range(startRow + 1, endRow)):
            if startCol == endCol:
                break
            result.append(array[row][startCol])
            
        startRow += 1
        endRow -= 1
        startCol += 1
        endCol -= 1
        
    return result

所以如果样本输入是

array = [[1, 2, 3, 4],[12, 13, 14, 5],[11, 16, 15, 6],[10, 9, 8, 7]]

输出将是

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

我试图用指针将其转换为 C，但该函数无法打印最终数组。该文件编译但带有与多维数组相关的警告作为 spiralTraverse() 中的参数。我从 main() 调用 spiralTraverse 函数，如下所示：spiralTraverse(*array[r], r, c)，其中 r=rows 和 c=cols分别是行数和列数。

这是我所做的：

void spiralTraverse(int *vector[], int rows, int cols)
{
    int i, indx_col, indx_row;
    int indx_array = 0;
    int startRow = 0;
    int endRow = rows-1;
    int startCol = 0;
    int endCol = cols-1;
    int new_array[rows*cols];

    
        while ((startRow <= endRow) && (startCol <= endCol))
        {
            for (indx_col=startCol;indx_col<endCol+1;indx_col++)
                new_array[indx_array++] = *(*(vector+startRow)+indx_col);
            
            for (indx_row=startRow+1;indx_row<endRow+1;indx_row++)
                new_array[indx_array++] = *(*(vector+indx_row)+endCol);

            for (indx_col=endCol;indx_col>startCol;indx_col--)
            {
                if (startRow == endRow)
                    break;
                new_array[indx_array++] = *(*(vector+endRow)+indx_col);
            }
            for (indx_row=endRow;indx_row>startRow+1;indx_row--)
            {
                if (startCol == endCol)
                    break;
                new_array[indx_array++] = *(*(vector+indx_row)+startCol);
            }
            startRow++;
            endRow--;
            startCol++;
            endCol--;
        }

        puts("");
        puts("The array below displays the elements in spiral order");
        for (i=0;i<(rows*cols);i++)
            printf("%d, ", new_array[i]);
        puts("");
    }
}

为什么程序无法打印我的最终一维数组？

Answer 1

函数参数

The file compiles but with warnings related to the multidimensional array as argument in spiralTraverse().

有关在 C:

中分配和传递多维数组作为函数参数的正确方法的详细信息，请参阅其他问答

What's the point of VLA anyway?
How to pass a multidimensional array to a function in C and C++

给定数组

int array[][4] = {
    { 1,  2,  3, 4},
    {12, 13, 14, 5},
    {11, 16, 15, 6},
    {10,  9,  8, 7}
};

函数签名可以是其中之一

// Declaring m as a Variable Length Array (since C99, optional from C11)
void spiral_traverse(int rows, int cols, int m[rows][cols]);

// or as a pointer to arrays of size 4
void spiral_traverse(int rows, int *m[4]);

保持简单

该算法的 C 实现在循环的外部存在问题，特别是第二个和第三个：

for ( indx_row = startRow + 1; indx_row < endRow + 1; indx_row++ )
//                                      ^^^^^^^^^^^^
    /* ... */ = *(*(vector+indx_row)+endCol);

for ( indx_col = endCol; indx_col > startCol; indx_col-- )
//    ^^^^^^^^^^^^^^^^^
    /* ... */ = *(*(vector+endRow)+indx_col);

第一个（好吧，第二个）循环访问的最后一个元素是 vector[endRow][endCol]，这是另一个循环首先访问的同一个。

以下版本生成 expected output。

请注意，我更改了循环的极端值。

#include <stdio.h>

void spiral_traverse(int rows, int cols, int m[rows][cols]);

int main(void)
{
    int array[][4] = {
        { 1,  2,  3, 4},
        {12, 13, 14, 5},
        {11, 16, 15, 6},
        {10,  9,  8, 7}
    };
    spiral_traverse(4, 4, array);
    spiral_traverse(3, 4, array); // Elements are stored row-major.
}

void spiral_traverse(int rows, int cols, int m[rows][cols])
{ // m is a Variable Length Array        ^^^^^^^^^^^^^^^^^
    int startRow = 0;
    int endRow = rows - 1;
    int startCol = 0;
    int endCol = cols - 1;
    int new_array[rows*cols]; // <-- Another VLA

    int i = 0;
    while ((startRow <= endRow) && (startCol <= endCol))
    {
        for (int col = startCol; col < endCol; ++col, ++i)
        { //                         ^              ^^^^^
            new_array[i] = m[startRow][col];
        } //               ^^^^^^^^^^^^^^^^      
        
        for (int row = startRow; row < endRow; ++row, ++i)
        { //         ^^^^^^^^^^      ^              ^^^^^        
            new_array[i] = m[row][endCol];
        } //               ^^^^^^^^^^^^^^

        for (int col = endCol; col > startCol; --col, ++i)
        { //         ^^^^^^^^      ^                ^^^^^           
            new_array[i] = m[endRow][col];
        } //               ^^^^^^^^^^^^^^

        for (int row = endRow; row > startRow; --row, ++i)
        { //         ^^^^^^^^      ^                ^^^^^
            new_array[i] = m[row][startCol];
        } //               ^^^^^^^^^^^^^^^^

        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }

    puts("\nThe array below displays the elements in spiral order");
    for (i=0;i<(rows*cols);i++)
        printf("%d, ", new_array[i]);
    putchar('\n');
}

当然，如果目标只是打印元素，你真的不需要将它们全部复制到另一个数组中。此外，引入函数指针参数，该函数可以变得更通用（参见 here）。

如何使用指针在 C 中以螺旋方式遍历矩阵？

How to traverse a matrix in a spiral fashion in C using pointers?

c

python-3.x

pointers

函数参数

保持简单