什么是数组
数组是一种数据结构，用于存储相同数据类型的元素的集合。这些元素在内存中是连续存储的。数组的每个元素都可以通过其索引来访问，索引从 0 开始，到数组长度减 1。这种连续存储的方式使得数组在访问和处理大量数据时非常高效。
在编程中，数组被广泛用于各种场景，例如存储和处理一系列数字、字符串、对象等。它们可以是一维的（线性数组），也可以是多维的（如二维数组、三维数组等）。多维数组通常用于表示更复杂的数据结构，如矩阵、表格等。请注意，虽然数组的元素必须是相同的数据类型，但这个数据类型可以是基本数据类型（如整数、浮点数、字符等），也可以是复杂的数据类型（如对象、结构体等）。这使得数组在编程中非常灵活和有用。
数组
数组中偏移量（offset）是一个重要的概念。它表示从数组的起始位置（通常为 0）到特定元素位置的距离。通过增加一个偏移量到数组的起始位置，我们可以轻松地计算出每个元素在数组中的位置。例如，如果我们有一个名为 “friends” 的数组，并且我们知道第一个朋友在第 10 个阶梯上，那么当我们想要找到第 2 个朋友时，我们可以将偏移量设置为1（第 2 个朋友在第 11 个阶梯上），然后添加这个偏移量到基础值（10）来得到新的位置。
数组的每个元素都存储在连续的内存地址中。数组的每个元素占用的内存大小取决于其数据类型。例如，如果数组的数据类型是整数，那么每个元素通常占用4个字节（这可能会根据编程语言和计算机架构的不同而有所不同）。同样，如果数据类型是浮点数，每个元素可能占用更多的字节，如4或8个字节。因此，如果我们知道一个特定索引的位置，以及数组中元素的数据类型，我们就可以计算出下一个索引的位置。
索引与内存
在 C 语言中，数组的大小在声明时就已经确定，并且之后不能更改。这是因为 C 语言中的数组是在栈上分配的静态内存，这意味着在编译时就已经为数组分配了固定大小的内存空间。确实，数组的这种特性使得我们无法动态地扩展或缩小数组的大小。如果尝试扩展数组，我们无法保证下一个内存位置是空闲的，因此可能无法获得所需的额外空间。同样地，如果尝试缩小数组，由于内存是静态分配的，编译器是唯一能够销毁并释放该内存的实体，因此缩小操作也无法实现。
C语言提供了指针和动态内存分配函数（如 malloc 和 free），使我们能够创建动态数组或链表等数据结构，这些结构可以根据需要动态地扩展和缩小。通过使用指针和动态内存分配，我们可以在运行时根据需要分配和释放内存，从而灵活地处理数组和其他数据结构的大小。
需要注意的是，动态内存分配需要谨慎处理，以避免内存泄漏或其他与内存管理相关的问题。因此，在使用动态内存分配时，我们需要确保正确地分配和释放内存，以避免潜在的错误和资源浪费。
无序数组操作
在未排序的数组中进行搜索、插入和删除操作通常需要 O(n) 的时间复杂度，其中 n 是数组的元素数量。这是因为在最坏的情况下，我们需要遍历整个数组来找到特定的元素或进行插入或删除操作。以下是在未排序的数组中进行搜索、插入和删除操作的算法示例。
搜索
#include <bits/stdc++.h>
using namespace std;
// Function to implement search operation
int findElement(int arr[], int n, int key){
int i;
for (i = 0; i < n; i++)
if (arr[i] == key)
return i;
// If the key is not found
return -1;
}
int main(){
int arr[] = { 12, 34, 10, 6, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
// Using a last element as search element
int key = 40;
// Function call
int position = findElement(arr, n, key);
if (position == -1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;
return 0;
}- 时间复杂度：O(n)。
空间复杂度：O(1)。
插入
#include <iostream>
using namespace std;
void insertElement (int arr[], int n, int x, int pos){
// shift elements to the right
// which are on the right side of pos
for (int i = n - 1; i >= pos; i--)
arr[i + 1] = arr[i];
arr[pos] = x;
}
int main (){
int arr[15] = { 2, 6, 1, 9, 15 };
int n = 5;
cout << "Before insertion : ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
int x = 11, pos = 2;
// Function call
insertElement (arr, n, x, pos);
n++;
cout << "After insertion : ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}Before insertion : 2 6 1 9 15
After insertion : 2 6 11 1 9 15删除
#include <iostream>
using namespace std;
// Function to delete an element
int deleteElement (int arr[], int n, int key){
// Find position of element to be deleted
int pos = -1;
for (int i = 0; i < n; i++)
{
if (arr[i] == key)
{
pos = i;
break;
}
}
if (pos == -1)
{
cout << "Element not found";
return n;
}
// Deleting element
for (int i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
return n - 1;
}
int main (){
int arr[] = { 10, 50, 30, 40, 20 };
int n = sizeof (arr) / sizeof (arr[0]);
int key = 30;
cout << "Array before deletion\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
// Function call
n = deleteElement (arr, n, key);
cout << "\n\nArray after deletion\n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}Array before deletion
10 50 30 40 20
Array after deletion
10 50 40 20数组优缺点
- 按照索引查询元素速度快。
- 能存储大量数据。
- 按照索引遍历数组方便。
- 数组定义简单，而且访问很方便。
- 可以随机访问其中的元素。
- 根据内容查找元素速度慢。
- 数组的大小一经确定不能改变，不适合动态存储。
- 数组只能存储一种类型的数据。
- 增加、删除元素效率慢。
- 未封装任何方法，所有操作都需要用户自己定义。
- 数组的空间必须是连续的，这就造成数组在内存中分配空间时必须找到一块连续的内存空间。所以数组不可能定义的太大，因为内存中不可能有那么多大的连续的内存空间，而解决这个问题的方法就是使用链表。