C语言转置矩阵如何高效实现？

Of course! In C, "transposition" most commonly refers to a matrix transposition. This is a fundamental operation in linear algebra where you convert rows of a matrix into columns.

Let's break it down with a clear explanation, code examples, and a discussion of other possible meanings.

Matrix Transposition (The Most Common Meaning)

What is it?

Given a matrix A with dimensions M x N (M rows and N columns), its transpose, denoted A^T or A', is a new matrix with dimensions N x M.

The element at position [i][j] in the original matrix becomes the element at position [j][i] in the transposed matrix.

Visual Example:

Original Matrix A (2x3):

1  2  3
4  5  6

Transposed Matrix A^T (3x2):

1  4
2  5
3  6

Key Point: Square vs. Rectangular Matrices

• Square Matrix (M x M): If the matrix has the same number of rows and columns (e.g., 3x3), the transposed matrix will have the same dimensions. You can perform the "in-place" transposition, meaning you can modify the original matrix without needing a second one.
• Rectangular Matrix (M x N, where M ≠ N): If the matrix is not square (e.g., 2x3), the transposed matrix will have different dimensions (3x2). You cannot perform an in-place transposition because the shape of the matrix changes. You must create a new matrix to store the result.

Example 1: Transposing a Rectangular Matrix (The General Case)

This is the most common scenario. We'll create a function that takes a source matrix and its dimensions and returns a new, transposed matrix.

The Code

#include <stdio.h>
#include <stdlib.h> // For malloc and free
// Function to print a matrix
void printMatrix(int **matrix, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d\t", matrix[i][j]);
        }
        printf("\n");
    }
}
// Function to transpose a rectangular matrix
// It returns a new matrix (the caller is responsible for freeing it)
int** transposeMatrix(int **matrix, int rows, int cols) {
    // 1. Allocate memory for the transposed matrix (cols x rows)
    int **transposed = (int **)malloc(cols * sizeof(int *));
    if (transposed == NULL) {
        fprintf(stderr, "Memory allocation failed for rows.\n");
        exit(1);
    }
    for (int i = 0; i < cols; i++) {
        transposed[i] = (int *)malloc(rows * sizeof(int));
        if (transposed[i] == NULL) {
            fprintf(stderr, "Memory allocation failed for columns.\n");
            exit(1);
        }
    }
    // 2. Copy elements from the original matrix to the transposed one
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            transposed[j][i] = matrix[i][j]; // The core transposition logic
        }
    }
    return transposed;
}
// Function to free the memory allocated for a matrix
void freeMatrix(int **matrix, int rows) {
    for (int i = 0; i < rows; i++) {
        free(matrix[i]);
    }
    free(matrix);
}
int main() {
    int rows = 2, cols = 3;
    // Allocate and initialize the original matrix
    int **matrix = (int **)malloc(rows * sizeof(int *));
    matrix[0] = (int[]){1, 2, 3};
    matrix[1] = (int[]){4, 5, 6};
    printf("Original Matrix (%dx%d):\n", rows, cols);
    printMatrix(matrix, rows, cols);
    // Transpose the matrix
    int **transposed = transposeMatrix(matrix, rows, cols);
    printf("\nTransposed Matrix (%dx%d):\n", cols, rows);
    printMatrix(transposed, cols, rows);
    // Free the allocated memory
    freeMatrix(matrix, rows);
    freeMatrix(transposed, cols);
    return 0;
}

Explanation

1. Memory Allocation: We first allocate memory for the new transposed matrix. Its dimensions are swapped: cols rows and rows columns.
2. Element Copy: We use nested loops to iterate through the original matrix. The key line is transposed[j][i] = matrix[i][j];. Notice how the row and column indices are swapped.
3. Memory Management: Since we use malloc, we are responsible for freeing the memory with free to prevent memory leaks. The freeMatrix helper function makes this easier.
4. Inapplicability to Square Matrices: This code works for square matrices too, but it's less efficient than an in-place solution because it allocates new memory even when it's not strictly necessary.

Example 2: In-Place Transposition of a Square Matrix

For a square matrix (e.g., 3x3), we can save memory by transposing the matrix directly without creating a new one. The trick is to only swap the elements above the main diagonal with those below it. If we swap all elements, we would end up swapping them twice and getting the original matrix back.

The Code

#include <stdio.h>
// Function to print a square matrix
void printSquareMatrix(int **matrix, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("%d\t", matrix[i][j]);
        }
        printf("\n");
    }
}
// Function to transpose a square matrix in-place
void transposeSquareMatrix(int **matrix, int size) {
    for (int i = 0; i < size; i++) {
        // Start the inner loop from i+1, not 0.
        // This ensures we only swap the upper triangle with the lower triangle.
        for (int j = i + 1; j < size; j++) {
            // Swap matrix[i][j] with matrix[j][i]
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}
int main() {
    int size = 3;
    // Allocate and initialize a square matrix
    int **matrix = (int **)malloc(size * sizeof(int *));
    for (int i = 0; i < size; i++) {
        matrix[i] = (int *)malloc(size * sizeof(int));
    }
    int counter = 1;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            matrix[i][j] = counter++;
        }
    }
    printf("Original Square Matrix (%dx%d):\n", size, size);
    printSquareMatrix(matrix, size);
    // Transpose in-place
    transposeSquareMatrix(matrix, size);
    printf("\nTransposed Square Matrix (%dx%d):\n", size, size);
    printSquareMatrix(matrix, size);
    // Free memory
    for (int i = 0; i < size; i++) {
        free(matrix[i]);
    }
    free(matrix);
    return 0;
}

Explanation

The core of this function is the nested loop and the swap logic:

• for (int i = 0; i < size; i++): Iterates through each row.
• for (int j = i + 1; j < size; j++): This is the crucial part. It iterates from the element after the diagonal (i+1) to the end of the row. This prevents swapping an element with itself and avoids double-swapping.
• int temp = ...; ... = ...; ... = temp;: A standard three-step swap to exchange the values at matrix[i][j] and matrix[j][i].

Other Possible Meanings of "Transposition"

While matrix transposition is the most likely meaning, "transposition" can refer to other concepts in programming:

a) String Transposition (Cipher)

A simple transposition cipher rearranges the letters of a plaintext according to a regular system. For example, a "rail fence cipher" writes the text in a zig-zag pattern and then reads it off row by row.

// Conceptual example of a simple transposition cipher
void simpleTransposeCipher(char *text, int key) {
    // This is a placeholder for a real cipher implementation
    // A real one would involve writing text into a grid and reading it out differently
    printf("Applying a transposition cipher with key %d to '%s'\n", key, text);
}

b) Data Transposition (Swapping Variables)

This is a general term for swapping the values of two variables, which is a fundamental operation. The matrix transposition code above uses this concept when it swaps matrix[i][j] and matrix[j][i].

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int x = 10, y = 20;
printf("Before swap: x = %d, y = %d\n", x, y);
swap(&x, &y);
printf("After swap:  x = %d, y = %d\n", x, y);

Summary

When you hear "transposition" in a C programming context, especially related to arrays or data structures, it's almost certainly referring to matrix transposition.