Arrays(数组)

---

数组是一个固定长度的存储相同数据类型的数据结构，数组中的元素被存储在一段连续的内存空间中。它是最简单的数据结构之一，大多数现代编程语言都内置数组支持。

为何使用数组存储一堆变量

---

与单独为每一个元素声明一个变量名相比，我们可以使用数组的索引值访问数组中的每一个元素。

例如：我们需要实现一个系统来存储办公室所有员工的年龄，传统的存储方式如下：

我们为办公室的每一个员工创建一个变量。假设办公室由三个员工，只需声明三个变量：empl_age,emp2_age和emp3_age.

当我们新招募员工进来时，我们需要创建更多的变量来存储员工的年龄。维护这样的系统非常麻烦，每添加一个新的员工，我们就需要修改这个系统的代码。

要人工计算超过20个员工的平均年龄，逐一访问每一个变量让人头痛的。

数组数据结构的出现尝试解决这种问题。数组的特性之一就是，以一个名称保存多个相同数据类型的数据。

在这个例子中，我们可以声明一个名为employees_ages的整型数组来保存所有员工的年龄。

数组的第二个特性就是，数组中的每一个数据元素被存储在一段连续的内存空间中，我们可以以索引的方式访问数组的数据元素。

通过遍历数组的索引来访问每个员工的年龄，使得计算员工年龄的平均值变得更加容易；因为在遍历过程中，数组的名称是恒定的，只有索引在变化。

声明一个一维数组

---

在使用一个数组之前，我们需要声明这个数组。声明数组意味着我们需要指定以下内容：

• 数据类型 这个数组将要存储怎样一种类型的数据（不同类型占据的内存空间是不同的.如：字符、整型、浮点型等一些数据类型。

• 名称 用于标识这个数组并与之交互的变量名

• 数量 数组的数量，它指定这个数组最多能存储的数据元素的数量

声明数组的语法

C语言中声明数组的语法如下:

type name[size]

创建一个存储100个学生成绩的数组

int marks[100]

为数组分配值的两种方式：

初始化时分配值

---

声明数组时为数组分配值。如果一些值没有明确定义，会被设置为0：

int marks[10]={5,10,20,30,40,60};

初始化后分配值

---

默认情况下，只要由足够的内存，创建的数组会被随机分配一个位置，我们无法获知这个内存位置包含哪些信息。

如果在创建数组时，没有初始化数组元素。这时，我们就访问数组元素的话，会得到一个垃圾值。因此，如果要对一个数组执行计算，我们建议清空数组值或者为其分配初始值。

int ages[10];
//未为数组分配初始值，访问数组元素
for (int o=0;i<10;i++>){
    printf("\n arr[%d]=%d",i,ages[i]);
}

数组的遍历

---

数组中的每一个元素都可以通过索引访问到。数组的索引通常从0开始，即数组中第一个元素的索引为0.数组的最后一个元素位于（n-1)个索引处。我们将其称之为基于0的索引。数组也可以是基于其它数的，我们将其称之为基于n的索引。

使用for循环简单的遍历数组中的所有索引，可以访问数组中的所有元素。

int id[10];
//使用循环为数组分配值
for (int i=0;i<10;i++>){
    printf("\nEnter an id:");
    scanf("%d",%id[i]);
}
//遍历数组中的元素
for( int i=0;i<10;i++){
    printf("\n id[%d]=%d",i,id[i]);
}

在对数组元素进行插入或者删除时，为了保持数组的顺序。需要处理数组中已经存在的其它数组元素。对于较大的数组，这项工作对性能的消耗是昂贵的。

插入元素到数组中

---

插入尾部

在数组还有足够的空间可供插入时，在数组的尾部插入一个元素是非常容易的。找到数组最后一个元素的索引，并将新插入元素的索引+1即可完成插入。

任意位置插入

通过将该位置后的所有元素的位置向后移动，可在该位置插入元素。

void insert_position(int arr[]){

    int i=0,pos,num;
    printf("输入要插入的元素值:");
    scanf("%d",&num);

    printf ("输入要插入元素的索引位置");
    scanf("%d",&pos);

    for(i=n-1;i>=pos;i--){
        arr[i+1]=arr[i];
    }
    arr[pos]=num;
    n=n+1;//增加已使用索引的总数
}

