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  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) 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);
    }
  

五、結語

數組作為一種基本數據結構，可以高效地存儲和訪問數據，同時也是構建其他數據結構演算法的基礎。掌握數組的定義和使用方法，可以提高代碼的效率，並且適用於各種類型的問題。