Tech Docs Station

Appearance

数组 ​

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

一维数组 ​

数组的定义和初始化 ​

cpp
#include <iostream>
#include <array>  // C++11 array容器
using namespace std;

int main() {
    // ============ 数组定义 ============
    
    // 方式1：指定大小，不初始化
    int arr1[5];  // 5个元素，值不确定
    
    // 方式2：指定大小，部分初始化
    int arr2[5] = {1, 2, 3};  // 剩余元素为0
    
    // 方式3：指定大小，完全初始化
    int arr3[5] = {1, 2, 3, 4, 5};
    
    // 方式4：不指定大小，自动推导
    int arr4[] = {1, 2, 3, 4, 5};  // 大小为5
    
    // 方式5：全部初始化为0
    int arr5[5] = {0};  // 所有元素都是0
    int arr6[5] = {};   // 所有元素都是0（C++11）
    
    // 方式6：C++11列表初始化
    int arr7[5]{1, 2, 3, 4, 5};  // 等价于 = {1, 2, 3, 4, 5}
    
    
    // ============ 访问数组元素 ============
    
    int numbers[5] = {10, 20, 30, 40, 50};
    
    // 通过索引访问（索引从0开始）
    cout << "第一个元素: " << numbers[0] << endl;  // 10
    cout << "第三个元素: " << numbers[2] << endl;  // 30
    cout << "最后一个元素: " << numbers[4] << endl;  // 50
    
    // 修改元素
    numbers[0] = 100;
    cout << "修改后第一个元素: " << numbers[0] << endl;
    
    // 越界访问（危险！不检查边界）
    // cout << numbers[10];  // 未定义行为
    
    
    // ============ 遍历数组 ============
    
    // 方式1：传统for循环
    cout << "\n传统for循环: ";
    for (int i = 0; i < 5; i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;
    
    // 方式2：范围for循环（C++11）
    cout << "范围for循环: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // 方式3：范围for循环（引用，可修改）
    cout << "修改前: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    for (int& num : numbers) {
        num *= 2;  // 每个元素乘以2
    }
    
    cout << "修改后: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    
    // ============ 计算数组大小 ============
    
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout << "\n数组大小: " << size << endl;
    
    // 使用constexpr（C++17）
    // constexpr int arrSize = std::size(numbers);
    
    
    // ============ C++11 std::array ============
    
    // 更安全的数组容器
    array<int, 5> stdArr = {1, 2, 3, 4, 5};
    
    cout << "\nstd::array: ";
    for (int num : stdArr) {
        cout << num << " ";
    }
    cout << endl;
    
    // std::array的方法
    cout << "size(): " << stdArr.size() << endl;
    cout << "front(): " << stdArr.front() << endl;
    cout << "back(): " << stdArr.back() << endl;
    cout << "at(2): " << stdArr.at(2) << endl;  // 带边界检查
    
    // std::array支持赋值
    array<int, 5> arrCopy = stdArr;
    
    return 0;
}

数组与函数 ​

cpp
#include <iostream>
using namespace std;

// ============ 数组作为函数参数 ============

// 方式1：传递数组（实际上传递指针）
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 方式2：传递指针
void printArrayPtr(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 方式3：使用模板传递数组引用（保留数组大小信息）
template<size_t N>
void printArrayRef(int (&arr)[N]) {
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "数组大小: " << N << endl;
}

// 修改数组元素
void doubleArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] *= 2;  // 修改会影响原数组
    }
}

// 返回数组指针（不推荐）
int* createArray(int size) {
    int* arr = new int[size];  // 动态分配
    for (int i = 0; i < size; i++) {
        arr[i] = i + 1;
    }
    return arr;
    // 注意：调用者需要delete[]释放内存
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    
    // 传递数组
    cout << "传递数组: ";
    printArray(numbers, size);
    
    // 传递指针
    cout << "传递指针: ";
    printArrayPtr(numbers, size);
    
    // 传递数组引用
    cout << "传递数组引用: ";
    printArrayRef(numbers);
    
    // 修改数组
    cout << "\n修改前: ";
    printArray(numbers, size);
    
    doubleArray(numbers, size);
    
    cout << "修改后: ";
    printArray(numbers, size);
    
    // 动态创建数组
    int* dynamicArr = createArray(5);
    cout << "\n动态数组: ";
    printArrayPtr(dynamicArr, 5);
    delete[] dynamicArr;  // 释放内存
    
    return 0;
}