从数组中删除元素

---

删除尾部元素

只要数组不为空，删除数组中的元素是很容易的。找到最后一个元素的索引，然后删除该元素即可。

删除任意位置元素

可以在任意索引处删除元素，方法是删除该位置的元素，然后将该位置之后的所有元素向前移动以填充删除的位置。

void delete_position(int arr[]){

    int i,pos;
    printf("输入要删除元素的索引位置");
    scanf("%d",&pos);

    for (i=pos;i<n-1;i++>){
        arr[i]=arr[i+1];
    }
    n=n-1;增加已使用索引的总数
}

多维数组

---

数组可能具有多个维度来表示数据，我们将其称之为多维数组，可以使用多个索引来访问多维数组中的元素。

二维数组

---

二维数组可以视为数组中的数组。它可以使用行和列的表格来展示。可以使用与行和列对应的2个索引来访问表中的每个元素。

使用2个参数声明一个二维数组：

type name[max_size_x][max_size_y]

max_size_x和max_size_y分别代表每个维度可存储数据的最大数据量

三维数组

---

类似的，可将三维数组视为一个立方体，可以使用与三维坐标相对应的3个索引来访问数组中的元素。

例如：魔方的每个方块都可以由尺寸为3x3x3的三维数组表示

声明一个三维数组：

type name[max_size_x][max_size_y][max_size_z];

max_size_x、max_size_y和max_size_z分别代表每个维度能存储数据数量的最大值。

数组的内存分配

---

由于数组是将其所有的数据元素存储在连续的内存空间中。在存储数组时，仅存储数组的基地址，即第一个元素的地址。数组其它元素的地址可以通过对基地址的偏移来计算。

一维数组的内存地址

---

使用以下公式计算数组元素的内存地址

A[i]=base_address(A)+size_of_element(i-lower_bound);

lower_bound表示数组的最小索引，同样的，up_bound表示数组的最大索引。在C语言中，最小下标通常是0，因此可以省略。

二维数组的内存地址

---

二维数组的存储形式由两种表示方法，并且其对应元素的地址均可以通过公式计算出来。

按列存储

以这种形式存储，元素逐列存储。第一列的m个元素存储在前m个位置中，第二列的元素存储在接下来的m个位置中，一次类推。

Address(A[i][j])=base_address+width{number_of_rows(j-1)+(i-1)}

按行存储

以这种形式，元素逐行存储，第一行的n个元素，存储在前n个位置中，第二行的元素存储在第二行的前n个位置中，以此类推。

Address(A[i][j])=base_address+width{number_of_cols(i-1)+(j-1)}

时间复杂度

---

访问

数组可以直接使用索引访问，因此，访问数组元素的时间复杂度为O(1)

查找

从数组中查找一个给定的值，需要遍历数组中的每一个元素，知道找到给定值为止。假设查找的形式为线性查找（数组最基本的查找形式），则查找的时间复杂度为O(n).

也存在一些其它的查找算法，比如，二分搜索，可在O(log n)的时间复杂度内搜索，但前提是当前数组为有序数组。

插入

在数组的两个元素之间插入一个新的元素，需要将插入之后的所有位置的元素向后移动。这就意味着如果在数组的开头插入元素，需要将数组的所有元素向后移动，因此插入操作的时间复杂度为O(n)

删除

在数组的两个元素之间删除一个元素，需要将删除位置之后的所有位置的元素向前移动。这就意味着，如果删除数组的第一个元素，需要将数组的所有元素统一向前移动，因此删除操作的时间复杂度为O(n)

空间要求

数组仅占据用于存储指定数据类型的元素的空间，这就意味着，存储n个元素所要求的空间复杂度为O(n)

数组的优点

---

相比其它类型的数据结构，数组有以下优点：

• 数组允许随机访问数组元素，每个存储在数组中的元素可以通过直接访问其索引来使用
• 数组对存储友好。这意味着在某些情况下，由于数组的线性存储方式，代码的执行顺序会大大提高

数组的缺点

---

• 声明数组时，需要指定数组的长度。初始声明数组的长度过长或过短，在移动数组元素时都会有导致效率变低
• 插入和删除元素之后保持数组的连续性代价是昂贵的，因为有可能需要重新排列所有数组元素。

更多内容,欢迎关注：