数组

数组是C语言中重要的数据结构，用于存储相同类型的多个元素。数组在内存中连续存储，可以通过索引快速访问元素。本章将详细介绍C语言数组的定义和使用。

一维数组

数组的定义和初始化

/*
 * 一维数组的定义和初始化
 */

#include <stdio.h>

int main(void)
{
    /* 数组声明 */
    int arr1[5];  /* 声明一个包含5个整数的数组 */
    
    /* 数组初始化 */
    /* 方式1：完全初始化 */
    int arr2[5] = {1, 2, 3, 4, 5};
    
    /* 方式2：部分初始化（未初始化的元素为0） */
    int arr3[5] = {1, 2};  /* 等价于 {1, 2, 0, 0, 0} */
    
    /* 方式3：省略大小（根据初始化列表确定） */
    int arr4[] = {1, 2, 3, 4, 5};  /* 大小为5 */
    
    /* 方式4：全部初始化为0 */
    int arr5[5] = {0};  /* {0, 0, 0, 0, 0} */
    
    /* 方式5：指定初始化器（C99） */
    int arr6[5] = {[0] = 1, [2] = 3};  /* {1, 0, 3, 0, 0} */
    
    /* 访问数组元素 */
    printf("arr2[0] = %d\n", arr2[0]);  /* 第一个元素 */
    printf("arr2[4] = %d\n", arr2[4]);  /* 最后一个元素 */
    
    /* 修改数组元素 */
    arr2[0] = 10;
    printf("修改后 arr2[0] = %d\n", arr2[0]);
    
    /* 数组大小 */
    printf("arr2的大小: %zu 字节\n", sizeof(arr2));
    printf("arr2的元素个数: %zu\n", sizeof(arr2) / sizeof(arr2[0]));
    
    /* 遍历数组 */
    printf("\n遍历arr2: ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n");
    
    return 0;
}

数组的输入输出

/*
 * 数组的输入输出
 */

#include <stdio.h>

#define SIZE 5  /* 使用宏定义数组大小 */

int main(void)
{
    int arr[SIZE];
    int i;
    
    /* 输入数组元素 */
    printf("请输入%d个整数:\n", SIZE);
    for (i = 0; i < SIZE; i++) {
        printf("arr[%d] = ", i);
        scanf("%d", &arr[i]);
    }
    
    /* 输出数组元素 */
    printf("\n你输入的数组是:\n");
    for (i = 0; i < SIZE; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }
    
    /* 计算数组元素的和 */
    int sum = 0;
    for (i = 0; i < SIZE; i++) {
        sum += arr[i];
    }
    printf("\n数组元素的和: %d\n", sum);
    
    /* 找出最大值和最小值 */
    int max = arr[0];
    int min = arr[0];
    
    for (i = 1; i < SIZE; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    
    printf("最大值: %d\n", max);
    printf("最小值: %d\n", min);
    
    return 0;
}

数组与函数

/*
 * 数组作为函数参数
 */

#include <stdio.h>

/* 打印数组 */
void print_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/* 计算数组元素和 */
int array_sum(int arr[], int len)
{
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum += arr[i];
    }
    return sum;
}

/* 查找最大值 */
int find_max(int arr[], int len)
{
    int max = arr[0];
    for (int i = 1; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

/* 查找元素 */
int find_element(int arr[], int len, int target)
{
    for (int i = 0; i < len; i++) {
        if (arr[i] == target) {
            return i;  /* 返回索引 */
        }
    }
    return -1;  /* 未找到 */
}

/* 修改数组 */
void double_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        arr[i] *= 2;
    }
}

int main(void)
{
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组: ");
    print_array(arr, len);
    
    printf("元素和: %d\n", array_sum(arr, len));
    printf("最大值: %d\n", find_max(arr, len));
    
    int index = find_element(arr, len, 3);
    printf("元素3的索引: %d\n", index);
    
    double_array(arr, len);
    printf("翻倍后: ");
    print_array(arr, len);
    
    return 0;
}

数组排序

冒泡排序

/*
 * 冒泡排序
 */

#include <stdio.h>

