C++数组：实现高效的数据存储和访问

一、数组的定义和基本概念

数组是一组同类型数据的集合，通过一个名字和一组下标来访问存储在数组中的每个元素。数组中的元素在内存中是连续存储的。

C++ 中数组的定义格式为：数据类型 数组名[元素个数]；其中，数据类型可以是任何数据类型，元素个数必须是整型常量或者常量表达式。

int arr[10]; //定义一个包含10个整型元素的数组

定义数组时可以初始化，数组的初始化可以通过给出初始值列表的方式，如下：

int arr[5] = {1, 2, 3, 4, 5}; //定义并初始化一个包含5个整型元素的数组

如果省略了初始值列表，所有元素都将被默认初始化为0：

int arr[5] = {}; //定义并初始化一个包含5个整型元素的数组，所有元素都为0

二、多维数组

数组不仅可以是一维的，还可以是多维的。例如，二维数组就是由行和列构成的矩阵。对于二维数组，我们需要使用两个下标来访问数组中的元素。

在 C++ 中，多维数组的定义形式为：数据类型 数组名[数组1维长度][数组2维长度]...[数组n维长度]；

int arr[3][4] = { { 1,2,3,4 },{ 5,6,7,8 },{ 9,10,11,12 } };

以上为一个3 × 4的数组，可以通过下标来访问数组中的元素：

cout << arr[1][2] << endl;

以上代码表示访问数组中第2行第3列的元素，输出7。

三、动态内存分配数组

在定义数组时，需要指定数组的大小，而大小一旦确定就不能再改变，这可能会造成一些不便。针对这个问题，C++ 提供了动态内存分配的方法，可以根据需要在程序运行时动态分配内存。

动态内存分配的方法是使用 new 运算符，它会返回一个指向所分配空间的指针。例如，我们可以通过如下方式动态地创建一个包含10个整型元素的数组：

int *arr = new int[10];

动态分配完成之后，我们可以像使用普通数组一样使用动态分配的数组：

arr[0] = 1;
arr[1] = 2;
cout << arr[0] << " " << arr[1] << endl;

使用完动态分配的数组要记得释放内存，否则会造成内存泄漏。释放内存使用 delete 运算符：

delete[] arr;

四、数组的应用

数组不仅是一种存储和访问数据的数据结构，也可以作为其他数据结构的基础构建。例如，我们可以使用数组来实现以下几个算法：

• 冒泡排序：通过不断地交换相邻两个元素，将最大或最小的元素移动到数组的一段。最差的情况下需要比较n*(n-1)/2次，时间复杂度为O(n^2)。

    void bubbleSort(int arr[], int length) {
      for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }
    }
  

• 选择排序：从数组中选择最小的元素，将其和数组的第一个元素交换位置，接着从剩下的元素中选择最小的元素，将其与数组的第二个元素交换位置。时间复杂度为O(n^2)。

    void selectionSort(int arr[], int length) {
      for (int i = 0; i < length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
          if (arr[j] < arr[minIndex]) {
            minIndex = j;
          }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
  

• 快速排序：通过递归地将数组分成小于和大于基准值的两部分，分别进行排序。时间复杂度为O(nlogn)。

    void quickSort(int arr[], int left, int right) {
      if (left >= right) return;

      int i = left, j = right;
      int pivot = arr[(left + right) / 2]; //取中间元素为基准值

      while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
          i++;
          j--;
        }
      }

      quickSort(arr, left, j);
      quickSort(arr, i, right);
    }
  

五、结语

数组作为一种基本数据结构，可以高效地存储和访问数据，同时也是构建其他数据结构算法的基础。掌握数组的定义和使用方法，可以提高代码的效率，并且适用于各种类型的问题。