二维数组 ​

cpp
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    // ============ 二维数组定义 ============
    
    // 方式1：指定行列
    int matrix1[3][4];  // 3行4列
    
    // 方式2：完全初始化
    int matrix2[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    
    // 方式3：省略内层大括号
    int matrix3[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    
    // 方式4：部分初始化
    int matrix4[3][4] = {
        {1, 2},      // 第一行：1, 2, 0, 0
        {3, 4, 5},   // 第二行：3, 4, 5, 0
        {6}          // 第三行：6, 0, 0, 0
    };
    
    // 方式5：省略行数（列数必须指定）
    int matrix5[][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8}
    };  // 自动推导为2行
    
    // 方式6：全部初始化为0
    int matrix6[3][4] = {0};
    
    
    // ============ 访问二维数组 ============
    
    int matrix[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    
    // 访问元素
    cout << "matrix[0][0] = " << matrix[0][0] << endl;  // 1
    cout << "matrix[1][2] = " << matrix[1][2] << endl;  // 7
    cout << "matrix[2][3] = " << matrix[2][3] << endl;  // 12
    
    // 修改元素
    matrix[0][0] = 100;
    
    
    // ============ 遍历二维数组 ============
    
    cout << "\n二维数组内容：" << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            cout << setw(4) << matrix[i][j];
        }
        cout << endl;
    }
    
    // 范围for循环（C++11）
    cout << "\n范围for循环：" << endl;
    for (auto& row : matrix) {
        for (int elem : row) {
            cout << setw(4) << elem;
        }
        cout << endl;
    }
    
    
    // ============ 二维数组应用 ============
    
    // 矩阵加法
    int A[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int B[2][3] = {{6, 5, 4}, {3, 2, 1}};
    int C[2][3];
    
    cout << "\n矩阵加法：" << endl;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) {
            C[i][j] = A[i][j] + B[i][j];
            cout << setw(4) << C[i][j];
        }
        cout << endl;
    }
    
    // 矩阵转置
    int D[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int E[3][2];
    
    cout << "\n矩阵转置：" << endl;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) {
            E[j][i] = D[i][j];
        }
    }
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            cout << setw(4) << E[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

数组排序 ​

cpp
#include <iostream>
#include <algorithm>  // STL算法
using namespace std;

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// ============ 冒泡排序 ============

void bubbleSort(int arr[], int size) {
    // 比较相邻元素，将大的元素"冒泡"到后面
    for (int i = 0; i < size - 1; i++) {
        bool swapped = false;  // 优化：检测是否发生交换
        
        for (int j = 0; j < size - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // 如果没有发生交换，说明已经有序
        if (!swapped) break;
    }
}

// ============ 选择排序 ============

void selectionSort(int arr[], int size) {
    // 每次选择最小的元素放到前面
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;
        
        // 找到最小元素的索引
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// ============ 插入排序 ============

void insertionSort(int arr[], int size) {
    // 将元素插入到已排序部分的正确位置
    for (int i = 1; i < size; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;
        
        // 向后移动大于key的元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入key
        arr[j + 1] = key;
    }
}

// ============ 快速排序 ============

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++;
            // 交换
            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 quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr1) / sizeof(arr1[0]);
    
    cout << "原始数组: ";
    printArray(arr1, size);
    
    // 冒泡排序
    int arr2[] = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr2, size);
    cout << "冒泡排序: ";
    printArray(arr2, size);
    
    // 选择排序
    int arr3[] = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(arr3, size);
    cout << "选择排序: ";
    printArray(arr3, size);
    
    // 插入排序
    int arr4[] = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(arr4, size);
    cout << "插入排序: ";
    printArray(arr4, size);
    
    // 快速排序
    int arr5[] = {64, 34, 25, 12, 22, 11, 90};
    quickSort(arr5, 0, size - 1);
    cout << "快速排序: ";
    printArray(arr5, size);
    
    // STL排序
    int arr6[] = {64, 34, 25, 12, 22, 11, 90};
    sort(arr6, arr6 + size);  // 默认升序
    cout << "STL排序: ";
    printArray(arr6, size);
    
    // STL降序排序
    sort(arr6, arr6 + size, greater<int>());
    cout << "STL降序: ";
    printArray(arr6, size);
    
    return 0;
}

