Systematic Learning of C Language Without Textbooks: Definition and Reference of 2D Arrays

<Definition and Reference of 2D Arrays>From beginner to expert, from Hello World to ACMAll content, no textbooks required!

<Lecture>

A two-dimensional array is essentially an “array of arrays” that is stored in memory in a row-major order.

1. Concept and Memory Model of 2D Arrays

1.1 What is a 2D Array?

A two-dimensional array is a data structure composed of multiple one-dimensional arrays, which can be understood as a table made up of rows and columns.

For example, a 3-row by 4-column two-dimensional array resembles a 3×4 grid, with each cell storing a data element.

Key Features:

• All elements have the same data type.

• Elements are uniquely identified by row and column indices.

• Stored contiguously in memory, following the row-major order (C language standard).

1.2 Detailed Memory Model

A two-dimensional array is actually stored linearly in memory. For example, <span>int arr[3][4]</span> is arranged in memory as follows:<span>arr[0][0]</span>, <span>arr[0][1]</span>, <span>arr[0][2]</span>, <span>arr[0][3]</span>, <span>arr[1][0]</span>, <span>arr[1][1]</span>… until <span>arr[2][3]</span>.

Memory Address Calculation: The address of <span>arr[i][j]</span> = Base Address + (i × Number of Columns + j) × Size of Element

#include <stdio.h>
int main() {
    int matrix[2][3] = {{1,2,3},{4,5,6}};    // Verify memory continuity
    printf("Memory address verification:\n");
    for(int i=0; i<2; i++) {
        for(int j=0; j<3; j++) {
            printf("matrix[%d][%d] address:%p, value:%d\n",
                    i, j, &matrix[i][j], matrix[i][j]);
        }
    }
    return 0;
}

Common Pitfalls: Many beginners mistakenly believe that a two-dimensional array is a two-dimensional structure in memory; in reality, it is stored as a one-dimensional linear array. This misunderstanding can lead to various issues in subsequent programming.

2. Definition and Initialization of 2D Arrays

2.1 Definition of 2D Arrays

Syntax format:

Type Specifier ArrayName[Number of Rows][Number of Columns];

// Correct definition example
int scores[5][3];        // 5 rows, 3 columns, storing scores of 5 students in 3 subjects
float temperature[12][31]; // Temperature records for 12 months × 31 days
char chessBoard[8][8];   // 8×8 chessboard

// Incorrect definition examples
int a[3,4];     // Error: cannot separate dimensions with a comma
int b[3][];     // Error: column size cannot be omitted
int c[][];      // Error: both row and column sizes cannot be omitted

2.2 Initialization of 2D Arrays

There are various ways to initialize a two-dimensional array, each suitable for specific scenarios.

Complete Initialization: Explicitly specify all element values

// Method 1: Initialize by grouping rows (recommended)
int matrix1[2][3] = {{1,2,3}, {4,5,6}};

// Method 2: Continuous initialization
int matrix2[2][3] = {1,2,3,4,5,6};

// Method 3: Specify row size, automatically calculate column size (rarely used)
int matrix3[][3] = {1,2,3,4,5,6}; // Automatically recognized as 2 rows

Partial Initialization: Only initialize some elements, the rest are automatically assigned 0

// First row fully initialized, second row partially initialized, the rest are 0
int matrix[3][4] = {{1,2}, {5,6,7}, {9}};// Equivalent to:
// {1,2,0,0}, {5,6,7,0}, {9,0,0,0}

In-Class Exercise 1: Analyze the following initialization result

int arr[2][2] = {{1}, {3,4}};
printf("%d %d\n", arr[0][1], arr[1][1]); // What will be output?

Common Questions and Answers:

• Q: Why can the column size be omitted but not the row size?

• A: The compiler needs to calculate the memory offset based on the column size. For example, the address of <span>arr[i][j]</span> = Base Address + (i×Number of Columns+j)×Size of Element. If the column size is unknown, the position cannot be calculated.

3. Matrix Operations and Traversal

3.1 Input and Output of 2D Arrays

Use nested loops to traverse a two-dimensional array, with the outer loop controlling rows and the inner loop controlling columns.

