Data Structures Algorithms 简明教程

Array Data Structure

What is an Array?

数组是一种线形数据结构，被定义为具有相同或不同数据类型的元素的集合。它们存在于单维度和多维度中。当有必要将多个类似性质的元素一起存储在一个地方时，这些数据结构就会出现在图片中。

数组索引和内存地址之间的区别在于，数组索引充当键值来标记数组中的元素。然而，内存地址是可用空闲内存的起始地址。

以下是理解数组概念的重要术语。

Element - 存储在数组中的每个项称为一个元素。
Index - 数组中每个元素的位置都有一个数字索引，用于标识元素。

Syntax

在 C 和 C++ 编程语言中创建数组 −

data_type array_name[array_size]={elements separated by commas}
or,
data_type array_name[array_size];

在 Java 编程语言中创建数组 −

data_type[] array_name = {elements separated by commas}
or,
data_type array_name = new data_type[array_size];

Need for Arrays

数组用作从小型排序问题到更为复杂问题（例如旅行商问题）的许多问题的解决方案。除了数组以外，还有许多能够为这些问题提供有效时间和空间复杂度的数据结构，那么使用数组有什么好处？答案在于随机访问查找时间。

数组提供了 O(1) 的随机访问查找时间。这意味着访问数组的第 1 个索引和数组的第 1000 个索引所需的时间都是一样的。这是由于数组带有指针和偏移值。指针指向内存的正确位置，偏移值表明在所述内存中查找距离。

                           array_name[index]
                              |       |
                           Pointer   Offset

因此，在包含 6 个元素的数组中，要访问第 1 个元素，数组指向第 0 个索引。类似地，要访问第 6 个元素，数组指向第 5 个索引。

Array Representation

数组表示为多个存储桶的集合，其中每个存储桶存储一个元素。这些存储桶的索引从“0”到“n-1”，其中 n 是特定数组的大小。例如，大小为 10 的数组将具有索引为 0 到 9 的存储桶。

此索引也将类似于多维数组。如果它是一个二维数组，它将在每个存储桶中具有子存储桶。然后，它将被索引为 array_name[m][n]，其中 m 和 n 是数组中每一级的尺寸。

根据上述说明，以下是要考虑的重要事项。

Index starts with 0.
数组长度为 9，这意味着它可以存储 9 个元素。
可以通过其索引访问每个元素。例如，我们可以获取索引 6 处的元素，如 23。

Basic Operations in Arrays

数组中的基本操作是插入、删除、搜索、显示、遍历和更新。通常执行这些操作以修改数组中的数据或报告数组的状态。

数组支持的基本操作如下。

Traverse - 逐个打印所有数组元素。
Insertion - 在给定的索引处添加一个元素。
Deletion - 删除给定索引处的元素。
Search - 使用给定索引或按值搜索元素。
Update - 更新给定索引处的元素。
Display − 显示数组的内容。

在 C 中，当一个数组用大小初始化时，它会按以下顺序将其默认值分配给其元素。

Array - Insertion Operation

在插入操作中，我们将一个或多个元素添加到数组。根据要求，可以在数组的开头、结尾或任何给定索引处添加新元素。这是使用编程语言的输入语句完成的。

Algorithm

以下是将元素插入线性阵列中的算法，直到我们到达数组的末尾 −

1. Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable 'i' as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop

Example

在这里，我们看到了插入操作的实际实现，我们在其中在数组的末尾添加数据 −

Output

Array Before Insertion:
LA[0] = 0
LA[1] = 0
LA[2] = 0
Inserting elements..
Array After Insertion:
LA[0] = 2
LA[1] = 3
LA[2] = 4
LA[3] = 5
LA[4] = 6

对于数组插入操作的其他变体， click here 。

Array - Deletion Operation

在此数组操作中，我们将从数组的特定索引处删除一个元素。当我们将后续索引中的值分配给当前索引时，就会发生此删除操作。

Algorithm

考虑 LA 是一个包含 N 个元素的线性数组，而 K 是一个正整数，使得 K⇐N。以下是删除 LA 的第 K 个位置的元素的算法。

1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

Example

以下是该操作在各种编程语言中的实现 −

Output

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
The array elements after deletion :
LA[0] = 1
LA[1] = 5

Array - Search Operation

使用键在数组中搜索元素；键元素顺序比较数组中的每一个值，以检查键是否存在于数组中。

Algorithm

根据 LA 是一个包含 N 个元素的线性数组以及 K 是正整数（使得 K⇐N）的条件。以下为使用顺序搜索查找值 ITEM 的元素的算法。

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

Example

以下是该操作在各种编程语言中的实现 −

Output

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3

Array - Traversal Operation

此操作会遍历数组的所有元素。我们使用循环语句完成此操作。

Algorithm

以下是遍历线性数组中所有元素的算法−

1  Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable ‘i’ with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End

Example

以下是该操作在各种编程语言中的实现 −

Output

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8

Array - Update Operation

更新操作是指在给定索引处从数组中更新现有元素。

Algorithm

根据 LA 是一个包含 N 个元素的线性数组以及 K 是正整数（使得 K⇐N）的条件。以下为更新 LA 的第 K 个位置的元素的算法。

1. Start
2. Set LA[K-1] = ITEM
3. Stop

Example

以下是该操作在各种编程语言中的实现 −

Output

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8

Array - Display Operation

此操作会使用 print 语句显示整个数组中的所有元素。

Algorithm

假设 LA 是一个具有 N 个元素的线性数组。以下是要显示数组元素的算法。

1. Start
2. Print all the elements in the Array
3. Stop

Example

以下是该操作在各种编程语言中的实现 −

Output

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8