Data Structures Algorithms 简明教程

Array Data Structure

What is an Array?

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

An array is a type of linear data structure that is defined as a collection of elements with same or different data types. They exist in both single dimension and multiple dimensions. These data structures come into picture when there is a necessity to store multiple elements of similar nature together at one place.

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

The difference between an array index and a memory address is that the array index acts like a key value to label the elements in the array. However, a memory address is the starting address of free memory available.

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

Following are the important terms to understand the concept of Array.

Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to identify the element.

Syntax

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

Creating an array in C and C++ programming languages −

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

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

Creating an array in Java programming language −

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

Need for Arrays

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

Arrays are used as solutions to many problems from the small sorting problems to more complex problems like travelling salesperson problem. There are many data structures other than arrays that provide efficient time and space complexity for these problems, so what makes using arrays better? The answer lies in the random access lookup time.

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

Arrays provide O(1) random access lookup time. That means, accessing the 1st index of the array and the 1000th index of the array will both take the same time. This is due to the fact that array comes with a pointer and an offset value. The pointer points to the right location of the memory and the offset value shows how far to look in the said memory.

                           array_name[index]
                              |       |
                           Pointer   Offset

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

Therefore, in an array with 6 elements, to access the 1st element, array is pointed towards the 0th index. Similarly, to access the 6th element, array is pointed towards the 5th index.

Array Representation

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

Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from '0' to 'n-1', where n is the size of that particular array. For example, an array with size 10 will have buckets indexed from 0 to 9.

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

This indexing will be similar for the multidimensional arrays as well. If it is a 2-dimensional array, it will have sub-buckets in each bucket. Then it will be indexed as array_name[m][n], where m and n are the sizes of each level in the array.

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

As per the above illustration, following are the important points to be considered.

Index starts with 0.
Array length is 9 which means it can store 9 elements.
Each element can be accessed via its index. For example, we can fetch an element at index 6 as 23.

Basic Operations in Arrays

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

The basic operations in the Arrays are insertion, deletion, searching, display, traverse, and update. These operations are usually performed to either modify the data in the array or to report the status of the array.

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

Following are the basic operations supported by an array.

Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
Display − Displays the contents of the array.

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

In C, when an array is initialized with size, then it assigns defaults values to its elements in following order.

Array - Insertion Operation

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

In the insertion operation, we are adding one or more elements to the array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array. This is done using input statements of the programming languages.

Algorithm

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

Following is an algorithm to insert elements into a Linear Array until we reach the end of the array −

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

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

Here, we see a practical implementation of insertion operation, where we add data at the end of the array −

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 。

For other variations of array insertion operation, click here.

Array - Deletion Operation

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

In this array operation, we delete an element from the particular index of an array. This deletion operation takes place as we assign the value in the consequent index to the current index.

Algorithm

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

Consider LA is a linear array with N elements and K is a positive integer such that K⇐N. Following is the algorithm to delete an element available at the Kth position of LA.

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

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

Following are the implementations of this operation in various programming languages −

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

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

Searching an element in the array using a key; The key element sequentially compares every value in the array to check if the key is present in the array or not.

Algorithm

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

Consider LA is a linear array with N elements and K is a positive integer such that K⇐N. Following is the algorithm to find an element with a value of ITEM using sequential search.

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

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

Following are the implementations of this operation in various programming languages −

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

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

This operation traverses through all the elements of an array. We use loop statements to carry this out.

Algorithm

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

Following is the algorithm to traverse through all the elements present in a Linear Array −

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

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

Following are the implementations of this operation in various programming languages −

Output

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

Array - Update Operation

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

Update operation refers to updating an existing element from the array at a given index.

Algorithm

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

Consider LA is a linear array with N elements and K is a positive integer such that K⇐N. Following is the algorithm to update an element available at the Kth position of LA.

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

Example

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

Following are the implementations of this operation in various programming languages −

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 语句显示整个数组中的所有元素。

This operation displays all the elements in the entire array using a print statement.

Algorithm

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

Consider LA is a linear array with N elements. Following is the algorithm to display an array elements.

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

Example

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

Following are the implementations of this operation in various programming languages −

Output

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