数组查找 ​

cpp
#include <iostream>
#include <algorithm>
using namespace std;

// ============ 线性查找 ============

int linearSearch(int arr[], int size, int target) {
    // 逐个比较，找到返回索引
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // 未找到
}

// ============ 二分查找 ============

int binarySearch(int arr[], int size, int target) {
    // 要求数组已排序
    int left = 0;
    int right = size - 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 binarySearchRecursive(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 binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

// 查找第一个等于目标的位置
int findFirst(int arr[], int size, int target) {
    int left = 0;
    int right = size - 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 findLast(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续向右找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    // 无序数组 - 线性查找
    int unsorted[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(unsorted) / sizeof(unsorted[0]);
    
    cout << "===== 线性查找 =====" << endl;
    int index = linearSearch(unsorted, size, 25);
    cout << "查找25: 索引 = " << index << endl;
    
    index = linearSearch(unsorted, size, 100);
    cout << "查找100: 索引 = " << index << " (未找到)" << endl;
    
    // 有序数组 - 二分查找
    int sorted[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    size = sizeof(sorted) / sizeof(sorted[0]);
    
    cout << "\n===== 二分查找 =====" << endl;
    index = binarySearch(sorted, size, 11);
    cout << "查找11: 索引 = " << index << endl;
    
    index = binarySearch(sorted, size, 10);
    cout << "查找10: 索引 = " << index << " (未找到)" << endl;
    
    // 有重复元素的二分查找
    int duplicates[] = {1, 3, 3, 3, 5, 7, 7, 9};
    size = sizeof(duplicates) / sizeof(duplicates[0]);
    
    cout << "\n===== 有重复元素的查找 =====" << endl;
    cout << "数组: ";
    for (int n : duplicates) cout << n << " ";
    cout << endl;
    
    cout << "第一个3的位置: " << findFirst(duplicates, size, 3) << endl;
    cout << "最后一个3的位置: " << findLast(duplicates, size, 3) << endl;
    cout << "第一个7的位置: " << findFirst(duplicates, size, 7) << endl;
    cout << "最后一个7的位置: " << findLast(duplicates, size, 7) << endl;
    
    // STL查找
    cout << "\n===== STL查找 =====" << endl;
    
    // find
    int* pos = find(sorted, sorted + size, 11);
    if (pos != sorted + size) {
        cout << "find(11): 索引 = " << (pos - sorted) << endl;
    }
    
    // binary_search（只判断是否存在）
    bool found = binary_search(sorted, sorted + size, 11);
    cout << "binary_search(11): " << (found ? "存在" : "不存在") << endl;
    
    // lower_bound（第一个 >= 目标的位置）
    int* lower = lower_bound(sorted, sorted + size, 11);
    cout << "lower_bound(11): 索引 = " << (lower - sorted) << endl;
    
    // upper_bound（第一个 > 目标的位置）
    int* upper = upper_bound(sorted, sorted + size, 11);
    cout << "upper_bound(11): 索引 = " << (upper - sorted) << endl;
    
    return 0;
}

本章小结 ​

本章学习了：

  • 一维数组：定义、初始化、访问、遍历
  • std::array：C++11安全的数组容器
  • 数组与函数：传递数组、指针、引用
  • 二维数组：定义、初始化、矩阵运算
  • 数组排序：冒泡、选择、插入、快速排序
  • 数组查找：线性查找、二分查找

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