什么是数组？

在本节课中，我们将复习数组的基本概念，并通过一些实际示例来深入掌握这一简单却强大的数据结构。

引言

数组是一种将相同类型的数据项连续存储在内存中的集合。它是最简单且应用最广泛的数据结构。大多数其他数据结构，例如栈和队列，都可以通过数组实现。这使得数组成为所有数据结构的核心构建模块。

下图展示了一个包含四个元素的简单数组。集合中的每个项目称为一个数据元素，数组中存储的数据元素数量称为其大小。

声明数组

在 C++ 中，数组可以声明为静态或动态。

声明静态数组

在 C++ 中，静态数组的内存分配发生在编译时，且分配在栈内存上。

静态数组的一般定义如下：

1数据类型 数组名 [大小];

静态数组可以在声明时赋值，这称为数组初始化。数组初始化的一个例子是：

1int dots[3] = { 1, 4, -2 };

在初始化数组时，可以省略大小。此时，编译器会根据提供的值列表自动确定数组大小。以下写法与上面的例子等价：

1int dots[] = { 1, 4, -2 };

如果未对数组进行初始化，其元素的值是不确定的。如果初始化时提供的值少于数组大小，剩余的元素将被自动初始化为 0。例如，以下语句将创建一个包含元素 1、2、3、0、0 的数组：

1int dashes[5] = {1, 2, 3};

声明动态数组

静态数组的大小是固定的，其分配的内存无法增长或缩小。动态数组是在运行时在堆内存中分配的，通常通过指针实现。

动态数组的一般声明方式如下：

1数据类型 * 数组名 = new 数据类型[大小];

数据类型可以是 int、float、double、char 或任何用户自定义类型。

访问数组元素

可以通过指定整数索引并使用方括号来访问数组元素。在 C++ 中，数组索引从 $0$ 开始，一直递增到 $n-1$，其中 $n$ 是数组的大小。

数组索引

数组中的每个数据元素都关联一个称为索引的数值，该数值对应于该元素在数组中的位置。需要注意的是，索引值是非负的，且始终从 0 开始。因此，数组的第一个元素位于索引 0，最后一个元素位于索引 n-1，其中 n 是数组的大小。

索引使得我们可以直接访问数组中的任意元素，这也是数组被称为随机访问数据结构的原因。这是数组与其他数据结构（如链表）的关键区别。

因此，要引用名为 hills 的数组中的第三个元素，应写作：

1hills[2]

C++ 运行时不会对数组索引进行边界检查，因此如果一个名为 hills 的数组大小为 $3$，而你尝试访问 hills[5]，结果是不可预测的。程序可能因段错误而崩溃，也可能继续运行但产生不正确的结果。

考虑下面的例子：

1int main(){
2  const int size = 10;
3  
4  // 动态数组初始化
5  int * dynamicArray = new int[size];
6  for(int i = 0 ; i < size; i++){
7    dynamicArray[i] = i;
8  }
9  
10  // 静态数组初始化
11  int staticArray[size] = {1,2,3,4,5,6,7,8,9,10};
12  float staticArray2[] = {2.3, 7.9, 5.6, 4.2, 9.1};
13  
14  // 打印静态数组
15  cout << "静态数组: ";
16  for(int i = 0 ; i < size; i++){
17    cout << staticArray[i] << " ";
18  } 
19  cout << endl;
20  
21  // 打印第二个静态数组
22  cout << "静态数组2:  ";
23  for(int i = 0 ; i < 5; i++){
24    cout << staticArray2[i] << "  ";
25  } 
26  cout << endl;
27  
28  // 打印动态数组
29  cout << "动态数组: ";
30  for(int i = 0 ; i < size; i++){
31    cout << dynamicArray[i] << " ";
32  } 
33  
34  // 释放分配的内存
35  delete[] dynamicArray;
36}

数组在内存中的存储方式

静态数组在内存中使用连续的内存空间存储，而动态数组则通过一个指向数组首元素的指针来存储。例如，如果我们创建一个大小为 3 的动态整型数组并命名为 arr，那么变量将指向数组的起始位置。分配给 arr 的内存位于栈上，而由 new 关键字创建的内存位于堆上。如下图所示：

修改或添加数组元素

要修改静态数组的元素，只需访问其索引并更改值即可。例如：

1int arr[3] = {1,2,3};
2arr[2] = 4;

此时，数组变为 {1,2,4}。

要向数组中添加新元素，必须先调整大小，而这只有在动态数组中才可行。以下是实现此功能的代码示例，请查看！

1class ArrayList{
2  int * arr; // 动态增长的数组
3  int num_elements; // 数组中元素的数量
4  int capacity; // 数组当前容量
5};

1void resize(){
2    // 容量（大小）翻倍
3    int * tempArr = new int[capacity*2];
4    capacity *= 2;
5    
6    // 将旧数组的值复制到新数组
7    for(int i = 0; i < num_elements; i++){
8        tempArr[i] = arr[i]; 
9    }
10    
11    // 删除已分配的空间
12    delete [] arr;
13    
14    // 指向新分配的内存
15    arr = tempArr;
16}

课程结束时，你将看到 ArrayList 类的完整实现。

我们可以通过 ArrayList 类的 insert(int val) 成员函数向数组中添加一个或多个元素。

1void insert(int val){
2    // 如果数组大小小于列表容量
3    if(num_elements < capacity){
4        arr[num_elements] = val;
5        num_elements++;
6    } else {
7        resize();
8        arr[num_elements] = val;
9        num_elements++;
10    }
11}

要获取当前数组的长度，可以调用 ArrayList 类的 length() 函数。

1int length(){
2    return num_elements;   // 返回元素数量
3}

以下是包含 print() 函数的 ArrayList 类的完整实现，用于打印数组中的元素。

1#include <iostream>
2using namespace std;
3
4class ArrayList {
5    int *arr;
6    int num_elements;
7    int capacity;
8
9public:
10    ArrayList(int size) {
11        arr = new int[size];
12        num_elements = 0;
13        capacity = size;
14    }
15    
16    void insert(int val) {
17        if(num_elements < capacity) {
18            arr[num_elements] = val;
19            num_elements++;
20        } else {
21            resize();
22            arr[num_elements] = val;
23            num_elements++;
24        }
25    }
26    
27    int getAt(int index){
28        return arr[index];
29    }
30
31    void resize() {
32        int* tempArr = new int[capacity*2];
33        capacity *= 2;
34
35        for(int i = 0; i < num_elements; i++) {
36            tempArr[i] = arr[i];
37        }
38
39        delete [] arr;
40        arr = tempArr;
41    }
42
43    int length() {
44        return num_elements;
45    }
46
47    void print() {
48        for(int i = 0; i < num_elements; i++)
49            cout << arr[i] << " ";
50        cout << endl;
51    }
52};
53
54int main() {
55    ArrayList arr(1);
56    cout << "数组长度 : " << arr.length() << endl;
57    arr.insert(1);
58    arr.insert(2);
59    arr.insert(3);
60    arr.insert(4);
61    arr.insert(5);
62    arr.insert(6);
63    arr.insert(7);
64    arr.insert(8);
65    cout << "数组长度 : " << arr.length() << endl;
66    cout << "数组内容: ";
67    arr.print();  
68    cout << "索引5处的元素是 " << arr.getAt(4) << endl;  
69}