/* 冒泡排序 */
void bubble_sort(int arr[], int len)
{
    int i, j, temp;
    
    for (i = 0; i < len - 1; i++) {
        /* 每次遍历将最大的元素"冒泡"到最后 */
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                /* 交换相邻元素 */
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

/* 优化的冒泡排序 */
void bubble_sort_optimized(int arr[], int len)
{
    int i, j, temp;
    int swapped;  /* 标记是否发生交换 */
    
    for (i = 0; i < len - 1; i++) {
        swapped = 0;
        
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        /* 如果没有发生交换，说明已经有序 */
        if (!swapped) {
            break;
        }
    }
}

void print_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int len = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("原数组: ");
    print_array(arr1, len);
    
    bubble_sort(arr1, len);
    
    printf("排序后: ");
    print_array(arr1, len);
    
    return 0;
}

选择排序

/*
 * 选择排序
 */

#include <stdio.h>

/* 选择排序 */
void selection_sort(int arr[], int len)
{
    int i, j, min_idx, temp;
    
    for (i = 0; i < len - 1; i++) {
        /* 找到未排序部分的最小元素 */
        min_idx = i;
        
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        /* 将最小元素放到已排序部分的末尾 */
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

void print_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int arr[] = {64, 25, 12, 22, 11};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组: ");
    print_array(arr, len);
    
    selection_sort(arr, len);
    
    printf("排序后: ");
    print_array(arr, len);
    
    return 0;
}

快速排序

/*
 * 快速排序
 */

#include <stdio.h>

/* 分区函数 */
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];  /* 选择最后一个元素作为基准 */
    int i = low - 1;        /* 小于基准的元素的索引 */
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            /* 交换arr[i]和arr[j] */
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    /* 将基准放到正确的位置 */
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

/* 快速排序 */
void quick_sort(int arr[], int low, int high)
{
    if (low < high) {
        /* 分区 */
        int pi = partition(arr, low, high);
        
        /* 递归排序分区 */
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

void print_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void)
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组: ");
    print_array(arr, len);
    
    quick_sort(arr, 0, len - 1);
    
    printf("排序后: ");
    print_array(arr, len);
    
    return 0;
}

数组查找

线性查找

/*
 * 线性查找
 */

#include <stdio.h>

/* 线性查找 */
int linear_search(int arr[], int len, int target)
{
    for (int i = 0; i < len; i++) {
        if (arr[i] == target) {
            return i;  /* 找到，返回索引 */
        }
    }
    return -1;  /* 未找到 */
}

/* 查找所有匹配的位置 */
void find_all(int arr[], int len, int target, int indices[], int *count)
{
    *count = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] == target) {
            indices[(*count)++] = i;
        }
    }
}

int main(void)
{
    int arr[] = {3, 7, 2, 9, 7, 5, 7, 1};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    /* 查找单个元素 */
    int target = 7;
    int index = linear_search(arr, len, target);
    
    if (index != -1) {
        printf("找到 %d 在索引 %d\n", target, index);
    } else {
        printf("未找到 %d\n", target);
    }
    
    /* 查找所有匹配 */
    int indices[10];
    int count;
    find_all(arr, len, target, indices, &count);
    
    printf("%d 出现在 %d 个位置: ", target, count);
    for (int i = 0; i < count; i++) {
        printf("%d ", indices[i]);
    }
    printf("\n");
    
    return 0;
}

二分查找

/*
 * 二分查找（要求数组已排序）
 */

#include <stdio.h>

/* 迭代版二分查找 */
int binary_search(int arr[], int len, int target)
{
    int left = 0;
    int right = len - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  /* 避免溢出 */
        
        if (arr[mid] == target) {
            return mid;  /* 找到 */
        } else if (arr[mid] < target) {
            left = mid + 1;  /* 在右半部分 */
        } else {
            right = mid - 1;  /* 在左半部分 */
        }
    }
    
    return -1;  /* 未找到 */
}

/* 递归版二分查找 */
int binary_search_recursive(int arr[], int left, int right, int target)
{
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binary_search_recursive(arr, mid + 1, right, target);
    } else {
        return binary_search_recursive(arr, left, mid - 1, target);
    }
}

/* 查找第一个出现的位置 */
int find_first(int arr[], int len, int target)
{
    int left = 0;
    int right = len - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  /* 继续在左半部分查找 */
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main(void)
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    int target = 7;
    
    /* 迭代查找 */
    int index = binary_search(arr, len, target);
    printf("迭代查找: %d 在索引 %d\n", target, index);
    
    /* 递归查找 */
    index = binary_search_recursive(arr, 0, len - 1, target);
    printf("递归查找: %d 在索引 %d\n", target, index);
    
    /* 有重复元素的数组 */
    int arr2[] = {1, 2, 3, 3, 3, 4, 5};
    int len2 = sizeof(arr2) / sizeof(arr2[0]);
    
    int first = find_first(arr2, len2, 3);
    printf("\n第一个3的位置: %d\n", first);
    
    return 0;
}

