什么是数组？

在本节课中，你将复习数组的基本概念，并通过一些实际示例来理解这一简单但功能强大的数据结构。

引言

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

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

C# 有两种类型：引用类型和值类型。引用类型变量存储对其数据（对象）的引用，而值类型变量直接包含其数据。C# 中的所有数组都是引用类型。

声明数组

一维数组的通用定义如下：

1datatype [] arrayName;

例如：

1int[] array1 = new int[10];

这声明了 array1 为一个包含10个整数的数组。

初始化数组

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

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

这实际上是以下等价数组创建表达式的简写形式：

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

在初始化数组时，可以省略大小。在这种情况下，编译器会根据值列表自动确定数组的大小。下面的写法与上一个例子完全等效：

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

访问数组元素

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

数组索引

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

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

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

1hills[2]

C# 运行时会对数组索引进行边界检查。如果声明了一个大小为 3 的数组 hills，而你尝试访问 hills[5]，则会抛出 IndexOutOfRangeException 异常。

静态数组与动态数组

C# 同时支持静态数组和动态数组。

静态数组具有固定大小，在声明数组时即已确定。下面的代码定义了一个只能容纳五个整数的数组：

1int[] odds = new int[5];

动态数组没有预定义的大小，随着向数组中添加新元素，其大小会自动增长。

考虑以下示例：

1namespace Chapter_2
2{
3    class Example_1
4    {
5        static void Main(string[] args)
6        {
7            int size = 10;
8  
9            // 固定大小数组：长度由变量 size 在创建时确定
10            int [] dynamicArray = new int[size];
11            for(int i = 0 ; i< size; i++)
12            {
13                dynamicArray[i] = i;
14            }
15  
16            // 静态数组初始化
17            int [] staticArray= {1,2,3,4,5,6,7,8,9,10};
18            float [] staticArray2 = {2.3f, 7.9f, 5.6f, 4.2f, 9.1f};
19  
20            // 打印静态数组
21            Console.Write("静态数组: ");
22            for(int i = 0 ; i< size; i++)
23            {
24               Console.Write( staticArray[i] + " ");
25            } 
26            Console.WriteLine("");
27  
28            // 打印第二个静态数组
29            Console.Write("静态数组2:  ");
30            for(int i = 0 ; i< 5; i++)
31            {
32               Console.Write(staticArray2[i] + "  ");
33            } 
34            Console.WriteLine("");
35  
36            // 打印动态数组
37            Console.Write("动态数组: ");
38            for(int i = 0 ; i< size; i++)
39            {
40               Console.Write(dynamicArray[i] + " ");
41            } 
42       }
43    }
44}

数组在内存中如何存储？

在 C# 中，所有数组都是动态分配的。
数组可以包含基本数据类型，也可以包含类的对象，具体取决于数组的定义。当使用基本数据类型时，实际值必须存储在连续的内存位置中。对于类的对象，则实际对象存储在堆段中。

例如，如果你创建一个大小为3的整数数组并命名为 arr，那么该变量将指向数组的起始位置。分配给 arr 的内存位于栈上，而由 new 关键字创建的内存则位于堆上。如下图所示：

修改或添加数组元素

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

1int [] arr = {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    arr=tempArr;
13}

尽管 C# 提供了内置的 ArrayList，但在课程结束时，你将看到我们对 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}

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

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