数组数据结构
什么是数组？
数组是一种线性数据结构，定义为具有相同或不同数据类型的元素集合。它们可以是一维的，也可以是多维的。这些数据结构在需要将多个相似性质的元素存储在同一位置时派上用场。
数组索引与内存地址的区别在于，数组索引就像一个键值，用于标记数组中的元素。而内存地址则是可用空闲内存的起始地址。
以下是理解数组概念的重要术语。
元素 − 存储在数组中的每个项目称为一个元素。
Index − 数组中每个元素的位置都有一个数字索引，用于标识该元素。
语法
在 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];
数组的需求
数组被用作从小型排序问题到更复杂问题（如旅行商问题）的许多问题的解决方案。除了数组之外，还有许多其他数据结构为这些问题提供高效的时间和空间复杂度，那么使用数组有什么优势？答案在于随机访问查找时间。
数组提供 O(1) 随机访问查找时间。这意味着访问数组的第 1st 个索引和第 1000th 个索引所需的时间相同。这是因为数组带有指针和偏移值。指针指向内存的正确位置，偏移值指示在该内存中查找多远。
array_name[index]
| |
Pointer Offset
因此，在一个包含 6 个元素的数组中，要访问第 1 个元素，数组指向第 0 个索引。同样，要访问第 6th 个元素，数组指向第 5th 个索引。
数组表示
数组被表示为一组桶的集合，每个桶存储一个元素。这些桶从 '0' 到 'n-1' 进行索引，其中 n 是该数组的大小。例如，大小为 10 的数组将有从 0 到 9 索引的桶。
多维数组的索引方式也类似。如果是二维数组，每个桶中会有子桶。然后它将被索引为 array_name[m][n]，其中 m 和 n 是数组每一层的尺寸。
根据上图说明，以下是需要考虑的重要点。
索引从 0 开始。
数组长度为 9，这意味着它可以存储 9 个元素。
每个元素都可以通过其索引访问。例如，我们可以获取索引 6 处的元素为 23。
数组中的基本操作
数组中的基本操作包括插入、删除、搜索、显示、遍历和更新。这些操作通常用于修改数组中的数据或报告数组的状态。
以下是数组支持的基本操作。
遍历 − 逐一打印所有数组元素。
插入 − 在给定索引处添加一个元素。
删除 − 删除给定索引处的元素。
搜索 − 使用给定索引或值搜索元素。
更新 − 更新给定索引处的元素。
显示 − 显示数组的内容。
在 C 中，当数组初始化时指定大小，则会按照以下顺序为其元素分配默认值。
| 数据类型 | 默认值 |
|---|---|
| bool | false |
| char | 0 |
| int | 0 |
| float | 0.0 |
| double | 0.0f |
| void | |
| wchar_t | 0 |
数组 - 插入操作
在插入操作中，我们向数组添加一个或多个元素。根据需求，可以在数组的开头、结尾或任意给定索引处添加新元素。这是通过编程语言的输入语句完成的。
算法
以下是将元素插入线性数组直到数组末尾的算法 −
1. 开始 2. 创建指定数据类型和大小的 Array。 3. 初始化变量 'i' 为 0。 4. 在数组的第 i 个索引处输入元素。 5. 将 i 递增 1。 6. 重复步骤 4 和 5，直到数组末尾。 7. 结束
示例
这里，我们看到插入操作的实际实现，在数组末尾添加数据 −
C
C++
Java
Python
#include <stdio.h>
int main(){
int LA[3] = {}, i;
printf("Array Before Insertion:\n");
for(i = 0; i < 3; i++)
printf("LA[%d] = %d \n", i, LA[i]);
printf("Inserting Elements.. \n");
printf("The array elements after insertion :\n"); // 打印数组值
for(i = 0; i < 3; i++) {
LA[i] = i + 2;
printf("LA[%d] = %d \n", i, LA[i]);
}
return 0;
}
#include <iostream>
using namespace std;
int main(){
int LA[3] = {}, i;
cout << "Array Before Insertion:" << endl;
for(i = 0; i < 3; i++)
cout << "LA[" << i <<"] = " << LA[i] << endl;
//打印垃圾值
cout << "Inserting elements.." <<endl;
cout << "Array After Insertion:" << endl; // 打印数组值
for(i = 0; i < 5; i++) {
LA[i] = i + 2;
cout << "LA[" << i <<"] = " << LA[i] << endl;
}
return 0;
}
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[3];
System.out.println("Array Before Insertion:");
for(int i = 0; i < 3; i++)
System.out.println("LA[" + i + "] = " + LA[i]); //打印空数组
System.out.println("Inserting Elements..");
// 插入后打印数组
System.out.println("Array After Insertion:");
for(int i = 0; i < 3; i++) {
LA[i] = i+3;
System.out.println("LA[" + i + "] = " + LA[i]);
}
}
}
# 使用插入操作插入元素的 python 程序
def insert(arr, element):
arr.append(element)
# 主代码
if __name__ == '__main__':
# 声明数组和要插入的值
LA = [0, 0, 0]
x = 0
# 插入元素前的数组
print("Array Before Insertion: ")
for x in range(len(LA)):
print("LA", [x], " = " , LA[x])
print("Inserting elements....")
# 插入元素后的数组
for x in range(len(LA)):
LA.append(x);
LA[x] = x+1;
print("Array After Insertion: ")
for x in range(len(LA)):
print("LA", [x], " = " , LA[x])
输出
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
有关数组插入操作的其他变体，请点击这里。
数组 - 删除操作
在这种数组操作中，我们从数组的特定索引删除一个元素。该删除操作通过将后续索引的值赋给当前索引来实现。
算法
假设 LA 是一个包含 N 个元素的线性数组，K 是一个正整数且 K<=N。以下是删除 LA 中第 Kth 位置元素的算法。
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
示例
以下是该操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
void main(){
int LA[] = {1,3,5};
int n = 3;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
for(i = 1; i<n; i++) {
LA[i] = LA[i+1];
n = n - 1;
}
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
}
#include <iostream>
using namespace std;
int main(){
int LA[] = {1,3,5};
int i, n = 3;
cout << "The original array elements are :"<<endl;
for(i = 0; i<n; i++) {
cout << "LA[" << i << "] = " << LA[i] << endl;
}
for(i = 1; i<n; i++) {
LA[i] = LA[i+1];
n = n - 1;
}
cout << "The array elements after deletion :"<<endl;
for(i = 0; i<n; i++) {
cout << "LA[" << i << "] = " << LA[i] <<endl;
}
}
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[3];
int n = LA.length;
System.out.println("Array Before Deletion:");
for(int i = 0; i < n; i++) {
LA[i] = i + 3;
System.out.println("LA[" + i + "] = " + LA[i]);
}
for(int i = 1; i<n-1; i++) {
LA[i] = LA[i+1];
n = n - 1;
}
System.out.println("Array After Deletion:");
for(int i = 0; i < n; i++) {
System.out.println("LA[" + i + "] = " + LA[i]);
}
}
}
#python program to delete the value using delete operation
#使用删除操作删除值的 Python 程序
if __name__ == '__main__':
# Declaring array and deleting value
# 声明数组并删除值
LA = [0,0,0]
n = len(LA)
print("Array Before Deletion: ")
# 删除值如果存在
# 或显示错误信息，如果列表中不存在
for x in range(len(LA)):
LA.append(x)
LA[x] = x + 3
print("LA", [x], " = " , LA[x])
# delete the value if exists
# or show error it does not exist in the list
for x in range(1, n-1):
LA[x] = LA[x+1]
n = n-1
print("Array After Deletion: ")
for x in range(n):
print("LA", [x], " = " , LA[x])
输出
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
数组 - 搜索操作
在数组中使用 key 搜索元素；key 元素依次比较数组中的每个值，以检查 key 是否存在于数组中。
算法
假设 LA 是一个包含 N 个元素的线性数组，K 是一个正整数且 K<=N。以下是使用顺序搜索查找值为 ITEM 的元素的算法。
1. 开始 2. 设置 J = 0 3. 当 J < N 时重复步骤 4 和 5 4. 如果 LA[J] 等于 ITEM 则跳转到步骤 6 5. 设置 J = J +1 6. 打印 J, ITEM 7. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
for(i = 0; i<n; i++) {
if( LA[i] == item ) {
printf("Found element %d at position %d\n", item, i+1);
}
}
}
#include <iostream>
using namespace std;
int main(){
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0;
cout << "The original array elements are : " <<endl;
for(i = 0; i<n; i++) {
cout << "LA[" << i << "] = " << LA[i] << endl;
}
for(i = 0; i<n; i++) {
if( LA[i] == item ) {
cout << "Found element " << item << " at position " << i+1 <<endl;
}
}
return 0;
}
public class ArrayDemo{
public static void main(String []args){
int LA[] = new int[5];
System.out.println("Array:");
for(int i = 0; i < 5; i++) {
LA[i] = i + 3;
System.out.println("LA[" + i + "] = " + LA[i]);
}
for(int i = 0; i < 5; i++) {
if(LA[i] == 6)
System.out.println("Element " + 6 + " is found at index " + i);
}
}
}
#使用 python 进行搜索操作
def findElement(arr, n, value):
for i in range(n):
if (arr[i] == value):
return i
# 如果未找到 key
return -1
# 主程序代码
if __name__ == '__main__':
LA = [1,3,5,7,8]
print("Array element are: ")
for x in range(len(LA)):
print("LA", [x], " = ", LA[x])
value = 5
n = len(LA)
# 使用搜索操作找到元素
index = findElement(LA, n, value)
if index != -1:
print("Element", value, "Found at position = " + str(index + 1))
else:
print("Element not found")
输出
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
数组 - 遍历操作
此操作遍历数组中的所有元素。我们使用循环语句来实现。
算法
以下是遍历线性数组中所有元素的算法 −
1 开始 2. 初始化一个指定大小和数据类型的 Array。 3. 初始化另一个变量 i 为 0。 4. 打印数组中的第 i 个值并递增 i。 5. 重复步骤 4，直到到达数组末尾。 6. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
#include <iostream>
using namespace std;
int main(){
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
cout << "The original array elements are:\n";
for(i = 0; i<n; i++)
cout << "LA[" << i << "] = " << LA[i] << endl;
return 0;
}
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[5];
System.out.println("The array elements are: ");
for(int i = 0; i < 5; i++) {
LA[i] = i + 2;
System.out.println("LA[" + i + "] = " + LA[i]);
}
}
}
# 使用 Python 迭代数组的 Python 代码
LA = [1, 3, 5, 7, 8]
# 元素长度
length = len(LA)
# 使用 For 循环和 range 遍历元素
# 等同于 'for x in range(len(array))'
print("Array elements are: ")
for x in range(length):
print("LA", [x], " = ", LA[x])
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8
数组 - 更新操作
更新操作指的是在给定索引处更新数组中已存在的元素。
算法
假设 LA 是一个包含 N 个元素的线性数组，K 是一个正整数且 K≤N。以下是更新 LA 中第 K 个位置元素的算法。
1. 开始 2. 设置 LA[K-1] = ITEM 3. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
#include <iostream>
using namespace std;
int main(){
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
cout << "The original array elements are :\n";
for(i = 0; i<n; i++)
cout << "LA[" << i << "] = " << LA[i] << endl;
LA[2] = item;
cout << "The array elements after updation are :\n";
for(i = 0; i<n; i++)
cout << "LA[" << i << "] = " << LA[i] << endl;
return 0;
}
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[5];
int item = 15;
System.out.println("The array elements are: ");
for(int i = 0; i < 5; i++) {
LA[i] = i + 2;
System.out.println("LA[" + i + "] = " + LA[i]);
}
LA[3] = item;
System.out.println("The array elements after updation are: ");
for(int i = 0; i < 5; i++)
System.out.println("LA[" + i + "] = " + LA[i]);
}
}
#使用 Python 进行更新操作
#声明数组元素
LA = [1,3,5,7,8]
#更新前
print("The original array elements are :");
for x in range(len(LA)):
print("LA", [x], " = ", LA[x])
#更新后
LA[2] = 10
print("The array elements after updation are: ")
for x in range(len(LA)):
print("LA", [x], " = ", LA[x])
输出
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
数组 - 显示操作
此操作使用打印语句显示数组中的所有元素。
算法
假设 LA 是一个包含 N 个元素的线性数组。以下是显示数组元素的算法。
1. 开始 2. 打印数组中的所有元素 3. 结束
示例
以下是此操作在各种编程语言中的实现 −
C
C++
Java
Python
#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int n = 5;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
#include <iostream>
using namespace std;
int main(){
int LA[] = {1,3,5,7,8};
int n = 5;
int i;
cout << "The original array elements are :\n";
for(i = 0; i<n; i++)
cout << "LA[" << i << "] = " << LA[i] << endl;
return 0;
}
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[5];
System.out.println("The array elements are: ");
for(int i = 0; i < 5; i++) {
LA[i] = i + 2;
System.out.println("LA[" + i + "] = " + LA[i]);
}
}
}
#使用 Python 进行显示操作
#使用 Python 进行显示操作
#声明数组元素
LA = [2,3,4,5,6]
#显示数组
print("The array elements are: ")
for x in range(len(LA)):
print("LA", [x], " = " , LA[x])
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8