#include <stdio.h>
#define ROWS 3
#define COLS 3
int main() {
    int matrix[ROWS][COLS];
    int i, j;
    // Input 2D array
    printf("Please enter a %d×%d matrix:\n", ROWS, COLS);
    for(i = 0; i < ROWS; i++) {
        for(j = 0; j < COLS; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // Output 2D array (matrix format)
    printf("Matrix content:\n");
    for(i = 0; i < ROWS; i++) {
        for(j = 0; j < COLS; j++) {
            printf("%4d", matrix[i][j]); // Width 4, aligned output
        }
        printf("\n"); // New line at the end of each row
    }
    return 0;
}

3.2 Common Matrix Operations

Matrix Transposition: Swap rows and columns

// Transpose square matrix (number of rows = number of columns)
for(i = 0; i < ROWS; i++) {
    for(j = i+1; j < COLS; j++) { // j starts from i+1 to avoid repeated swaps
        // Swap matrix[i][j] and matrix[j][i]
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
}

Sum of Diagonal Elements of a Matrix

int sum = 0;
for(i = 0; i < ROWS; i++) {
    sum += matrix[i][i]; // Main diagonal
    if(i != ROWS-1-i) // Avoid double counting the center element (odd-order matrix)
        sum += matrix[i][ROWS-1-i]; // Anti-diagonal
}

In-Class Exercise 2: Write code to calculate the sum of the surrounding elements of the matrix (sum of the outermost elements)

3.3 Traversal Techniques for Multi-Dimensional Arrays

Row-Major Traversal: Outer loop for rows, inner loop for columns (efficient, conforms to memory layout)

for(i = 0; i < ROWS; i++) {
    for(j = 0; j < COLS; j++) {
        // Process matrix[i][j]
    }
}

Column-Major Traversal: Outer loop for columns, inner loop for rows (less efficient, jump access)

for(j = 0; j < COLS; j++) {
    for(i = 0; i < ROWS; i++) {
        // Process matrix[i][j]
    }
}

Performance Tip: Row-major traversal utilizes the principle of memory locality, resulting in a higher cache hit rate and significantly faster than column-major traversal.

4. Common Pitfalls and Questions

4.1 Out-of-Bounds Indexing Issues

Serious Error: C language does not check for out-of-bounds array indices, but it can lead to undefined behavior.

int arr[2][3];
arr[2][3] = 5; // Error: maximum row index is 1, maximum column index is 2

Preventive Measures: Always ensure indices are within the range of <span>0</span> to <span>Dimension Size - 1</span>.

4.2 Confusion Between Initialization and Assignment

int a[2][2];
a = {{1,2},{3,4}}; // Error: arrays cannot be assigned as a whole

// Correct Method 1: Initialize at definition
int a[2][2] = {{1,2},{3,4}};

// Correct Method 2: Assign values element by element
for(int i=0; i<2; i++)
    for(int j=0; j<2; j++)
        a[i][j] = i*2 + j + 1;

4.3 Multi-Dimensional Arrays as Function Parameters

Note: Although this will be covered in later courses, it is important to understand the basic concept: when a two-dimensional array is passed as a parameter, the number of columns must be specified.

// Correct declaration
void printMatrix(int mat[][3], int rows);

// Incorrect declaration
void printMatrix(int mat[][], int rows, int cols);

5. In-Class Practical Exercises

Exercise 1: Matrix Addition (Luogu P1009)

Problem Description: Input two n×m matrices and calculate their sum matrix. The rule for matrix addition: add corresponding elements.

Input Format:

• First line: n m (number of rows and columns of the matrix)

• Next n lines: each row of matrix A

• Next n lines: each row of matrix B

Output Format: n lines, each containing m space-separated numbers representing the sum matrix

Test Case:

Input:

2 31 2 34 5 67 8 910 11 12

Output:

8 10 1214 16 18

Reference Code Framework:

#include <stdio.h>
#define MAX 100
int main() {
    int n, m;
    int A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];
    // Read input
    scanf("%d%d", &n, &m);
    // Read matrix A
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d", &A[i][j]);
    // Read matrix B
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d", &B[i][j]);
    // Matrix addition
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            C[i][j] = A[i][j] + B[i][j];
    // Output result
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            printf("%d ", C[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Exercise 2: Find Maximum Value in Matrix (HDOJ 1062)

Problem Description: Find the maximum value in an n×m matrix and its position (row number and column number).

Input Format:

• First line: n m

• Next n lines: matrix content

Output Format: Maximum value, row number, column number (if there are multiple same maximum values, output the position of the first occurrence)

Test Case:

Input:

3 41 2 9 45 6 7 80 3 2 1

Output:

9 0 2

6. Course Summary

Today we systematically learned the core knowledge of two-dimensional arrays:

• Basic Concept: A two-dimensional array is an “array of arrays” that is stored contiguously in memory in row-major order.

• Definition and Initialization: Various initialization methods, note that the column size cannot be omitted.

• Matrix Operations: Practical techniques for traversal, transposition, diagonal operations, etc.

Key Points to Remember:

1. Two-dimensional array indices start from <span>[0][0]</span>, the maximum index is <span>[Number of Rows - 1][Number of Columns - 1]</span>

2. The memory layout is row-major contiguous storage, which affects traversal efficiency.

3. When passing arrays as function parameters, the number of columns needs to be specified (detailed in later courses).

<Exercise Class>

1. Detailed Explanation of Typical Example Problems

Example Problem 1: Matrix Transposition (Basic Operation of Two-Dimensional Arrays)

Problem Description: Given an n×m matrix, output its transposition (i.e., rows become columns and columns become rows).

Input Format: The first line contains two integers n and m, followed by n lines each containing m integers representing the matrix.

Output Format: The transposed matrix with m rows and n columns.

Test Case:

Input:

2 31 2 34 5 6

Output:

1 42 53 6

Code Implementation and Detailed Explanation:

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int matrix[100][100];  // Assume maximum 100×100 matrix
    int i, j;
    // Read original matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // Output transposed matrix (directly output in column-major order)
    for(j = 0; j < m; j++) {  // Outer loop traverses columns
        for(i = 0; i < n; i++) {  // Inner loop traverses rows
            printf("%d", matrix[i][j]);
            if(i < n - 1) {
                printf(" ");  // Add space for all but the last element
            }
        }
        printf("\n");  // New line at the end of each row
    }
    return 0;
}

Core Algorithm Analysis:

1. Essence of Transposition: Matrix transposition means <span>matrix[i][j]</span> becomes <span>result[j][i]</span>

2. Output Technique: There is no need to actually create a transposed matrix; directly output the original matrix in column-major order.

3. Boundary Handling: Pay attention to the handling of spaces and newline characters at the end of rows to ensure correct output format.

Common Pitfalls Reminder:

⚠️ After transposition, the number of rows becomes m and the number of columns becomes n; the loop order must be swapped.

⚠️ The output format must strictly conform to the requirements of the problem to avoid extra spaces.

Example Problem 2: Sum of Surrounding Elements of a Matrix (Boundary Handling)

Problem Description: Calculate the sum of the surrounding elements of an n×m matrix (i.e., the elements of the first row, last row, first column, and last column).

Input Format: The first line contains n and m, followed by n lines each containing m integers.

Output Format: The sum of the surrounding elements.

Test Case:

Input:

3 31 2 34 5 67 8 9

Output:

40

(Calculation: 1+2+3+4+6+7+8+9 = 40, note that 5 is the center element and does not participate in the calculation)

Code Implementation and Detailed Explanation:

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int matrix[100][100];
    int i, j, sum = 0;
    // Read matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // Calculate sum of surrounding elements
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            // Check if it is a surrounding element: first row/last row/first column/last column
            if(i == 0 || i == n-1 || j == 0 || j == m-1) {
                sum += matrix[i][j];
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}

Problem Solving Thought Analysis:

1. Definition of Surrounding Elements: Elements with row index 0 or n-1, or column index 0 or m-1.

2. Condition Checking: Use logical OR operators to combine multiple boundary conditions.

3. Avoiding Double Counting: The four corner elements will be checked multiple times but will not be counted more than once since each element is added only once.

Optimization Thought: For large matrices, you can traverse only the surrounding rows and columns without traversing the entire matrix to improve efficiency.

Example Problem 3: Sum of Diagonal Elements (Application of Matrix Properties)

Problem Description: Calculate the sum of the two diagonal elements of an n×n square matrix.

Input Format: The first line contains an integer n, followed by n lines each containing n integers.

Output Format: The sum of the two diagonal elements.

Test Case:

Input:

31 2 34 5 67 8 9

Output:

30

(Main diagonal: 1+5+9=15, Anti-diagonal: 3+5+7=15, total sum 30)

Code Implementation and Detailed Explanation:

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int matrix[100][100];
    int i, main_sum = 0, anti_sum = 0;
    // Read matrix
    for(i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // Calculate the sum of the two diagonals
    for(i = 0; i < n; i++) {
        main_sum += matrix[i][i];           // Main diagonal
        anti_sum += matrix[i][n-1-i];        // Anti-diagonal
    }
    // Calculate absolute difference
    int difference = abs(main_sum - anti_sum);
    printf("%d\n", difference);
    return 0;
}

Key Knowledge Points:

1. Main Diagonal: Elements with equal row and column indices, i.e., <span>matrix[i][i]</span>

2. Anti-Diagonal: Elements satisfying <span>i + j = n - 1</span>, i.e., <span>matrix[i][n-1-i]</span>

3. Center Point Handling: When n is odd, the center point will be counted twice and needs special handling.

2. Summary of Problem Types and Problem-Solving Techniques

2.1 Common Types of Two-Dimensional Array Problems

Type 1: Matrix Traversal and Output

• Characteristics: Requires traversing matrix elements in a specific order.

• Problem Solving Template: Nested loops, with the outer loop controlling rows and the inner loop controlling columns.

• Variants: Snake traversal, spiral traversal, diagonal traversal, etc.

Type 2: Matrix Operations

• Characteristics: Involves operations such as transposition, addition, multiplication, etc.

• Problem Solving Template: Strictly follow mathematical definitions to implement algorithms.

• Note: Matrix multiplication requires triple loops, with a time complexity of O(n³).

Type 3: Matrix Statistics and Queries

• Characteristics: Finding specific elements, counting elements that meet certain conditions.

• Problem Solving Template: Traversal + condition checking.

• Optimization: Utilize matrix orderliness (if ordered) for optimization.

2.2 Core Techniques for Two-Dimensional Array Operations

Technique 1: Row-Major Traversal Optimization

// Row-major traversal (recommended, cache-friendly)
for(int i = 0; i < rows; i++) {
    for(int j = 0; j < cols; j++) {
        // Process matrix[i][j]
    }
}

Technique 2: Unified Handling of Boundary Conditions

// Safe matrix access function (concept demonstration)
int getMatrixElement(int matrix[][100], int i, int j, int rows, int cols) {
    if(i >= 0 && i < rows && j >= 0 && j < cols) {
        return matrix[i][j];
    }
    return 0; // or error handling
}

Technique 3: Matrix Input and Output Template

// Standard input and output template
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        scanf("%d", &matrix[i][j]);  // Input
    }}
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        printf("%d", matrix[i][j]);   // Output
        if(j < m-1) printf(" ");     // Control space
    }
    printf("\n");  // New line at the end of the row
}