二维数组

二维数组的定义和初始化

/*
 * 二维数组的定义和初始化
 */

#include <stdio.h>

int main(void)
{
    /* 二维数组声明 */
    int matrix1[3][4];  /* 3行4列 */
    
    /* 完全初始化 */
    int matrix2[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    
    /* 省略内层大括号 */
    int matrix3[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    
    /* 部分初始化 */
    int matrix4[3][4] = {
        {1, 2},      /* {1, 2, 0, 0} */
        {3},         /* {3, 0, 0, 0} */
        {4, 5, 6}    /* {4, 5, 6, 0} */
    };
    
    /* 省略行数（列数不能省略） */
    int matrix5[][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8}
    };  /* 2行4列 */
    
    /* 访问元素 */
    printf("matrix2[0][0] = %d\n", matrix2[0][0]);
    printf("matrix2[1][2] = %d\n", matrix2[1][2]);
    
    /* 修改元素 */
    matrix2[0][0] = 100;
    printf("修改后 matrix2[0][0] = %d\n", matrix2[0][0]);
    
    /* 遍历二维数组 */
    printf("\n遍历matrix2:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%3d ", matrix2[i][j]);
        }
        printf("\n");
    }
    
    /* 计算行数和列数 */
    int rows = sizeof(matrix2) / sizeof(matrix2[0]);
    int cols = sizeof(matrix2[0]) / sizeof(matrix2[0][0]);
    printf("\n行数: %d, 列数: %d\n", rows, cols);
    
    return 0;
}

二维数组应用

/*
 * 二维数组应用示例
 */

#include <stdio.h>

/* 打印矩阵 */
void print_matrix(int rows, int cols, int matrix[rows][cols])
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%3d ", matrix[i][j]);
        }
        printf("\n");
    }
}

/* 矩阵加法 */
void matrix_add(int rows, int cols, 
                int a[rows][cols], int b[rows][cols], int result[rows][cols])
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            result[i][j] = a[i][j] + b[i][j];
        }
    }
}

/* 矩阵乘法 */
void matrix_multiply(int m, int n, int p,
                     int a[m][n], int b[n][p], int result[m][p])
{
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            result[i][j] = 0;
            for (int k = 0; k < n; k++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

/* 矩阵转置 */
void matrix_transpose(int rows, int cols, 
                      int matrix[rows][cols], int result[cols][rows])
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            result[j][i] = matrix[i][j];
        }
    }
}

int main(void)
{
    /* 矩阵加法 */
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int b[2][3] = {{6, 5, 4}, {3, 2, 1}};
    int sum[2][3];
    
    printf("矩阵A:\n");
    print_matrix(2, 3, a);
    
    printf("\n矩阵B:\n");
    print_matrix(2, 3, b);
    
    matrix_add(2, 3, a, b, sum);
    printf("\nA + B:\n");
    print_matrix(2, 3, sum);
    
    /* 矩阵乘法 */
    int c[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int d[3][2] = {{7, 8}, {9, 10}, {11, 12}};
    int product[2][2];
    
    printf("\n矩阵C:\n");
    print_matrix(2, 3, c);
    
    printf("\n矩阵D:\n");
    print_matrix(3, 2, d);
    
    matrix_multiply(2, 3, 2, c, d, product);
    printf("\nC × D:\n");
    print_matrix(2, 2, product);
    
    /* 矩阵转置 */
    int e[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int transposed[3][2];
    
    printf("\n矩阵E:\n");
    print_matrix(2, 3, e);
    
    matrix_transpose(2, 3, e, transposed);
    printf("\n转置后:\n");
    print_matrix(3, 2, transposed);
    
    return 0;
}

小结

本章学习了：

• 一维数组：定义、初始化、访问、遍历
• 数组与函数：数组作为参数传递
• 数组排序：冒泡排序、选择排序、快速排序
• 数组查找：线性查找、二分查找
• 二维数组：定义、初始化、矩阵运算

下一章，我们将学习指针，了解C语言指针的概念和使用。