3. Condensed Essence of Knowledge Points

3.1 Key Points in Defining Two-Dimensional Arrays

1. Syntax Format:<span>Data Type ArrayName[Number of Rows][Number of Columns]</span>

2. Memory Layout: Row-major contiguous storage.

3. Address Calculation: The address of <span>matrix[i][j]</span> = Base Address + (i×Number of Columns + j)×Size of Element.

3.2 Initialization Methods for Two-Dimensional Arrays

1. Complete Initialization:<span>int arr[2][3] = {{1,2,3}, {4,5,6}}</span>

2. Partial Initialization: Unspecified elements are automatically initialized to 0.

3. Omission of Row Size:<span>int arr[][3] = {1,2,3,4,5,6}</span> (only row size can be omitted).

3.3 Core Formulas for Matrix Operations

1. Transposition: <span>result[j][i] = matrix[i][j]</span>

2. Addition: <span>C[i][j] = A[i][j] + B[i][j]</span>

3. Multiplication: <span>C[i][j] = Σ(A[i][k] × B[k][j])</span>

4. Homework Assignments

Basic Problems (Must Do)

1. Matrix Addition (Self-compiled Problem)

   Problem Description: Calculate the sum of two n×m matrices.

   Input Format: The first line contains n and m, followed by n lines of matrix A, then n lines of matrix B.

   Output Format: The sum matrix C.

   Test Case:

   Input:
   

   2 21 23 45 67 8

   
   
   Output:
   

   6 810 12

Input:

3 31 2 34 9 56 7 8

Output:

9 1 1

Input:

31 2 34 5 67 8 9

Output:

0

(Main diagonal: 1+5+9=15, Anti-diagonal: 3+5+7=15, difference is 0)

Advanced Problems (Optional)

1. Spiral Matrix (Luogu P2239)

   Problem Description: Output the elements of an n×n matrix in spiral order.

   Input Format: Integer n, representing the size of the matrix.

   Output Format: Output in spiral order.

   Test Case:

   Input:
   

   3

   
   
   Output:
   

   1 2 38 9 47 6 5

Input:

31 2 34 5 67 8 9

Output:

7 4 18 5 29 6 3

5. Answers to Homework Assignments

Answer to Problem 1: Matrix Addition

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int A[100][100], B[100][100], C[100][100];
    int i, j;
    // Read matrix A
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    // Read matrix B
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            scanf("%d", &B[i][j]);
        }
    }
    // Matrix addition
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
    // Output result
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            printf("%d", C[i][j]);
            if(j < m-1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

Answer to Problem 2: Find Maximum Value in Matrix

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int matrix[100][100];
    int i, j, max_val, max_i, max_j;
    // Read matrix and find maximum value
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
            // First element or found a larger value
            if(i == 0 && j == 0 || matrix[i][j] > max_val) {
                max_val = matrix[i][j];
                max_i = i;
                max_j = j;
            }
        }
    }
    printf("%d %d %d\n", max_val, max_i, max_j);
    return 0;
}

Answer to Problem 3: Difference of Diagonal Elements

#include <stdio.h>
#include <stdlib.h>  // For abs function
int main() {
    int n;
    scanf("%d", &n);
    int matrix[100][100];
    int i, main_sum = 0, anti_sum = 0;
    // Read matrix
    for(i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // Calculate the sum of the two diagonals
    for(i = 0; i < n; i++) {
        main_sum += matrix[i][i];           // Main diagonal
        anti_sum += matrix[i][n-1-i];        // Anti-diagonal
    }
    // Calculate absolute difference
    int difference = abs(main_sum - anti_sum);
    printf("%d\n", difference);
    return 0;
}

Answer to Problem 4: Spiral Matrix (Advanced Problem)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int matrix[100][100] = {0};
    int num = 1;
    int top = 0, bottom = n-1, left = 0, right = n-1;
    int i, j;
    // Spiral fill matrix
    while(top <= bottom && left <= right) {
        // Fill top row from left to right
        for(j = left; j <= right; j++) {
            matrix[top][j] = num++;
        }
        top++;
        // Fill right column from top to bottom
        for(i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        // Fill bottom row from right to left
        if(top <= bottom) {
            for(j = right; j >= left; j--) {
                matrix[bottom][j] = num++;
            }
            bottom--;
        }
        // Fill left column from bottom to top
        if(left <= right) {
            for(i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
    }
    // Output spiral matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            printf("%d", matrix[i][j]);
            if(j < n-1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

Answer to Problem 5: Matrix Rotation (Advanced Problem)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int original[100][100], rotated[100][100];
    int i, j;
    // Read original matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            scanf("%d", &original[i][j]);
        }
    }
    // Rotate 90 degrees: rotated[j][n-1-i] = original[i][j]
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            rotated[j][n-1-i] = original[i][j];
        }
    }
    // Output rotated matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            printf("%d", rotated[i][j]);
            if(j < n-1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

6. Common Questions and Answers

Q: How are two-dimensional arrays arranged in memory?

A: Two-dimensional arrays are stored contiguously in memory in row-major order. For example, <span>int arr[2][3]</span> is arranged in memory as:<span>arr[0][0]</span>, <span>arr[0][1]</span>, <span>arr[0][2]</span>, <span>arr[1][0]</span>, <span>arr[1][1]</span>, <span>arr[1][2]</span>.

Q: Why is row-major traversal more efficient than column-major traversal?

A: Because row-major traversal conforms to the physical storage order in memory, the CPU cache can better prefetch data, reducing cache misses and thus improving access efficiency.

Q: Why can the row size be omitted but not the column size when defining a two-dimensional array?

A: The compiler needs to calculate the memory offset based on the column size. In the formula <span>Address = Base Address + (i×Number of Columns+j)×Size of Element</span>, if the column size is unknown, the specific position cannot be calculated.

Q: How can I avoid out-of-bounds indexing in two-dimensional arrays?

A: Always ensure that the row index is within the range [0, Number of Rows – 1] and the column index is within the range [0, Number of Columns – 1]. Use strict condition checks in loops, such as <span>i < rows</span> instead of <span>i <= rows</span>.

In the next class, we will learn about:

Character Arrays and String Processing

If you have questions, feel free to comment!

Follow YunJie Algorithm, no textbooks needed, just a few clicks to systematically learn programming!